1
$\begingroup$

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.

$\endgroup$
1
  • 3
    $\begingroup$ It sounds like you approach the question from the wrong end. Why do you parse at all (i.e. what's the exact problem are you trying to solve)? this would defy the whole point of having Earley-like parsers that allow parsing of ambiguous grammars! - it doesn't matter what's the point of Earley-like parsers. The only thing that matters whether your selected approach solves your problem. In other words, how do you programmatically choose the 'correct' parse tree is entirely up to you to define, depending on what you want. Whether you need the entire forest or not depends on your problem. $\endgroup$
    – user114966
    Apr 27 at 3:15
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.