´ÙÀ½ ÀÌÀü Â÷·Ê

1. Lex & Yacc

lex¿Í yacc´Â º§¿¬±¸¼Ò(Bell Laboratories)¿¡¼­ 70³â´ë¿¡ °³¹ßµÇ¾ú°í, ÈÄ¿¡ À̰͵éÀº À¯´Ð½ºÀÇ Ç¥ÁØ À¯Æ¿¸®Æ¼·Î ¼±Á¤ÀÌ µÇ¾î System V¿Í Ãʱâ BSD ¹öÀüÀº ¿ø·¡ÀÇ AT&T ¹öÀüÀÌ ÀÌ¿ëµÇ°í ÀÖÀ¸¸ç »õ·Î¿î BSD¹öÀüÀ¸·Î´Â flex³ª Berkely yaccÀÌ ³ª¿Í ÀÌ¿ëµÇ°í ÀÖ´Ù. ¶Ç FSF(Free Software Foundation)ÀÇ GNU ÇÁ·ÎÁ§Æ®ÀÇ bisonÀ̶ó ºÒ¸®´Â °ÍÀº yacc¿¡ ºñÇØ Á»´õ Çâ»óµÈ ±â´ÉÀ» °¡Á³À¸¸ç BSD¿Í GNU ÇÁ·ÎÁ§Æ®ÀÇ flex(Fast Lexical Analyzer Generator)¿Ü¿¡µµ ¿©·¯ ¿î¿µÃ¼Á¦ÇÏ¿¡¼­ ¿©·¯ °¡Áö ´Ù¸¥ À̸§À¸·Î lex¿Í yaccÀÇ º¯ÇüÀÌ Áö¿øµÇ°í ÀÖ´Ù.

¡Ø MS-DOS³ª OS/2 µîÀÇ OS»ó¿¡¼­µµ ÀÌ¿ëÇÒ ¼ö ÀÖ´Â lex¿Í yacc¸¦ ¸¸µç °÷À¸·Î MKS(Mortice Kern Systems Inc.)°¡ ÀÖ´Ù.

1.1 LexÀÇ »ç¿ë(Lex¸¦ ÀÌ¿ëÇÑ °£´ÜÇÑ ÇÁ·Î±×·¥)

¿¹Á¦) Lex´Â ¾Æ·¡¿Í °°ÀÌ %%¿Í %%»çÀÌ¿¡´Â lex°¡ ±â¼úµÇ°í ±× ÀÌÈÄ¿¡´Â C°¡ ±â¼úµÈ´Ù.

%%
.|\n    ECHO;
%%
 
main()
{
        yylex();
}

À§´Â Ç¥ÁØÀÔ·ÂÀ» Ç¥ÁØÃâ·ÂÀ¸·Î ³»º¸³»´Â °¡Àå °£´ÜÇÑ lex ÇÁ·Î±×·¥À¸·Î Á¤±Ô Ç¥Çö .¿Í \nÀ¸·Î Ç¥½ÃµÇ´Â ¹®ÀÚ°¡ µé¾î¿ÔÀ» ½Ã ±×´ë·Î ¿¡ÄÚÇØÁØ´Ù. (½ÇÁ¦·Î lex¿¡¼­ À§ÀÇ ³»¿ëÀº defaultÀÌ´Ù.)

À¯¿ëÇÑ ´Ù¸¥ °£´ÜÇÑ ¿¹·Î ´ÙÀ½°ú °°Àº

 [\t ]+          ;       # whitespace¸¦ ¹«½ÃÇÑ´Ù
¸¦ %%¿Í %%»çÀÌ¿¡ Æ÷ÇÔ½ÃÅ°¸é ÅÇÀ̶óµç°¡ Çϳª ÀÌ»óÀÇ °ø¹éÀÌ ÀÖ´Â °æ¿ì C¿¡¼­¿Í ¸¶Âù°¡Áö·Î ¾Æ¹« 󸮵µ ¾ÈÇØÁÖ´Â ';'¸¦ »ç¿ëÇÏ¿´±â ¶§¹®¿¡ ¾Æ¹« 󸮵µ ÇÏÁö ¾Ê´Â´Ù.(È­¸é¿¡ °°Àº ¸Þ½ÃÁö¸¦ ¿¡ÄÚÁ¶Â÷µµ ÇÏÁö ¾Ê´Â´Ù.)

À§ÀÇ ¼Ò½º¸¦ simple.lÀ̶ó°í Çϸé(¹ØÁ٠ǥ½Ã´Â »ç¿ëÀÚ ÀÔ·Â)

[ post ] % lex simple.l
                           # lex¸¦ C¾ð¾î·Î, lex.yy.cÆÄÀÏ »ý¼º
[ post ] % cc lex.yy.c -o simple -ll
                           # lex¶óÀ̺귯 Æ÷ÇÔ ÄÄÆÄÀÏ
[ post ] % ./simple < simple.l
                           # simple.lÀ» Ç¥ÁØÀÔ·ÂÀ¸·Î ÇÏ´Â ÇÁ·Î±×·¥ ½ÇÇà
%%
.|\n ECHO;
%%

main()
{
        yylex();
}

À§¿Í °°ÀÌ µÇ¾î UNIXÀÇ cat°ú À¯»çÇÑ ÇÁ·Î±×·¥ÀÌ ¿Ï¼ºµÈ´Ù.(ÀÎÀÚ°¡ ¾ø´Â cat ¸í·ÉÀÇ »ç¿ë½Ã ½ÇÁ¦·Î À§ÀÇ ÇÁ·Î±×·¥°ú °°´Ù)

¡Ø lexÀÇ ±¸¼ºÀº ´ÙÀ½ ¼¼°¡Áö definitions, rules, user code sectionÀ¸·Î ÀÌ·ç¾îÁø´Ù.

definitions 
  # rules¿¡ patternÀ» °£´ÜÇÏ°Ô Çϱâ À§ÇÑ ¼±¾ð°ú Ãʱâ Á¶°Ç
  # CÄÚµå »ðÀԽà %{, }% ±âÈ£¸¦ Ç¥½ÃÇÏ°í »çÀÌ¿¡ ¾µ ¼ö ÀÖÀ½
%%
rules  
  # pattern°ú actionÀ¸·Î ÀÌ·ç¾îÁü
  # CÄÚµå´Â {, }·Î °¨½Î¼­ Ç¥½ÃÇÔ
%%
user code 
  # yylex()ÇÔ¼ö¿Í »ç¿ëÀÚ°¡ ¿øÇÏ´Â C ·çƾÀ¸·Î ÀÌ·ç¾îÁü

¿¹Á¦)

¶Ç %%¿Í %%»çÀÌ¿¡ lex¸¦ ±â¼úÇϱâ ÀÌÀü¿¡ C¸¦ ±â¼úÇϱ⸦ ¿øÇҽÿ¡´Â %{¿Í %}·Î CÀÇ ±â¼úÀ̶ó´Â Ç¥½Ã¸¦ ÇÏ°í ±× »çÀÌ¿¡ ±â¼úÇÒ ¼ö ÀÖ´Ù.

%{
        /*
         * My favorite...
         */
%}
%%

[\t ]+  ;
rain |
rose            { printf("%s!! That is my favorite.\n", yytext); }
love |
story           { printf("%s!! I like a love story. ^_~\n", yytext); }
"potato chip" |
potato |
chip  { printf("%s...!! now and then, I have a potato chip.\n", yytext); }
 
