Explicit formula and efficient computing algorithm for the least-cost insertion string in the LR-based error repair scheme are presented. The formula for the least-cost insertion string is derived from the expected vocabulary string which is an extension of LALR lookahead sets. Based on a new LALR formalism[PCC85], an efficient algorithm for the expected vocabulary string is devised.
This scheme can be viewed as an improvement of Fischer, et al.'s scheme [FDM79]. In order to compare with their method, we have implemented an error repair table constructor by modifying their parser generator(ECP).
Experimental results including comparison are presented with respect to time and space characteristics in construction of the error repair table and computation of the locally least-cost repair in LR-based parsers.
(Note)
Due to the restricted character set of the device on which this text was printed following conventions are introduced.
$\underline{c}$ stands for set membership ∈
U stands for set union U
a stands for Greek letter α
b stands for Greek letter β
c stands for Greek letter γ
d stands for Greek letter δ
e stands for Greek letter ε
w stands for Greek letter ω
s stands for Greek letter σ
{} stands for empty set ø
stands for inequality ≠
본 논문은 문법적 오류 수정을 위한 국소적 최척화 방법이 LR parser에서 기존 방법보다 더 효과적으로 활용될 수 있도록 하는 방법을 제시하였다. 국소적 최적화 오류 수정에서는 최저가 삽입 스트링을 구하는 문제가 가장 핵심 부분인데 이에 대한 구체적이고 명확한 공식과 효과적으로 계산할 수 있는 알고리즘을 제시하였다.
종래의 방법에서는 매 state에서 item간의 어떤 관계(Cl-relation)을 이용하어 삽입 스트링을 구한 반면, 새로 제시된 방법에서는 새로운 formalism(expected vocabulary string)을 제안하고 이를 토대로하여 삽입 스트링에 대한 명확한 공식을 유도하였으며, 이 공식에 새로운 LALR formalism을 적용시켜 nonterminal간에만 관련이 있는 어떤 관계(L-relation)을 추출 하여 시간및 기억장소 모든 면에서 더 좋은 특성을 갖는 새로운 효과적인 알고리즘을 개발하였다.
종래의 방법과 새로운 방법 모두를 기존의 parser generating system에 설치하였으며 Pascal, Ada등 실체적인 프로그래밍 언어의 문법에 실험하여 시간과 기억장소 모든 면에서 새로운 방법이 우월함을 실험적으로 입증하였다.
