Almost Boolean Algebraic Computation of LALR(1) Look-Ahead Sets

概要

論文の詳細を見る
In order to obtain an LALR(1) parser from a given grammar, it is necessary to construct an LR(0) automaton and to compute LALR(1) Look-Ahead sets. This paper presents a new method for doing so, based on the linear algebra-like approach instead of the traditional graph theoretical one. After pointing out that the regular language generated from the empty set is isomorphic to Boolean algebra, this paper shows that the above problems can be solved by partially reducing them to problems of this simplest language, Boolean algebra, in such a manner that unknown sets are defined by simultaneous equations each of whose coefficients is a Boolean number. For a given BNF, equations of this kind defining the state transition of an LR(0) automaton are given and solved. Follow sets are similarly defined and solved. Each solution is a formula for computing the desired sets, whose form is the product of the closure of a Boolean matrix and a vector of either Boolean numbers or sets of symbols. Finally, each Look-Ahead set is obtained as a union of properly selected Follow sets. Until now, this kind of computation has been done in an iterative manner of set computation on the equations until the sets obtained become unchanged. Instead, this paper gives a formula for computing them by almost Boolean matrix computation.
一般社団法人情報処理学会の論文
1991-03-31