digitalmars.D - [OT][Parsing] Parsing with Pictures
- Tobias Pankrath (18/18) Nov 18 2012 Since at least some of the reg...
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
Nov 18 2012