YACC 응용예 Desktop Calculator 7/23
Lex 입력 수식문법을위한 lex 입력 : calc.l %{ #include calc.tab.h" %} %% [0-9]+ return(number) [ \t] \n return(0) \+ return('+') \* return('*'). { printf("'%c': illegal character\n", yytext[0]) exit(-1) }
Yacc 입력 수식문법을위한 yacc 입력 : calc.y %{ #include <stdio.h> %} %token NUMBER %% Exp : Exp '+' Term { printf("rule 1\n") } Term { printf("rule 2\n") } Term : Term '*' Num { printf("rule 3\n") } Num { printf("rule 4\n") } Num : NUMBER { printf("rule 5\n") }
실행 UNIX 명령어 % gedit calc.l % gedit calc.y % flex calc.l % bison -d calc.y % gcc -o calc lex.yy.c calc.tab.c -ly ll % gedit input %./calc < input
확장 - 0 입력 하나의식 입력의끝은 $ 문자로표현 빼기 (-), 나누기 (/), 그리고괄호연산지원 출력 입력된식의계산결과를출력
Lex 입력 %{ #include <stdlib.h> #include calc.tab.h extern int yylval %} %% [0-9]+ {yylval = atoi(yytext) return(number)} [ \t] $ {return 0 /* end of input */ } \n. {return(yytext[0]) }
%{ #include <stdio.h> %} %token NUMBER %% Yacc 입력 Goal: Exp {printf( =%d\n, $1)} Exp : Exp + Term {$$=$1+$3} %{ Exp - Term {$$=$1-$3} Term {$$=$1} Term : Term '*' Fact {$$=$1*$3} Term / Fact {$$=$1/$3} Fact {$$=$1} Fact: NUMBER {$$=$1} ( Exp ) {$$=$2}
입력 확장 - 1 하나의식에서여러개의식으로확장 한줄에하나의식 출력 입력된식의계산결과를출력
Lex 입력 %{ #include <stdlib.h> #include calc.tab.h extern int yylval %} %% [0-9]+ {yylval = atoi(yytext) return(number)} [ \t] $ {return 0 /* end of input */ } \n. {return(yytext[0]) }
Yacc 입력 %{ #include <stdio.h> %} %token NUMBER %% ExpList: ExpList Exp \n {printf( =%d\n, $2)} Exp \n {printf( =%d\n, $1)}
Yacc 입력 Exp : Exp + Term {$$=$1+$3} Exp - Term {$$=$1-$3} Term {$$=$1} Term : Term '*' Fact {$$=$1*$3} Term / Fact {$$=$1/$3} Fact {$$=$1} Fact: NUMBER {$$=$1} ( Exp ) {$$=$2}
확장 - 2 입력 변수지원, 단변수이름은하나의소문자 입력되는식에변수에대한배정도포함 피연산자는실수도가능 출력 입력된식들의계산결과를출력 배정문일경우, 배정되는값은출력하지않는다.
확장 2 의예 입력 a = 10.0 a+1 b = a+10 b+a 출력 11.0 30.0
변수를어떻게처리? 가능한변수의수는 26 개임 크기 26 인배열을사용 인덱스 0 에는변수 a 의값, 인덱스 1 에는변수 b 의값,. 어휘분석단계에서변수를인식하면, 토큰 Name 의값으로변수에대한인덱스를전달 double vbltables[26] a b c d e f g h 0 1 2 3 4 5 6 7
토큰의값 토큰의값 yylval 을통하여파서에게전달 토큰값의타입 yylval의타입 YYSTYPE 여러타입의값을허용하려면 C: union을사용 Yacc: %union을사용
토큰값의종류 정수, 실수, 스트링, %union 여러타입의토큰을파서에게전달 Yacc 에서토큰의타입을정의 %union { double dval int vblno } 각토큰의타입을지정 %token <vblno> NAME %token <dval> NUMBER
문법기호의타입 %union 에서정의 %type 을이용하여지정 문법기호의타입 예 %union { double dval struct symtab *symp } %token <symp> NAME %token <dval> NUMBER %type <dval> expression
Lex 입력 %{ #include <stdlib.h> #include calc.tab.h extern double vbltables[26] %} %% ([0-9]+ [0-9]*\.[0-9]+) {yylval.dval = atof(yytext) return(number)} [ \t] [a-z] {yylval.vblno = yytext[0]- a return NAME} $ {return 0 /* end of input */ } \n. {return(yytext[0]) }
Yacc 입력 %{ #include <stdio.h> double vbltables[26] %} %union { double dval int vblno } %token <vblno> NAME %token <dval> NUMBER %type <dval> Fact Term Exp %%
Yacc 입력 StmtList: StmtList Stmt \n Stmt \n Stmt : NAME = Exp {vbltables[$1] = $3} Exp {printf( =%f\n, $1)} Exp : Exp + Term {$$=$1+$3} Exp - Term {$$=$1-$3} Term {$$=$1} Term : Term '*' Fact {$$=$1*$3} Term / Fact {$$=$1/$3} Fact {$$=$1} Fact : NUMBER {$$=$1} NAME {$$= vbltables[$1]} ( Exp ) {$$=$2}
변수이름 확장 - 3 Single character multiple characters 예입력출력 input = 10.0 result = input+1 result 11.0 result-input 1.0
Symbol table 심볼테이블의구조 //symbol.h #define NSYMS 20 /* maximum number of symbols */ struct symtab { char double } symtab[nsyms] *name value struct symtab *symlook() 어휘분석 변수를인식하면심볼테이블을검색하여, 심볼테이블항목의주소를리턴 symlook() 함수를이용
symlook() 함수 //look up a symbol table entry, add if not present struct symtab *symlook(char *s) { struct symtab *sp } for(sp=symtab sp < &symtab[nsyms] sp++) { /* is it already here? */ if(sp->name &&!strcmp(sp->name, s)) return sp /* is it free? */ if(!sp->name) { sp->name=strdup(s) return sp } /* otherwise continue to next */ } yyerror( Too many symbols ) exit(1)
Lex 입력 %{ #include <stdlib.h> #include symbol.h #include calc.tab.h %} %% ([0-9]+ [0-9]*\.[0-9]+) {yylval.dval = atof(yytext) return(number)} [ \t] [A-Za-z][A-Za-z0-9]* {yylval.symp = symlook(yytext) return NAME} $ {return 0 /* end of input */ } \n. {return(yytext[0]) }
Yacc 입력 %{ #include symbol.h #include <stdio.h> #include <string.h> %} %union { double dval struct symtab *symp } %token <symp> NAME %token <dval> NUMBER %type <dval> Fact Term Exp
Yacc 입력 %% StmtList: StmtList Stmt \n Stmt \n Stmt : NAME = Exp { $1->value = $3} Exp {printf( =%f\n, $1)} Exp : Exp + Term {$$=$1+$3} Exp - Term {$$=$1-$3} Term {$$=$1} Term : Term '*' Fact {$$=$1*$3} Term / Fact {$$=$1/$3} Fact {$$=$1} Fact : NUMBER {$$=$1} NAME { $$=$1->value} ( Exp ) {$$=$2}
확장 - 4 Allow mathematical functions Such as sqrt(), exp(), log(), 예 입력 s2 = sqrt(2) s2 s2*s2 출력 1.41421 2
Naïve approach In Yacc source %token SQRT LOG EXP %% Term: SQRT ( Exp ) { $$ = sqrt($3) } EXP ( Exp ) { $$ = exp($3) } LOG ( Exp ) { $$ = log($3) } In Lex source You must hardcode functions into parser and lexer Function names are reserved words sqrt log exp return SQRT return LOG return EXP
Reserved Words in Symbol Table 심볼테이블구조 struct symtab { char *name double (*funcptr) () double value } symtab[nsyms] 심볼테이블에예약어저장 main() { extern double sqrt(), exp(), log() addfunc( sqrt, sqrt) addfunc( sqrt, sqrt) addfunc( sqrt, sqrt) yyparse() } void addfunc (char *name, double(*func)( ) ) { struct symtab *sp = symlook(name) sp->funcptr = func }
Reserved Words in Symbol Table In Yacc source %token <symp> NAME FUNC %% Term: FUNC ( Exp ) { $$ = sqrt($3) } In Lex source [A-Za-z][A-Za-z0-9]* { struct symtab *sp = symlook(yytext) } yylval.symp = sp if(sp->funcptr) /* is it a function? */ return FUNC else return NAME