TinyCIn Lex Yacc
|
TinyC language parser
글쓴이 : 이 형채 <hclee80 atat gmail dotdot com>
최초 수정일 : 2008년 06월 19일 ( 흐림 )
최종 수정일 : 2008년 06월 20일 ( 맑음 )
1. TinyC ? ¶tinyC ( 타이니 씨(0) ) - compiler construction, principles and practice -> kenneth C, rouden ( 컴파일러 제작, 원리와 실제 -> 김재훈|도경구|우균|정덕길|정민수)
책에서 컴파일러의 스캐너 & 파서 ( front-end ) 설명을 위해서 쓰여진 간단한 언어입니다. 영어를 그대로 해석해도 좋을 듯 싶습니다. 별다른 설명이 필요없을 정도로 적은 예약어와 문법입니다. lex와 yacc의 사용법을 익히기 위한 언어라고 생각하시면 됩니다. 물론 Tiny C Compiler 도 존재합니다.
Tiny C -> C-Minus -> C-- -> ANSI C 순서대로 확장되는 개념이라고 생각하시면 됩니다. 물론 ANSI C부터는 표준이고, 그 이하는 표준이 없습니다. 이 말은 곧 정의 및 구현하는 방법에 따라서 달라질수 있습니다. 예약어중 하나인 int 를 integer 라고 정의할수도 있을테고, INTEGER 라고 정의할 수도 있는 것입니다.
lex & yacc 을 설명하는 책, 문서, 사이트 등에서 쉽게 볼수 있는 예제가 expr ( expression ) 예제일 겁니다.이 내용은 결국 우선순위가 있는 calc 계산기 만들기와 동일합니다. 또한, "shift/reduce 충돌" 문제에 대한 내용에서도 언급되는 부분입니다. 그러나, 이 예제만으로 lex & yacc의 사용법은 익힐수 있으나, 정확한 이해는 매우 힘든 것같습니다.
그래서, Tiny C 가 lex & yacc 이용한 프로그래밍언어 파서를 만드는데 가장 좋은 예제인것 같습니다. 물론 lex & yacc가 꼭 프로그래밍언어만을 위한 것은 아닙니다. 응용방법은 무궁무진합니다. 이에 대해서는 추후에 다른 글을 참고하시면 됩니다.
유명한 awk, Perl 같은 문자열처리가 편한 툴 및 언어들처럼 c, c++ 에서도 유연하게 개발하실수 있습니다. awk 는 결국 lex & yacc 의 불편함(?)때문에 나온 것이고, Perl은 awk의 부족함을 채우기 위해서 만들어졌다. awk 주목적 개발목적은 빠른 테스팅(문자열처리)과 간편함을 위함이었다.
2. TinyC lexical ¶
2.1. TinyC.l ¶
%{
%{
#include "list.h"
#define YYSTYPE ListPtr
#include "y.tab.h"
extern YYSTYPE yylval;
%}
%%
"==" return EQ;
"<" return '<';
">" return '>';
"=" return '=';
"+" return '+';
"-" return '-';
"*" return '*';
"/" return '/';
"," return ',';
";" return ';';
"(" return '(';
")" return ')';
"{" return '{';
"}" return '}';
"[" return '[';
"]" return ']';
"int" return INT;
"return" return RETURN;
"if" return IF;
"else" return ELSE;
[0-9]+ { List* lst = NullList();
yylval = AddInteger(lst, atoi(yytext));
return Number;
}
[A-Za-z][A-Za-z0-9]* { List* lst = NullList();
yylval = AddSymbol(lst, MakeSymbol(yytext));
return Identifier;
}
[ \t\n] ;
. return BADTOKEN;
%%
3.1. TinyC.y ¶
/*
tinyc.y -- a parser of Tiny C
*/
%{
#include <stdio.h>
#include "list.h"
#define YYSTYPE ListPtr
static List* MakeBinaryExpr(char* op, List* exp1, List* exp2);
static List* MakeTriple(char* op, List* e1, List* e2, List* e3);
%}
/* yacc produces yyparse() from the following grammar. */
%token Identifier
%token Number
%token '=' '+' '-' '*' '/' ',' ';' '(' ')' '{' '}' '[' ']' '<' '>'
%token INT
%token RETURN
%token IF
%token ELSE
%token EQ /* == */
%token BADTOKEN
%%
program
: function
{}
| program function
{}
| error '}' /* error recovery: ignore tokens until '}' */
{} /* is encountered. */
function
: typename Identifier '(' formal.arguments ')' function.body
{
List* lst;
lst = ConcatLists($1, $2);
lst = AddList(lst, $4);
lst = ConcatLists(lst, $6);
PrintList(lst);
$$ = lst;
}
typename
: INT
{ $$ = AddSymbol(NullList(), "int"); }
| INT '*'
{ $$ = AddSymbol(NullList(), "int*"); }
formal.arguments
: /* empty */
{ $$ = NULL; }
| formal.argument.list
{ $$ = $1; }
formal.argument.list
: formal.argument
{ $$ = MakeList($1); }
| formal.argument.list ',' formal.argument
{ $$ = AddList($1, $3); }
formal.argument
: typename Identifier
{ $$ = MakeTriple("*var*", $2, $1, NULL); }
function.body
: '{' '}' /* empty body */
{ $$ = NULL; }
| '{' statements '}'
{ $$ = $2; }
statements
: statement
{ $$ = MakeList($1); }
| statements statement
{ $$ = AddList($1, $2); }
statement
: declaration
{ $$ = $1; }
| RETURN expression ';' /* return statement */
{ $$ = MakeBinaryExpr("return", $2, NULL); }
| if.statement
| term '=' expression ';' /* assignment */
{ $$ = MakeBinaryExpr("=", $1, $3); }
| expression ';'
{ $$ = MakeBinaryExpr(";", $1, NULL); }
| '{' statements '}'
{ $$ = MakeBinaryExpr("{}", $2, NULL); }
| ';' /* null statement */
{ $$ = NULL; }
declaration
: typename Identifier ';'
{ $$ = MakeTriple("*var*", $2, $1, NULL); }
| typename Identifier '[' Number ']' ';' /* array */
{ $$ = MakeTriple("*var*", $2, $1, $4); }
if.statement
: IF '(' expression ')' statement
/* ??? */
| IF '(' expression ')' statement ELSE statement
/* ??? */
expression
: additive.expression
{ $$ = $1; }
| expression EQ additive.expression
/* ??? */
| expression '>' additive.expression
/* ??? */
| expression '<' additive.expression
/* ??? */
additive.expression
: term
{ $$ = $1; }
| additive.expression '+' term
{ $$ = MakeList(MakeBinaryExpr("+", $1, $3)); }
| additive.expression '-' term
/* ??? */
term
: Identifier
{ $$ = $1; }
| Number
/* ??? */
| Identifier '(' opt.actual.arguments ')' /* function call */
{ $$ = MakeList(ConcatLists($1, $3)); }
| Identifier '[' expression ']' /* array access */
{ $$ = MakeList(MakeBinaryExpr("[]", $1, $3)); }
| '(' expression ')'
{ $$ = $2; }
opt.actual.arguments
: /* empty */
{ $$ = NullList(); }
| actual.arguments
{ $$ = $1; }
actual.arguments
: expression
{ $$ = $1; }
| actual.arguments ',' expression
{ $$ = ConcatLists($1, $3); }
%%
static List* MakeBinaryExpr(char* op, List* exp1, List* exp2)
{
List* lst = NullList();
lst = AddSymbol(lst, op);
lst = ConcatLists(lst, exp1);
return ConcatLists(lst, exp2);
}
static List* MakeTriple(char* op, List* e1, List* e2, List* e3)
{
List* lst = NullList();
lst = AddSymbol(lst, op);
lst = ConcatLists(lst, e1);
lst = ConcatLists(lst, e2);
return ConcatLists(lst, e3);
}
yyerror(msg)
char* msg;
{
#if !defined(YYBISON)
extern int yynerrs;
++yynerrs;
#endif
fprintf(stderr, "Error: %s\n", msg);
}
main()
{
extern int yynerrs;
#ifdef YYDEBUG
yydebug = !0;
#endif
yyparse();
fprintf(stderr, "%d errors.\n", yynerrs);
}
4. Makefile ¶#YACC = bison -dvy YACC = yacc -dv #LIB = -lfl # Linux LIB = -ll CC = gcc -g OBJ = y.tab.o lex.yy.o list.o codegen.o build : $(OBJ) gcc -g -o tinyc $(OBJ) $(LIB) debug : y.tab.c lex.yy.c gcc -DYYDEBUG -o tinyc y.tab.c lex.yy.c $(LIB) list.o : list.c list.h gcc -g -c list.c y.tab.c : tinyc.y $(YACC) tinyc.y lex.yy.c : tinyc.l lex tinyc.l clean : rm -f y.output y.tab.c y.tab.h lex.yy.c a.out tinyc *.s *.o *~ |
   
|
![[http]](/imgs/http.png)
