Earley recognizer to Earley parser

I managed to create Earley recognizer, everything works fine. I have all proper sets of situation. But I only can use it to decide if word is accepted by grammar. How to make it to parse? I nee开发者_高级运维d some article or explanation, it seems that I need to create associations to situations that made new situations. Any help would be appreciated.

My implementation it's based exactly on: http://www.cs.uvic.ca/~nigelh/Publications/PracticalEarleyParsing.pdf

Parse forest generation from Earley recognizers is tricky. There is this paper "Recognition is not parsing — SPPF-style parsing from cubic recognisers" that explains that Earley's parser version is incorrect and then shows how to generate parse forests from Earley recognizers.

http://www.sciencedirect.com/science/article/pii/S0167642309000951

Whenever you do an inference, keep track of where you came from, ie. what items where used to form the new item. Then the parse forest can be found by exploring the top element spanning the entire input. If you are parsing with ambigous grammars, you should also consider ambiguity packing, ie. do not recombine (locally) equivalent analyses together.

I really recommend Klaas Sikkel's excellent book "Parsing Schemata" for the theoretical side of things.