3

I've already coded an Earley parser with back pointers but it doesn't handle nullable grammars very well. I've also implemented Aycock & Horspool 2002's solution which is to make PREDICT skip over the nonterminal token if it is nullable. Unfortunately this does not tell you exactly which particular path the token needs to take to get to epsilon.

My idea (pretty stupid) is:

For each nullable nonterminal, create a list of paths for that nonterminal to get to epsilon.

Every time you skip over a nullable nonterminal, add a back pointer called NULL.

When you're expanding the tree, every time you encounter NULL, you create a list of trees, one for each path in the list for that nullable nonterminal.

Finally, you go through the list of trees and get rid of duplicates.

I think this would significantly increase the time complexity of my algorithm but I can't think of a more efficient method to generate all the possible parse trees.

Can anyone suggest a more efficient method of implementing Aycock & Horspool 2002 to create parse trees?

user2108462
  • 855
  • 7
  • 23

1 Answers1

4

Have you heard about Marpa?

It's basically Earley + Aycock&Horspool + Leo + author's (Jeffrey Kegler's) improvements.

You might be interested in Theory section of the author's blog and the author's paper about Marpa.

Hope this helps.

rns
  • 771
  • 4
  • 9
  • thanks! could you give me a link to the part where Marpa constructs the parse tree for an nullable nonterminal? – user2108462 Sep 17 '14 at 23:12
  • 1
    Well, I'm not so versed in theory, sorry, I told the Marpa author about this question via [IRC](http://irclog.perlgeek.de/marpa/today) and on the [mailing list](https://groups.google.com/forum/#!forum/marpa-parser). – rns Sep 18 '14 at 03:56
  • 2
    I'm not sure this addresses your question, but I prune all nulled trees back to their topmost nulled node. The tree can be re-expanded later, if desired. – Jeffrey Kegler Sep 18 '14 at 04:00
  • Thanks Jeffrey, how would that change the time complexity of the parser? – user2108462 Sep 18 '14 at 13:41
  • My apologies for the extremely late reply. Time complexity is unchanged by the pruning of null trees -- no better, no worse. – Jeffrey Kegler Apr 04 '18 at 21:37