순환 속성 문법의 효율적 점진 평가 기법 = An Efficient Incremental Evaluation Method of Circular Attribute Grammar

국문 초록 (Abstract)

본 논문은 순환적으로 정의된 순환 속성 문법(Circular Attribute Grammars)을 효율적으로 평가하기 위한 점진 평가 기법을 제시한다. 기존의 방법에서는 종속 그래프를 구성하고 변경된 속성의 변화를 파급시키는 과정이 복잡하게 수행된다. 이러한 변화 추적 과정을 간단히 하기 위해 기존의 방법에서 사용하지 않은 새로운 종속 테이블을 구성하여 평가하는 기법을 제시한다. 이 종속 테이블을 참조하면 값이 변경된 속성(attribute)의 변화를 파급시키는 과정이 생략될 수 있어 효율적으로 수행된다. 기존의 방법에서는 값이 변경된 속성에 영향받는 모든 속성을 평가하지만 종속 테이블을 사용하면 조건 속성의 값에 따라 평가 여부를 결정하여 프로그램 수행 상 필요한 속성만을 평가하는 최적의 평가를 수행할 수 있다.
본 논문에서는 순환 속성 문법을 평가할 때 발생되는 문제점과 그 해결책을 제시한다. 예 명령문에 대해 종속 테이블과 종속 그래프를 구성하여 그 효율성을 비교하고 기존의 방법처럼 영향받는 모든 속성을 평가하는 것과 종속 테이블을 사용하여 조건 속성에 따라 필요한 속성만을 평가하는 방법을 모의 실험을 통해 효율성을 비교 분석한다.

다국어 초록 (Multilingual Abstract)

This paper presents the incremental evaluation method of circular attribute grammars. In traditional, the dependency graph is constructed and the progress of change propagation for changed attributes is complexity executed. To simplify this progress, our method evaluates attributes by construction of new dependency table that have not used in existing methods. We implement an efficient evaluation for reference the dependency table because of omitting the progress that propagate the change of changed variables. All attributes affected by the changed attributes are evaluated in existing method. On the other hand, if the dependency table is used, only attributes needed to execute the program are evaluated because the value of conditional attribute determines whether or not to evaluate an attribute, and optimal evaluation is performed.
This paper presents issues which occur in the evaluation of circular attribute grammars and their solutions. Through execution of example program we construct the dependency table and dependency graph, and compare the first to the second in view of efficiency. Also, we compare the evaluation of all affected attributes as existing method to this presenting evaluation through simulation and analyze the efficiency.

목차 (Table of Contents)

• 요약
• ABSTRACT
• 1. 서론
• 2. 표기법 및 정의
• 3. 순환 AG의 점진 평가 기법
• 4. 실험 및 효율성 분석
• 5. 결론
• 참고문헌
• 저자소개