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?
source to share