Parse forest from an ambiguous grammar

Question

Parser-generators like nearleyjs can return a parse forest instead of a parse tree.

Since not all input may result in a parse forest (eg, the input may exercise only a non-ambiguous subset of the grammar), how do you programmatically choose the 'correct' parse tree from the forest?

One option is to always choose the first element from the array of parse-trees returned.

Another option is to flag the returning of a parse-forest (instead of a single tree) as an error. But then, this would defy the whole point of having Earley-like parsers that allow parsing of ambiguous grammars!

Also, since only some input may result in a parse-forest (instead of a single parse-tree), how do you rule out surprises in a live/Production environment? Assumption: For non-trivial or non-trivially long grammars, it's not humanly possible to create tests that cover all inputs.

Answer 1

To use such a parser, you need some external way to select among the possible trees in the forest. Typically there are additional constraints beyond what is encoded in the context-free grammar, which can be used to identify the correct parse. In other words, there are some rules that are part of the syntax (they are part of the context-free grammar, and thus handled by the parser), and some rules that are part of the semantics; there may be multiple parses that are compatable with the syntax rules, and then the semantic rules are used to select which one complies with the semantic rules.