https://hackage.haskell.org/package/Earley

하스켈 Earley


이름처럼 Earley's algorithm을 사용하는 파서 구현임.

Earley parser에 대한 위키피디아 링크

이 알고리즘의 가장 큰 특징은 모든 context free grammar를 변환 없이 직접 파싱할 수 있다는 점임.


형식언어의 분류(촘스키 위계)를 잠깐 살펴보자면

0. recursively enumerable

1. context-sensitive

2. context-free

3. regular


대부분의 프로그래밍 언어 문법은 여기에서 context-free 문법에 속한다.

또 context-free 문법은 어떤 알고리즘으로 파싱될 수 있느냐에 따라서 LL, LR 파서 등의 하위 분류가 있음.

LL, LR 같은 파싱 알고리즘들은 효율적이긴 하지만, CFG의 일부밖에 파싱할 수 없음.

반면에 Earley's algorithm은 모든 CFG를 전부 파싱할 수 있는 알고리즘임.


물론 문법에 제한을 두지 않은것에 대한 trade-off로 시간복잡도가 더 크고,

문법을 원하는 대로 바꿀 수 있는 경우 처음부터 LL 문법 등으로 만들면 되기 때문에 컴파일러 같은데서는 쓸 이유가 별로 없음.


하지만 이 Earley 파서 라이브러리는 효율성 문제를 떠나서 그냥 압도적으로 편리함.

아래 코드는 내가 이 라이브러리를 사용해서 만든 typed lambda calculus 파서인데

https://github.com/damhiya/MetaLambda/blob/main/src/Parser/Parser.hs

그냥 CFG 문법을 하스켈 코드로 적기만 하면 파서가 튀어나오는 수준임.

파서 컴비네이터도 다른 파싱 방법에 비하면 굉장히 간편한 편인데 이건 그것보다도 쉽다.


이 라이브러리 사용을 방해하는 유일한 장벽은 "Backus-Naur form으로 문법을 쓸줄 알아야 한다" 뿐 이다.

BNF는 생성규칙을 위한 표기법임. 아마 BNF를 쓸줄 모르면 어떤 방법을 사용하더라도 파서를 만들기 쉽지 않을거라고 생각함.


물론 단점도 있음.

일단 아까 말했듯이 Earley's algorithm 자체가 그렇게 효율적인 파싱알고리즘이 아니고,

파서 제너레이터가 아니기 때문에 추가적인 런타임 오버헤드가 있음.

그리고 error report가 썩 좋지 못함.


그렇지만 이런건 프로토타이핑에서는 별로 문제가 안되고, 파싱이 병목이 되는 상황은 흔치 않기 때문에

간단히 파서를 만들어야 한다면 반드시 고려해볼만한 라이브러리라고 생각함