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.
LL언어를 특징짓는 정형화 방법으로 LL 커버링 문법 변환들이 존재하는 LR 문법들의 부분 클래스에 대해 연구가 진행되었다. PLR문법과 κ-transformable문법이 그 예이다. 특히, κ-transformable 문법 클래스는 커버링 성질을 만족하는 LL변환이 존재하는 LR문법들의 최대 클래스로 추측되었다. 그런데 이 문법에 대해 제안된 변환 방법은 다중 스택 기계의 생성을 필요로 한다. 또한 어떤 문법이 κ-transformable인지 결정하기 위해선 문법 변환의 가능성 여부를 테스트 해야하며, 이는 여러번의 다중 스택 기계의 생성을 요구한다. 한편 PLR문법은 특징화가 쉬운 장점을 가진 κ-transformable문법의 부분 문법으로 알려졌다. 그러나 PLR문법과 κ-transformable 문법간의 포함 관계는 증명이 주어지지 않았기에 명확하지 않다.
본 학위 논문에선 κ-transformable문법에 대해서 다중 스택 기계의 생성을 필요로 하지 않는 LL변환 방법과 특징화 방법을 제안한다. 이들은 문법의 유도과정을 이용하였기에, 직관적으로 이해하기 쉬우며, 다른 문법 클래스와의 관련성을 찾기가 쉽다.
둘째로는 PLR문법 클래스와 κ-transformable 문법 클래스가 서로 포함 관계가 없음을 증명한다.
셋째로는 확장된 LL-to-LR 커버링 변환 방법을 제안한다. 기존의 κ-transformable 문법에서의 LL변환을 얻기 위한 시행 착오 작업과 달리, 새로운 변환 방법에선 단 한번의 변환 작업만을 필요로 한다. 제안된 변환으로 LL문법을 얻을 수 있는 문법을 확장된 PLR이라고 정의한다. 새로운 이 문법 클래스는 PLR과 κ-transformable 문법을 포함하며, 현재까지 알려진 LL-to-LR커버링 문법이 존재하는 가장 큰 클래스이다.
넷째로는 미리 결정할 수 있는 리덕션 골을 가진 LR파서를 제안한다. LR파서내에 각 LR 상태는 어떤 골과 스택 스트링의 우위 부분에 대한 정보를 저장하고 있다. 이 정보의 의미는 저장된 파싱 스택의 후위 부분과 남은 입력 스트링의 전위위 부분이 확실히 저장된 골로 리듀스가 됨을 말한다. 이러한 예상하는 LR 파서에 대한 응용을 보인다.
