· KLDP.org · KLDP.net · KLDP Wiki · KLDP BBS ·
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

  • 예약어 : int, return, if, else

  • 기호 : "==", "<", ">", "=", "+", "-", "*", "/", ",", ";", "(", ")", "{", "}", "\\"

  • 정수 : 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
    • (0) 123, 456, 100, 1000, 0, 1
    • (X) 34a, x93, df2, +234, -223

  • 식별자 : a ... z | A ... Z | 0 ... 9
    • (0) abc123def, word2008, HELLOworld, helloWORLD,
    • (X) _main, 2008word,

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. TinyC BNF

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

  • 코드생성 ( code generate ) 소스입니다. 아래의 사이트를 참고하시면 됩니다.
#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 *~

5. 예제

int foo(int k) {
    return k;
}

6. 참고




sponsored by andamiro
sponsored by cdnetworks
sponsored by HP

Valid XHTML 1.0! Valid CSS! powered by MoniWiki
last modified 2008-06-21 01:25:32
Processing time 0.0076 sec