UTCS Programming Languages Lunch Series - Keshav Pingali/UTCS, "Parsing with Pictures," PAI 3.14

Contact Name: 
Jenna Whitney
PAI 3.14
Sep 10, 2012 12:00pm - 1:30pm

Type of Talk: UTCS Programming Languages Lunch Series

Speaker/Affiliation: Keshav Pingali/UTCS

Talk Audience: UTCS Faculty and Graduate Students

Date/Time: Monday, September 10, 2012, 12:00 pm

Location: PAI 3.14

Host: Keshav Pingali

Talk Title: Parsing with Pictures

Talk Abstract: The development of elegant and practical algorithms for parsing context-free languages is one of the major accomplishments of 20th century Computer Science. These algorithms are presented in the literature using string rewriting or abstract machines like pushdown automata, but the resulting descriptions are unsatisfactory for several reasons. First, even a basic understanding of parsing algorithms for some grammar classes such as LR(k) grammars requires mastering a formidable number of difficult concepts and terminology. Second, parsing algorithms for different grammar classes are often presented using entirely different formalisms, so the relationships between these grammar classes are obscured. Finally, these algorithms seem unrelated to algorithms for regular language recognition even though regular languages are a subset of context-free languages. In this talk, we show that these problems are avoided if parsing is reformulated as the problem of finding certain kinds of paths in a graph called the Grammar Flow Graph (GFG) that is easily constructed from a context-free grammar. Intuitively, GFG's permit parsing problems for context-free grammars to be formulated as path problems in graphs in the same way that non-deterministic finite-state automata do for regular grammars. We show that the GFG enables a unified treatment of Earley's parser for general context-free grammars, recursive-descent parsers for LL(k) and SLL(k) grammars, and shift-reduce parsers for LR(k) and SLR(k) grammars. Computation of look-ahead sets becomes a simple inter-procedural dataflow analysis. These results suggest that the GFG can be a new foundation for the study of context-free languages. This is joint work with Gianfranco Bilardi of the University of Padova, Italy.