Tracing of conflicts manually is not so easy in LALR(1) analysis; It involves troublesome tracing of LR(0) states and/or examination of productions in the grammar. DeRemer and Penello suggested an automatic tracing method, where information called trace which shows sources of conflicts, is produced in a predefined form. In the original method of computing traces, a relation needed in computing lookahead sets is used to find out the items which make the conflict symbol by included in the lookahead set of a reducible item.
In this thesis, the trace computation method is re-examined under new formalism of Park et al., and a more efficient method based on the formalism is proposed. Both the old and new method are implemented on KAIST Parser Generating System (KPGS), and experimental results for the comparison of the two methods are presented.
LALR(1) 분석에서 발생하는 conflict의 원인을 찾아 제거하는 일은, 적지않은 LR(0) 스테이트들을 일일이 따라가고, 또, 프로덕션을 검사해야하는 매우 번거로운 작업이다. DeRemer와 Pennello는 conflict의 원인을 알려주는 정보 (추적)를 파서 생성 시스템이 특정한 양식으로 출력하는 방법을 제시하였다.
DeRemer와 Pennello의 추적 계산 방법에서는, lookahead 집합의 계산을 위하여 구성한 방향 그래프를 이용하여 추적을 구성하는 일부 요소를 쉽게 계산하지만, 비효율적인 측면을 가지고 있다.
박철희등의 새로운 LALR 해석논리에 기초하는 효율적인 새로운 추적 계산 방법을 제시하였다. 제안된 새로운 방법은, lookahead 집합의 계산을 위하여 계산된 넌터미널들 사이의 관계를 효과적으로 이용하여, 보다 효율적으로 추적을 계산한다.
기존의 방법과 제안된 새로운 방법을 KAIST 파서 생성 시스템에 구현하고, 몇개의 문법에 대하여 실험한 결과, 새로운 방법이 기존의 방법보다 효율적임을 알 수 있었다.