[A-Za-z]+ { printf("%s..., what is that?\n", yytext); }
 
.|\n    { ECHO; }
 
%%

main()
{
        yylex();
}

yytext´Â lex¿¡¼­ »ç¿ëµÇ´Â ÀÔ·Â ÅؽºÆ®¿¡ ´ëÇÑ global character pointerÀÌ´Ù. À§ÀÇ ¼Ò½º¸¦ simple.l°ú °°Àº ¹æ¹ýÀ¸·Î ÄÄÆÄÀÏÇÏ¿© ½ÇÇà½ÃÄÑ º¸¸é

[ post ] % ./favor
potato chip
potato chip...!! now and then, I have a potato chip.
 
love7
love!! I like a love story. ^_~
7
distress
distress...,  what is that?
À§¿Í °°ÀÌ µÈ´Ù.

lovestory
lovestory...,  what is that?

love story
love!! I like a love story. ^_~
story!! I like a love story. ^_~

À§¿¡ ³ªÅ¸³­ ¼öÇà°á°úÀÇ Ãâ·Â°ú °°ÀÌ Ã³¸®Çϱ⸦ ¿øÇÏ´Â ÆÐÅÏ¿¡ ´ëÇؼ­ 󸮰¡ ÀÌ·ç¾îÁø´Ù. love7ÀÇ °æ¿ì¿¡´Â love¿¡ ´ëÇÑ Ã³¸®¸¦ ÇØÁÖ°í 7Àº ¾ËÆĺªÀÌ ¾Æ´Ï¹Ç·Î ´ÙÀ½ÁÙ¿¡ ¿¡ÄÚ°¡ µÈ´Ù. ¶Ç °á°úÁß ¹Ù·Î À§ÀÇ 'love story'´Â love¸¦ ÀνÄÇÏ°í whitespace·Î ºóÄ­À» ÀνÄÇÏ°í ´ÙÀ½¿¡ story¸¦ ÀνÄÇÑ °ÍÀÌ´Ù. µû¶ó¼­ love¿¡ ´ëÇÑ Ã³¸®¿Í ºóÄ­¿¡ ´ëÇÑ ¾Æ¹« 󸮾øÀ½°ú story¿¡ ´ëÇÑ Ã³¸®°¡ °á°ú ³»¿ëÀÌ µÉ °ÍÀÌ´Ù. À§ÀÇ ¿¹·Î¼­ loveyou¶ó°í ÀÔ·ÂÀ» Çß´Ù¸é love ´ÙÀ½¿¡ you¸¦ µû·Î º¸´Â °ÍÀÌ ¾Æ´Ï¶ó ÇϳªÀÇ ÆÐÅÏÀ¸·Î º¸¾Æ distress¿Í °°Àº °á°ú°¡ ³ª¿Ã °ÍÀÓÀ» ¿¹»óÇÒ ¼ö ÀÖ´Ù.

¿¹Á¦) ´ÙÀ½Àº ÀüÀÇ ¿¹Á¦¿Í °°Àº °£´ÜÇÑ Çü½ÄÀ¸·Î ´Ù¸¸ ¼ýÀÚ¿¡ ´ëÇÑ CÀÇ enumÇü½ÄÀ¸·Î ¼±¾ðÇÏ¿© ½Éº¼ Å×À̺íÀÇ °ªÀ» ÀÌ¿ëÇÏ´Â ¿¹¸¦ º¸¿©ÁØ´Ù.

[ post ] % cat number.l
%{
enum {
        NONE = 0,
        ONE,
        TWO,
        THREE,
        FOUR,
        FIVE,
        SIX,
 SEVEN
};

int number;
void action();
%}

%%
oneone  { number = SEVEN; action(); }
one |
ONE  { number = ONE; action(); }
two |
TWO  { number = TWO; action(); }
three |
THREE  { number = THREE; action(); }
four |
FOUR  { number = FOUR; action(); }
five |
FIVE  { number = FIVE; action(); }
six |
SIX  { number = SIX;  action(); }
[a-zA-Z]+ { number = NONE; action(); }
%%

void action()
{
        if (number != NONE)
                printf("%s is %d\n", yytext, number);
        else
                printf("%s?? I don't learn it.\n", yytext);
}
 
main()
{
        yylex();
}

[ post ] % ./number
tow
tow?? I don't learn it.
 
five
five is 5
 
four7
four is 4
7
SIX
SIX is 6
 
ten
ten?? I don't learn it.

oneone
oneone is 7

twotwo
twotwo?? I don't learn it.

two two
two is 2
 two is 2

À§ÀÇ ¸¶Áö¸· 'two two'´Â two¿¡ ´ëÇÑ Ã³¸®¸¦ ÇØÁÖ°í ' 'ÀÇ ºóÄ­Àº ´ÙÀ½ ÁÙ¿¡ ´Ü¼øÈ÷ ¿¡ÄÚÇØÁÖ°í ´ÙÀ½ÁÙ·Î ³Ñ¾î°¡Áö ¾Ê°í ´ÙÀ½ÀÇ two°¡ ó¸®µÇ¾î ³ªÅ¸³­ °á°úÀÌ´Ù. µû¶ó¼­ µÎ ¹ø°ÀÇ two¿¡´Â ¾Õ¿¡ ºóÄ­ÀÌ Çϳª ´õ ÀÖ´Ù. ±×¸®°í oneoneÀ̶ó´Â ÆÐÅÏÀÌ Á¸ÀçÇÒ ¶§¿¡´Â oneÀÇ ÆÐÅÏÀÌ ¾Æ´Ñ oneoneÀÇ ÆÐÅÏÀ» µû¸£´Â °ÍÀº ±ä ¹®ÀÚ¿­ÀÌ ¿ì¼±¼øÀ§¸¦ °¡Áö±â ¶§¹®ÀÌ´Ù.(Á¤±Ô Ç¥Çö½Ä ÂüÁ¶)

¿¹Á¦) ´ÙÀ½Àº lexÀÇ À§¿¡ Á¦½ÃÇÑ °Íº¸´Ù ¾à°£ º¹ÀâÇÑ ¼ýÀÚ¿Í ¿¬»êÀÚ¿Í º¯¼ö¸¦ ÀνÄÇÏ´Â ¿¹Á¦·Î¼­ Á¶±Ý¸¸ °³¼±½ÃÅ°¸é ¿ÏÀüÇÑ °è»ê±â ÇÁ·Î±×·¥ÀÌ µÉ ¼ö ÀÖ´Ù. ÀÌ ¿¹Á¦´Â ´Ü¼øÈ÷ ¼ýÀÚÀÎÁö, ¿¬»êÀÚÀÎÁö, ¿¹¾à¾î ¶Ç´Â º¯¼ö·Î¼­ »ç¿ëµÉ °ªÀÎÁö¸¦ Ãâ·ÂÇÏ¿© ³ªÅ¸³»µµ·Ï ÇÏ´Â ¿¹Á¦ÀÌ´Ù.

%{
/* need this for the call to atof() below */
#include <math.h>
%}

DIGIT    [0-9]  /* ¸ÅÅ©·Î¸¦ Á¤ÀÇÇÑ´Ù */
ID       [a-z][a-z0-9]*

