· 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. 참고


ID
Password
Join
He who invents adages for others to peruse takes along rowboat when going on cruise.


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.0072 sec