a new approach to context-free language parsing

Keshav Pingali <pingali@cs.utexas.edu>
Sun, 14 Oct 2012 13:34:41 -0500

          From comp.compilers

Related articles
a new approach to context-free language parsing pingali@cs.utexas.edu (Keshav Pingali) (2012-10-14)
| List of all articles for this month |

From: Keshav Pingali <pingali@cs.utexas.edu>
Newsgroups: comp.compilers
Date: Sun, 14 Oct 2012 13:34:41 -0500
Organization: Compilers Central
Keywords: parse
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
and LR
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.

Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.