|a new approach to context-free language parsing email@example.com (Keshav Pingali) (2012-10-14)|
|From:||Keshav Pingali <firstname.lastname@example.org>|
|Date:||Sun, 14 Oct 2012 13:34:41 -0500|
|Posted-Date:||14 Oct 2012 17:36:06 EDT|
Gianfranco Bilardi and I have developed a new approach
to parsing context-free languages that we call "Parsing with pictures".
It provides an alternative (and, we believe, easier to understand) approach
to context-free language parsing than the standard presentations using
derivations or pushdown automata. It also unifies Earley, SLL, LL, SLR,
and LR parsers among others.
Parsing problems are formulated as path problems in a graph called the
grammar flow graph (GFG) that is easily constructed from a given
grammar. Intuitively, the GFG is to context-free grammars what NFAs
are to regular languages. Among other things, the paper has :
(i) an elementary derivation of Earley's algorithm for parsing general
context-free grammars, showing that it is an easy generalization of
the well-known reachability-based NFA simulation algorithm,
(ii) a presentation of look-ahead that is independent of particular
parsing strategies, and is based on a simple inter-procedural dataflow
(iii) GFG structural characterizations of LL and LR grammars
that are simpler to understand than the standard definitions,
and bring out a symmetry between these grammar classes,
(iv) derivations of recursive-descent and shift-reduce parsers for LL
grammars by optimizing the Earley parser to exploit this structure, and
(v) a connection between GFGs and NFAs for regular grammars based on the
continuation-passing style (CPS) optimization.
You can find the tech report at this URL:
We welcome feedback from the community - please email me or Bilardi.
Return to the
Search the comp.compilers archives again.