디지털 라이브러리[ 검색결과 ]
Equi-LR 오토마타
http://doi.org/10.5626/JOK.2021.48.3.352
LR 구문분석은 대표적인 상향식 구문분석방법이며, LR 오토마타를 이용하여 구문분석을 수행한다. 본 논문에서는 보편적으로 사용되어 왔던 LR 오토마타의 LR 아이템에 대한 동치 클래스를 정의하고, 이를 사용한 Equi-LR 오토마타의 생성 방법을 제시한다. Equi-LR 오토마타의 상태는 새롭게 정의된 동치클래스를 아이템으로 사용하여 구성되기에, 보편적으로 사용되었던 기존 LR 오토마타에 비해서 Equi-LR 오토마타의 생성 시간이 줄어든다. 본 논문에서는 Equi-LR 오토마타와 기존 보편적 LR 오토마타의 생성시간 복잡도를 정형적으로 비교 분석한 결과를 제시한다. 또한 Equi-LR 오토마타를 이용하면 기존 보편적인 LR 오토마타상에서의 LR 파서 크기의 복잡도보다 더 엄격한 복잡도를 제시할 수 있음을 보인다.
LR 문법에 대한 단일상태파싱오토마톤의 적용
단일상태파싱오토마톤은 구문 분석할 때 행동의 결정이 현재 상태로만 가능하다는 특징이 있고, LR오토마톤과 비교하여 상태수가 적고 구문 분석 시간이 단축된다는 장점이 있다. 한편 단일 상태파싱오토마톤은 적용 가능한 문법 클래스가 LR문법보다 작다는 단점이 있다. 본 논문에서는 단일상태파싱오토마톤을 LR문법 클래스에 적용 가능하도록 확장하는 방법을 제시한다. 기존 방법에서는 파싱오토마톤 생성 과정에서 싸이클릭 상태가 생성되는 경우에 대한 처리 방법을 제시하지 못하였다. 본 논문은 싸이클릭상태에 대한 입력스트링에 따른 동적 처리 작업을 제시하여, 싸이클릭 상태에 대한 문제를 해결한다. 본 논문에서 확장한 방법은 모든 LR 문법에 대해 단일상태파싱오토마톤을 생성할 수 있게 한다.
