On LL-to-LR covering languages

Abstract

As formal approaches to characterize LL languages, the restricted LR grammars, PLR and κ-transformable grammars have been characterized by suggesting left-to-right covering transformations. The κ-transformable grammar was conjectured as the upper bound of the grammars which have such covering transformations. The previous transformation of κ-transformable grammars, however, requires construction of intricate multiple stack machine. Moreover, κ-transformable-ness of a grammar is determined by trial-and-error construction of cycle-free multiple stack machines. On the other hand, PLR grammar is known as a well-characterized subgrammar of κ-transformable grammar. The claim, however, is not obvious since there is no proof about the relationship between PLR and κ-transformable grammars. First, a grammatical transformation and a grammatical characterization of κ-transformable grammar are suggested. They do not require any construction of multiple stack machine. Second, it is shown that PLR grammar class is not a subclass of κ-transformable grammar class. Third, an extended LL-to-LR covering transformation is suggested. The transformable grammar class includes PLR and κ-transformable grammar strictly, and it is called extended PLR. The new transformation needs a single deterministic process compared to the teial-and-error processes of κ-transformable grammars. Fourth, an LR parser with predetermined reduction goals is suggested. In the LR parser, each LR state has the goal and the suffix of the stack string such that the suffix stack string and some prefix of the remaining input string will be certainly reduced into the goal. Some applications of the predictive LR parser are shown.