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?


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.