Abstract: In the compiler literature, parsing algorithms for context-free grammars are presented using string rewriting systems or abstract machines such as nondeterministic pushdown automata, but the resulting descriptions can be baroque, and even a basic understanding of some parsing algorithms, such as Earley’s algorithm for general context-free grammars, can be elusive. In this talk, we argue that these problems can be addressed by using a graphical representation of context-free grammars called the Grammar Flow Graph (GFG), which enables parsing problems to be reframed as reachability problems in graphs. Among other advantages, this leads to a simple description Earley's algorithm for parsing general context-free grammars and Knuth's algorithm for parsing of LR(k) grammars. These results suggest that the GFG can be a new foundation for studying and teaching context-free grammars.
This is joint work with Gianfranco Bilardi, University of Padova, Italy.
Biography: Keshav Pingali is a professor in the CS department at the University of Texas at Austin, where he holds the W.A."Tex" Moncrief Chair of Computing. He received the B.Tech. degree from I.I.T. Kanpur and the Sc.D. degree from MIT in Computer Science. Between 1986 and 2006, he was on the faculty in the CS and ECE Departments at Cornell University, where he held the India Chair of Computing.
Dr. Pingali is a Fellow of the ACM, IEEE, AAAS and a foreign member of the Academia Europaea. He is the recipient of the 2023 IEEE CS Charles Babbage Award, the 2023 ACM/IEEE Ken Kennedy Award, and the 2024 ACM SIGPLAN Programming Languages Achievement Award. In 2013, he was awarded the IIT Kanpur Distinguished Alumnus Award. He has served on the Gordon Bell Prize Committee (2013-2017), the NSF CISE Advisory Committee (2009-2012), and he was co-Editor-in-chief of ACM Transactions on Programming Languages and Systems (TOPLAS) (2007-2010).