Generating minimal equivalent grammars for deterministic LR parsers of non-LR grammars

Abstract

Deterministic LR parsing of non-LR grammars is widely accepted by modern parser generating systems, and receives more attention for obtaining an efficient parser with a simple description of a language syntax. For deterministic parsing of non-LR grammars, one action is selected from conflicting actions by prescribed rules. In this dissertation, we formalize this scheme as a transformation of the parser resulted from deleting actions. To provide a formal model for the deterministic LR parsing method of non-LR grammars, a right-cover grammar of a transformed parser is introduced, which has the equivalent language set to the parser and also generates the same structure for each sentence. Formalizing parser transformations in terms of right-cover grammars offers clear description owing to the rigorous concepts of grammar coverings. As a framework for generating right-covers, context-free grammars attributed with parser information are introduced, on which we can find a set of productions corresponding to the set of deleted actions of the parser. This model shows the effect of the parser transformation, and enables an analysis on further behavior of the parser. Correctness of the model is shown by the relation between parser actions and grammar derivations. Since there are more than one right-cover grammars for a given transformed parser, the minimal one is formally defined, and the reduction method is also investigated. On the other hand, a useful class of namely consistent parser transformations was proposed. If the parser transformation is consistent, then generating a minimal right-cover grammar is substatially simple. Observations on the consistent class is given, which show that the class is useful for providing a practical model of deterministic parsing of non-LR grammars. Several languages including C++ are examined to be contained in the consistent class.