..ᠭ쥢, ..祭   "᭮ 樨"  ᥭ,1991

                   ਠ  樨 7. YACC

   ணࠬ YACC (Yet Another Compiler Compiler) ।祭a
 ஥ ᨭ⠪᪮  ⥪⭮-᢮
 몠. 㥬  뢠   ࠬ⨪ 
,  ଥ  -  ().  ⮬  ࠡ
YACC'a  ணࠬ  , ॠ 室騩 LALR(1)
ᯮ⥫.

                    YACC-ணࠬ

   YACC-ணࠬ ⮨   ᥪ権, ࠧ  ᨬ
%% - ᥪ樨 ᠭ,  ᥪ樨  ࠢ,    ன  뢠
ࠬ⨪,  ᥪ樨 ணࠬ, ᮤন ன   
  室 䠩. ਬ ⥩襩 ணࠬ  YACC'e:

        %token name
        %start e
        %%
        e : e '+' m | e '-' m | m ;
        m : m '*' t | m '/' t | t ;
        t : name | '(' e ')' ;
        %%

    ࠢ ᮤন ଠ  ⮬,  ᨬ name 
 ᥬ (ନ) ࠬ⨪,  ᨬ e  -    
砫 ନ.
   ࠬ⨪ ᠭ  ࠧ - 䨪 
 ନ  ନ, ᨬ ⠭ ⨯ '+' '-'
- ନ.  : | ; - ਭ     
"  ।", ""  " ࠢ" ᮮ⢥⢥.

                     襭 䫨⮢

   ᠭ ࠬ⨪ (  ᢮⢮ LALR(1) -  
ࠦ)   䬥᪨ ,  ஬  ਮ
 '*'  '/'  ਮ '+'  '-', a  樨 
樠⨢.  㪠  ᢮ 몠  ࠬ⨪ 
 ⥫ ନ m,  t. 㣠  ࠬ⨪  ⮣
몠:

e : e '+' e | e '-' e | e '*' e | e '/' e | '(' e ')' | name ;

 筠 (, ᫥⥫쭮,  LALR(1)). ⪠ ਬ
YACC    ࠬ⨪  ਢ    ᫥
(16) ࠧ襭 䫨⠬ ⨯ ᤢ/ᢥ⪠ (shift/reduce)
 ஥ ⮬. ᫨ ᬮ 䫨    
஡, ,    砥  筮 
 ᤢ  ᢥ⪮, ᭮뢠  ਮ 権
 浪 믮 ࠢਮ 権 ᫥  ࠢ.
(筮 ⮬  ୮ ।⢮).
   YACC   ࠬ⨪ ଠ樥 ⠪  த
  ᪮䫨 ᯮ⥫:

        %token name
        %left '+' '-'
        %left '*' '/'
        %%
        e : e '+' e | e '-' e | e '*' e | e '/' e
          | '(' e ')' | name ;
        %%

   । %left, %right  %nonassoc  ᥪ樨 ᠭ 
뢠 ᥬ ᫥   ᨬ  ਮ
  ᮮ⢥饥 祭 樠⨢. (⢨ 
樠⨢ 砥 ⨬ ࠦ  a @ b @ c)
ਮ 㢥稢 ᢥ      ।
.
   LALR(1)-䫨 ᤢ/ᢥ⪠  ᢥ⪠/ᢥ⪠ ࠧ
 롮஬  ਮ⭮ ⢨. ਮ ᤢ 
 ਮ 뢠  ᥬ.  ਮ  ᢥ⪨  ࠢ
ਮ ᠬ ࠢ ᥬ  ࠢ,  ஬ ந
 ᢥ⪠.  ⠪  㪠 ਮ ᢥ⪨,  
ᠢ "%prec <ᥬ>" ࠢ  ࠢ.
        㭠୮ ,   
, 祬  樨,  ᫥騬 ࠧ:

        %token name
        %left '+' '-'
        %left '*' '/'
        %left UMIN
        %%
        e : e '+' e | e '-' e | e '*' e | e '/' e
          | '(' e ')' | name ;
        e : '-' e %prec UMIN ;
        %%

   ⨢ ᥬ UMIN ᯮ ⮫쪮    
 ᢥ⪨  ࠢ e : '-' e ;

   ⠪, YACC ࠧ蠥 䫨 (᫨  )   ᫥
騬 ࠢ:
   - ᫨ ਮ ୠ⨢ ⢨ ।   ࠧ
