Regular right part grammar is an alternative to context-free grammar, in which right parts of productions are nondeterministic finite state machines to extend the descriptive power of context-free grammar by including notations for describing repetitions and alternations. However, on its LR parsing, extra work is required to identify the left end of a handle at reduction time because a nonterminal can derive potentially infinite number of strings via a single production. Properties of LALR(k) regular right part grammars and their extended LR(0) automata are examined. An improved method for building efficient extended LALR(k) parsers for such grammars is given, which uses only kernel items of extended LR(0) automata. Neither grammar transformation nor extra readback state of a parser is needed, which is used to construct readback machine to recognize the reverse of the state sequences leading to a reduction. For a reduction by particular production in a state, parser may refer to lookback states in which the parser may be restarted after a reduction. An optimizing algorithm to reduce these references is presented. An efficient method to compute lookahead sets by using only kernel items of extended LR(0) automation is also presented.
우변 정규표현 문법은 자유문맥문법의 일종으로, 반복 또는 교번(병렬선택)등의 표현기법을 활용하므로써 자유문맥문법의 표현력을 확장시키기 위해 프로덕션의 우변을 정규표현이나 미결정적인 유한 오토마타로 나타낸다. 우변 정규표현 문법은 종전의 자유문맥문법에 비해 프로그래밍 언어에 대한 구문의 기술이 간결하고 자연스러우며, 이를 이해하거나 구성하기가 매우 쉬운 장점을 지니고 있다. 그러나, 이에 대한 LR 구문해석시, 하나의 프로덕션을 통해 한 넌터미널 심볼은 무한히 긴 스트링이나 무한개의 스트링을 생성할 수 있기 때문에 축약할 때 핸들의 왼쪽 끝을 알아내기가 쉽지 않다. 본 논문에서는, 먼저 LALR(k) 우변 정규표현 문법과 그 확장 LR(0) 오토마타에 대한 특성들을 분석하였다. 게다가, ELR(0) 오토마타의 커널 항목만을 이용하여 매우 효율적인 ELALR(k) 구문해석기를 생성할 수 있는 개선된 방법을 제시하였다. 이 방법에서는 문법을 변환할 필요가 없을 뿐만 아니라, 축약할 때 일련의 스테이트 순에 대해 거꾸로 인식하기 위해 필요한 readback machine(프로덕션의 우변이 유한 오토마타이므로 축약시에는 이에 대한 역방향의 유한 오토마타)을 구성하는 readback 스테이트 역시 필요없다. 축약시에 lookback 스테이트(축약후에 프로덕션의 우변이 새로 시작되는 곳, 즉, 구문해석기가 다시 시작되는 곳)를 확인해야만 하는데, 이의 확인 과정을 최소로하는 방안도 함께 제시하였다. 또한, ELR(0) 오토마타의 커널 항목만을 이용하여 효과적으로 lookahead 집합을 구하는 방법도 제시하였다.
