이 글은 Introduction to yacc - Wayne Cochran
를 보고 배운것을 정리한 것임.
yacc
는 BNF와 같은 형식의 rules의 항목들로부터 parser를 만들어내는 프로그램이다lex
는 코드를 해석하고 token으로 분해한다. yacc
에 yylex() 함수를 제공.yacc
기술파일의 main()함수에서 yyparse()함수라는 yacc
에 의해 만들어지는 구문분석기를 부르고, yyparse()함수는 yylex()라는 lex
가 만들어 주는 해석기(lexer)를 이용해서 입력열에서 처리단위의 토큰을 뽑아오게 된다.image source from https://www.youtube.com/watch?v=yTXCPGAD3SQ
아래 7라인의 파싱 문법으로 코드를 파싱한다고 할때 yacc는 이미지에서 우측과 같이 파싱트리를 생성하고 계산한다. 각 토큰을 만날때 문법내용을 이용해 토큰을 하나하나씩 줄이는 방식으로 동작한다. 결국 최종 상단인 S -> E $
로 수렴하게 된다. 이것을 간단하게 구현해보자. calc.y 파일에 해당 문법을 구현하고 yacc로 파싱 C코드를 생성해보자.
image source from https://www.youtube.com/watch?v=yTXCPGAD3SQ
%token NUM
%%
S : E
;
E : E '+' T
| T
;
T : T '*' F
| F
;
F : '(' E ')'
| '-' F
| NUM
;
%%
y.tab.c 파일이 생성되고 코드를 살펴보면 yyparse() 함수가 생성되어있다. 추후 작성하는 프로그램에서 이 함수를 호출하면 될듯.
$ yacc calc.y
$ ls
calc.y y.tab.c
이제 yacc와 lex를 사용해 간단한 사칙연산 구문을 파싱하고 계산하는 소스코드를 생성해보자.
image source from https://www.youtube.com/watch?v=yTXCPGAD3SQ
calc.y 파일 전체 코드. 자세한 설명은 하단에
%{
#include <stdio.h>
#include <stdlib.h>
extern int yylex();
void yyerror(char *msg);
%}
%union {
float f;
}
%token <f> NUM
%type <f> E T F
%%
S : E {printf("%f\n", $1);}
;
E : E '+' T {$$ = $1 + $3;}
| E '-' T {$$ = $1 - $3;}
| T {$$ = $1;}
;
T : T '*' F {$$ = $1 * $3;}
| T '/' F {$$ = $1 / $3;}
| F {$$ = $1;}
;
F : '(' E ')' {$$ = $2;}
| '-' F {$$ = -$2;}
| NUM {$$ = $1;}
;
%%
void yyerror(char *msg) {
fprintf(stderr, "%s\n", msg);
exit(1);
}
int main() {
yyparse();
return 0;
}
awk 처럼 패턴과 action형태. $1는 E, $2는 '+', $3은 T를 의미
E : E '+' T {$$ = $1 + $3;}
모든 값을 float 타입으로 설정.
%union {
float f;
}
%token <f> NUM
%type <f> E T F
main() 함수에서 yyparse() 호출
void yyerror(char *msg) {
...
int main() {
yyparse();
상단에 헤더파일 include 및 함수 프로토타입 선언
%{
#include <stdio.h>
...
%}
calc.l 파일 전체 코드. 자세한 설명은 하단에
%{
#include <stdio.h>
#include <stdlib.h>
#include "y.tab.h" // generated via yacc -d, it contains yylval, NUM symbols.
%}
%option noyywrap
%%
[0-9]+(\.[0-9]+)?([eE][0-9]+)? {yylval.f = atof(yytext); return NUM;}
[-+()*/] {return yytext[0];}
[ \t\n\f\v] { ; }
%%
yacc -d
수행시 생성되는 y.tab.h
헤더 include. 여기에 yylval, NUM등의 변수나 define등이 정의 되어있다.
%{
#include "y.tab.h" // generated via yacc -d, it contains yylval, NUM symbols.
%}
정규 표현식 정의 및 해당 패턴에 대한 action 추가
[0-9]+(\.[0-9]+)?([eE][0-9]+)? {yylval.f = atof(yytext); return NUM;}
yywrap 에러 해결하기, 아래 라인 추가.
%option noyywrap
또는 아래 라인 추가.
/* %option noyywrap */
...
int yywrap() {return -1;}
이 라인이 없다면 아래의 에러가 발생 (mac os x환경에서 수행)
$ cc y.tab.c lex.yy.c -o calc
Undefined symbols for architecture x86_64:
"_yywrap", referenced from:
_yylex in lex-5cad3a.o
ld: symbol(s) not found for architecture x86_64
clang: error: linker command failed with exit code 1 (use -v to see invocation)
yacc
$ yacc -d calc.y
$ ls
y.tab.c y.tab.h
-d
옵션을 사용하면 헤더파일도 생성된다.
lex
$ lex calc.l
$ ls
lex.yy.c
cc
이제 위에서 생성 된 두 c파일을 빌드하면 된다. (이 환경에서 cc는 clang임)
$ cc y.tab.c lex.yy.c -o calc
$ ls
calc
./calc
를 수행하고, 수식을 입력하고 ctrl + d 하면 내부적으로 파스트리 생성 및 계산결과 확인가능.
$ ./calc
(-3 + 4) * 10 / 5
2.000000