,  믮 ⢨  `訬 ਮ⮬;
   - ᫨ ਮ ⢨ ।  ,   
砥  樠⨢ 롨ࠥ ᢥ⪠,   砥  ࠢ
樠⨢ - ᤢ, ᫨  樠⨢ - 㦤
訡筠 ;
   -  (ਮ     ୠ⨢   ᯥ
஢)  砥 䫨 ᤢ/ᢥ⪠ 믮 ᤢ,  
 砥 䫨 ᢥ⪠/ᢥ⪠ - ᢥ⪠  ࠢ,  
   ⥪  ᠭ ࠬ⨪,   
YACC ᮮ頥  ࠧ襭 䫨  ⮬ ﭨ.

   ⬥⨬,   䫨⭮ ࠬ⨪  ࠢ

        s : if '(' e ')' s
          | if '(' e ')' s else s
          ;
।⥭ ᤢ "ࠢ쭮" ࠧ蠥 䫨   ࠧ
ࠦ 

        if( e ) if( e ) s _ else s

- else 㤥 ⭥ᥭ  襬 if',   ਭ   
 몠.
    䫨⭮ ࠬ⨪ 䬥᪨ ,  ࠢ
 ਢ  ᫥ ࠦ ࠢ-   
⮢ 権.

                    ᪨ ⢨

     ࠢ ࠬ⨪     易  ⢨,
஥ 㤥 믮  ᢥ⪥   ࠢ.  
뢠   祭  䨣 ᪮  ᫥⥫
 ஢ 몠 , ᯮ ᫥ ࠢ  
⢥饣 ࠢ.

    statement : IF '(' expr ')' statement    { if_ctr++; }
              | WHILE '(' expr ')' statement { while_ctr++; }
              | assign_st                    { ass_ctr++; }
              ;

    ⮬ ਬ ⢨ if_ctr++ 㤥 믮 ᫥  ࠧ
 ᥣ  if.  室  믮  ᥬ
᪨ ⢨, ਬ,  ࠧ  ᫥  ᫥  ࠦ
expr,     ᨬ ࠢ  ࠢ.

    statement: IF '(' expr { action_1 } ')'
                 statement { action_2 } ;

   YACC ⮬᪨ ८ࠧ ࠬ⨪, 
⥫ ନ  ᮮ⢥騥  ࠢ   
⮩ ࠢ .   ᢥ⪥    믮  ⢨,
ᯮ  ᨬ 室 ࠬ⨪.

    statement: IF '(' expr void_1 ')' statement { action_2 } ;
    void_1:    { action_2 } ;

                      ᪨ ⥪

    ⢥  묨    ⢨ﬨ,  
ନ  ନ   祭.  㯠  
  ⢨ ᯮ ᥢ६ $$ - 祭  
 ᨬ ࠢ, $<i> - 祭 i- ᨬ ࠢ 
 ࠢ (ᨬ 㬥 ᫥  ࠢ,  稭    1).
㣨 ᫮, ஬  筮  ⥪  ﭨ  ஥
YACC'  ᮤন  "ᥬ᪨"  ⥪,  ᮤঠ騩
祭 ᨬ. 祭  ⨯ YYSTYPE,   㬮
砭 ।  int. ⢨

        expr : expr '+' expr { $$ = $1 + $3; } ;

  ᯮ짮   ,  ஬ 
祭 ନ "ࠦ"   ᫥ 祭.
   ᫨  ࠢ  㪠  ⢨,   ⢨
 ᮤন 㯮 ᥢ६ $$,   祭  
 ࠢ ⠭ ࠢ 祭 ࢮ ᨬ ࠢ
, ..  믮 ⢨ { $$ = $1; }.  祭
। ᥬ   ६ int yylval,   
  筮  ᪠.
    ᨬ ࠬ⨪   祭 ࠧ 
.  ⮣ ᫥ । ⨯ YYSTYPE  union   ᯥ
஢ ⨯ ନ  ନ  ࠧ  ᠭ.
 ⮬ 㤥 ⢫ ஫ ⨯   ᯮ짮
ᥢ६,  饭   㤥 ࠭᫨஢  
饭  ᮮ⢥饬  union.

        %{
        #define YYSTYPE yys
        typedef union {
          int      intval;
          long     longval;
          nodeptr *ptrval;
        } yys;
        %{
        %token <intval> ICONST
        %token <intval> LCONST
        %type  <ptrval> expr

   ᫨  ⢥ ७ ।⠢ ணࠬ  ᯮ
 ॢ, 㤮     ⢥  祭  ନ
㪠⥫  ᮮ⢥騩  㧥 ॢ.

                 ஢ ᥬ   䥩

   , ஦ YACC'   ࠡ, ᮤন ⠡
 LALR(1)-  -⥪ 㭪樨 int yyparse( void  ),
ॠ饩  ⠡  ᥬ᪨ ⢨.  
᪠  筮 맢  㭪.  砥 ᯥ
 ࠧ  頥 0,  砥 訡 - 1.
    祭 । ᥬ  뢠 㭪  int
yylex( void ).     ᥬ   
祭  ६ YYSTYPE yylval.
    ᥬ - ⥫쭮 楫 ᫮. ᥬ,  
  ᨬ ⠭, ᮮ⢥      ᨬ
  (筮 ASCII), 騩   0..255. ᥬ,
騬 ᨬ᪨ , ᢠ  稭  257.
   室 䠩 ᮤন  #define, ।騥 
ᥬ   . ᫨  ᥬ ॡ   㣨  䠩
, ᫥ 㪠  -d  ᪥ YACC',   த㡫
  ।  䠩 y.tab.h.  䠩  ᫥  
  㣨 䠩 ணࠬ (ਬ, ᪠),  ᯮ騥
 ᥬ.

                       ࠡ⪠ 訡

   ᫨ 㥬 ।  ᮮ⢥ ,   
   訡筠 , ..  
  ﭨ,  ஬   ।ᬮ७    ᤢ,  
ᢥ⪨  祭 訡筮 ᥬ. 筠 ॠ  
 - 맮 㭪樨 void yyerror( const char * )   㬥⮬
"Syntax error"  襭 ࠡ -   㭪樨 yyparse
 祭 1.  㭪樨 yyerror    
⥫,     ࣠   뤠 
ࠧ㬭 ⨪ ( ᯮ짮 YACC-   
 ਢ쭮 祩).
      ⥫쭮 -  த  ࠧ.
  ⠭  ᫥  訡  YACC   ᮤন   ᫥騥
।⢠.  ᯥ樠쭠 ᥬ    error,  
 㯮ॡ  ࠬ⨪.   訡  
⠭ 䫠 訡, 뢠 㭪 yyerror,   ⥬
 ⥪ ﭨ 㤠 ,     
ﭨ, ᪠饥 ᥬ error.  㦥 ⠪  
ﭨ 믮 ᤢ, ᮮ⢥騩 ᥬ error   ⮬
ﭨ  ࠧ த. ᫨   ⠭  䫠
訡 ᭮  訡筠  ,      
 ᮮ饭 yyerror  뢠,  訡筠  
ᥬ .  訡 뢠 ⮫쪮  ᫥  
ᯥ譮 ⠭ ᥬ.
   樠묨 ⢨ﬨ  ࠢ, ࠡ뢠 訡
樨   ⨢ 訢   .
   yyerrok()   - 뢠 䫠 訡
   yyclearin() - 㤠 ᬮ७ । 訡 ᥬ
    YYERROR  ࠧ 㦤 訡 .

ਬ:

   statement :  ....
             | error ';'

  訡  statement  த  ࠧ
 ⮫쪮 稭  ';' -   १    ய饭
 ᥬ  窨  ⮩,  ⥬ 㤥 ᢥ  
ନ statement.

                            

 YACC  S UNIX  :

   yacc [-v] [-d] _䠩.

 ࠡ (⥪  ) 뢠  䠩 y.tab.c

:
   v - ᮧ ⥪⮢ 䠩 y.output  ᠭ ﭨ  
       䫨⮢ ஥ 
   d - ᮧ 䠩 y.tab.h  ।ﬨ ᥬ.

  YACC'  㣨 ⥬  䠩  祩  
 㣨, ਬ:

   -i -d,  _室_䠩.(i,c,h)  RSX11M  RT11

   y.out, ytab.c ytab.h  ⥬  䠩 ⥬ MS-DOS


ࠣ 䠩 y.output:

        state 3
                stat :  expr_    (4)
                expr :  expr_+ expr

                +       shift 11
                .  reduce 4

ᠭ ﭨ (state) 3, ᮮ⢥饥  ᭮  
.  ⮬ ﭨ ᨬ '+' 뢠 ᤢ  (shift)  
室   ﭨ  11,      㣮  ᨬ  -  ᢥ
(reduce)  ࠢ 4 - stat : expr.

           ਬ ⥩襣  

%token ICONST
%left '+' '-'
%left '*' '/'

%%

p : /* empty */
  | p s
  ;

s : e '\n' { printf( "%d\n", $1 ); }
  | error '\n'
  ;

e : e '+' e  { $$ = $1 + $3; }
  | e '-' e  { $$ = $1 - $3; }
  | e '*' e  { $$ = $1 * $3; }
  | e '/' e  { $$ = $1 / $3; }
  | '(' e ')'{ $$ = $2; }
  | ICONST;
  ;
%%

#include <stdio.h>
main() { yyparse(); }
yyerror( mes ) char *mes; {  printf( "%s\n", mes ); }

yylex() {
  int c, d;
  while((c=getchar())==' '); /* Skip spaces */
  if( c>='0' && c<='9' ) {   /* Integer constant */
    for( d=c-'0'; (c=getchar()) >='0' && c<='9'; ) d=d*10+c-'0';
    ungetc( c, stdin );
    yylval = d;
    return ICONST;
  }
  return c;                  /* Others */
}

                -  ਠ  樨 7 -
