이 글은 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
yacc 기초
아래 7라인의 파싱 문법으로 코드를 파싱한다고 할때 yacc는 이미지에서 우측과 같이 파싱트리를 생성하고 계산한다. 각 토큰을 만날때 문법내용을 이용해 토큰을 하나하나씩 줄이는 방식으로 동작한다. 결국 최종 상단인 S -> E $ 로 수렴하게 된다. 이것을 간단하게 구현해보자. calc.y 파일에 해당 문법을 구현하고 yacc로 파싱 C코드를 생성해보자.
image source from https://www.youtube.com/watch?v=yTXCPGAD3SQ
calc.y (yacc 파일의 확장자는 y)
%token NUM
%%
S : E
;
E : E '+' T
| T
;
T : T '*' F
| F
;
F : '(' E ')'
| '-' F
| NUM
;
%%yacc로 C파일 생성
y.tab.c 파일이 생성되고 코드를 살펴보면 yyparse() 함수가 생성되어있다. 추후 작성하는 프로그램에서 이 함수를 호출하면 될듯.
$ yacc calc.y
$ ls
calc.y y.tab.cyacc 와 lex로 계산기 C파일 생성하기
이제 yacc와 lex를 사용해 간단한 사칙연산 구문을 파싱하고 계산하는 소스코드를 생성해보자.
image source from https://www.youtube.com/watch?v=yTXCPGAD3SQ
1. [yacc] calc.y 생성
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 Fmain() 함수에서 yyparse() 호출
void yyerror(char *msg) {
...
int main() {
yyparse();상단에 헤더파일 include 및 함수 프로토타입 선언
%{
#include <stdio.h>
...
%}2. [lex] calc.l 파일 생성
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)3. C파일 생성 및 컴파일
yacc
$ yacc -d calc.y
$ ls
y.tab.c y.tab.h-d옵션을 사용하면 헤더파일도 생성된다.
lex
$ lex calc.l
$ ls
lex.yy.ccc
이제 위에서 생성 된 두 c파일을 빌드하면 된다. (이 환경에서 cc는 clang임)
$ cc y.tab.c lex.yy.c -o calc
$ ls
calc4. 계산기 실행
./calc를 수행하고, 수식을 입력하고 ctrl + d 하면 내부적으로 파스트리 생성 및 계산결과 확인가능.
$ ./calc
(-3 + 4) * 10 / 5
2.000000References