%%
{DIGIT}+  { printf( "An integer: %s (%d)\n", yytext, atoi( yytext ) ); }
{DIGIT}+"."{DIGIT}* { printf( "A float: %s (%g)\n", yytext, atof( yytext ) ); 
}
if|then|begin|end|procedure|function { printf( "A keyword: %s\n", yytext ); }
{ID}   { printf( "An identifier: %s\n", yytext ); }
"+"|"-"|"*"|"/"  { printf( "An operator: %s\n", yytext ); }
"{"[^}\n]*"}"  ; /* { } ¾ÈÀÇ ³»¿ëÀº ÁÖ¼®À¸·Î ¹«½ÃÇÑ´Ù. */
[ \t\n]+  ; /* whitespace¸¦ ¹«½ÃÇÑ´Ù. */
.   printf( "Unrecognized character: %s\n", yytext );
%%

main( argc, argv )
int argc;
char **argv;
{
    ++argv, --argc;  /* skip over program name */
    if ( argc > 0 )
            yyin = fopen( argv[0], "r" );
    else
            yyin = stdin;

    yylex();
}

À§ÀÇ ¿¹¿¡¼­ yyin¿¡ ´ëÇÑ ÁöÁ¤Àº ÀÔ·ÂÀ» Ä¿¸Çµå ¶óÀλóÀÇ Ã¹ÀÎÀÚ°¡ °¡¸®Å°´Â ÆÄÀÏÀÇ ³»¿ëÀ» ó¸®ÇÒ °ÍÀÌÁö È­¸é¿¡¼­ Ç¥ÁØÀÔ·ÂÀ» ¹Þ¾Æ ó¸®ÇÒ °ÍÀÎÁö¿¡ ´ëÇÑ Ã³¸®¸¦ ÇÒ ¼ö ÀÖ°Ô ÇÑ´Ù.

1.2 Lex¿Í YaccÀÇ °ü°è(Lex scanner, Yacc parser)

Lex scanner¿Í Yacc parser´Â °°ÀÌ ±¸ÇöÇÏ´Â °æ¿ì°¡ ´ëºÎºÐÀε¥, Yacc°¡ LexÀÇ »óÀ§¿¡¼­ ±¸ÇöµÈ´Ù. Lex´Â ÀԷ¹®ÀÚ¿­¿¡ ´ëÇÑ ÀÏÂ÷ÀûÀÎ °Ë»öÀ» ÇÏ°í ½ÇÁ¦ÀûÀÎ ºÐ¼®Àº Yacc°¡ ÇÏ´Â °ÍÀÌ´Ù. Yacc´Â ÀԷ¿¡ ´ëÇÑ ÅäÅ«(token)ÀÌ ÇÊ¿äÇϸé, Lex¿¡¼­ Á¦°øÇÏ´Â yylex()ÇÔ¼ö¸¦ È£ÃâÇÏ¿©, ÀÔ·ÂµÈ ÅäÅ«µéÀÇ ¹è¿­ÀÌ ÁÖ¾îÁø ¹®¹ý¿¡ ¸Â´ÂÁö¸¦ üũÇϸ鼭 ±× Á¶°Ç¿¡ ¸Â´Â ½ÇÇàÀ» ÇÏ°Ô µÈ´Ù. ´Ù¸£°Ô Ç¥ÇöÇϸé, Lex¿Í YaccÀ» »ç¿ë µ¿½Ã¿¡ »ç¿ëÇÒ ½Ã¿¡´Â yacc ±â¼úÆÄÀÏÀÇ main()ÇÔ¼ö¿¡¼­ yyparse()ÇÔ¼ö¶ó´Â yacc¿¡ ÀÇÇØ ¸¸µé¾îÁö´Â ±¸¹®ºÐ¼®±â¸¦ ºÎ¸£°í, yyparse()ÇÔ¼ö´Â yylex()¶ó´Â lex°¡ ¸¸µé¾î ÁÖ´Â Çؼ®±â(lexer)¸¦ ÀÌ¿ëÇؼ­ ÀԷ¿­¿¡¼­ 󸮴ÜÀ§ÀÇ ÅäÅ«À» »Ì¾Æ¿À°Ô µÈ´Ù. ¿¹¸¦ µé¾î lex¿¡¼­ '[\t ]+'·Î Ç¥½ÃµÇ¾ú´ø °ø¹éÀ̳ª ÅÇ°¡ °°Àº whitespace¹®ÀÚ´Â ´ëºÎºÐÀÇ ÇÁ·Î±×·¥¿¡¼­ ½ÇÁ¦·Î ó¸®Çϱ⸦ ¿øÄ¡ ¾Ê´Â´Ù. µû¶ó¼­ À§¿Í °°Àº ÀÇ¹Ì ¾ø´Â ¹®ÀÚ³ª ó¸®ÇÒ ÇÊ¿ä°¡ ¾ø´Â ¹®ÀÚ¿­¿¡ ´ëÇؼ­´Â ±× ³»¿ëÀ» parser¿¡°Ô ³Ñ°ÜÁÙ ÇÊ¿ä°¡ ¾ø´Ù. ±×¸®°í ´ÙÀ½¿¡ ¿À´Â ó¸®ÇÒ ¹®ÀÚ°¡ ÀÖÀ» °æ¿ì ±× ³»¿ë(ÅäÅ«)À» yacc parser¿¡°Ô ³Ñ±â¸é ±× 󸮸¦ ÇÒ °ÍÀÌ´Ù. ÀÌ·± °æ¿ì°¡ lex¿Í yacc¸¦ °°ÀÌ ¾²°Ô µÇ´Â °£´ÜÇÑ ¿¹·Î »ý°¢µÉ ¼ö ÀÖÀ» °ÍÀÌ´Ù.

¡Ø MS-DOS³ª OS/2 µîÀÇ OS»ó¿¡¼­µµ ÀÌ¿ëÇÒ ¼ö ÀÖ´Â lex¿Í yacc¸¦ °³¹ßÇß´ø MKS(Mortice Kern Systems Inc.)°¡ WWW°ú °ü·ÃÇÏ¿© NetscapeÀÇ FasttrackÀ̳ª MicrosoftÀÇ IIS¿¡ ´ëÇÑ °Ë»ö ¿£Áø µî¿¡ ÀÌ¿ëÇÒ ¼ö ÀÖ°Ôµµ ÇÏ¿´´Ù.

1.3 YaccÀÇ »ç¿ë

Yacc´Â Yet Another Compiler CompilerÀÇ ¾àÀÚ·Î, ÄÄÆÄÀÏ·¯ »ý¼ºÀ» À§ÇÑ ÇÁ·Î±×·¥À» compiler-generator ¶Ç´Â compiler-compiler¶ó°í ºÎ¸£´Âµ¥, Yacc°¡ BNF¿Í °°Àº Çü½ÄÀÇ rulesÀÇ Ç׸ñµé·ÎºÎÅÍ parser¸¦ ¸¸µé¾î³»´Â ÇÁ·Î±×·¥ÀÌ´Ù.(Yacc ÀÔ·ÂÀº BNF¸¦ °£´ÜÇÏ°Ô ¸¸µç ¹öÀüÀÌ´Ù.) Yacc¸¦ ÀÌ¿ëÇÑ ÇÁ·Î±×·¥µéÀº portable C ÄÄÆÄÀÏ·¯, APL, Pascal, Ratfor, tbl, eqn µîÀÌ ÀÖ´Ù.

