• 참고 문헌 : lex & yacc, Tony Mason 외 1인, O'Reilly (1990)
• 참고 인터넷 자료
  • http://nlp.kookmin.ac.kr/sskang/lect/compiler/lexyacc/Lex_Yacc.htm
  • https://github.com/swmaestro06-apus/apus/wiki/Lex-&-Yacc-(flex-&-bison)-%EB%82%B4%EC%9A%A9-%EC%A0%95%EB%A6%AC

와씨 겁나 오래된 책이네.

이 책은 Parser의 구현을 공부하기 위해 위의 내용을 번안한 내용을 서술합니다. 오타 및 오역이 있을 수도 있습니다.

간단하게, 이런거

lex와 yacc은 구조화된 입력을 변환해서 활용하는데 사용. 단순한 텍스트 서칭부터 컴파일러 까지 두루두루.

다음의 두가지 일이 반복적으로 수행됨 :

• 구조화된 입력;structured input을 의미있는 형태소로 변환하고
• 형태소 간의 관계를 파악한다.

유닛으로의 '변환'이 바로, lexical analysis;lexing. 이때 변환된 유닛을 개태 '토큰'으로 칭한다. Lex specification 은 lex에게 제공되는 description set. '토큰'과 'Lex specification을 lexical analyzer에게 주면, '토큰'의 '식별'이 가능해진다 ㅇㅇ.

Lex는 Tokenizer라고 봐도 되는걸까.

lex는 token description 에 정규 표현식을 사용한다. Lex는 이러한 정규표현식을 고속 스캐닝이 가능한 형태로 변환하여 사용한다. C로 직접 기술된 형태보다 Lex의 Lexer 가 더 빠름…(…)

이후 token으로의 변환이 성공하면, token간의 관계를 부여해야 한다. 이과정이 parsing이며, 이때 필요한 것이 grammar(문법).

Yacc 는 문법요소를 파악하고 실행 가능한 루틴을 형성한다. yacc은 직접 작성된 parser에 비해선 그리 빠르진 않지만, parser의 작성과 변경에 낮은 위험도로 신속하게 대응할 수 있다.

그러니까 정리하면,

• Lex Scanner
• Yacc Parser; 'Yet Another Compiler Compiler'

%%
.|\n      ECHO;
%%

이것은 옵션을 주지 않은 cat명령과 같은 역할을 수행한다.

%
{
%}
%%

[\t ]+  /*ignore white space*/;

is |
am |
are |
were |
was |
be |
being |
been |
do |
does |
did |
will |
would |
can |
could |
has |
have |
had |
go           { printf("%s is a verb\n", yytext); }

[a-zA-Z]+  { printf("%s: is not a verb\n",  yytext); }

.|\n     { ECHO; /*normal default anyway */ }
%%

main()
{
    yylex();
}

이것을 완성해서 실행하면 다음과 같음.

% examp
did I have fun?
did : is a verb
I : is not a verb
have : is a verb
fun : is not a verb
?
^D

1. definition section : C 프로그램 코드가 들어갈 자리를 명시함. “%{” 로 시작, “%}“로 종료. 이 안에 C코드를 명시하면 file generating시 바로 c코드를 삽입시켜놓음.
2. rules section : 규칙은 2개의 파트로 구성됨, pattern, action. 이 둘은 whitespace(공백)으로 구분. pattern은 Unix-style 정규 표현식으로 표현. 여기서 (세로하이픈) 의 표현은 다음 액션과 같은 액션을 취하겠다는 이야기.
3. user subroutines section : C 코드로 구성됨. lex는 이것을 lex generated code 의 맨 끝에 삽입한다.

Lexer는 다음을 통해 모호한 상황을 해소한다.

1. lex pattern은 글자/단어에 대해 1회만 매칭한다.
2. 가장 현 입력에 대해 길게(?) 맞는 것에만 매칭한다. 가령, “is”를 찾을때, “island”가 매칭이 되더라도 그냥 “is” 만 찾게끔.

