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

    ਠ  樨 5.  ᭨-. -ᢥ⪠.
             ⮥  ୮ ।⢮.

   ᬮਬ ࠧ ᭨-,  ஬ ஬ 
 ६  ॢ  ࠢ  . ᫨ 
 ᨬ 楯窨 ᫥ ࠢ,    ॢ  ࠧ  㤥
룫拉 ᫥騬 ࠧ:

             S
            /    \
           /x   \
          /       \
          wbu

஬ 뢮   xbu,  x - 楯窠 ନ 
ନ,  ன 뢮 ᬮ७    ନ
쭮 楯窨 w, bu - ᬮ७  ନ쭮  
窨, b - । ᨬ. ⮡ த ࠧ,  
  ᨬ b  ᬮ७   楯窨  (믮
⠪ 뢠 "ᤢ"),  뤥   x ⠪  楯
z (x=yz),   z  ਬ   ࠢ ࠬ⨪ B:z
  x  楯 yB  (믮  ⠪  뢠  "ᢥ
"):
             S                            S
            /    \                          /    \
           /xb \                        /yB   \
          /       \                      /       \
          wbu                      wbu
         ᫥ ᤢ                    ᫥ ᢥ⪨

   ᫨ ᢥ ਬ ⮫쪮  ᫥ ᨬ x,   
㤥  ࠢ 뢮 楯窨.  ࠧ 稫 
 LR,  ᨬ L (Left,) ⭮   ᬮ  
窨 ᫥ ࠢ,  R (Right, ࠢ) ⭮  砥
뢮. ࠦ: ,   ࠢ 뢮  室
 -筮 ᮮ⢥⢨  ᫥⥫쭮ﬨ ᤢ
  ᢥ⮪.
   ਬ LR-ࠧ 楯窨 aabb  ᮮ⢥⢨   ࠬ⨪
S : SaSb | e.  _ 㪠뢠  ࠭  ᬮ७
 ᬮ७ ﬨ 楯窨: _aabb : S_aabb  :  Sa_abb  :
SaS_abb : SaSa_bb : SaSaS_bb : SaSaSb_b : SaS_b :  SaSb_  :  S_
   ᫥⥫쭮 権 ᤢ  ᢥ⪨  ⢥  -
᫨   ਢ ਬ ࢮ 樥      ᤢ,
ࠧ  㤠    . ⮬  ନ
 ࠧ ॡ    롨   ᤢ
  ᢥ⪮ ( ࠧ묨 ࠢ ᢥ⪨).    
ᬮ७  ᯮᮡ 롮: ⮥  ୮  ।
⢮  LR(k)-ࠧ.

              ࠬ⨪ ⮣ ।⢮

   ࠬ⨪ 뢠 ⨬, ᫨      ࠢ
 묨 ࠢ묨 ﬨ. ,  ࠬ⨪ 뢠
 ਢ, ᫨    e-ࠢ, ᯮ ᨬ
 横.
    楫   ⢥ ନ   ନ
 ᨬ  ⭮襭 (⠪ 뢠 "⭮襭 ।
⢮") (㤥   <', ='  >' ) ⠪,  ⮡  
,  ॡ ᢥ⪠ 楯窨 z, ⭮襭  ᨬ
 ஥  뢮 (楯窨 x    祭  
砫 樨)  । ᨬ b 뫨 ᫥騬:

        <'  =' <' =' =' >'
       
            y         z      b     u
᫨ 㤠 ந ⠪ ⭮襭,  LR-ࠧ   
⨬ ࠬ⨪  ஢ 祭 :
   - ᤥ ᤢ, ᫨ ᫥ ᨬ x <' b   ᫥
     ᨬ x =' b
   - ᤥ ᢥ, ᫨ ᫥ ᨬ x >'  b,    ⮬
     ࠢ  ࠢ z 祭   ⭮襭ﬨ  <'  
     >'.
   ࠬ⨪ 뢠 ࠬ⨪ ⮣  ।⢮,
᫨  ਢ, ⨬   묨  ନ
  ନ  믮        ⭮襭
।⢮.
   ࠪ᪨ ⭮襭 ।⢮  ᫨ ᫥
騬 ࠧ (X,Y - ନ  ନ, A,B,C-ନ
, y - ନ, ... -  楯窠 (.. )):
     X =' Y, ᫨  ࠬ⨪  ࠢ A : ...XY...
     X <' Y, ᫨  ࠬ⨪  ࠢ A : ...XB...
                                           B :: Y...
     X >' y, ᫨  ࠬ⨪  ࠢ A : ...By...
                                         A : ...BC...
                                           B :: ...X
                                           C :: y...
    ⭮襭 ।⢮  ࠬ⨪  S:aSSb|c,
稬: a='S, S='S, S='b, {a,S} <' {a,c}, {b,c} >' {a,b,c}.
 ࠬ⨪  ࠬ⨪ ⮣ ।⢮.
    ࠪ⨪  㤮 ,   砫    
窨 몠  ᨬ-࠭⥫  #.      ⭮襭
।⢮ । ⠪:
        # <' X, ᫨ S :: X...
        X >' #, ᫨ S :: ...X
 襬 ਬ {b,c} >' #, # <' {a,c}.
   ⬥⨬,  ⭮襭 <',>',='  宦   䬥
᪨ ⭮襭 <, >, = : ='   ⭮襭  
⭮, <'  >'  易⥫쭮 ࠭⨢.
   ⭮襭 ।⢮ 㤮   ,   
ன ப  ⮫ 祭 ନ  ନ ࠬ
⨪. ࠦ:   .   ,
 ன  ᨬ  믮    ⭮襭
।⢮?

            ࠬ⨪ ୮ ।⢮

   ᫨  ࠢ ਢ ⨬ ࠬ⨪  
 冷  ନ, ,    ࠬ⨪  
୮. ᪨ ਬ  -  ࠬ⨪  䬥᪨
.  ⠪ ࠬ⨪      ⭮襭  ।
⢮ ⮫쪮  ⢥ ନ ᨬ.  
 㥬 ࠢ ᫥ ⭮襭 ।⢮:
   a =' b, ᫨  ࠬ⨪  ࠢ A : ...ab...
                                          A : ...aBb...
   a <' b, ᫨  ࠬ⨪  ࠢ A : ...aB...
                                            B :: b...
                                          B :: Cb...
   a >' b, ᫨  ࠬ⨪  ࠢ A : ...Bb...
                                            B :: ...a
                                          B :: ...aC
   # <' a, ᫨  ࠬ⨪  뢮   S :: Ca...
                                          S :: a...
   a >' #, ᫨  ࠬ⨪  뢮   S :: ...aC
                                          S :: ...a
   ᫨  묨  ନ 믮   
 ⭮襭 ।⢮, ୠ ࠬ⨪  뢠
 ࠬ⨪ ୮ ।⢮.
   ᫨  ୮ ।⢮  ࠬ⨪
䬥᪨ :
                        Ŀ
                            ( a * + ) #
    S : S + T | T       Ĵ
    T : T * E | E        )      > > > >
    E : (S)   | a        a      > > > >
                         *  < < > > > >
                         +  < < < > > >
                         (  < < < < =  
                         #  < < < <    
                        
    ⭮襭   ।  ନ,  室騥  
ࠢ  ᢮稢 ࠢ,   ନ. ,
 ࠪ᪮ ࠧ   室 ࠧ 
ନ S, T  E.  뫨  ⮫쪮  ਤ  ࠬ
⨪ 筮   ਮ  樠⨢  
権. , 稢 ⭮襭 ।⢮,    
  ⢥  ନ  S:
   S : S+S | S*S | (S) | a
  ࠧ, ࠡ뢠  ନ .

              ਧ  ।⢮

    ⭮ ࠭  ।⢮  
ᯮ짮 ᫥騩 ਥ.   M[n][n],   
ன ਭ ⮫쪮   祭  (<'  ='  >'),  ⠥
ந  楫᫥  f  g:
   M[i][j] ࠢ >', ᫨ f[i]>g[j]
   M[i][j] ࠢ <', ᫨ f[i]<g[j]
   M[i][j] ࠢ =', ᫨ f[i]=g[j]
 祭  ஢ ᯮ ᫥騩 ⮤:
   - ந ਥ஢ , ᮤঠ騩 n 設 ⨯ F
      n 設 ⨯ G;
   - ந ॡ  F[i]->G[j], ᫨ i >' j
   - ந ॡ  F[i]<-G[j], ᫨ i <' j
   - ᪫ 設 F[i]  G[j], ᫨ i =' j
᫨ 祭  横᪨,   ਧ  .
  f[i] ࠢ  ᠬ     F[i],
g[i] ࠢ  ᠬ    G[i].
   ਬ  ⮤    ஥    ୮
।⢮, 稬:
        ᨬ  # a + * ( )
        f       0 4 2 4 0 4
        g       0 5 1 3 5 0

       (୮ ।⢮)

    ॠ樨     䨪 
 殮   ᢥ⪮ ⢨:
        a : ᫮         -  ᫮  
        S : a | (S)             - 祣  
        S : S*S | S+S           -   樨
஥  뢮 x 㤥 ࠭  ⥪:

%{                       /*  ᥬ  ᨬ */
#define EF      0          /*  䠩 */
#define ID      1          /* 䨪  ᫮ */
#define PLUS    2          /* '+' */
#define MULT    3          /* '*' */
#define LP      4          /* '(' */
#define RP      5          /* ')' */
%}

%%
"+"             { return(PLUS); }
"*"             { return(MULT); }
"("             { return(LP); }
")"             { return(RP); }
[A-Z0-9]+       { printf("%s ",yytext); return(ID); }
\n              { }
.               { printf("%s: ",yytext); error(0); }
%%

static char *view[] = { /* 䨪᭮ ।⠢ ନ */
   "",    /*  䠩 */      "",    /* 䨪 */
   "+ ",  /* '+' */              "* ",  /* '*' */
   "",    /* '(' */              "",    /* ')' */
};

/* ਧ  ୮ ।⢮ */
static f[] = { 0, 4, 2, 4, 0, 4, };
static g[] = { 0, 5, 1, 3, 5, 0, };

main() {
 register c, d;
  stinit(); stpush(EF);
  do {
    c = yylex();
    while ( f[sttop()] > g[c] ) {
      do {
         d = stpop();
         printf ("%s",view[d]);
      } while ( f[sttop()]==g[d] );
    }
    stpush(c);
  } while(c!=EF);
}

/*  ⥪ ନ */
#define MAXSTK  100
static int stack[MAXSTK], *stptr;

stinit()  { stptr = stack+MAXSTK; }
stpush(e) {
  if ( stptr==stack ) error(1);
  *--stptr = e;
}
sttop() { stcheck(); return(*stptr);   }
stpop() { stcheck(); return(*stptr++); }
stcheck() { if (stptr==stack+MAXSTK) error(1); }

static char *ermsg[] = { /*  ᮮ饭  訡 */
  /* 00 */ "訡 ᨬ",   /* 01 */ "⪠",
};

error(e) { printf ("%s\n", ermsg[e]); exit(1); }
yywrap() { return(1); }

  襭  :
1. ।  ⠪, ⮡    ᪠  訡
   (..  ஦ ࠬ⨪) 楯祪.
2.       ⥯  (ࠢ
   樠⨢  "^"  訬 ਮ⮬).
3. ।    .
4.     "㭠 ".

                 -  ਠ  樨 5 -
