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

          ਠ  樨 4. -모  ࠬ⨪.
        LL(k)-ࠬ⨪. ⥩訩 LL(1)-.

                   ⥪⭮-᢮ 모

    ⥪⭮-᢮ 몮 ᪠ ᯮ  
 ନ஢    ⥪  (  )
.
   ⥪⭮-ᨬ 모 - ᫥  몮, 
 䥪⨢ ᯮ   . 樠  ᪠,
  ᪠ ஭ ନ஢묨  
࠭祭묨 ⮬⠬.  ᪠ 楯祪 몠  ࠭
祭  饬 砥 ॡ 㭨ᠫ ᫨⥫ (
 ਭ, 設  ࠭祭 ᫮ ॣ஢   ..).
⥪⭮-ᨬ 모  모  ࠭祭  ᯮ
  ஥ ஢   쭥襬 ᬠਢ
 .
   ⮬  ⥪   ⫨稥  筮    
⥪,      ᯥ樠  ..  ""
ᨬ. 室   ﭨ  㣮   ⮫쪮
 室 ᨬ,    孨 ᨬ  (  
㭪  㣫 ᪮).  砫 ࠡ    ᯥ
樠 ᨬ S.
    믮 室   㤠 孨 ᨬ
, ᮮ⢥騥 ࠢ,     楯窠  ᨬ,
ᮮ⢥ 室 ( 㭪  ࠦ    
᪮,  ᨬ 楯窨 ⠭ 孨 ᨬ  
). ᪠ ⠪ 室,   室 ᨬ
 (, ⥬ ᠬ, 㤥 室 ᨬ    ᫥
饬 室).  室 뢠  e-室.  ⮬
뢠 ନ஢, ᫨       
ﭨ, 室 ᨬ  設        祬
 室. ᫨  砭 楯窨  ⮬  室  
   ﭨ,  ⥪ , 楯窠 ⠥ 
饭 (᫥ 砭 楯窨   ᤥ  e-
).

            Ŀ0(S) Ŀ1(0) ¿
            砫>  1  > 2 
            [0]   []  
                          <       <
                         0(0)[00]     1(0)[]

 楯窨 ᪠  ⮬? - ࠦ.

    ⥪⭮-᢮ ࠬ⨪  ந ନ
஢    ,   ᪠  楯窨
⮣ 몠.  ᯮ ⮫쪮   ﭨ    ᫥騩
 室:
     e(A)[x]   ࠢ ࠬ⨪ A:x
     ()[]    ନ 

    ந  㣮 ⮬,  ⠪ ᮤন 
 ﭨ   ᫥騥 室:
     ()[]   ନ 
     (x)[A]   ࠢ ࠬ⨪ A:x

    ,   砫 ࠧ  ⮣  ⮬
.    ࠧ   ⠭ ᨬ S.  
 (ࠢ  ) 뢮  ( 筮 ࠬ
) ⮫쪮  ஥ ⮬? - ࠦ.
     ନ஢           
ந  -ࠬ⨪  (ࠦ).    ࠧ   
-몮   몮, ᪠ ⮬⠬    
, .
    ᮦ,   - ᪠  ࠧ    
ନ஢ ⮬. ਬ,  楯祪-஬
 0  1    饭 ନ஢    
  ( 룫廊 ନ஢ ⮬, ᪠
騩  ? - ࠦ).  ࠧ, ନ஢
 ⮬  ⥪  ᯮ   ப  
몮, 祬 ନ஢ ⮬  ⥪ -    ⮬  
⢥ ⫨稥  . ࠪ᪨   ॠ樨
஢   ।⠢   ନ஢   -모    -
ᮡ⢥ ⢮ -몮, ᪠饥 ᯮ 
 ନ஢ ⮬⮢   .
    (ନ஢)  ⮬,  ஥    
-ࠬ⨪ ।   ⮤ ࠧ  -몮:
ᢥ- ᭨ .
    ࢮ 砥 (ਬ - ४ᨢ )    ᬮ
楯窨 ᫥ ࠢ ⢥     뢮
.  ନ஢ ࠧ  ஡  㤥    
⮬,  ࠢ ਬ   ᠬ  
.
    ஬ 砥 ନ஢ ࠧ 㤮  ଠ
  ନ "ᤢ" (७ ᨬ  室  楯窨  
)  "ᢥ⪠" (ਬ  設  -
ࠢ ࠬ⨪).  ᬮ 室 楯窨 ᫥ 
  ⮬   ࠢ  뢮.  ஡    ⮬
