jnw@shades.cis.ufl.edu (Joseph N. Wilson) (03/29/90)
C.I.S. COLLOQUIUM SERIES
Department of Computer Science University of Florida
Recent Advances in the Study of
LR Parsing Formalisms
Dr. George Logothetis
AT&T Bell Laboratories
Liberty Corner, New Jersey
Monday, April 2
11:00 a.m. - 12:30 p.m.
Building CSE, Room 305
(Refreshments Provided After the Talk)
Abstract
________
We will discuss some recent fundamental developments in the
formalisms of certain types of LR parsing schemes, that
considerably enhance their understandabiliy. These developments
include a fundamentally new and better way of formulating the
problem of computing lookahead for LR parsers, and new algorithms
that are as efficient as their old counterparts, but much more
concise and straightforward.
Specifically, we will discuss a new LALR(1) technique based on
the following discovery: the computation of LALR(1) lookahead
amounts to nothing more than the computation of certain suitable
Follow sets. This observation captures, once and for all, the
essence of the problem of computing LALR(1) lookahead. It also
leads to the most straightforward and concise LALR(1) algorithm
yet discovered, and reveals important structural similarities
between LALR(1) and other types of LR techniques.