슬라이드 1

LEX & YACC An Introduction jbkang @ Aug 2009

Part I. (F)LEX

Overview of Lex Automata Revisited 목표 : integer 또는 real number를 인식하는 Finite State Automaton 작성 (단, 소수점 이후에는 숫자가 하나 이상 있도록) accept : 정수 0~9 0~9 1~9. 0~9 S accept : 실수 starting state 0. accept : zero 3

Overview of Lex What s (F)lex? Lex = Lexical Analyzer Generator Flex = The Fast Lexical Analyzer - 오래된 Lex 에 대한 대체 프로그램 (Adobe Flex 와는 무관) Scanner (=tokenizer) 생성을 위한 도구 - recognize lexical patterns in text 확장 regular expression으로 패턴 규칙을 명시하고, 각 규칙에 대해 액션을 지정한다 Lex code lex C/C++ code 주어진 패턴을 분석할 수 있는 DFA (Deterministic Finite Automata) 코드를 생 성 4

Overview of Lex Lex 프로그램의 구조 Definitions section %% Rules section C/C++ code block simple name definitions start conditions patterns & actions %% User code section user-supplied C/C++ code 5

%{ #include <stdio.h> #include <string.h> #include <math.h> %} DIGIT [0-9] HEX [0-9A-Fa-f] ID [A-Za-z][A-Za-z0-9]* DOT "." %% {DIGIT}+{DOT}{DIGIT}* {DIGIT}+ printf("[%s]: float, value=%g\n", yytext, atof(yytext)); printf("[%s]: decimal, value=%d\n", yytext, atoi(yytext)); "0"[Xx]{HEX}+ { printf("[%s]: hexadecimal, value=%ld\n", yytext, strtol(yytext+2,0,16)); } {ID} printf("[%s]: identifier\n", yytext); [ \t\n]+ ;. printf("[%s]: unknown input\n", yytext); patterns actions %% #ifndef yywrap extern "C" int yywrap() { return 1; } #endif

$ ls foo.l main.cpp $ cat main.cpp #include <stdio.h> extern int yylex(); int main() { return yylex(); } $ flex foo.l $ ls foo.l lex.yy.c main.cpp $ c++ -c lex.yy.c main.cpp ; c++ *.o $ ls a.out foo.l lex.yy.c lex.yy.o main.cpp main.o $./a.out jbkang 100 3.14159 0xAC00 foo123 what's up? [jbkang]: identifier [100]: decimal, value=100 [3.14159]: float, value=3.14159 [0xAC00]: hexadecimal, value=44032 [foo123]: identifier [what]: identifier [']: unknown input [s]: identifier [up]: identifier [?]: unknown input

Lex Definitions Code Block %{ 과 %} 사이에 임의의 C/C++ 코드 삽입 가능 #include, #define, 변수 및 함수 선언 등에 사용 Simple Name Definitions 일종의 macro라고 보면 됨 %{ #include <stdio.h> #include <string.h> #include <math.h> %} definition에는 확장 regular expression 사용 가능 Start Conditions Lex에서는 규칙을 조건적으로 적용 가능 그런 경우들을 symbolic하게 정의해둠 DIGIT [0-9] HEX [0-9A-Fa-f] ID [A-Za-z][A-Za-z0-9]* DOT "." %x COMMENT 8

Lex Rules Patterns x Character x. Newline (\n) 제외한 모든 char [xyz] [abc-gz] [^A-Z\n] x, y, z 중 하나 a, b, c ~ g사이, z 중 하나 대문자와 newline을 제외한 모든 char {DIGIT}+ {DIGIT}+{DOT}{DIGIT}* R* R+ R? 0 or more; 1 or more; optional R R{4} R{2,5} 4번의 R; 2~5번의 R "0"[Xx]{HEX}+ {ID} {NAME} "[hello\"" \n\t\b\f \xba definitions section에 정의된 NAME이라는 패 턴 문자 그대로의 [hello" C언어에서와 같음 16진수로 0xBA인 char [ \t\n]+. ^R R$ 행 시작에 있는 R; 행 끝에 있는 R <sc>r Start condition = sc 일 때의 R 9

Lex Rules Actions 아무 C/C++ statement나 사용 가능. 여러 줄에 걸칠 때는 { } 로 싸 준다. 여러 pattern에 대해 같은 action일 경우 로 이어준다. 예) a b printf( matched a or b\n ); Special Directives ECHO : 현재 매치된 내용(yytext)을 그대로 출력(yyout) BEGIN : 특정 start condition을 시작함 ( 초기 condition은 INITIAL 로 정의) REJECT : 현재 패턴에 대한 second best rule로 넘어감 10

C Language Interface Available to the User int yylex(void) char* yytext int yyleng FILE* yyin void yyrestart(file*) FILE* yyout lexical analyzer 메인 함수 현재 매치된 token 현재 매치된 token의 길이 입력 스트림 (default: stdin) 입력을 전환함 출력 스트림 (default: stdout) (cf. ECHO) YY_CURRENT_BUFFER 현재 text buffer의 핸들 (메모리 해제시 등) YY_START 현재 start condition을 나타내는 정수 값 (cf. BEGIN) Supplied by User int yywrap(void) 입력이 끝났을 때 종료 (return 1) 혹은 계속 (return 0) 11

Starting Conditions Example : One-Line Comment int commentcaller; %x COMMENT %% // commentcaller = YY_START; BEGIN(COMMENT); \n. /* anything else is ignored */; <COMMENT>{ \r\n \n BEGIN(commentCaller);. /* eat up comment */; } %% 12

The Generated Scanner lex.yy.c 의 대략적인 구조 state transition 등 각종 table을 비롯한 global 정의; int yylex() { loop { scan된 token에 따라 state 변경; action 수행; yyin EOF 이면 return 0; (입력이 여러개라면 caller측에서 yyrestart()로 전환하면 됨) action에 return이 있을 경우 해당 값으로 return; (다음 yylex 호출시는 거기서 resume) } } 그 외 각종 support functions. 13

%{ #include <stdio.h> #include <string.h> #include <math.h> %} 다시 봅시다.. DIGIT [0-9] HEX [0-9A-Fa-f] ID [A-Za-z][A-Za-z0-9]* DOT "." %% {DIGIT}+{DOT}{DIGIT}* {DIGIT}+ printf("[%s]: float, value=%g\n", yytext, atof(yytext)); printf("[%s]: decimal, value=%d\n", yytext, atoi(yytext)); "0"[Xx]{HEX}+ { printf("[%s]: hexadecimal, value=%ld\n", yytext, strtol(yytext+2,0,16)); } {ID} printf("[%s]: identifier\n", yytext); [ \t\n]+ ;. printf("[%s]: unknown input\n", yytext); %% #ifndef yywrap extern "C" int yywrap() { return 1; } #endif int main() { return yylex(); }

Part II. YACC

Overview of Yacc What s Yacc? Yet Another Compiler-Compiler 컴파일러 제작에서 Parser (Syntactic Analyzer) 생성을 위한 도구 Lex와 함께 1975년 발표되었음 Yacc code yacc C/C++ code Lexical analyzer를 필요로 함 (따라서 lex와 종종 같이 쓰임) GNU Bison, Berkeley Yacc, MKS Yacc 등의 변종이 있음 16

The Power of Automata? Lex로 처리할 수 없는 패턴? 예 1. ((( a ) b ) c ) 예 2. a k b k, k 0 현재 state와 input만 알 수 있을 뿐, 지난 일을 기억해둘 수는 없다. Finite State Automata 혹은 regular language의 한계. 기억 을 위해 Stack을 추가 Pushdown Automata 이런 식으로 automata의 능력이 증대되면, 인식 가능한 패턴들이 더 늘어난다...사람이란, 기억의 총합인가?...... from <Ghost in the Shell> 17

Formal Language Theory 먼저, 용어부터 단 어 설 명 비 고 alphabet a set of symbols { 0, 1 } string ordered sequence of symbols 0011101 ε empty string epsilon language a set of words (finite strings) { 00, 01, 10, 11, ε } terminal literal string을 나타내는 기호 (트리 단말 노드를 연상) a nonterminal production rule을 나타내는 기호 (트리 중간 노드) A production rule grammar LHS RHS 형태로 된, symbol sequence의 rewriting rule 어떤 string이 특정 language에 속하는지를 기술하기 위한 변환 규칙의 집합. A ab terminals, nonterminals, rules, starting symbol 18

Formal Language Theory Formal Language Theory? (formal) language : a set of finite strings formal language theory : 이런 언어들의 구조적인 성질을 연구하는 분야 (의 미: ) language가 grammar에 의해 생성 혹은 grammar가 language를 인식 Different Power of Grammars grammars minimal automaton 비 고 Type-0 Unrestricted Turing Machine α β Type-1 Context- Sensitive Linear-bounded αaβ αγβ Nondeterministic Type-2 Context-Free V w cf. Yacc Pushdown See http://en.wikipedia.org/wiki/formal_language_theory Chomsky Type-3 hierarchy Regular Finite A ab a cf. Lex 19

Regular Grammar Regular Language 다음에 의해 정의된다: - alphabet에 속하는 각 symbol들과 empty string ε - union (A B), concatenation (AB) - Kleene star (A*) /'kleini:/ Production Rule A a / A ab / A ε 의 모습 right regular grammar A a / A Ba / A ε 의 모습 left regular grammar a*는 A aa, A ε로 표현 가능 +와?는 불필요 : a+ 는 aa*로, a? 는 ( a ε) 로 대체 Regular Expression : expressive power가 regular language를 종종 넘어선 다. 20

Context-Free Grammar 특 징 프로그래밍 언어와 컴파일러의 설계에서 핵심적인 역할 자연언어 처리에서도 종종 사용됨 1950년대에 언어학자 Noam Chomsky에 의해 제시 (cf. Chomsky hierarchy) Production Rule V w 의 모습 : V는 nonterminal 이고 w는 (term nonterm)* 좌항(LHS)이 하나뿐이라 앞뒤 문맥과 무관하다고 해서 context-free라고 함 언어 { a k b k k 0 } 을 생성하는 CFG의 예 : S a S b S ε S S S S S a a a ε b b b 21

Context-Free Grammar Pushdown Automata Context-Free Language 를 생성 { a k b k k 0 } 를 생성하는 오토마타의 예 push A a ; Z/AZ a ; A/AA b ; A/ε pop ε ε; Z/Z A, Z : stack alphabet Z : initial stack symbol 22

So Far So Good.. So What? Where is Yacc? 많은 프로그래밍 언어가 그 문법을 BNF (Backus-Naur Form) 로 정의한다. C 언어의 예 : <Typedef Decl> ::= typedef <Type> ID ';' Yacc에서는 BNF 와 유사한 방식으로 Context-Free Grammar를 기술할 수 있다. typedef_decl : T_TYPEDEF type T_ID ';' (물론 프로그래밍 언어 외의 용도로도 쓸 수 있다) What about Lex? Yacc는 내부적으로 yylex()를 호출 Lex의 yylex()는 입력으로부터 token들 (terminal) 을 추려내어 yacc에게 공급 yylex()의 return 값을 yacc에서 token 종류로 인식 (예: T_ID) token definition은 y.tab.h 헤더파일을 통해 공유 23

Compilation Sequence source code a = b + c * d Lexical Analyzer Lex patterns tokens id1 = id2 + id3 * id4 Syntactic Analyzer Yacc grammar syntax tree id1 = + id2 * id3 id4 Code Generator generated code LDA id3 MUL id4 ADD id2 STO id1 from http://epaperpress.com/lexandyacc/ 24

Lex & Yacc Co-operating foo.y yacc y.tab.c source code yyparse() y.tab.h cc foo.exe foo.l lex lex.yy.c yylex() compiled output from http://epaperpress.com/lexandyacc/ 25

Overview of Yacc Yacc 프로그램의 구조 %{ %} Prologue Declarations %% Lex와 거의 같다 Grammar Rules %% Epilogue 26

Sample Code : foo.l %{ #include <stdio.h> #include <string.h> #include <math.h> #include <string> #include <map> #include "y.tab.h" using namespace std; typedef map<string,int>::iterator MapIter; namespace { // local scope } %} map<string,int> symtab; int symindex( const char* ); DIGIT [0-9] HEX [0-9A-Fa-f] ID [A-Za-z][A-Za-z0-9]* DOT "." %% %% #ifndef yywrap extern "C" int yywrap() { return 1; } #endif namespace { int symindex( const char* s ) { MapIter it = symtab.find(s); if( it == symtab.end() ) { int idx = symtab.size(); symtab.insert( map<string,int>::value_type(s,idx)); return idx; } else { return it->second; } } } // namespace // EOF {DIGIT}+{DOT}{DIGIT}* yylval.fval = atof(yytext); return T_FLOAT; {DIGIT}+ yylval.ival = atoi(yytext); return T_INT; "0"[Xx]{HEX}+ yylval.ival = strtol(yytext+2,0,16); return T_INT; {ID} yylval.ival = symindex(yytext); return T_ID; [ \t\n]+ /* skip whitespaces */;. return yytext[0];

Sample Code : foo.y %{ #include <stdio.h> extern int yylex( void ); int yyerror( char* ); %} %union { int ival; float fval; }; %token <ival> T_ID T_INT %token <fval> T_FLOAT %% stmts stmt : stmts stmt none ; : assign_stmt ; assign_stmt : T_ID '=' T_INT ';' { printf("assignment: ID (idx=%d) <= INT (val=%d)\n", $1, $3); } T_ID '=' T_FLOAT ';' { printf("assignment: ID (idx=%d) <= FLOAT (val=%g)\n", $1, $3); } ; none : /* empty */ ; %% int yyerror( char *s ) { fprintf(stderr, "%s\n", s); return 0; } int main() { return yyparse(); }

$ ls Makefile Makefile.dep foo.l foo.y $ make flex -8 foo.l yacc -d foo.y g++ -Wall -O -c lex.yy.c g++ -Wall -O -c y.tab.c g++ -o a.out lex.yy.o y.tab.o $ ls Makefile a.out foo.y lex.yy.o y.tab.h Makefile.dep foo.l lex.yy.c y.tab.c y.tab.o $./a.out foo=100; assignment: ID (idx=0) <= INT (val=100) foo2 = 200 ; assignment: ID (idx=1) <= INT (val=200) bar = 0x1010; assignment: ID (idx=2) <= INT (val=4112) foo2 = 3.14159; assignment: ID (idx=1) <= FLOAT (val=3.14159)

Yacc Declarations %union token이나 nonterminal들이 가질 수 있는 value type이 int가 아닐 때 별도로 지정 %union { int ival; double dval; } %token %right %left %nonassoc token의 이름 선언 %union이 쓰였으면 value type도 지정 token (주로 연산자) 을 선언하면서 associativity (결합 방향) 와 우선순위 (나중에 나온것이 높다) 를 지정 %token T_NUM %token <ival> T_NUM %left T_PLUS T_MINUS %left T_MULTIPLY T_DIVIDE %type %union이 쓰였을 때 nonterminal의 value type 지정 %type <ival> some_expr %start 이 grammar의 start symbol 지정 미지정시 첫번째 rule의 LHS로 간주 %start stmts 30

Yacc Grammar Rules Rule LHS : RHS ; 의 형태로 문법을 기술한다. - LHS에는 하나의 nonterminal, RHS에는 terminal / nonterminal 들이 온다. (CFG니 까) 같은 LHS에 대해 여러 RHS를 로 연결할 수 있다. 예) assign_stmt : T_ID '=' T_INT ';' T_ID '=' T_FLOAT ';' ; Action 각 grammar rule 마다 { } 사이에 C/C++ 코드로 액션을 지정한다. special symbols - $$ : 현재 LHS의 value - $1, $2, : 현재 RHS에서 첫번째 심볼, 두번째 심볼, 예) { printf("id (idx=%d): INT (val=%d)\n", $1, $3); $$ = $3; } 31

Yacc Grammar Rules Recursive Rules A*, A+, A? 는 regular grammar때와 동일한 방법으로 표현 - A* S : S a ε ; - A+ S : S a a ; - A? S : a ε ; 구현시에는 left recursion 형태의 규칙만 써야 함 (right recursion은 stack에다 나머지 심볼들을 모두 쌓아야 해서 제한이 발생) Empty Rule ε 에 대한 rule은 아래와 같이 하면 된다 empty : /* just a comment */ ; 32

C Language Interface Available to the User int yyparse(void) YYACCEPT YYABORT int yylex(void) yylval top level parser function 성공, 0을 리턴하는 매크로 실패, 1을 리턴하는 매크로 Lex가 생성한걸 쓰던지 사용자가 직접 작성 token이 가진 값. 기본값은 int 이며 %union이 지정된 경우 그 중 한 값이 된다. (Lex에서 사용) Supplied by User yyerror void yyerror( const char* ) 정도면 무난함 33

Debugging Grammar Rules ADV How to Debug Grammar yacc v 옵션으로 parsing table 파일 생성 (y.output) yacc conflict 메시지와 parsing table에 기초하여 문법 수정 Grammar Ambiguity 어떤 상황에서 action이 유일하게 정의되지 않는 경우 shift/reduce 와 reduce/reduce conflict가 있다. shift/reduce conflict의 예: if_stmt : IF cond THEN stmt IF cond THEN stmt ELSE stmt 34

Sample y.output ADV Grammar state 0 state 1 state 2 0 $accept: S $end 1 S: a b 2 a S b 0 $accept:. S $end a shift, and go to state 1 S go to state 2 1 S: a. b 2 a. S b a shift, and go to state 1 b shift, and go to state 3 S go to state 4 0 $accept: S. $end $end shift, and go to state 5 state 3 1 S: a b. $default reduce using rule 1 (S) state 4 2 S: a S. b b shift, and go to state 6 state 5 0 $accept: S $end. $default accept state 6 2 S: a S b. $default reduce using rule 2 (S)??

Parser Architecture ADV Table-based Bottom-up Parser input ID = NUM + NUM ; stack 4 1 0 Parser grammar output state들 action table goto table state transition 및 rule reduction 정보 See http://en.wikipedia.org/wiki/lr_parser 36

The Parsing Table ADV Shift Action 현재 state에서 Terminal 을 만났을 때. (예: s3) 현재 input token을 소비한다. 주어진 next state를 stack에 push 한다. Reduce Action 현재 state에서 Nonterminal 이 생성될 때. (예: r2) 생성에 관련된 rule 번호가 주어진다. input은 그대로 둔다. stat e action goto a b $ S 0 s1 2 1 s1 s3 4 2 s5 3 r1 r1 r1 4 s6 5 acc acc acc 6 r2 r2 r2 rule의 RHS에 있는 심볼 수 만큼 stack에서 pop 한다. (예: S a S b 는 3개) GOTO table에서 (stack[top], nonterminal) 의 entry를 찾아서 next state로 삼고 stack에 push 한다. 37

Parsing Procedure Example ADV { a k b k k 1 } 를 생성하는 grammar aabb$ 의 파싱 과정 (1) S : a b (2) a S b stack input act next output stat e action goto a b $ S 0 s1 2 1 s1 s3 4 2 s5 3 r1 r1 r1 4 s6 5 acc acc acc 6 r2 r2 r2 앞 페이지에 나온 테이블 (yacc가 내부적으로 만든다) [0] aabb$ s1 1 [0,1] abb$ s1 1 [0,1,1] bb$ s3 3 [0,1,1,3] b$ r1 4 (1) [0,1,4] b$ s6 6 [0,1,4,6] $ r2 2 (1) (2) [0,2] $ s5 5 [0,2,5] $ acc 38

Yacc Review Parser Generator Context-Free Grammar, Pushdown Automata Lex return value & yylval y.tab.h %union, %token Production Rule terminal, nonterminal, LHS, RHS shift, reduce, conflict parsing table, y.output 終 39