砥 ⮨  롮  ᤢ   ᢥ⪮      롮
ࠢ  ᢥ⪨. 騥 樨   饭  ࠪ
᪨ ⮤ ࠧ ନ஢ -몮 ᢥ  
 ᭨-.

                 ࠧ⠭  -몮

     -몠  ⠪  ᫮  m,    
ਭ  楯 z : |z|>m  ࠧ  5 ⥩
                                                 n   n
z = uvwxy : |vx| > 0, |vwx|<=m  楯窨   uv  wx  y,  n>=0
⠪ ਭ .
   ⥫⢮:  -ࠬ⨪ 몠 ᮤন q  
,  ᠬ  楯窠  ࠢ    ࠢ  
 k. ᬮਬ ॢ 뢮  楯窨   k**(2*q+3)
 ⠢   ⮫쪮  ⢫,    ନ
   (㥬  e-ࠢ).  ⢥ত:  
    ஭,     ࠩ    q+2
 ( q+2 ࠢ) ⢫ (ࠦ). ᫨  設
ॢ  묨 ନ,     ࠩ  
   (ਬ, A)   ⮬    ࠧ
(ࠦ).   ஭ ॢ ⢥ ࠧ ࠧ
  5 ⥩:         S
                        /  \
                       /  A  \
                      / /  \ \
                     / /  A  \ \
                    / / /   \ \ \
                   
                    u v   w  x  y
  㤥 ᪮ ࠧ  楯窨,  ⠪    uvwxy  
㤮⢮ ॡ  (ࠦ).
                                  n  n  n
ࠦ: ,     0  1  2      ⥪
⭮-᢮.

                  ८ࠧ -ࠬ⨪.

   ஡ ⭮  몮, 뢠 ࠧ묨
-ࠬ⨪,  饬 砥 ࠧ訬.    㤠
 ८ࠧ ࠬ⨪  ॡ㥬  ⮣    
ନ஢ ࠧ    "ᯮ⨢"  뢠  
.

             ᯮ ᨬ  ࠢ

    ᨬ  ᯮ, ᫨    砥    
 뢮 楯窨 ନ  砫쭮 ᨬ ࠬ
. O祢,  ᯮ ᨬ   ᮤঠ騥   
   㤠  ࠬ⨪. ਬ,  ࠬ⨪

   S : a | A ;   A : Ab ;   B : b

 ନ A  뢥   ନ쭮  楯窨,
 ନ B    뢥  砫쭮 ᨬ S.
   ⢮ ନ,     뢮  ନ
楯窨  ᫨:

    K := { A |  ࠢ A:ନ }; 1 := ;
    横   != 1 믮
      1 := 
       :=  U { A |  ࠢ
                     A:(ନ  1   ନ) }
     横

⢨: ஡  -몠  ࠧ訬  -    ,
᫨  ⮫쪮 ᫨ S  ਭ K.
   ᫥ 㤠  ࠬ⨪ ନ,   ਭ
, ᫮  ⢮ L ᯮ ᨬ:

    L := {S}; L1 := ;
    横  L != L1 믮
      L1 := L
      L := L U { B | . ࠢ A:..B..,   ਭ L1 }
     横

   ᫥ 㤠  L  ࠬ⨪,   㤥  
ঠ ᯮ ᨬ (⥫⢮ - ࠦ). 
  㤠  ᯮ ᨬ  ࠬ⨪, ᫨ ᫨
ਬ ᭠砫 ன,  ⥬  ?

                      ࠭ -ࠢ

   ࠢ  A:e 㤥 뢠 e-ࠢ. ᫨   
ন ⮩ 楯窨,      ࠬ⨪    㤠  
e-ࠢ,  ⨢ 砥    砫 ᨬ
 S1, ࠢo S1 : S | e,  㤠  ⠫  e-ࠢ.
ᠭ ⬠ - ࠦ.  :  ᫨  砫
⢮ ନ,    뢮    楯窠.
⢨: -,  ᮤঠ騩 ⮩  楯窨,    
ᠭ 㪮稢饩 ࠬ⨪.

               ࠭ 横  楯 ࠢ

   稬 ᨬ :: 뢮  楯窨  㣮  
 ⮩ ᫥⥫쭮 ࠢ.  横  
  A::A... .  ࠭ 横  㤠  ࠬ
