We introduce a new grammar called LR(k) colored grammar in which every grammar symbol and production rule of a context-free grammar G is colored by the information derived from the LR(k) parser for G. By using the grammar, we develop two results on the theory of grammars and parsing.
First, we show that every LR(k) grammar can be covered by an SLR(k) grammar (thus an LALR(K) grammar), which is known to be parsed more easily than LR(k) grammars. This new covering result for LR(k) grammars is obtained by showing that a context-free grammar G is covered by the LR(k)-colored grammar for G and that G is LR(k) if and only if the grammar is SLR(k). In addition, a natural reduction of the grammar which preserves the SLR(k) covering property is also developed.
Second, we present a new class of context-free grammars whose sentences are parsable in linear time and space. The class called boundedly LR(k)-conflictable (BLRC(k)) grammars includes all LR(k) grammars, some non-LR unambiguous grammars and some ambiguous grammars. A context-free grammar is said to be BLRC(k) if the number of conflict occurrences during LR(k) parsing for every sentence of the grammar is inherently bounded. A BLRC(k) grammar can be considered as a natural extension of an LR(k) grammar whose sentences can be parsed by an LR(k) manner with multiple stacks. We show that it is a decidable problem whether a context-free grammar is BLRC(k) for a given k. But it is undecidable for arbitrary k. The result is obtained by deriving another grammar called LR(k)-context description grammar from the LR(k)-colored grammar as a tool for describing the behavior of given LR(k) parser in terms of the grammar symbols.
본 논문에서는 임의의 문맥자유문법의 LR(k) 파서로부터 추출한 정보를 가지고 문법기호와 생성규칙을 색칠한LR(k)-colored 문법을 소개하였으며, 또한 그 문법을 이용하여 grammartical covering과 linear time parsing 분야에 있어서 두가지 새로운 결과를 유도하였다.
첫째로, grammartical covering의 분야에 있어서는 모든 LR(k) 문법은 LR(k) 문법보다 파싱이 용이한 SLR(k) 문법으로 covering이 가능하다는 것을 보임으로써 LR(k) 문법에 대한 새로운 covering의 존재를 밝혀 내었다. 본 논문에서는 임의의 문법이 LR(k) 문법이면 그 문법의 LR(k)-colored 문법이 SLR(k) 문법이라는 것을 입증하고, 나아가 SLR(k)-cover의 성질을 유지하면서 LR(k)-colored grammar를 축약시키는 방법을 제시하였다.
둘째로, linear time parsing 분야에 있어서는 BLRC(k) 문법이라는 문맥자유문법의 새로운 집합체가 형성될 수 있음을 보였다. BLRC(k) 문법은 모든 LR(k) 문법을 포함하며 LR(k)가 아니면서도 모호하지 않은 문법을 부분적으로 포함할 뿐 아니라 모호한 문법조차도 부분적으로 포함한다. 문법의 문장을 LR(k) 파싱할 때 발생할 수 있는 충돌의 횟수가 본질적으로 제한되어 있는 문법을 BLRC(k) 문법이라고 정의하며, 이러한 문법은 다중스택을 이용하는 LR(k) 방식에 의해 파싱될 수 있다는 점에서 LR(k) 문법을 자연스럽게 확장한 것으로 볼 수 있다. 본 논문에서는 LR(k)-colored 문법을 확장하여 LR(k) 파서의 행동을 문법기호로 기술할 수 있는 LR(k)-context description 문법을 개발하고, 이를 이용하여 k가 주어졌을 때 임의의 문맥자유문법이 BLRC(k) 문법인지 아닌지를 판정할 수 있다는 것을 보였으며 또한 BLRC(k) 문법의 여러가지 성질을 연구하였다.
