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.
LR이 아닌 문법의 결정적 LR 파싱은 문법이 간단하고 효율적인 파서를 만들 수 있으므로 YACC등의 파서 생성 시스템에서 널리 사용되고 있다. LR이 아닌 문법은 LR 파서를 생성하였을 때 충돌이 발생하므로 파서의 액션을 일부 삭제하여 충돌을 해결한 결정적 LR 파서를 만들 수 있다. 그러나 일부 액션을 삭제하므로서 파서는 원래 정의된 LR 파서와 달라지며 문법에 정의된 문장을 받아들이지 못하는 등 의도하지 않았던 행동을 할 수도 있다.
본 논문에서는 LR이 아닌 문법과 해결규칙에 의해 결정적 LR 파서를 만드는 과정을 파서에서 액션을 일부 제거하는 변환으로 정형화하고, 이를 기초로 하여 변환된 파서의 결과를 보여줄 수 있는 이론적인 모델로서 동치 문법을 정의하였다. 또한 파서의 액션과 문법의 생성규칙과의 관계를 함수로서 표현하고 이를 이용하여 변환된 파서의 동치 문법을 생성하는 방법을 제안하고 증명하였다. 제안된 모델을 이용하여 변환된 파서의 동치 문법을. 최소화 방법을 보였다.
본 논문에서는 파서 변환의 한 부류로서 일관된(consistent) 파서 변환을 정의하였으며, 그 부류에 대해서는 최소 동치 문법의 생성이 간단한 방법으로 가능함을 보였다. 파서변환이 일관된 조건을 만족하면 LR이 아닌 문법의 LR파싱에서 나타나는 검증의 어려움을 도와주는 효과적인 도구를 제공할 수 있다. C ++ 언어를 포함하여 현재 사용되고 있는 대부분의 문법은 일관된 조건을 만족하는 파서변환의 형태로 만들 수 있으므로 이 방법은 LR이 아닌 문법의 LR 파싱에 대한 실제적인 해결책을 위한 유용한 모델이 되리라 기대된다.
