Dr. Keshav Pingali - Parsing with Pictures





The interactive transcript could not be loaded.



Rating is available when the video has been rented.
This feature is not available right now. Please try again later.
Published on Dec 13, 2013

Computer Science and Engineering Distinguished Lecturer Series

"Parsing with Pictures"

Keshav Pingali
W.A."Tex" Moncrief Chair of Grid and Distributed Computing Professor
Department of Computer Science
University of Texas, Austin

4:10 p.m., Monday, October 14, 2013
Room 124, Bright Building


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 difficult to understand even for experts in programming 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, the GFG permits 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 and elementary treatment of parsing algorithms such as 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, among others.

These results suggest that the GFG can be a new foundation for the study of context-free languages. No knowledge of parsing is required to understand this lecture - the only prerequisites are elementary graph theory and an open mind.

This is joint work with Gianfranco Bilardi of the University of Padova, Italy.


Keshav Pingali is a Professor in the Department of Computer Science at the University of Texas at Austin, and he holds the W.A."Tex" Moncrief Chair of Computing in the Institute for Computational Engineering and Sciences (ICES) at UT Austin. He was on the faculty of the Department of Computer Science at Cornell University from 1986 to 2006, where he held the India Chair of Computer Science. Pingali is a Fellow of the ACM, IEEE and AAAS. He served as co-Editor-in-chief of the ACM Transactions on Programming Languages and Systems (TOPLAS) in 2007-2010, and on the NSF CISE Advisory Committee in 2009-2012.

Comments are disabled for this video.
When autoplay is enabled, a suggested video will automatically play next.

Up next

to add this to Watch Later

Add to

Loading playlists...