On the reduction of LR(k) parsers

Abstract

Two problems on the parsing conflicts in LR(k) parsers, (1) computing the condition for two semikernel items to be in an LR(k) state and (2) reducing the number of states in a given LR(k) parser, are addressed in this thesis. On the first problem, we derive two lemmas which show whether two semikernel items are in an LR(k) state or not. An LR(κ) state with two semikernel items is a necessary condition for the given parser to have a parsing conflict. The one is a recursive condition using relationship between nonterminals, which is applicable only to LR(0) semikernel items. The other computes the condition by extending the domain of function leftcontext. It can be applied to any LR(k) semikernal items (k ≥0). On the second problem, we propose a new formalism for merging LR(k) states without any conflict, after constructing the full LR(k) parsing table. First, we define a new relation compatitable C and C-covering for a core block, both of which are different from the notion in dynamic reduction methods. Then, we propose well-defined reduction (WDR) which is a set of C-covering for each core block which reflect the rationale for LR(k) state reduction, as a new formalism. We present algorithms to compute a WDR and an LR(k)-based parser for the reduction. Furthermore, we introduce a useful core-restricted method, a locally optimal reduction as an approximation to an optimal reduction. The contribution of this thesis to LR(k) parsing theory is summarized as follows: (1) to discover that set of LR(k) states of a core block after the merging is not a partition, but a covering of the block. (2) to propose WDR which provides a new formal view for the computation of an optimal reduction.