Optimization of LR( k) “Reduced parsers”

Some optimization algorithms for LR( k) tables presented by A.V. Aho and J.D. Ullman ( J. Comput. System Sci. 6 (1972) 573-602) are extended to a new type of parsing tables, called Reduced Tables. The corresponding algorithms are compared and a sufficient condition which guarantees a lower space siz...

Full description

Saved in:
Bibliographic Details
Published in:Information processing letters 1992-01, Vol.41 (1), p.13-20
Main Authors: Ancona, Massimo, Fassino, Claudia, Gianuzzi, Vittoria
Format: Article
Language:English
Subjects:
Algorithms
Applied sciences
Computer languages
Computer science
control theory
systems
Exact sciences and technology
Formal languages
Information processing
LR( k) grammars
LR( k) parsers
Mathematical models
Optimization
parsing
parsing tables
Programming languages
reduced tables
Software
Theory
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Some optimization algorithms for LR( k) tables presented by A.V. Aho and J.D. Ullman ( J. Comput. System Sci. 6 (1972) 573-602) are extended to a new type of parsing tables, called Reduced Tables. The corresponding algorithms are compared and a sufficient condition which guarantees a lower space size of the new tables with respect to the canonical LR tables is introduced. The analysis of the grammar of some programming languages confirm the convenience of this approach.
ISSN:0020-0190
1872-6119
DOI:10.1016/0020-0190(92)90074-6