5

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 need 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

hippietrail
  • 15,848
  • 18
  • 99
  • 158
dfens
  • 5,413
  • 4
  • 35
  • 50
  • 1
    Can you tell us on what article you based your recognizer, otherwise it is hard to know what extra you need to do. – Nick Fortescue Jan 05 '11 at 14:26
  • You might want to look at [Marpa](https://metacpan.org/pod/Marpa::R2). It's an open source Earlery parser which has a C back end and a Perl front end. – hippietrail Sep 19 '14 at 15:07

2 Answers2

2

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

Wickoo
  • 6,745
  • 5
  • 32
  • 45
1

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.