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 파서 크기의 복잡도보다 더 엄격한 복잡도를 제시할 수 있음을 보인다.