´ÙÀ½Àº YaccÀÇ ±¸Á¶À̸ç, Yacc´Â Lex¿Í ºñ½ÁÇÑ ±¸Á¶¸¦ °¡Áö°í Àִµ¥ ½ÇÁ¦·Î´Â Lex°¡ YaccÀÇ ±¸Á¶¸¦ º»µû ¾´ °ÍÀÌ´Ù.

definitions 
   # CÄÚµå »ðÀԽà %{, }% ±âÈ£·Î Ç¥½ÃÇÏ°í »çÀÌ¿¡ ¾µ ¼ö ÀÖÀ½
%%
rules 
   # °¢ ruleÀº "LHS: RHS;"¿Í °°Àº Çü½ÄÀ¸·Î ÀÌ·ç¾îÁü
%%
user code
   # lex¿ÍÀÇ °áÇսà yylex()¸¦ ÀÌ¿ëÇÑ´Ù.

¡Ø LHS´Â left-hand symbolÀÇ ¾àÀÚ·Î ':'ÀÇ ¿ÞÂÊ¿¡ ¿À´Â statement,
   expression°ú °°ÀÌ ¿ÞÂÊ¿¡ ¿À´Â ±âÈ£¸¦ ¸»Çϸç,  RHS´Â right-hand
   symbolÀÇ ¾àÀÚ·Î ':'ÀÇ ¿À¸¥ÂÊ¿¡ ¿À´Â ±âÈ£¸¦ ¸»ÇÑ´Ù.
   °¢ ruleÀÇ ³¡Àº ';'À¸·Î Ç¥½ÃÇÑ´Ù.

¿¹Á¦) yaccÀÇ ÀÌÇظ¦ À§ÇÑ °£´ÜÇÑ ´ÜÁö µ¡¼À°ú »¬¼À¸¸ÀÌ °¡´ÉÇÑ ¾ÆÁÖ °£´ÜÇÑ ±â´ÉÀ» °¡Áø °è»ê±â¸¦ ¸¸µç´Ù°í ÇÒ ¶§ ±×°ÍÀÇ ½ÇÁ¦ ½ÇÇà ¿¹¸¦ º¸ÀÌ¸é ¾Æ·¡¿Í °°´Ù.

[ post ] % cat y_calc.y
%token NAME NUMBER
%%
statement:    NAME '=' expression
            | expression  { printf("= %d\n", $1); }
            ;
expression:   expression '+' NUMBER { $$ = $1 + $3; }
            |   expression '-' NUMBER { $$ = $1 - $3; }
            |   NUMBER  { $$ = $1; }
            ;
[ post ] % cat y_calc.l
%{
#include  "y.tab.h"
extern int  yylval;
%}
%%
[0-9]+ { yylval = atoi(yytext); return NUMBER;  }
[\t ]+ ;
\n return 0;    /* ³í¸®ÀûÀÎ ÀÔ·Â󸮿­ÀÇ ³¡ */
. return  yytext[0];
%%

yacc°¡ lex¸¦ È£ÃâÇϸé(=yylex()¸¦ È£ÃâÇϸé) NAME, NUMBER, ±×¸®°í +, -, =ÀÇ ÇüÅ·ΠÅäÅ«À» ³Ñ°Ü ¹Þ´Â´Ù.(Á¤±Ô½Ä Ç¥Çö¿¡ ÀÇÇؼ­ ' '¾È¿¡ ³õ¿©Áø ¹®ÀÚ´Â ±× ¹®ÀÚ ±× ÀÚü·Î º»´Ù) ¶Ç y_calc.y¸¦ º¸¸é, $1, $2, $3´Â °¢°¢ ÀԷ¹ÞÀº ÅäÅ«ÀÇ À§Ä¡¿¡ ÇØ´çÇÏ´Â °ªÀ» °¡Áö°í ÀÖ°í, ÀÌ °ªÀº yacc¿¡¼­ yylval°¡ type int, Á¤¼ö·Î 󸮰¡ µÇ¾î %d·Î Á¤¼ö¸¦ Ãâ·ÂÇÑ´Ù.(y_calc.l¿¡¼­ »ç¿ëÇÏ°í ÀÖ´Â yylvalÀ̶ó´Â º¯¼ö´Â unionÀ¸·Î ¼±¾ðµÇ¾î ÀÖ´Ù. ÀÌ°ÍÀ» lex¿¡¼­ ¿ÜºÎº¯¼ö·Î ¸¸µé¾î ÀÌ¿ëÇÏ¿© yyparse()ÇÔ¼ö¸¦ È£ÃâÇÏ´Â yacc°¡ ó¸®Çϵµ·Ï °ªÀ» Àü´ÞÇÏ°Ô µÇ´Â °ÍÀÓ) ±×¸®°í $2ÀÇ °æ¿ì¿¡ ÇØ´çÇÏ´Â °ÍÀº ¿¬»êÀÚ¿¡ ÇØ´çÇÏ´Â ¹®ÀÚ°¡ µé¾î°¡±â ¶§¹®¿¡ expressionÀÇ RHSÀÇ { } ¾È¿¡¼­ +, ¿Í -·Î ÀÌ¿ëÇÏ°í ÀÖ´Ù. ±×¸®°í $$´Â LHSÀÇ °ª, expressionÀÇ °ªÀÌ µÈ´Ù.

yacc¸¦ ½ÇÁ¦·Î »ç¿ëÇϱâ À§Çؼ­ example.y¶ó´Â yaccÆÄÀÏÀÌ ÀÛ¼ºµÇ¸é yacc¸¦ ÀÌ¿ëÇÏ¿©, yyparse()¶ó´Â ±¸¹®ºÐ¼®±â ÇÔ¼ö¸¦ °¡Áø y.tab.c¶ó´Â C¾ð¾î È­ÀÏÀ» ¸¸µé±â À§Çؼ­ 'yacc example.y'¸¦ ½ÇÇàÇÏ°í CÄÄÆÄÀÏ·¯¸¦ ÀÌ¿ëÇؼ­, y.tab.o¶ó´Â ¿ÀºêÁ§Æ® È­ÀÏÀ» ¸¸µç ÈÄ¿¡, ÄÚµå»ý¼º±â³ª ´Ù¸¥ ÇÁ·Î±×·¥°ú ¸µÅ©ÇÏ¿© ¿øÇÏ´Â °á°ú¸¦ ¸¸µç´Ù. À§ÀÇ ÇÁ·Î±×·¥(y_calc.y¿Í y_calc.l)À» ÄÄÆÄÀÏÇÏ¿© ½ÇÇàÇÑ °á°ú´Â ¾Æ·¡¿Í °°´Ù.

[ post ] % yacc -d y_calc.y /* y.tab.h¿Í y.tab.c°¡ ¸¸µé¾îÁø´Ù */
[ post ] % lex y_calc.l
[ post ] % cc -o y_calc y.tab.c lex.yy.c -ly -ll
[ post ] % ./y_calc
1+101
= 102
[ post ] % ./y_calc
1000-300+200+100
= 1000