⨪  楯 ࠢ  A:B.   楯  
  :...,   ࠬ⨪ ࠢ B:...,    
B,     楯 ࠢ 뢮 . ᫥  ⮣
㤠 楯 ࠢ   몠. ࠬ⨪  横,
e-ࠢ  譨 ᨬ 뢠 ਢ.
   ࠦ. ࠬ⨪  ଠ쭮 ଥ ᪮  ᮤন
⮫쪮 ࠢ  A:BC, A:a  S:e, ᫨  ᮤন  
楯. ,   -    ࠬ⨪
 ଠ쭮 ଥ ᪮.

                   ࠭  ४ᨨ

   ନ A 뢠 ४ᨢ, ᫨  뢮:
᫨ x=e,  A 뢠 ४ᨢ, ᫨ y=e,   ࠢ
४ᨢ.

        A :: xAy

   ࠦ:   ᪠  , ᠭ  ࠬ
  ४ᨢ ନ?
   ⮤ ४ᨢ ᪠    ࠡ⠫    ४ᨢ
ࠬ⨪.   ४ᨨ ᥣ   (  
砥,  ⮤ ४ᨢ ᪠ ਬ   .)
 砫,  8࠭      ४,  ..
ࠢ  A:A... . 

        A : Aa1|...|Aan | b1|...|bn 

 A-ࠢ ࠬ⨪,     楯祪 bi  稭
 A. , ਬ A-ࠢ  ᠬ  ନ,  
  뢥 ᫥饥 ॣ୮ ⢮ 楯祪:

        (b1|...|bn)(a1|...|an)*

    ⢮ 뢮   ८ࠧ ࠬ⨪:

        A : b1|...|bn | b1T|...|bnT
        T : a1|...|an | a1T|...|anT

   ࠭   ४       ᫥饣
, 饣 ᫥⥫쭮 ᪫祭  ६
 襭 ⥬ ࠢ ⮤ .

    横  i  1  n
      ਠ:   k<i (. ࠢ Ak:Al...) => l>k
      横  j  1  i-1
        ਠ:   k<j (. ࠢ Ak:Al...) => l>k
         ࠢ Ai:Aj...   ࠢ Ai:Lj...,
         Lj -  ࠢ  Aj-ࠢ
       横
      ࠭   ४  Ai
     横

   ࠦ. ࠬ⨪  ଠ쭮 ଥ  ३  ᮤন
⮫쪮 ࠢ  A:aB,  a-ନ,  B  -  ᫥⥫
 (  ) ନ,  ⠪ S:e, ᫨  
ᮤন  楯. ,   -  
 ࠬ⨪  ଠ쭮 ଥ ३.

                   --ᠬ

   : -ࠬ⨪  楯窠  ᨬ.  ॡ  ।
, 뢮   楯窠  ࠬ⨪.  ,  
 ॣ 몮 筠 ஡ 蠫  
  楯窨  ६.  ᬮ७      蠥
஡ ਭ 楯窨 -   쭮  
 楯窨 ६.
   砫 ८ࠧ㥬 ࠬ⨪  ଠ   ᪮,
..  ࠬ⨪  ࠢ  A:BC  A:a.   a1a2...an
- 室 楯窠 ᨬ. ந 㣮 ⠡ Ti,j:
1<=i<=n, 1<=j<=n-i+1. i,j - ⢮ ନ,  
뢮 楯窠 ନ aj...aj+i-1. (楯窠   i,
 ᨬ ன   j).

| T1,j ନ,   뢮 ᨬ 楯窨
   横  j  1  n
     T1,j := { A |  ࠢ A:aj }
    横
|  蠣 뢮    i-ᨬ쭮  楯窨  (i>1)  
|  ⮫쪮 ਬ ࠢ A:BC,   B 뢮 
| 楯窠,   C - ࠢ, 祬  楯窨  
|   i.  뢠 "᪮ ணࠬ஢":
   横  i  2  n
     横  j  1  n-i+1
       Tij := 
       横  k  1  i-1
         Tij := Tij U { A | ( ࠢ A:BC)
                           (B ਭ k,j)
                           (C ਭ i-k,j+k) }
        横
      横
    横
   楯窠 뢮  ࠬ⨪ := S ਭ Tn,1

    ॡ ६ 浪 n**3   n**2,  n -
 楯窨 (!).       ਣ  
