Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.compilers > #767 > unrolled thread

a new approach to context-free language parsing

Back to article view | Back to comp.compilers

Contents

  a new approach to context-free language parsing Keshav Pingali <pingali@cs.utexas.edu> - 2012-10-14 13:34 -0500

#767 — a new approach to context-free language parsing

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
analysis,

(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:
http://apps.cs.utexas.edu/tech_reports/reports/tr/TR-2102.pdf

We welcome feedback from the community - please email me or Bilardi.

[toc] | [standalone]

Back to top | Article view | comp.compilers

csiph-web