'Lemon'에 해당되는 글 1건
SQL Scanner 및 Parser의 구현 :: 2007/11/29 18:00 by 양정석(17기)
DB 제작을 위해 필요한 SQL Scanner와 Parser를 구현하는 과정을 적어볼까 합니다. 아직 완전히 완성된 것은 아닙니다만, 실제 Parsing 부분(SQL 문법에 Accept한지에 대한 부분)까지 진행되어 간략히 적어보려 합니다.
먼저 SQL Scanner와 Parser를 구현하기 위해서는 SQL 문이 어떻게 이루어져 있는지를 알아야 합니다. 이를 위해서 SQL 표준에 관한 부분을 알아야 할 필요가 있습니다. SQL 표준에 대한 부분은 여기를 참고해 주세요.
SQL 표준이나 실제 구현할 표준 스펙(전체 혹은 그 부분)을 정했다면, 그 스펙에 맞는 Grammar를 작성해야 합니다. 다음은 정리한 Grammar입니다.
..정리한 Grammar..
Grammar가 정리되었다면, 이를 바탕으로 이제 Scanner와 Parser를 만들어야 합니다. SLR Parser나 LALR Parser를 만들기 위해서는 다음과 같이 직접 디자인하여 구현할 수도 있습니다.
하지만.. 역시나 미련한 짓입니다.(그렇습니다. 미련했었습니다... OTL)
세상에는 좋은 Parser 생성기와 Scanner 생성기가 많이 있습니다. 예를 들면, 많이들 아시는 lex & yacc, flex & bison 등 말이죠. 저희 팀에서는 Scanner 생성기로 flex를, 그리고 Parser 생성기로 Lemon을 사용하기로 했습니다.(아직 완전히 결정한 것은 아닙니다. 왜냐하면 flex의 경우 전역 변수를 사용하여 실행되므로 스레드나 기타 동시 제어에 안전한지 확실하지 않습니다. 문제가 생긴다면, 직접 구현해야겠죠; Lemon은 SQLite3와 같은 프로젝트에서 사용하고 있는 Parser generator입니다. 빠르고, 스레드에 안전하다는 장점이 있기 때문에 yacc와 같은 좀 더 대중화된 도구보다 이 도구를 선택하게 되었습니다.
자, 이제 툴까지 선정되었으니.. 이제 만들어봐야겠죠.
Lemon이라는 툴은 Parser생성 과정에서 터미널에 대한 정보를 헤더 파일로 만들어 주므로 lex 생성전에 정리한 문법을 토대로 Parser 먼저 생성합니다. Lemon 사용에 대한 간략한 순서는 다음과 같습니다.
이로써, Parser가 생성되었습니다.
Parser 생성시에 생성된 Terninal들의 토큰 번호들을 가지고 이제 Scanner를 만들어 봅니다. (f)lex에 대한 자세한 사용법은 서적이나 인터넷 자료들을 참고하세요. grammar.l 파일 작성에 대해 중요한 몇 가지만 설명드리면, 맨 앞에서는 실제 정리된 파일을 사용하기 위해서 #include "grammar.h" 해주고, %% 와 %% 사이에 정리된 파일에서 define된 이름들을 가지고 룰을 만듭니다. 마지막에 yywrap에 대한 함수도 정의해 주어야 합니다. lex를 이용해서 grammar.l 파일을 돌리면 우리가 원하는 Scanner의 소스 파일은 lex.yy.c 가 생성됩니다.
이로써 Scanner와 Parser의 소스파일을 모두 생성하였네요. 둘을 결합하여 실제 원하는 구현물에 사용하면 됩니다. 아래는 제가 만든 것들로 테스트한 콘솔 애플리케이션의 모습입니다.
흐흐.. 잘 돌아갑니다^^
세상에는 좋은 Parser 생성기와 Scanner 생성기가 많이 있습니다. 예를 들면, 많이들 아시는 lex & yacc, flex & bison 등 말이죠. 저희 팀에서는 Scanner 생성기로 flex를, 그리고 Parser 생성기로 Lemon을 사용하기로 했습니다.(아직 완전히 결정한 것은 아닙니다. 왜냐하면 flex의 경우 전역 변수를 사용하여 실행되므로 스레드나 기타 동시 제어에 안전한지 확실하지 않습니다. 문제가 생긴다면, 직접 구현해야겠죠; Lemon은 SQLite3와 같은 프로젝트에서 사용하고 있는 Parser generator입니다. 빠르고, 스레드에 안전하다는 장점이 있기 때문에 yacc와 같은 좀 더 대중화된 도구보다 이 도구를 선택하게 되었습니다.
자, 이제 툴까지 선정되었으니.. 이제 만들어봐야겠죠.
Lemon이라는 툴은 Parser생성 과정에서 터미널에 대한 정보를 헤더 파일로 만들어 주므로 lex 생성전에 정리한 문법을 토대로 Parser 먼저 생성합니다. Lemon 사용에 대한 간략한 순서는 다음과 같습니다.
1. lemon.c, lempar.c 를 다운로드 받습니다. lemon.c 는 Lemon Parser Generator의 실제 소스 코드이고 lempar.c 는 Parser 생성 시 참조하는 템플릿 파일입니다. 실제 생성된 코드와 템플릿 파일을 비교해 보시면 lempar.c 안의 %% 안의 내용이 적용 Grammar에 따라 적절히 채워지는 것을 볼 수 있습니다.
2. lemon.c 를 컴파일하여 실제 실행 파일(예를 들면, lemon)을 만듭니다.
3. 정리한 문법을 .y(확장자는 그냥 관습에 따릅니다.) 파일로 형식에 맞춰 저장합니다. 이에 대한 설명은 여기에서 참고하실 수 있습니다. Terminal은 대문자로 시작, Non-terminal은 소문자로 시작하는 것들입니다. 이를 인식해서 Non-terminal에 대한 토큰 번호를 생성해줍니다.
4. lemon [-s] grammar.y 하여 grammar.c 와 grammar.h 를 생성합니다. 중간에 생략가능하게 표시한 -s 옵션은 생성시에 Grammar에 대한 Terminal과 Non-terminal, state 수와 conflict 등을 표시해줍니다. grammar.h 는 터미널들을 정리해서 실제 토큰 번호들을 생성해 줍니다. grammar.c안에는 *ParserAlloc, *Parser, *ParserFree 함수를 가집니다. 사용법은 예상할 수 있듯이, Alloc 후 Parser 함수를 호출해서 검사하고 끝날 때 Free 함수를 호출합니다.
2. lemon.c 를 컴파일하여 실제 실행 파일(예를 들면, lemon)을 만듭니다.
3. 정리한 문법을 .y(확장자는 그냥 관습에 따릅니다.) 파일로 형식에 맞춰 저장합니다. 이에 대한 설명은 여기에서 참고하실 수 있습니다. Terminal은 대문자로 시작, Non-terminal은 소문자로 시작하는 것들입니다. 이를 인식해서 Non-terminal에 대한 토큰 번호를 생성해줍니다.
4. lemon [-s] grammar.y 하여 grammar.c 와 grammar.h 를 생성합니다. 중간에 생략가능하게 표시한 -s 옵션은 생성시에 Grammar에 대한 Terminal과 Non-terminal, state 수와 conflict 등을 표시해줍니다. grammar.h 는 터미널들을 정리해서 실제 토큰 번호들을 생성해 줍니다. grammar.c안에는 *ParserAlloc, *Parser, *ParserFree 함수를 가집니다. 사용법은 예상할 수 있듯이, Alloc 후 Parser 함수를 호출해서 검사하고 끝날 때 Free 함수를 호출합니다.
이로써, Parser가 생성되었습니다.
Parser 생성시에 생성된 Terninal들의 토큰 번호들을 가지고 이제 Scanner를 만들어 봅니다. (f)lex에 대한 자세한 사용법은 서적이나 인터넷 자료들을 참고하세요. grammar.l 파일 작성에 대해 중요한 몇 가지만 설명드리면, 맨 앞에서는 실제 정리된 파일을 사용하기 위해서 #include "grammar.h" 해주고, %% 와 %% 사이에 정리된 파일에서 define된 이름들을 가지고 룰을 만듭니다. 마지막에 yywrap에 대한 함수도 정의해 주어야 합니다. lex를 이용해서 grammar.l 파일을 돌리면 우리가 원하는 Scanner의 소스 파일은 lex.yy.c 가 생성됩니다.
이로써 Scanner와 Parser의 소스파일을 모두 생성하였네요. 둘을 결합하여 실제 원하는 구현물에 사용하면 됩니다. 아래는 제가 만든 것들로 테스트한 콘솔 애플리케이션의 모습입니다.
흐흐.. 잘 돌아갑니다^^
Trackback Address :: http://blog.swssm.org/trackback/103
-
8822c7cb6602
Tracked from 8822c7cb6602 | 2008/04/14 22:27 | DEL8822c7cb6602365f1ec8