The left context in LR-based parsing can be defined as the sequence of states in the parsing stack. The right contexts are the expected vocabulary strings that will appear for a given left context. One of the important applications of right contexts is syntax error repair. If a syntax error occurs during a parsing, right contexts may be used to get an insertion string that corrects the syntax error.
An LR-based parser, however, requires additional space and time in computing right contexts since an LR parsing stack contains the vocabulary strings that have been seen until now, whereas an LL parsing stack contains the expected vocabulary strings from this point. For the practical programming languages, however, the LR parser is required for deterministic parsing. Hence the methods of computing right contexts for an LR-based parser have been studied by many researchers.
One of the principle sources of the inefficiencies of the previous methods, in our view, comes from the fact that there are multiple kernel items in an LR(0) state. In general, there are many LR(0) states that contain multiple kernel items. In previous works, the right contexts for an LR(0) state are considered as the union of the right contexts for each kernel item in the state. Our investigation has been devoted to the relationships between the kernel items in the same state. We have found that every kernel item in the same state has the common suffixes in computing right contexts in most cases.
By means of factoring out the common suffixes at parser generation time, it is possible to avoid some redundant computations of right contexts at parsing time. Also, through defining the right contexts for LR(0) states, not for LR(0) kernel items, we develop an efficient method of computing right contexts such that our method simplifies the previous diverging algorithm into a linear algorithm.
LR을 근간으로 하는 구문분석에서, 좌문맥은 파싱스택에 저장되어 있는 상태들의 연속으로 정의할 수 있고, 우문맥은 주어진 좌문맥에 대해 구해질 수 있는 문법스트링들로 정의할 수 있다. 우문맥의 중요한 응용분야 중의 하나는 구문오류보정이다. 만일 구문분석과정에서 오류를 만났을 경우, 이 우문맥이 구문오류보정을 위한 삽입스트링을 구하는데 이용될 수 있다.
LL 구문분석기의 경우에는 그 파싱스택에 현재 시점에서부터 구해질 수 있는 문법스트링을 저장하고 있지만 LR 구문분석기의 경우에는 파싱스택에 지금까지 검조한 입력스트링으로부터 생성된 문법스트링을 저장하고 있어 우문맥을 계산하는데 있어 추가의 기억장소와 수행시간을 요구한다.
그러나 실제 프로그래밍 언어의 경우, 결정적 구문분석을 위해서 LR 구문분석기를 사용해야하므로, LR 구문분석기를 위한 우문맥의 계산방법에 대해서 여러가지 연구가 진행되어 왔다. 본 연구에서는 이들 방법이 가진 비효율성의 원인 중의 하나는 한 LR(0) 상태내에 여러개의 커널아이텀이 있기 때문이라는 사실을 밝혀냈다. 기존의 방법들에서는 한 상태의 우문맥을 그 상태내에 있는 각 아이텀들의 우문맥의 단순한 합으로 간주했다. 본 연구는 같은 상태내의 아이텀들간의 상호관계를 조사했으며, 조사 결과 대부분의 경우에 있어서 같은 상태내의 모든 아이텀들의 우문맥은 공통부분이 있음을 찾아냈다.
따라서 구문분석기 생성시에 이들 우문맥의 공통부분을 미리 한번 계산을 해둠으로써, 구문분석시에는 이 공통부분을 중복계산하지 않는 효율적인 우문맥 계산방법을 제시한다. 또한 각 커널아이텀에 대해서가 아닌 각 상태에 대해 우문맥을 정의함으로서, 기존의 발산하면서 우문맥을 구하는 알고리즘을 선형알고리즘으로 간략화 시킬 수 있음을 보였다.
