pythonparsinggrammarambiguous-grammar

How to generate all possible parsings of an ambiguous grammar


I've looked at quite a few grammar parsers, but none of them seem to be able to generate all parsings of an ambiguous grammar. (I've also checked these questions, which don't provide any helpful solutions to my problem.)

How can I go about generating all the parsings of an ambiguous grammar?

For example, imagine my (ambiguous) grammar is

E -> E E
   | id

Then, there are two valid parsings for id id id. It can be

  1. E(E(id) E(id)) E(id)
  2. E(id) E(E(id) E(id)).

example of the parse trees

How can I go about generating all valid parsings of a string in Python given an ambiguous grammar?

To be clear, I don't care too much about the format of the input and output, as long as it can take in a grammar and a string and output all the valid parsings of that string using that grammar.


Solution

  • This is not a recommendation, and I'm sure there are other Python parser generator capable of producing Earley parsers (or variants thereof).

    But it is certainly possible to use Lark (link from the OP) to produce a parse forest. Select an "earley" parser and set the ambiguity option to "forest" (or "explicit" if there isn't too much ambiguity).