· 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
The luck that is ordained for you will be coveted by others.


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