¿©±â¼­´Â y.tab.h¸¦ lexer¿¡¼­ includeÇϱ⠶§¹®¿¡, yacc¿¡¼­ ¸¸µé¾îÁÖ±â À§ÇØ -d ½ºÀ§Ä¡¸¦ ÀÌ¿ëÇÏ¿´´Ù. lex¸¦ ÀÌ¿ëÇÏ¿©, lex.yy.c¸¦ ¸¸µé°í, yaccÀ» ÀÌ¿ëÇÏ¿©, y.tab.c¸¦ ¸¸µé¾î¼­ liby.a¿Í libl.a¸¦ ¸µÅ©ÇÏ¿© ¿øÇÏ´Â ½ÇÇàÈ­ÀÏÀ» ¸¸µé°Ô µÈ´Ù.

¡Ø Yacc¿¡¼­ÀÇ ¸ðÈ£¼º - ´ÙÀ½°ú °°Àº ¿¹Á¦¸¦ »ý°¢Çغ¸ÀÚ.

expression : expression '+' expression
    |        expression '-' expression
    |        expression '*' expression
    |        expression '/' expression
    |        '-' expression
    |        '(' expression ')'
    |        NUMBER
À§ÀÇ yacc ¹®¹ýÀ» °¡Áö°í, 2+3*4¸¦ ÆĽÌÇÏ·Á°í Çϸé, ±×¸²°ú °°ÀÌ, (2+3)*4·Î ÆĽºÆ®¸®¸¦ ±¸¼ºÇÒ ¼öµµ ÀÖ°í, 2+(3*4)·Î ó¸®µÉ ¼öµµ ÀÖ°Ô µÇ¾î, ¹®Á¦°¡ »ý±â°Ô µÈ´Ù. ¶ÇÇÑ 2-3-4-5ÀÇ °æ¿ì¿¡µµ, 2-(3-(4-5))ÀÎÁö, (2-3)-(4-5)ÀÎÁö ¹®Á¦°¡ »ý±â°Ô µÈ´Ù µû¶ó¼­ ¾Ö¸ÅÇÏÁö ¾ÊÀº ¹®¹ýÀ¸·Î ¹Ù²Ü ¼ö°¡ Àִµ¥, ¿ì¼±¼øÀ§¿Í °áÇÕ¹ýÄ¢À» ¹®¹ý¿¡ °¨¾ÈÇÏ´Â ¹æ¹ýÀ¸·Î ÇÑ°¡Áö´Â À§ÀÇ ¹®Á¦°¡ »ý±âÁö ¾Ê°Ô ¾²´Â °ÍÀÌ°í, ´Ù¸¥ ÇÑ°¡Áö´Â ÀÌ·± ¹®Á¦¸¦ ÇØ°áÇϱâ À§ÇÏ¿© yacc¿¡¼­ ÁöÁ¤µÇ¾î ÀÖ´Â »ç¿ëÇÏ´Â ¸í·ÉÀ» ÀÌ¿ëÇÏ¿©(%prec, %left, %right, ...) ¿ì¼±¼øÀ§¿Í °áÇÕ¹ýÄ¢À» ÁöÁ¤ÇÏ´Â °ÍÀÌ´Ù. À̸¦ ÇØ°áÇÏ´Â ¹æ¹ý¿¡´Â ¹®¹ýÀ» ¹Ù²Ù´Â °æ¿ìÀÇ ±âº»ÀûÀÎ ¾ÆÀ̵ð¾î´Â ¿ì¼±¼øÀ§¸¦ ³ô°Ô °¡Áö´Â ¿¬»êÀÚ¿¡ ´ëÇؼ­´Â LHS¿¡ ¿À°Ô ¸¸µé¾î¼­, ¹Ì¸® reduceµÇµµ·Ï ÇÏ´Â °ÍÀ̸ç, °áÇÕ¹ýÄ¢¿¡ ´ëÇؼ­µµ ¸¶Âù°¡Áö·Î ¹®Á¦¸¦ ÇØ°áÇÒ ¼ö ÀÖ´Ù. ¾ÕÀÇ ¹®¹ýÀ» ¹Ù²Ù¾î¼­ shift/reduce conflict¸¦ ÇØ°áÇÑ °ÍÀº ¾Æ·¡¿Í °°´Ù.
expression: expression '+' mulexp
  |   expression '-' mulexp
  |   mulexp
  ;
mulexp : mulexp '*' primary
  |   mulexp '/' primary
  |   primary
  ;
primary:  '(' expression ')'
  |   '-' primary
  |   NUMBER
  ;
¹®Á¦¸¦ ÇØ°áÇÏ´Â ¶Ç´Ù¸¥ ¹æ¹ýÀ¸·Î yacc¿¡¼­ Á¦°øÇÏ´Â ¸í·É¾î¸¦ ÀÌ¿ëÇÏ´Â ¹æ¹ýÀ¸·Î ÀÌ ¸í·É¾î¸¦ ÀÌ¿ëÇؼ­, ¿ì¼±¼øÀ§ ¹× °áÇÕ¹ýÄ¢À» Á¦°øÇÒ ¼ö ÀÖ°Ô µÈ´Ù. ¸î°¡Áö À¯¿ëÇÑ ¸í·ÉÀÇ ¿¹¸¦ µé¾îº¸¸é ´ÙÀ½°ú °°´Ù.

%left  '+' '-'
%left  '*' '/'
%right '='
%nonassoc  UMINUS /* unary operatorÀÇ Á¤ÀÇ·Î °áÇÕ¹ýÄ¢ÀÌ Àû¿ëÀÌ ¾ÈµÈ´Ù.  */

À§¿Í °°ÀÌ ±â¼úÇÏ°Ô µÇ¸é, + - * / = ÀÇ ¿ì¼±¼øÀ§´Â + - °¡ °¡Àå ³·°í, * /°¡ ±×°Íº¸´Ù ³ô°í, ´ëÀÔ¿¬»êÀÚ = ÀÌ ³ô°í, ºÎÈ£¿¬»êÀÚÀÎ -°¡ °¡Àå ³ôÀº ¿ì¼±¼øÀ§¸¦ °¡Áø´Ù´Â °ÍÀ» º¸¿©ÁÖ°í ÀÖ´Ù. ¶ÇÇÑ +³ª -, *, /´Â ¿ÞÂÊÀ¸·Î °áÇÕ¹ýÄ¢À» °¡Áö°í, ´ëÀÔ¿¬»êÀÚ =´Â ¿ìÃøÀ¸·Î °áÇÕ¹ýÄ¢À» µû¸¥´Ù.

%token NAME NUMBER
%left '-' '+'
%left '*' '/'
%nonassoc UMINUS
expression:     expression '+' expression
         |      expression '-' expression
         |      expression '*' expression
         |      expression '/' expression
         |      '-' expression %prec UMINUS
         |      '(' expression ')'
         |      NUMBER
         ;
À§¿¡¼­ Áß°£¿¡ º¸ÀÌ´Â %prec UMINUS´Â '-' expression°ú °°Àº ¹®ÀÚ¿­À» ÆĽÌÇÏ°Ô µÇ¸é -¿¡ ´ëÇؼ­´Â UMINUS·Î ÁöÁ¤µÈ ¿ì¼±¼øÀ§¸¦ »ç¿ëÇ϶ó´Â ÀǹÌÀÌ´Ù. µû¶ó¼­, ¸ðÈ£ÇÑ ¹®¹ý¿¡¼­ º¸ÀÌ´Â shift/reduce conflict°¡ »ý±æ¶§, ¿ì¼±¼øÀ§¿Í °áÇÕ¹ýÄ¢À» Àû¿ëÇÔÀ¸·Î½á, ½±°Ô ÇØ°áÇÒ ¼ö°¡ ÀÖ°Ô µÈ´Ù.