ࠪ᪨  楫.     ࠪ⨪   ਬ   ᯥ樠
 -ࠬ⨪,       
 ࠧ.

                   LL(k) 모  ࠬ⨪

   ᬮਬ ॢ 뢮   祭   뢮
楯窨. ஬筠 楯窠   뢮 ⮨  
窨  ନ w, ᠬ  ନ  A,  뢥
  x:
             S
            /    \
           / ڀx\
          /       \
          wu
    த ࠧ ॡ  ନ  A  
  ࠢ  A:y. ᫨ ॡ, ⮡ ࠧ  
ନ஢ ( ⮢),  ࠢ ॡ 롨
ᯥ樠 ᯮᮡ. ,   ࠬ⨪    ᢮⢮
LL(k), ᫨  롮 ࠢ 뢠 筮  ᬮ
 ⮫쪮 wAx   k ᨬ ᬮ७ 楯窨  u.
ࢠ 㪢 L (Left, ) ⭮  ᬮ 室  
窨 ᫥ ࠢ,  -  ᯮ㥬  뢮.
   ।  ⢠ 楯祪:
     FIRST(x) - ⢮ ନ 楯祪, 뢮  x,
                㪮祭  k ᨬ.
     FOLLOW(A)- ⢮ 㪮祭  k ᨬ  ନ
                 楯祪,      ᫥  
                ।⢥  A  뢮 楯窠.
ࠬ⨪  ᢮⢮ LL(k), ᫨  ⢮  
祪  뢮:

       S :: wAx : wzx :: wu
       S :: wAx : wtx :: wv

 ᫮ FIRST(u)=FIRST(v) ᫥ z=t.
    砥 k=1  롮  ࠢ    ,  筮  
⮫쪮 ନ A   -  ᨬ 楯窨 u:
   ᫥  ࠢ A:x, ᫨  室  FIRST(x)
   ᫥  ࠢ A:, ᫨  室  FOLLOW(A)
,  ⠪ 롮 ࠢ ⨢稢  -  ࠦ.
: ᯮ 䠪⮬,      LL(1)-ࠬ⨪  
ࠢ   A:x      A:y   ⢠    FIRST(xFOLLOW(A))    
FIRST(yFOLLOW(A))  ᥪ (ࠦ).  k>1  
ত  ୮   (ࠦ).
   ࠦ: । , 騩 ⢠ FIRST
 FOLLOW  ᨬ -ࠬ⨪
   LL()-᢮⢮ 뢠 쭮 ᨫ  ࠭祭  
ࠬ⨪. ਬ, LL(2) ࠬ⨪

        S : aS | a

  ᢮⢮  LL(1),  ..  FIRST(aS)=FIRST(a)={a}.  
 砥   稭 k     "䠪ਧ
樨" (뭥ᥭ ⥫  ᪮):

        S : aA
        A : S | e

 LL(k)-ࠬ⨪ 筠.  ४ᨢ  ࠬ⨪
 ਭ  LL(k)      k.  (⥫⢮
  䠪⮢ - ࠦ).  㤠 ८ࠧ 
LL(1)-ࠬ⨪    LL(1)-ࠬ⨪   
࠭  ४ᨨ  䠪ਧ樨.   ஡  
⢮ ⭮ LL(k)-ࠬ⨪  ந쭮  
LL(k)-ࠬ⨪ ࠧ訬.
     ନ஢  모,      
                                     n  n   n  2n
LL(k)    k, ਬ  - {0 10 U 0 10 | n>=1}.


                            ਬ

   ࠬ⨪  䬥᪨ :

         :  |  + 
         :  |  * 
        M : (  ) | 

  LL(1), .. ࠢ     ᮤঠ  
४, ࠭ :
      Ŀ
                              FIRST         FOLLOW   
      Ĵ
         :  1               ( a           ) e     
       1 :  | +  1         + e           ) e     
         :  1               ( a           + ) e   
       1 :  | *  1         * e           + ) e   
       M  : (  ) |           ( a           * + ) e 
      
    楯窨 ஦ ⮫쪮 ନ 1   1.  
 ࠢ    ନ  1    1;  ⢠
