Aarley's hands-on analysis (Aycock & Horspool 2002): How to add back pointers?

I've already coded the Earley parser with back pointers, but it doesn't handle null grammars. I also implemented Aycock and Horspool's 2002 solution, which is to make PREDICT a non-terminal token pass if it is null. Unfortunately, it doesn't tell you exactly which path the token should use to get to epsilon.

My idea (rather stupid):

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

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

When you expand a tree, each time you encounter NULL, you create a list of trees, one for each path in the list for this nullable nonterminal.

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

I think this will greatly increase the time complexity of my algorithm, but I cannot think of a more efficient method for generating all possible parse trees.

Can anyone suggest a more efficient implementation method by Aycock and Horspool 2002 for generating parse trees?

+3


source to share


1 answer


Have you heard of Marpa ?

These are mostly improvements to Earley + Aycock & Horspool + Leo + (Jeffrey Kegler's).



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

Hope it helps.

+3


source







All Articles