¡Ø ¶Ç´Ù¸¥ YaccÀÇ ¸ðÈ£¼º, LALR(1)ÀÌ ¾Æ´Ñ ¹®¹ýÀÇ ¿¹ ´ÙÀ½°ú °°Àº ¹®¹ýÀ» »ìÆ캸ÀÚ.

phrase: cart_animal AND CART
        | work_animal  AND PLOW
cart_animal: HORSE | GOAT
work_animal: HORSE | OX

À§ÀÇ ¿¹´Â µé¾î, HORSE AND CART ¶ó´Â ÀÔ·ÂÀÌ µé¾î¿ÔÀ» °æ¿ì¿¡, HORSE¸¦ cart_animal·Î reduceÇØ¾ß ÇÏ´ÂÁö, work_animal·Î reduceÇØ¾ß ÇÏ´ÂÁö ¾Ë·Á¸é, HORSE¸¦ º¸°í, AND¸¦ º¸°í, CART¸¦ º¸°í ³ª¼­¾ß ¾Ë ¼ö°¡ ÀÖ°Ô µÈ´Ù. Yacc°¡ ó¸®ÇÒ ¼ö ¾ø´Â ÀÌ ¹®Á¦´Â, yacc°¡ ±¸¹® ºÐ¼®À» Çϴµ¥ »ç¿ëÇÏ´Â ±â¼úÀº LALR(1)Àε¥ LALRÀº LookAhead Left Recursive, Áï, ÇÑ °³ÀÇ ´Ü¾î¸¦ ´õ º¸°í ¸Â´Â ¹®¹ýÀ» °áÁ¤ÇÒ ¼ö ÀÖ´Ù´Â °ÍÀ̱⠶§¹®ÀÌ´Ù. µû¶ó¼­, HORSE ´ÙÀ½¿¡ 2°³ÀÇ ´Ü¾î¸¦ ´õ Àоî¾ß ÇÏ´Â °æ¿ìÀε¥, ÀÌ °æ¿ì LALR(2)¹®¹ýÀ̸ç, yacc´Â ÇÑ °³ÀÇ lookahead¸¸À» º¼ ¼ö ÀÖ´Â ¹®¹ýÀÎ LALR(1)¿¡ ÇØ´çÇϹǷÎ, À§ÀÇ ¹®¹ýÀº ó¸®ÇÒ ¼ö ¾ø´Ù. µû¶ó¼­ À§ÀÇ ¹®¹ýÀº ´ÙÀ½°ú °°ÀÌ LALR(1)¹®¹ýÀ¸·Î ¹Ù²Ù¾î ÁÖ¾î¾ß ÇÑ´Ù.

phrase -> cart_animal  CART
         | work_animal  PLOW
cart_animal  -> HORSE | GOAT
work_animal -> HORSE | OX

À§ÀÇ ¹®¹ýÀº HORSE¸¦ º¸°í, ¹Ù·Î µÚÀÇ ÇÑ ´Ü¾îÀÎ CART¸¸À» º¸¸é cart_animal·Î reduceÇÒÁö, work_animal·Î reduceÇؾßÇÒÁö¸¦ ¾Ë°Ô µÈ´Ù.

¿¹Á¦) ´ÙÀ½°ú °°ÀÌ º¯¼ö 󸮰¡ °¡´ÉÇÑ Å¹»ó °è»ê±â¸¦ ±¸ÇöÇÏ·Á°í ÇÑ´Ù.

a = 2.3 + 3.5
b = 3.5 + 5.2
c = a + b - 1
c
= 13.5

À§¿Í °°Àº ±â´ÉÀ» ¼öÇàÇÏ·Á¸é ±âº»ÀûÀ¸·Î ±â¾ïÀå¼Ò·Î »ç¿ëµÉ ¼ö ÀÖ´Â ½Éº¼Å×À̺íÀ» À¯ÁöÇÏ°í, ½Éº¼Å×ÀÌºí¿¡ º¯¼öÀÇ À̸§°ú °ªÀ» À¯ÁöÇØ¾ß ÇÑ´Ù. ´ÙÀ½Àº º¯¼öÀ̸§ÀÌ ¿µ¹®ÀÇ ¾ËÆĺª¸¸À» °¡Áø´Ù°í °¡Á¤ÇÑ ±×·¯ÇÑ ¿¹¸¦ º¸ÀÎ °ÍÀÌ´Ù.

[ post ] % cat variable.y
%{
double vbltable[26];  /* doubleÇüÀÇ ±â¾ïÀå¼Ò ¹è¿­ */
%}
%union  {
                double dval;
                int vblno;
        }
%token    <vblno> NAME
%token    <dval> NUMBER
%left '-' '+'
%left '*' '/'
%nonassoc UMINUS
%type <dval> expression
%%
statement_list: statement '\n'
          |         statement_list statement '\n'
          ;
statement:        NAME '=' expression  { vbltable[$1] = $3; }
          |   expression                 { printf("= %g\n",$1); }
          ;
expression: expression '+' expression  { $$ = $1 + $3;  }
          | expression '-' expression  { $$ = $1 - $3;  }
          | expression '*' expression  { $$ = $1 * $3;  }
          | expression '/' expression
                    {  if($3 == 0.0)
                             yyerror("divide by zero");
                       else   $$ = $1 /$3;
                    }
           |  '-'expression  %prec UMINUS   { $$ = -$2; }
           |  '('expression')'     { $$ = $2; }
           |       NUMBER
           |       NAME       { $$ = vbltable[$1]; }
           ;
%%
main()
{
    yyparse();
}