위 코드에서 '.'(온점) 은 한 글자에 대해 모두 매칭하는 경우. '\n'은 개행문자에 매칭하는 경우에 해당함. 이때는 ECHO명령을 수행하도록 한다.

lexer가 생성하는 C 루틴이 yylex()임. return을 따로 명시하지 않을 경우, 전체 입력에 대해 명령을 수행할 때 까지는 return하지 않음.

다음의 컴파일 과정으로 수행한다.

$ lex (something).l
gcc something.yy.c -o (binary) -ll

Lex는 *.ㅣ 파일을 c코드로 변환하고, gcc가 lex library -ll을 활용해 컴파일을 수행한다.

그리고, dynamic declaration. 그러니까, 유닛 패턴을 테이블화 해서 동적으로 관리하는 것도 역시 가능하다는 이야기. 허나 이렇게 Symbolic table을 두어 관리하게 되는 경우, 코드 형태가 꽤 변화한다.

• enum{}을 두어 속성 관리
• 따로 state를 부여할 수 있는 함수 생성
• pattern에 따른 state 부여 코드 추가 등.
• 단어를 관리하는 구조체가 링크드 리스트 형태로 구현.

이 코드는 책 10-11에 서술됨.

단어간의 관계가 이치에 맞는가 여부를 판단하는데 사용. 다음과 같은 경우를 생각하면 이해하기 쉬울 것.

• 명사 동사
• 명사 동사 명사
• 전치사 → 명사 | 동사
• 목적어 → 명사
• 문장 → 전치사 동사 목적어

뭐 이런거.

둘을 같이 쓸때는 Parser 가 더 Higher Level Routine이 된다. 이게 토큰이 필요할 때 yylex()를 부른다. 모든 토큰이 Parser가 알고 싶은건 아니니깐, parser를 귀찮게 하지 않고 다음 토큰으로… 뭔소린지.

yacc에서는 ”#define” 코드를 통해서 토큰들을 정의해놓는다. 뒷부분에 설명이 더 잘 되어있겠지?

rules section에 서술된 소스코드의 경우에 return을 사용한 경우, yylex()함수가 coroutine과 같이 동작한다. token의 증가함에 따라서 토큰을 검사하고 적절한 명령을 실행하는게 가능해짐.

%{

#include <stdio.h>
%}

%token NOUN ....
%%
sentence : subject VERB object {printf(...)}

subject : NOUN
       | PRONOUN
       ;

%%

extern FILE *yyin;
main(){
    do{
        yyparse();
    }
}

다음의 구조를 따르는데, lex lexer의 구조와 유사하다.

1. definition section : literal code block영역 “%{”, “%}” 으로 구성. 마찬가지로 C코드가 삽입됨. 이후 lexical analyzer로 부터 전달받는 token에 대한 정의가 삽입됨. 토큰 정의야 아무렇게나 써도 되기는 하다만, 대체로 이때 사용되는 토큰 이름은 거진 다 uppercase.
2. subroutine section : main()은 yyparse()를 호출하여 lexer의 input file이 다 끝날때 까지 돌아간다. yyparse()는 yacc이 만들어내는 parser.

(production) rules의 집합인 실제 문법을 서술하는 영역. rule의 표기 형태는 (rulename): (symbole list) (action code);

가장 앞에 오는 rule이 가장 강력한 (highest-level) rule이 된다. action part에서는 c 코드가 서술 됨. 당연히 rule이 매칭되면 command 실행되는 구조.

subroutine section 에서는, c 코드 루틴이 삽입됨. main()과 yyerror()는 lex lexer를 위해 parser가 만들어준다. FILE yyin의 EOF를 만날 때 까지 parser가 작동한다. yylex() 도 lexer가 만들어줌.

다음을 통해 컴파일

lex <file>.l
yacc -d <file>.y
cc -c lex.yy.c y.tab.c
cc -o <something> lex.yy.o y.tab.o -ll

C로도 Lexer를 짤수는 있겠지만 Lex Lexer로 짜는게 가독성, 코드 유지보수 면에서 좀더 좋습니다 ㅇㅇ.