Lemon 파서 생성기

Lemon 파서 생성기 (The Lemon Parser Generator)

1. 개요 (Overview)

SQLite의 SQL 언어 파서는 "Lemon"이라는 코드 생성 프로그램을 사용해 만들어져요. Lemon 프로그램은 입력 언어의 문법을 읽고, 그 언어를 위한 파서를 구현하는 C 코드를 내보내요.

출처: The Lemon Parser Generator

본문

1.1. Lemon 소스 파일과 문서 (Lemon Source Files And Documentation)

Lemon은 자체 소스 저장소가 없어요. 대신 Lemon은 SQLite 소스 트리의 몇 개 파일로 구성돼요:

lemon.html → Lemon의 원래 상세 사용 문서이자 프로그래머 참조 문서.
lemon.c → 문법 파일을 읽고 그에 해당하는 파서 C 코드를 생성하는 유틸리티 프로그램의 소스 코드.
lempar.c → 생성된 파서 C 코드의 템플릿. "lemon" 유틸리티 프로그램이 이 템플릿을 읽고 추가 코드를 삽입해 파서를 생성해요.

2. Lemon의 장점 (Advantages of Lemon)

Lemon은 LALR(1) 파서를 생성해요. 그 동작은 더 잘 알려진 도구인 Yacc와 Bison과 유사하지만, Lemon은 다음과 같은 중요한 개선점을 추가해요:

문법 구문이 오류에 덜 취약해요 - Yacc의 "$1" 스타일 위치 표기법 대신 의미 값을 위한 기호 이름을 사용해요.
Lemon에서는 토크나이저가 파서를 호출해요. Yacc은 파서가 토크나이저를 호출하는 반대 방식으로 동작해요. Lemon 방식은 재진입(reentrant) 가능하고 스레드 안전하지만, Yacc은 전역 변수를 사용하므로 둘 다 아니에요. 재진입성은 일부 SQL 문이 파서를 재귀적으로 호출하기 때문에 SQLite에 특히 중요해요. 예를 들어 CREATE TABLE 문을 파싱할 때 SQLite는 sqlite_schema 테이블에 새 항목을 만드는 INSERT 문을 생성하기 위해 파서를 재귀적으로 호출해요.
Lemon에는 구문 오류나 다른 중단된 파싱 이후 메모리나 다른 리소스를 회수하는 데 사용할 수 있는 비-터미널 소멸자(non-terminal destructor)의 개념이 있어요.

2.1. SQLite 내에서의 Lemon 사용 (Use of Lemon Within SQLite)

Lemon은 SQLite에서 두 곳에 사용돼요.

Lemon의 주요 용도는 SQL 언어 파서를 만드는 것이에요. parse.y 문법 파일은 Lemon에 의해 parse.c와 parse.h로 컴파일돼요. parse.c 파일은 추가 수정 없이 amalgamation에 통합돼요.

Lemon은 FTS5 확장의 질의 패턴 표현식을 위한 파서를 생성하는 데도 사용돼요. 이 경우 입력 문법 파일은 fts5parse.y예요.

2.2. 특히 SQLite를 위한 Lemon 맞춤화 (Lemon Customizations Especially For SQLite)

코드 생성기 도구를 프로젝트의 일부로 호스팅하는 것의 장점 중 하나는 그 도구들이 전체 프로젝트의 특정 요구를 서비스하도록 최적화될 수 있다는 점이에요. Lemon은 이런 효과의 혜택을 받았어요. 수년에 걸쳐 Lemon 파서 생성기는 SQLite에 새로운 기능과 향상된 성능을 제공하도록 확장되고 강화되었어요. SQLite가 사용하도록 특별히 설계된 Lemon의 구체적인 개선점 몇 가지는 다음과 같아요:

Lemon에는 "fallback" 토큰의 개념이 있어요. SQL 언어는 아주 많은 키워드를 포함하고 이 키워드들은 식별자 이름과 충돌할 가능성이 있어요. Lemon은 일부 키워드를 식별자로 "fallback"될 수 있도록 지정하는 기능이 있어요. 키워드가 그렇지 않으면 구문 오류가 될 맥락에서 입력 토큰 스트림에 나타나면, 구문 오류가 발생하기 전에 토큰이 자동으로 그 fallback으로 변환돼요. 이 기능은 파서가 식별자로 사용되는 예약어에 대해 매우 관대하도록 만들어 주는데, 이는 SQL 언어에서 자주 발생하는 문제예요.
SQLite의 100% MC/DC 테스트 목표를 지원하기 위해, Lemon이 생성한 파서 코드는 도달 불가능한 분기가 없고 테스트 커버리지 측정에 유용한 추가(컴파일 타임에 선택되는) 계측을 포함해요.
Lemon은 문법 파일 규칙의 조건부 컴파일을 지원하므로, 컴파일 타임 옵션에 따라 다른 파서를 생성할 수 있어요.
성능 최적화로, Lemon 입력 문법의 reduce 액션은 규칙의 오른쪽에 있는 의미 값 "A"가 왼쪽에 있는 의미 값 "Z"를 직접 덮어쓸 수 있음을 나타내는 "/A-overwrites-Z/" 형태의 주석을 포함할 수 있어요. 이 단순한 최적화는 입력 문법을 파싱하는 데 사용되는 push-down automaton의 스택 연산 수를 줄여 파서의 성능을 향상시켜요. 또한 생성된 코드를 약간 더 작게 만들어요.

SQL 문의 파싱은 어떤 SQL 데이터베이스 엔진에서도 CPU 사이클의 중요한 소비자예요. SQLite를 최적화하려는 지속적인 노력으로 인해 개발자들은 더 빠른 파서를 생성하도록 Lemon을 조정하는 데 많은 시간을 보냈어요. 이러한 노력은 SQLite뿐만 아니라 Lemon 파서 생성기의 모든 사용자에게 혜택을 주었어요. 하지만 Lemon이 별도로 유지 관리되는 도구였다면 SQLite와 Lemon 양쪽에 조정된 변화를 만드는 것이 더 어려웠을 것이고, 결과적으로 그만큼의 최적화가 이루어지지 못했을 거예요. 따라서 파서 생성기 도구가 SQLite 소스 트리에 포함된 사실은 도구 자체와 SQLite 모두에게 순이익으로 판명되었어요.

3. Lemon의 역사 (History Of Lemon)

Lemon은 원래 D. Richard Hipp(또한 SQLite의 창시자)가 1987년과 1992년 사이 Duke University 대학원에 있을 때 작성했어요. Lemon의 원래 생성 날짜는 잃어버렸지만, 아마 1990년경이었을 거예요. Lemon은 LALR(1) 파서를 생성해요. "Lime"이라는 LL(1) 파서 생성기 도구가 있었지만 Lime의 소스 코드는 잃어버렸어요.

Lemon 소스 코드는 원래 별도의 소스 파일로 작성되었고, 나중에 단일 "lemon.c" 소스 파일로 합쳐졌어요.

Lemon과 SQLite의 저자(Hipp)는 John Ousterhout의 원래 Tcl 소스 코드를 공부함으로써 자신의 C 프로그래밍 기술이 크게 향상되었다고 보고해요. Hipp는 1993년에 Tcl을 발견하고 공부했어요. Lemon은 그 이전에 작성되었고 SQLite는 그 이후에 작성되었어요. 이 두 제품의 코딩 스타일에는 뚜렷한 차이가 있으며, SQLite가 더 깨끗하고 읽기 쉽고 유지 관리하기 쉬운 것처럼 보여요.

Lemon 파서 생성기