On the reduction of \(LR(k)\) parsers (Q688231)

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 compatible \(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 paper 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.