digitalmars.D - [OT][Parsing] Parsing with Pictures
- Tobias Pankrath (18/18) Nov 18 2012 Since at least some of the regulars here seem be generally interested in...
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