AN EFFICIENT HIERARCHICAL CONSTRUCTING LR(K)PARSER AND ITS GRAMMAR PARTITIONING
HU Shi-jie · Computer Applications and Software · 1988
This paper presents an efficient hierarchical constructing LR(K) parser for context-free grammars and the its grammar partitioning. The case K=1 has been discussed in detail. This method can be used for any practical LR(K) grammar and is more efficient than Pager's. The proof for the correctness of the algorithm is also described The conditions of strong compatibility given in this paper is shown to be the weakest one among the all for merging two states with the same core while constructing. The size of result parsers obtained are similar to one of the LALR(K) parsers.