Efficient construction of LR(k) states and tables

A new method for building LR(k) states and parsing tables is presented. The method aims at giving a feasible construction of a collection of LR(k) parsing tables, especially when k > 1. for nontrivial grammars. To this purpose, the algorithm first attempts to build a set of normal states for the...

Full description

Saved in:
Bibliographic Details
Published in:ACM transactions on programming languages and systems 1991-01, Vol.13 (1), p.150-178
Main Authors: Anicona, M., Dodero, G., Gianuzzi, V., Morgavi, M.
Format: Article
Language:English
Subjects:
Applied sciences
Computer science
control theory
systems
Exact sciences and technology
Formal languages and automata theory
Grammars and context-free languages
Language processing and microprogramming
Parsing
Program reasoning
Semantics and reasoning
Software
Theory of computation
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:A new method for building LR(k) states and parsing tables is presented. The method aims at giving a feasible construction of a collection of LR(k) parsing tables, especially when k > 1. for nontrivial grammars. To this purpose, the algorithm first attempts to build a set of normal states for the given grammar, each one associated to a single parsing action in {accept, reduce, shift}. When such an action cannot be uniquely determined, that is, when up to k input symbols have to be examined (inadequacy), further states, belonging to a new type, called look-ahead states, are computed. The action associated with inadequate states is a new parsing action, look. States are built without actual computation of the FIRSTk and EFFk functions; that is, nonterminals are kept in the context string of items composing each state, and their expansion to terminals is deferred until indispensable to solve inadequacy. The aforementioned method is illustrated; then the canonical collection of states and the canonical tables are compared with those obtained from the proposed method. A sufficient condition is stated, by which the size of parsing tables, obtained by applying this new method, is smaller than that of canonical tables. Experimental results show that such a condition is verified by the grammars of several programming languagues and that significant speed is gained by avoiding the computation of the FIRSTk function.
ISSN:0164-0925
1558-4593
DOI:10.1145/114005.102809