LL 파서의 추억

Posted 2007. 5. 24. 09:55
Haskell 컴비네이터 파서(Combinator Parser)인 Parsec 문서를 보다가 학창 시절 파서에 얽힌 기억이 떠올라서 올려봅니다. 4학년 때 들은 컴파일러 수업은 기말 프로젝트가 C-라는 프로그래밍 언어의 컴파일러를 구현하는 것이었습니다. C-는 C의 서브셋으로 데이터 타입이 정수 밖에 없고 포인터도 없는 간단한 프로그래밍 언어입니다. 타겟 머신은 X86이 아닌 아주 간단한 어셈블리 언어였습니다.

학부 컴파일러 수업의 보통 여러 파싱 이론(Parsing Theory)를 배우는 데 많은 시간을 할애하는데, 물론 컴퓨터 프로그래밍 언어를 위한 파서이므로 자연어 처리에나 필요할 만한 깊이 있는 파싱 이론을 하지는 않습니다. CFG(Context Free Grammar) 파싱할 수 있는 LL, LALR, LR 파서가 대표적인 주제이죠.

당시 프로젝트 구현 언어는 자바였기 때문에 파서 생성기(Parser Generator) 선택을 두고 학생들은 LL(k) 파서(정확히 말하자면 Predicated-LL(k) 파서)인 ANTLR과 LALR(1) 파서인 자바 CUP으로 양분 되었습니다. 당시 교과서가 호랑이 책(Modern Compiler Implementation in Java)였기 때문에 원래 프로젝트는 파서 생성기로 CUP을 쓸 것을 명시해 놨었는데, 제가 강력 주장해서 ANTLR도 옵션으로 포함되었습니다. 일부 학생들은 저의 선동에 혹해서 ALTLR을 선택했었습니다.

ANTLR의 장점은 LL(k) 파서인데다 테이블 기반(Table-Driven)이 아닌, 사람이 손으로 작성한 것과 유사한(Recursive Descent Parser) 같은 코드를 토해내는 데 있었습니다. 따라서 생성된 코드를 쉽게 이해하고 문제점을 고칠 수 있었죠. 반대로 완전한 테이블 기반의 파서인 LALR 파서는 문제(주로 Reduce-Reduce Conflict)가 발생해도 에러 메시지만 가지고는 뭐가 문젠지 알기 힘든 점이 있었고요.

근데 ANTLR을 선택한 학생들이 저에게 원망을 하기 시작했습니다. LALR 파서에는 그냥 되는 문법이 ANTLR에서는 안 된다는 것입니다. 그럴 수 밖에 없는 게, ANTLR은 기본적으로 LL 파서이기 때문에 Left Recursion을 직접 제거(Left Factoring) 해주거나 일부 문법에 Predicate을 통해 미리보기(Lookahead)를 직접 지정해주어야 했거든요. 이 차이점을 제대로 이해 못한 사람들이 많았던 것이죠.

LL(1) 만으로 파싱할 수 있는 문법은 많지 않고 대게는 필요에 따라 LL(2), LL(3) 등으로 들어나는데, k 값이 1 증가할 때마다 파서 성능이 엄청 떨어집니다. 사실 문법 중에 단 한 군데만 LL(2)가 필요한데 전체 파서를 LL(2)로 처리하는 건 문제가 있습니다. ANTLR은 이 문제를 해결하기 위해 Syntatic Predicate, Semantic Predicate 같은 개념을 도입합니다. 쉽게 설명하면 LL 파서가 구분하지 못하는 특정 문법에만 Lookahead를 통해 힌트를 주는 것이죠.

다시 Haskell 이야기로 돌아가면, Parsec도 기본적으로 LL(1) 파서입니다. LL 파서는 필히 Left Recursion 문제에 대해 고민을 해야하는데, Parsec의 방식은 직관적이며 간단합니다. Parsec은 LL(1) 파서를 지향하되, 필요에 따라서는 백트래킹(Backtracking) 하는 전략을 취합니다. 즉, 파서 룰에 try 라고만 명시해주면, 일단 왼쪽 룰부터 파싱을 시도해보고 실패하면 아무 일도 없었던 것처럼 다음 걸 다시 시도해 보는 방식입니다. 따라서 개념적으로는 LL(무한대) 문법을 파싱할 수 있게 되는 것이죠. 물론 백트래킹 파서는 무척 비효율적이기 때문에 LL(1) 파서를 지향하되, try라고 명시된 부분에 한해서만 백트래킹 모드로 변신합니다.

요즘은 파싱이 필요한 거의 대부분의 데이터를 XML로 처리하기 때문에 파서를 작성하거나 파서 생성기를 쓸 일이 정말 드뭅니다. 프로그래밍 언어의 파서를 작성하거나 하는 일은 정말 소수의 개발자가 하는 일이니깐요. 하지만, 개발 작업을 보면 사실 대부분의 일이 파싱/언파싱입니다. 데이터를 얻어오고 저장하는 일에는 필히 파싱이 동반되니깐요. 시간만 되면 이쪽으로 좀 깊이 있게 공부해 보고 싶은데, 항상 마음만 굴뚝 같군요.