Practical optimizations of LR(k) parsing tables

Author

Ancona, M. ; Bartolozzi, A. ; Paci, M. ; Provvedi, S.

Author_Institution

Dipartimento di Matematica, Genova Univ., Italy

fYear

1992

fDate

1-3 April 1992

Firstpage

569

Lastpage

576

Abstract

A method for optimizing LR(k) tables is presented. This method extends the algorithms of phi -inaccessible tables and error postponement for LR(k) tables defined by A. V. Aho and J. D. Ullman (1972, 1973) to a new kind of parsing tables, called reduced tables. Reduced tables are more convenient than canonical tables for all classes of LR grammars. For example, reduced tables can be effectively used to create full LR parsers for programming languages like Pascal, C, Oberon, and Eiffel. Experiments with some important programming languages show rates of optimization of the order of 70% of the eliminated tables and of 50% of nonerror deleted entries. Such results have been obtained with the grammars of programming languages like Ada, Pascal, C, Oberon, and Modula-2.<>

Keywords

grammars; high level languages; program compilers; programming theory; Ada; C; Eiffel; LR grammars; LR parsers; LR(k) parsing tables; Modula-2; Oberon; Pascal; error postponement; programming languages; rates of optimization; reduced tables; Computer languages; Mars; Optimization methods;

fLanguage

English

Publisher

ieee

Conference_Titel

Computers and Communications, 1992. Conference Proceedings., Eleventh Annual International Phoenix Conference on

Conference_Location

Scottsdale, AZ, USA

Print_ISBN

0-7803-0605-8

Type

conf

DOI

10.1109/PCCC.1992.200607

Filename

200607