Techniques are provided to generate alternate phrases from a packed meaning representation. The semantics of input items in a packed meaning representation are matched against a lexicon to determine initial entries in a phrasal information structure. Context, syntax and semantic information describing each phrasal entry are added to the phrasal information structure. Linear or other implications are used to determine a set of unordered rewrite rules. The unordered rewrite rules associate semantic information with pseudofacts such that a complete set of choices from the set of disjunctions in the packed meaning representation is selected. Semantic information associated with the unordered rewrite rules identifies entries in the phrasal information structure to be updated with the pseudofact of the unordered rewrite rule.