I have a small context-free grammar, which I would like to use to turn input strings into parse trees. I need to get all possibilities in case of ambiguity (so shift-reduce is out), and there's quite a lot of left-recursion (so recursive descent is out).

With these constraints in mind, I've implemented Earley's algorithm, which is functioning quite well…as a recognizer. The problem is, I need a parser as well.

The problem is small enough that I'm not worried about space complexity, and my intended application will require expanding out every possible tree anyway. So the packing mechanisms of an SPPF (shared packed parse forest) aren't necessary here.

Is there a simple algorithm to do this?

  • $\begingroup$ What solution did you come up with in the end. Does cs.stackexchange.com/questions/27937/… answer your question? It explains creating an SPPF but not so well how to iterate over the contained parse trees. $\endgroup$ – Bruce Adams Sep 23 '19 at 10:50

Your Answer

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

Browse other questions tagged or ask your own question.