#
''' TinyC language parser '''

±Û¾´ÀÌ : ÀÌ Çüä <hclee80 atat gmail dotdot com>

ÃÖÃÊ ¼öÁ¤ÀÏ : 2008³â 06¿ù 19ÀÏ ( È帲 )

ÃÖÁ¾ ¼öÁ¤ÀÏ : 2008³â 06¿ù 20ÀÏ ( ¸¼À½ )

----

[[TableOfContents]]

= 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 ÁÖ¸ñÀû °³¹ß¸ñÀûÀº ºü¸¥ Å×½ºÆÃ(¹®ÀÚ¿­Ã³¸®)°ú °£ÆíÇÔÀ» À§ÇÔÀ̾ú´Ù.
= 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, 
== TinyC.l ==
  * [http://www.csg.is.titech.ac.jp/~chiba/lecture/os/tinyc/list.h list.h]

  * [http://www.csg.is.titech.ac.jp/~chiba/lecture/os/tinyc/list.c list.c]

{{{
%{
%{

#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;

%%
}}}
= TinyC BNF =
== TinyC.y ==
 * [http://www.csg.is.titech.ac.jp/~chiba/lecture/os/tinyc/list.h list.h]

 * [http://www.csg.is.titech.ac.jp/~chiba/lecture/os/tinyc/list.c list.c]

{{{
/*
   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);
}
}}}
= Makefile =
 * ÄÚµå»ý¼º ( code generate ) ¼Ò½ºÀÔ´Ï´Ù. ¾Æ·¡ÀÇ »çÀÌÆ®¸¦ Âü°íÇÏ½Ã¸é µË´Ï´Ù.
  *[http://www.csg.is.titech.ac.jp/~chiba/lecture/os/tinyc/codegen.c codegen.c]

  *[http://www.csg.is.titech.ac.jp/~chiba/lecture/os/tinyc/codegen.h codegen.h]

{{{
#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 *~
}}}
= ¿¹Á¦ =
{{{
int foo(int k) {
    return k;
}
}}}
= Âü°í =
 * lex & yacc »ç¿ë¹ý
  * http://wiki.kldp.org/wiki.php/LinuxdocSgml/Lex_Yacc-KLDP

 * À§ ³»¿ëÀÇ ´ëºÎºÐÀº À§ÀÇ »çÀÌÆ®¸¦ Âü°í(copy)À» ¹àÈü´Ï´Ù.  
  * Ref : http://www.csg.is.titech.ac.jp/~chiba/lecture/os/