º¯¼öÀ̸§ÀÌ ¿µ¹®ÀÇ ¾ËÆĺª¸¸À» °¡Áø 26°³ÀÇ ¿ø¼Ò¸¦ °¡Áø ¹è¿­ÀÎ vbltable[26]À» ¼±¾ðÇؼ­ º¯¼öÀÇ °ªÀ» À¯ÁöÇϵµ·Ï ÇÑ´Ù. À§¿¡¼­ %unionÀº lexer¿¡¼­ ¹Þ´Â tokenÀÎ NAME°ú NUMBER¸¦ NAMEÀº vbltable[]ÀÇ ÇÑ À妽º¸¦ ÁöĪÇÏ°Ô ÇÏ¿©, 0ºÎÅÍ 25ÀÇ °ªÀ» °¡Áö°Ô ÇÏ´Â ¹Ý¸é¿¡, NUMBER´Â ½Ç¼öÀÇ °ªÀ» °¡Áöµµ·Ï ÇÑ´Ù. µû¶ó¼­, °°Àº tokenÀ̶ó°í ÇÏ´õ¶óµµ, °¡Áö´Â °ªÀÌ ´Ù¸£°Ô µÇ´Âµ¥, °¡Áö´Â °ªÀº ´Þ¶óµµ, ÇÑ ¼ø°£¿¡´Â ¿ÀÁ÷ ÇÑ °³ÀÇ token¸¸ÀÌ ÀνĵDZ⠶§¹®¿¡, °°Àº ±â¾ïÀå¼Ò¸¦ À¯ÁöÇϵµ·Ï À§¿Í °°ÀÌ %unionÀ¸·Î ¼±¾ðÇÏ°Ô µÈ´Ù. ±×¸®°í %union¹®Àº ½ÇÁ¦, y.tab.c¾È¿¡¼­ CÀÇ unionÀ¸·Î º¯È¯µÇ¾î 󸮵ȴÙ. ``%type <dval> expression'' ¹®ÀåÀº ¿ª½Ã, token»ÓÀÌ ¾Æ´Ï¶ó tokenÀ¸·Î Á¤ÇØÁöÁö ¾ÊÀº LHSÀÇ °æ¿ì¿¡µµ ¾Ë¸ÂÀº ŸÀÔÀ¸·Î ¼³Á¤ÀÌ °¡´ÉÇÏ´Ù´Â °ÍÀ» º¸¿©ÁØ´Ù. ``NAME '=' expression { vbltable[$1] = $3; }''ÀÇ ¹®ÀåÀº ¿ÞÆíÀÇ ¹®¹ýÀ¸·Î reduceµÉ ¶§ ¿À¸¥ÆíÀÇ actionºÎ¸¦ ½ÇÇàÇÏ°Ô µÇ´Âµ¥, Àǹ̴ $1 Áï NAMEÀÇ °ª(0ºÎÅÍ 25»çÀÌÀÇ °ªÀ» yylex()·ÎºÎÅÍ ¹Þ¾Ò´Ù)À¸·Î vbltableÀÇ ÇÑ ¿ø¼Ò¿¡ $3 Áï expressionÀÇ °ªÀ» ³Ö´Â °ÍÀÌ´Ù. ¿¹¸¦ µé¾î x = 2.0 + 3.2À̾úÀ¸¸é x¿¡ ´ëÇÑ $1Àº 23ÀÌ µÇ¸ç vbltable[23] = 5.2ÀÇ Àǹ̸¦ °¡Áø´Ù. ``'-' expression %prec UMINUS { $$ = -$2; }''ÀÇ ¹®ÀåÀº -2¿Í °°Àº ´Ü¾î°¡ µé¾î¿ÔÀ» ¶§ -´Â 2-3¿¡¼­ÀÇ -°¡ ¾Æ´Ï¶ó %prec¿¡ ÀÇÇØ ºÎÈ£¿¬»êÀÚÀÎ -·Î ¿ì¼± ¼øÀ§¸¦ µÎ¾î ¿¬»êÀÌ ÀÌ·ç¾îÁüÀ» ÀǹÌÇÑ´Ù. ``NAME { $$ = vbltable[$1]; }''Àº ¸¸¾à y¶ó´Â º¯¼öÀ̸§ÀÌ ÁÖ¾îÁö¸é $1ÀÇ °ªÀÌ 0ºÎÅÍ 25»çÀÌÀÇ °ª Áß¿¡¼­ 24¹ø° ÇØ´çµÇ¹Ç·Î vbltable[24]ÀÇ °ªÀ» ½ºÅÿ¡ ÀúÀåÇÏ°Ô µÈ´Ù.

[ post ] % cat variable.l
%{
#include "y.tab.h"
#include <math.h>

extern double vbltable[26];
%}
%%
([0-9]+|([0-9]*\.[0-9]+)([eE][-+]?[0-9]+)?)  {
                  yylval.dval = atof(yytext); return NUMBER;
                }
[\t]   ;        /* ignore white space */
[a-z]    {      yylval.vblno = yytext[0] - 'a'; return NAME; }
"$"      { return 0; }    /*  end of input  */
\n       |
.                return yytext[0];
%%

À§ÀÇ lexÈ­ÀÏÀ» º¸¸é, yylval.dval·Î Ç¥ÇöÇÑ °ÍÀÌ ÀÖ´Â µ¥, ÀÌ°ÍÀº yylval°¡ unionŸÀÔÀ¸·Î ¼±¾ðÀÌ µÇ¾îÀÖÀ¸¹Ç·Î, NUMBERÇüÀ̸é, °ªÀ» ³ÖÀ»¶§¿¡µµ, yylval.dval½ÄÀ¸·Î ÇÏ¿©, ³ÖÀ¸¶ó´Â °ÍÀ» ³ªÅ¸³½´Ù. ¶ÇÇÑ º¯¼ö°¡ ¿µ¹® ¾ËÆĺª¸¸À» °¡Á¤Çϱ⠶§¹®¿¡, ´Ü¼øÈ÷ 0ºÎÅÍ 25»çÀÌÀÇ °ªÀ¸·Î vbltableÀ» À妽ÌÇÏ°Ô µÇ´Âµ¥, lex¿¡¼­ÀÇ yylval.vblno = yytext[0] - 'a'´Â yylval¿¡ 0ºÎÅÍ 25»çÀÌÀÇ °ªÀ» ³Ö°Ô µÈ´Ù. À§ÀÇ ÇÁ·Î±×·¥(variable.l °ú variable.y)À» ÄÄÆÄÀÏÇÏ¿© ½ÇÇàÇÑ °á°ú´Â ¾Æ·¡¿Í °°´Ù.

[ post ] % yacc -d variable.y
[ post ] % lex variable.l
[ post ] % cc -o variable y.tab.c lex.yy.c -ll
[ post ] % ./variable
7.5+3.5
= 10
200/20+20/2
= 20
x=20/2
y=x+1
y
= 11

1.4 Lex¿Í YaccÀÇ ÀÌ¿ë

´ÙÀ½Àº ½ÇÁ¦·Î Lex¿Í Yacc¸¦ µ¿½Ã¿¡ °áÇÕÇÏ¿© »ç¿ëÇÑ ¿¹ÀÌ´Ù.

[ post ] % cat example.h
#define NOUN 257
#define PRONOUN 258
#define  VERB  259
#define  ADVERB  260
#define  ADJECTIVE  261
#define  PREPOSITION   262
#define  CONJUNCTION 263
[ post ] % cat example.l
%{
/*
 * build a lexical analyzer to be used by a high-level parser.
 */
#include "example.h" /* token codes from the parser */
#define LOOKUP 0 /* default - not a defined word type.  */
int state;

%}
%%

\n { state = LOOKUP; }
\.\n { state = LOOKUP; return 0; }  /*  ³í¸®ÀûÀΠ󸮴ÜÀ§ÀÇ ³¡À» ÀÇ¹Ì */
^verb { state = VERB;  }
^adj { state = ADJECTIVE; }
^adv { state = ADVERB; }
^noun { state = NOUN; }
^prep { state = PREPOSITION; }
^pron { state = PRONOUN; }
^conj { state = CONJUNCTION; }
[a-zA-Z]+ {
            if (state != LOOKUP) {
                  add_word(state, yytext);
            } else {
                  switch(lookup_word(yytext))
                  {
                      case VERB  : return(VERB);
                      case ADJECTIVE : return(ADJECTIVE);
                      case ADVERB  : return(ADVERB);
                      case NOUN  : return(NOUN);
                      case PREPOSITION : return(PREPOSITION);
                      case PRONOUN : return(PRONOUN);
                      case CONJUNCTION : return(CONJUNCTION);
                      default   : printf("%s: don't reconize\n", yytext);
                                           /*  don't return just ignore it  */
                  }
            }
          }
