• Tobias Pankrath (18/18) Nov 18 2012 Since at least some of the regulars here seem be generally interested in...

Tobias Pankrath <lists pankrath.net> writes:

Since at least some of the regulars here seem be generally interested in 
parsing techniques, I'd like to share a paper I just found at 
comp.compilers about Grammar Flow Graphs.

The authors try to unify the description of LL, LR, Earley parsers using 
Grammar Flow Graphs, which basically consists of a Node for every 
grammar slot in LR parlance and edges between nodes just like in the LR 
automaton construction. Recognizing a sentence of a grammar than 
corresponds to finding a path in this graph.

Whats nice: I'd say the paper is successfull in providing a common
terminology for both bottom-up and top-down parsers and thinking in GFGs 
makes reasoning about parsing easier at least for me.
I wish I'd seen this before trying to understand GLL parsing.

What the paper is not: No new approach to parsing, no mention of GLL and 
GLR parsing, though GFGs are very well applicable to these as well.

The paper is here:
http://apps.cs.utexas.edu/tech_reports/reports/tr/TR-2102.pdf
The entry in comp.compilers:
http://compilers.iecc.com/comparch/article/12-10-009