FIRST(1), FOLLOW(1)  FIRST(T1), FOLLOW(T1)   ᥪ.
 ࠧ, ८ࠧ ࠬ⨪  LL(1).
    e, 饭  ⢠ FIRST  FOLLOW   ࠧ
    ਢ  䫨⠬: e  ⢥  FIRST  
  祭  뢮 ⮩ 楯窨 
 ନ, e  ⢥ FOLLOW  砥  ⢨
᫥饣 ᨬ   ப ନ.  ࠪ⨪  ஫
e  ஬ 砥   ନ ப.


               ⥩訩 LL(1)- 

   ᪮ ⢨  LL(1)-ࠧ  ⮫쪮   
"। ନ-। ᨬ",  ࠧ  
ணࠬ஢. ᨢ  -    ᯮᮡ  
஢ LL(1)-ࠧ. 㣮 ᯮᮡ ஢ ⠡ ᯮ
  ᫥饬 .
    ८ࠧ 楯窨 몠, ᮮ⢥饣 ࠬ
⨪:
      S: T {+T}
      : E {*}
      : <࠭>|(S)
 䨪 .

%{                       /*  ᥬ  ᨬ */
#define ID      1          /* ᥬ - 䨪 */
#define META    100        /* ᨬ ࠬ⨪ */
#define S       (META+0)
#define T       (META+1)
#define E       (META+2)
                         /*  室 */
#define NOGO    100        /*  襭 ࠧ */
#define OK      (NOGO+1)
#define ERR     110        /*  訡 */
%}

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

static lexcode, oldcode;  /*  ।  ।饩 ᥬ */

main() {
  lexcode = yylex();
  parse( S ); printf("\n");
  if ( lexcode ) error(4);  /* 訫  ࠧ   䠩? */
}

/*
 * LL(1)-⠡    :
 *   -  ᥬ  ᨬ  ᮯ⠢
 *   -  ⢨  ᯥ (ᥬ᪠ ணࠬ)
 *   - 室    ᯥ ( ப/ᯥ/ᯥ/訡)
 *   - 室  ᯥ
 */
static char stable[] = {    /* LL(1) - ⠡  S */
   /* 00 */ T,     0,      1,      ERR+1,
   /* 01 */ '+',   1,      2,      OK,
   /* 02 */ T,     2,      1,      ERR+1,
};
static char ttable[] = {   /* LL(1) - ⠡  T */
   /* 00 */ E,     0,      1,      ERR+2,
   /* 01 */ '*',   1,      2,      OK,
   /* 02 */ E,     2,      1,      ERR+2,
};
static char etable[] = {   /* LL(1) - ⠡  E */
   /* 00 */ ID,    0,      OK,     1,
   /* 01 */ '(',   0,      2,      NOGO,
   /* 02 */ S,     0,      3,      ERR+1,
   /* 03 */ ')',   0,      OK,     ERR+3,
};
/* ⥫  LL(1) - ⠡ */
static char *blocks[] = { stable, ttable, etable, };

/*
 *  LL(1)-⠡
 * 室:      m - ᥬ  ᨬ
 * : 1,  ᮯ⠢ 㤠
 */
parse (m) {
 register char *block, *p, sign;
  if ( m<META ) {
    if (lexcode != m) return(0);
    oldcode = lexcode; lexcode = yylex();
    return(1);
  }
  p = block = blocks[m-META];
  for(;;) {
    if ( parse( *p++ ) ) {
      switch ( *p++ ) {   /*  */
        case 0:  break;
        case 1:  sign = oldcode; break;
        case 2:  printf("%c ", sign); break;
        default: error(1);
      }
    } else p += 2;
    if      ( *p <  NOGO ) p = block+*p*4;
    else if ( *p <= OK ) return (*p-NOGO);
    else error(*p-ERR);
  }
}

static char *ermsg[] = { /*  ᮮ饭  訡 */
  /* 00 */ "訡 ᨬ",   /* 01 */ "⪠",
  /* 02 */ "  ࠭",  /* 03 */ " 墠⠥ )",
  /* 04 */ "  ",
};

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

   ࠦ  ணࠬ஢:    LL(1)-⠡
ࠧ ⥭ᨢ  ४ᨥ,      
᫨誮  䥪⨢.    ४ᨢ  
⠡.
