Two problems on the parsing conflicts in LR(k) parsers, (1) computing the condition for two semikernel items to be in an LR(k) state and (2) reducing the number of states in a given LR(k) parser, are addressed in this thesis.
On the first problem, we derive two lemmas which show whether two semikernel items are in an LR(k) state or not. An LR(κ) state with two semikernel items is a necessary condition for the given parser to have a parsing conflict. The one is a recursive condition using relationship between nonterminals, which is applicable only to LR(0) semikernel items. The other computes the condition by extending the domain of function leftcontext. It can be applied to any LR(k) semikernal items (k ≥0).
On the second problem, we propose a new formalism for merging LR(k) states without any conflict, after constructing the full LR(k) parsing table. First, we define a new relation compatitable C and C-covering for a core block, both of which are different from the notion in dynamic reduction methods. Then, we propose well-defined reduction (WDR) which is a set of C-covering for each core block which reflect the rationale for LR(k) state reduction, as a new formalism. We present algorithms to compute a WDR and an LR(k)-based parser for the reduction. Furthermore, we introduce a useful core-restricted method, a locally optimal reduction as an approximation to an optimal reduction.
The contribution of this thesis to LR(k) parsing theory is summarized as follows: (1) to discover that set of LR(k) states of a core block after the merging is not a partition, but a covering of the block. (2) to propose WDR which provides a new formal view for the computation of an optimal reduction.
본논문은 LR(k) 구문분석기의 충돌과 관련된 두가지 연구결과로 (1) 두개의 준커널항목(semikernel item)이 같은 상태에 있기 위한 조건 계산, (2) LR(k) 구문 분석기의 상태수 축소에 관한 새로운 관점을 제시하였다. 첫째로 두개의 준커널 항목이 같은 LR(k) 상태에 있기 위한 조건-이것은 충돌이 있기 위한 필요조건임-에 관한 두개의 소정리를 유도했다. 하나는 비종단 기호 사이의 관계를 이용한 재귀적 조건으로서 LR(O) 항목에 대해서만 적용이 가능하다. 다른 하나는 좌문맥 함수의 정의역을 확장하여 조건을 계산하는 것으로서 임의의 LR(k) 항목들(k ≥ 0)에 대해 적용 가능하다.
둘째로 LR(k) 구문분석표를 구축완료한 후, LR(k) 상태를 충돌이 발생하지 않도록 병합하기 위한 새로운 형식론을 제안했다. 먼저 기존의 동적인 상태축소방법에서와는 다른, 상태들간의 새로운 호환관계 C 및 코아 블록에 대한 C-커버링을 정의했다. 그 다음에 상태축소의 원리를 충족시키는 각 코아블록들에 대한 C-커버링들의 집합을 정축소(WDR: Well-Defined Reduction)라는 새로운 형식론으로 제안했다. 나아가서 정축소 및 그것에 대한 LR 구문분석기의 계산을 위한 알고리즘과 최적축소의 근사값으로서 국부적 최적축소(locally optimal reduction)를 제안했다.
결과적으로 (1) 주어진 코아블록에 대한 병합 결과가 그 블록의 분할(partition)이 아니고 커버링이라는 것을 발견한 것, (2) 새로운 형식론 WDR의 제안 및 이것에 기초한 최적축소에 대한 관점을 제시한 것이 이 논문이 LR 구문분석 분야에 기여한 사항이다.
