An Earley Parser using Equi-LR Items

Earley 구문분석기는 LR 구문분석기와 달리 모호한 문법을 포함한 일반 문법에 대한 구문분석이 가능하기에 자연어 처리나 영상처리 등의 분야에 널리 사용되고 있지만 Earley 구문분석기는 LR 구문분석기에 비해 시간과 공간에 대한 비용이 높다는 단점이 있다.BR 본 논문에서는 Earley 구문분석기의 아이템 형태를 변경하여 복잡도를 줄이는 Equi-Earley 구문분석기를 제안한다. Earley 구문분석기는 LR 아이템 형태로 구성된 것에 반해 Equi-Earley 구문분석기는 Equi-LR 아이템 형태로 구성되고, Equi-LR 아이템은 LR 아이템을 사용하는 경우보다 상태 내의 아이템 개수를 감소시킨다. Earley 구문분석기는 구문분석 시간에 아이템을 생성하기에 Equi-Earley 구문분석기의 아이템 개수의 감소는 시간과 공간 면에서 효율적인 구문분석기를 생성하게 한다.