.   ;

%%
/* ÇÑ ´Ü¾î ŸÀÌÇÁ¿¡ ´ëÇÏ¿© ´Ü¾î ¿©·¯°³¸¦ °®±â À§ÇÑ ±¸Á¶Ã¼ ¼±¾ð */
struct word {
        char *word_name;
        int  word_type;
        struct word *next;
};
struct word *word_list;
extern void *malloc();

int add_word(type, word)
int type; char *word;
{
        struct word *wp;
        if (lookup_word(word) != LOOKUP) {
                printf("!!! warning: word %s already defined \n",word);
                return 0;
        }

        /*  word not there, allocate a new entry and link it on the list */
        wp = (struct word *) malloc(sizeof(struct word));
        wp->next = word_list;
        /* have to copy the word itself as well */

        wp->word_name = (char *)malloc(strlen(word)+1);
        strcpy(wp->word_name, word);
        wp->word_type = type;
        word_list = wp;
        return 1;    /* it worked */
}

int lookup_word(word)
char *word;
{
        struct word *wp = word_list;
        /*  search down the list looking for the word  */
        for (; wp; wp = wp->next) {
                if (strcmp(wp->word_name, word) == 0)
                        return wp->word_type;
        }
        return LOOKUP; /*  not found  */
}

verb, noun µî¿¡ ´ëÇؼ­ state¸¦ ÀÌ¿ëÇÏ¿©, ÁÙÀÌ ³¡³ª±â Àü±îÁö ³ª¿À´Â ´Ü¾îµéÀ» ½Éº¼Å×ÀÌºí¿¡ µî·ÏÇÏ°Ô µÇ´Â °ÍÀÌ add_word()ÇÔ¼öÀÌ°í ±× µî·ÏµÈ ´Ü¾î¸¦ »ìÆ캸´Â ÇÔ¼ö°¡ lookup_word()ÀÌ´Ù.

´ÙÀ½Àº yaccÈ­ÀÏ example.yÈ­ÀÏÀÇ ³»¿ëÀÌ´Ù.

[ post ] % cat example.y
%{
 /*
  A lexer for basic grammar to use for recognizing english sentences.
  */
#include <stdio.h>
%}
%token  NOUN PRONOUN VERB ADVERB ADJECTIVE PREPOSITION CONJUNCTION
%%
sentence: subject VERB object { printf("Sentence is valid.\n"); }
  ;
subject:  NOUN
  | PRONOUN
  ;
object:  NOUN
  ;
%%

extern FILE *yyin;
main()
{
  while(!feof(yyin)) {
     yyparse();
  }
}

yyerror(s)
char *s;
{
  fprintf(stderr,"%s\n",s);
}

À§ÀÇ yaccÈ­ÀÏ¿¡¼­ "%token NOUN PRONOUN VERB ADVERB ADJECTIVE PREPOSITION CONJUNCTION"¹®Àº ÀÔ·Â ±âº»´ÜÀ§ÀÎ ÅäÅ«À¸·Î ó¸®ÇÑ´Ù´Â °ÍÀ» ÀǹÌÇÏ°í ¿©±â¼­´Â lexer¿¡°Ô¼­ ³Ñ°Ü¹Þ´Â °ÍÀÌ µÈ´Ù. Áï, yyparse()°¡ ¸Å¹ø yylex()¸¦ ºÎ¸£¸é, ±× °á°ú´Â NOUNÀ̳ª PRONOUN µîÀÇ tokenÀ¸·Î ¿À°Ô µÇ´Â °ÍÀÌ´Ù. µû¶ó¼­, yyparse´Â ±×·¯ÇÑ ÅäÅ«ÀÇ ³ª¿­ÀÌ ¹®¹ý¿¡ ¸Â´ÂÁö¸¦ ºÐ¼®ÇÏ¿©, ¸ÂÀ¸¸é ¿·¿¡ ÁÖ¾îÁø, actionÀÎ C¾ð¾î ¹®ÀåÀ» ¼öÇàÇÏ°Ô µÈ´Ù. yaccÀÇ ÀÔ·ÂÀº yyinÀ̶ó´Â È­ÀÏ¿¡¼­ µé¾î¿À°Ô µÇ°í, Ãâ·ÂÀº yyoutÀ̶ó´Â È­ÀÏ·Î ¾²°Ô µÈ´Ù. ±âº»ÀûÀ¸·Î´Â yyin°ú yyoutÀº stdin°ú stdout, Áï Ç¥ÁØ ÀÔ,Ãâ·ÂÀ¸·Î ¼³Á¤ÀÌ µÇ¾îÀÖÀ¸¹Ç·Î, Å°º¸µå¿Í È­¸éÀ» ÅëÇØ ÀÔÃâ·ÂÀÌ ÀÌ·ç¾îÁö°Ô µÈ´Ù. À̸¦ ¹Ù²Ù¾îÁÖ´Â °ÍÀº ¾Õ¿¡¼­ Á¦½ÃÇÏ¿´¾ú´Ù. yyparse()´Â yacc°¡ ¸¸µé¾îÁÖ´Â ±¸¹®ºÐ¼®±â(parser)ÀÌ°í, yyerror()´Â ±¸¹®ºÐ¼® Áß¿¡ ¿¡·¯°¡ »ý°åÀ» ¶§ ºÎ¸£´Â ÇÔ¼öÀÌ´Ù. ´ÙÀ½Àº ¾Õ¿¡¼­ ¼³¸íÇÑ lexÈ­ÀÏ(example.l)°ú yaccÈ­ÀÏ(example.y)À» ½ÇÁ¦ ÄÄÆÄÀÏÇÏ¿© ¼öÇàÇÑ °á°úÀÌ´Ù.

[ post ] % lex example.l
[ post ] % yacc example.y
[ post ] % cc -o example lex.yy.c y.tab.c -ll
[ post ] % ./example
noun pig fish I
verb run am are
verb outrun
pig outrun fish
Sentence is valid.
noun you
you are pig
Sentence is valid.
pig are
syntax error
syntax error
pig outrun fish.
Sentence is valid.
verb am
!!! warning: word am already defined 
I am fish
Sentence is valid.
i am fish
i: don't reconize
syntax error

1.5 MakefileÀÇ ÀÌ¿ë

ÄÄÆÄÀÏ ÀýÂ÷¸¦ °£¼ÒÈ­ÇÏ°í, ÇÁ·Î±×·¥ º¸¼ö¸¦ ½±°Ô Çϱâ À§Çؼ­ ´ÙÀ½°ú °°ÀÌ makefile¸¦ Á¤ÀÇÇÏ¿© Æí¸®ÇÏ°Ô ÄÄÆÄÀÏÀ» ¼öÇàÇÒ ¼ö ÀÖ´Ù.

[ post ] % cat makefile
CC = cc
LIBS = -ll
LEX = lex
YACC = yacc
CFLAGS = -DYYDEBUG=1
all: speech
speech: y.tab.c lex.yy.c
                $(CC) -o speech y.tab.c lex.yy.c $(LIBS)
y.tab.c: example.y
                $(YACC) -d example.y
lex.yy.c : exaple.l
                $(LEX) example-07.l
[ post ] % make
cc -o speech y.tab.c lex.yy.c -ll


´ÙÀ½ ÀÌÀü Â÷·Ê