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

             ਠ  樨 6. LR(k)-ࠬ⨪.
                 SLR(1), LALR(1) - ࠬ⨪.

   ᫨   LR-ࠧ ਭ ନ஢ 襭
 ᤢ/ᢥ⪥ 㤠, ᬠਢ ⮫쪮 楯 x   
 k ᨬ ᬮ७  室 楯窨 u  (  k
ᨬ 뢠 楯窮), ,  ࠬ⨪  
 LR(k)-᢮⢮.
             S
            /    \
           /x   \
          wu
   稥  LL(k)-  LR(k)-ࠬ⨪  ନ ॢ
뢮:
              S
             /  \
            /  A  \
           /  / \  \
          wvu
 砥 LL(k)-ࠬ⨪ 筮 । ࠢ,  ਬ
  A,   w    k  ᨬ  vu,      砥
LR(k)-ࠬ⨪ -  w,v   k ᨬ u.    ண
㦤 뢠,  LL(k)-모  <  LR(k)-모  (
࣭   k=0).

                        LR(0)-ࠬ⨪

   ᬮਬ 砫   ࠬ⨪ ⮣  
- LR(0).  ࠧ ப LR(0)-몠    ᯮ
 楯 - 롮  ᤢ  ᢥ⪮  
᭮ 楯窨 x (.⨭).       ࠧ
  ⮫쪮  ࠢ ,  뢠 ⥪.  
 ,   ࠬ⨪  ᯮ  ᨬ    
砫 ᨬ  砥  ࠢ   ࠢ  -  ⮣
ᢥ⪠  砫쭮 ᨬ ᨣ  ᯥ譮 
 ࠧ. ஡㥬  ⢮ 楯祪   ନ
 ନ,   ⥪     LR-ࠧ
஢ (㣨 ᫮ -  ࠢ 뢮  ࠬ⨪).
   । ᫥騥 ⢠:
    L(A:v) -  ⥪ ࠢ A:v  -  ⢮ ﭨ
⥪, ।⢥ । ᢥ⪮ v  A  室   ᯥ
 LR-ࠧ஢. 祢,  楯窠   L(A:v)  砥
 v. ᫨   ⠪ 楯祪 १ 墮 v,   
⢮ 楯祪,  ᫥  A    
 ࠢ 뢮. 稬  ⢮
    L(A) -  ⥪ ନ  A. ࠦ: ,
  । ४⭮, .. ⢮ L(A)   
  롮 ࠢ A:v.
   ந ࠬ⨪  ⢠  L(A).  ନ  
ࠬ⨪  ନ  ନ  室  ࠬ⨪,
ନ  ࠬ⨪ 稬 <L(A)>,... -  祭
ﬨ   ⥪ ନ 室 ࠬ⨪. 
 S - 砫 ᨬ 室 ࠬ⨪,  ࠬ⨪  
 ⥪⮢ 㤥 ᮤঠ ࠢ
    <L(S)> : e      -  ⥪ S ᮤন  楯
  ࠢ 室 ࠬ⨪, ਬ,
    A : B C d E
   ࠬ⨪ ࠢ:
    <L(B)> : <L(A)>           - L(B) 砥 L(A)
    <L(C)> : <L(A)> B         - L(C) 砥 L(A) B
    <L(E)> : <L(A)> B C d     - L(E) 砥 L(A) B C d
ࠦ: ,  L(A)  ᮤন 㣨 楯祪, 
 뢮  ࠬ⨪.
   祭 ࠬ⨪  ᯥ樠  (⠪ ࠬ
 뢠 묨),  ᫥⥫쭮,  ⢠  
⥪⮢ - ॣ.  ⮣  ᫥,    ਭ
楯窨  ⥪ - ନ    
 ⨢   筮 ⮬, ᬠਢ  
 ᫥ ࠢ. 襬   ⨢.
    LR(0)-樥 ࠢ ࠬ⨪    ⬥祭
 樥  ᨬ ࠢ    ࠢ.  ਬ,
 ࠬ⨪ S:A ; A:aAA ; A:b  ᫥騥 LR(0)-
樨: S:_A; S:A_; A:_aAA; A:a_AA; A:aA_A; A:aAA_; A:_b; A:b_.
( 祭 ᨬ ન).
   㤥 ,  楯窠 x ᮣᮢ  樥 :b_c,
᫨ x=ab  a ਭ L(A). (㣨 ᫮, LR-뢮  
  த x_... = ab_... :: abc_... :: aA_... :: S_ .)
  ନ L(A:b) - ⢮ 楯祪, ᮣᮢ  
樥 A:b_, L(A) - 楯窨, ᮣᮢ   樥  A:_b,
  ࠢ A:b. 
    V(u) - ⢮ 権, ᮣᮢ  u. ,
 㭪 V - ⨢.
   ᫨  ⢮ V(u) 室   A:b_cd,    
A:bc_d ਭ V(uc). (c - ନ  ନ; b, d  -
᫥⥫쭮 (  ) ନ   ନ
). 㣨 権  A:b_d,   b  V(uc) . 
⠫   V(uc) 樨  C:_...,     
ନ C,  ⥪ ண ᮤন uc. ᫨ 
A:..._C... (C-ନ) ਭ   V(uc),    uc
ਭ L(C)  V(uc) 砥  ᥡ 樨    C:_...
  C-ࠢ ࠬ⨪.
   ࠦ: ,  㣨 権 V(uc)  ᮤন.
   V(e) ᮤন 樨 S:_... (S-砫 ᨬ),   ⠪
樨 A:_..., ᫨ ନ A 砥  ।⢥
᫥ _  , 㦥 祭  V(e).

   ਬ: ந 㭪 V  ࠬ⨪ S:A; A:aAA; A:b.
0  V(e)   = { S:_A; A:_aAA, A:_b }
1  V(A)   = { S:A_ }
2  V(a)   = { A:a_AA; A:_aAA, A:_b }    V(aa)=V(a); V(ab)=V(b);
3  V(b)   = { A:b_ }
4  V(aA)  = { A:aA_A; A:_aAA, A:_b }   V(aAa)=V(a);V(aAb)=V(b);
5  V(aAA) = { A:aAA_ }

   ,  ⮢  । LR(0)-ࠬ⨪.  
u - ᮤন  ⥪      LR-ࠧ,  V(u)-⢮
LR(0) 権, ᮣᮢ  u. ᫨ V(u) ᮤন  
 :x_ (x-᫥⥫쭮 ନ  ନ),  
u ਭ L(A:x)  ⨬ ᢥ⪠ x  A. ᫨  V(u)  
ন  A:..._a... (-ନ),  ⨬ ᤢ. 
  䫨 ᤢ-ᢥ⪠, ᫨   楯窨  u  
⨬   ᤢ,    ᢥ⪠.      䫨  ᢥ⪠-
ᢥ⪠, ᫨ ⨬ ᢥ⪨  ࠧ ࠢ.
   ࠬ⨪ 뢠 LR(0), ᫨   ﭨ ⥪ 
   LR-뢮      䫨⮢    ᤢ-ᢥ⪠    
ᢥ⪠-ᢥ⪠.
   ᬮ७  ࠬ⨪  LR(0)-ࠬ⨪. 
㭪 V ਭ 6 ࠧ 祭 (  
⮬⮬  6 ﭨﬨ).  ﭨ 0,2,4   ⮫쪮
ᤢ,  ﭨ 3 - ᢥ⪠  ࠢ A:b,  ﭨ 5  -
ᢥ⪠ A:aAA,  ﭨ 1 - ᢥ⪠ S:A - .. ᯥ譮  
襭 ࠧ.
   ⠥ ,   ந  ,  ࠧ騩
। LR(0)-몠. ⮡   祭 㭪樨  V
    ﭨ ⥪, 㤥 ࠭  
    ᨬ xi 祭 V  楯窥 (x0...xi).

⥪.ᤥ 
⥪. ( '#', 砫쭮 ﭨ )
横
. 롮  V ( ⥪.設.ﭨ ).⢨
. . "ᤢ" =>
. .    । ᨬ  (  ᨬ )
. . "ᢥ⪠" =>
. .   㤠 ࠢ  ࠢ  ⥪
. .    ᨬ :=   ࠢ
. . "ᯥ" =>
. .   ⮯( "ᯥ" )
.  롮
. ஥ ﭨ := V ( ⥪.設.ﭨ )
.  ﭨ := ஥ ﭨ . 室 [ ᨬ]
. ᫨  ﭨ = "訡"  ⮯( "訡" ) ᫨
. ⥪. (  ᨬ,  ﭨ )
 横

 LR(0)-  ࠬ⨪ 1) S:A; 2) A:aAA; 3) A:b.
       Ŀ
           ⢨           室        
         䨪                 A      a      b    
       Ĵ
       0  e    ᤢ        1      2      3      
       1  A    ᯥ        訡 訡 訡 
       2  a    ᤢ        4      2      3      
       3  b    ᢥ⪠ 3,  訡 訡 訡 
       4  aA   ᤢ        5      2      3      
       5  aAA  ᢥ⪠ 2,  訡 訡 訡 
       

                       LR(k)-ࠬ⨪

    롮  ᤢ  ᢥ⪮   LR(0)  ࠧ  
 ⮫쪮 ﭨ ⥪.  LR(k) ࠧ  뢠
⠪ k- ᨬ ᬮ७   室  楯窨
(⠪ 뢠 楯窠).   ᭮  ⮤  ᫥
⭮  㦤  ।饣  ࠣ,  
  ।.
   㤥    ⥪ ࠢ  ⠪  楯.
᫨  ࠢ 뢮 ਬ  뢮  wAu  :  wvu,    
{wv,FIRSTk(u)} ਭ  Lk(A:v),      {w,FIRSTk(u)}  -
Lk(A). ⢮  ⥪⮢,    砥 LR(0),  
      樨       楯窥.   
LR(k)-樥 : ࠢ ࠬ⨪  ⬥祭  樥
 楯    k. ⤥ ࠢ  楯窨
㤥 ⨪쭮 ⮩.
   㤥  ,    楯窠  x  ᮣᮢ    樥
:b_c|t ᫨  LR-뢮: x_yz = ab_yz :: abc_z :: aA_z
:: S_,  FIRSTk(z)=t. ࠢ ⨢ ᫥ ⢠
ﭨ Vk ᫥騥:
   Vk(e) ᮤন 樨 S:_a|e      ࠢ  S:a,  
S-砫 ᨬ.   樨 :_Ba|u  Vk(e),  
 ࠢ B:b  楯窨 x,  ਭ饩  FIRSTk(au),  
  Vk(e)  B:_b|x.
   ᫨  V(w) 室  A:b_cd|u,    A:bc_d|u
㤥 ਭ Vk(wc).      樨  :b_Cd|u  
Vk(wc),    ࠢ  C:f    楯窨   x,   ਭ饩
FIRSTk(du)    Vk(wc)  C:_f|x.

   ਬ: ந 㭪 V1  ࠬ⨪ S:A; A:AaAb|e.
0 V1(e)     = { S:_A|e; A:_AaAb|e,a, A:_|e,a }
1 V1(A)     = { S:A_|e, A:A_aAb|e,a }
2 V1(Aa)    = { A:Aa_Ab|e,a; A:_AaAb|a,b, A:_|a,b }
3 V1(AaA)   = { A:AaA_b|e,a, A:A_aAb|a,b }
4 V1(AaAa)  = { A:Aa_Ab|a,b; A:_AaAb|a,b, A:_|a,b }
5 V1(AaAb)  = { A:AaAb_|e,a }
6 V1(AaAaA) = { A:AaA_b|a,b A:A_aAb|a,b }   V1(AaAaAa)=V1(AaAa)
7 V1(AaAaAb)= { A:AaAb_|a,b }

( A:_AaAb|e,a - ᮪饭   LR(1)-権:
  A:_AaAb|e  A:_AaAb| )

   ᯮ㥬 ஥ ⢠ LR(k)-ﭨ   ࠧ
襭  ᤢ-ᢥ⪠.  u - ᮤন ⥪,  x  -
楯窠. 祢,  ᢥ⪠  ࠢ  A:b    
஢, ᫨ Vk(u) ᮤন  A:b_|x. 襭 
 ⨬ ᤢ ॡ ⭮, ᫨    ࠬ⨪
 e-ࠢ.  樨 A:b_c|t (c  ) ᤢ 
, ᫨ c 稭  ନ  x ਭ  FIRSTk(ct).
ଠ쭮 ,     ⥪  ᠬ    ᨬ
ࠢ  ࠢ, ⠢ ᫥ ᢥ. ᫨ c
稭  ନ (   A:b_Cd|t),   
  ⥪ ᨬ, ⠢ ᢥ  C,  ⮫쪮  
砥, ᫨ C  ஦  楯. ਬ,   
ﭨ V(e)={ S:_A|e; A:_AaAb|e,a, A:_|e,a }  ⨬ ᤢ
, ..  뢮  A ନ 楯祪  ஬ 
 ॡ ਬ ࠢ A:e  ନ A, 室饬
    楯窨.
   । ⢮ EFFk(x),  饥      ⮢
⢠ FIRSTk(x),  뢮    ନ    
 x (᫨  )     楯.   
ନ ᤢ ⨬, ᫨  ⢥ Vk(u)    
:b_c|t, c    x ਭ EFFk(ct).
   ࠬ⨪ 뢠 LR(k)-ࠬ⨪, ᫨    LR(k)
ﭨ  ᮤন  権 A:b_|u  B:c_d|v, ⠪ 
u ਭ  EFFk(dv).      ᮮ⢥  䫨
ᢥ⪠-ᢥ⪠, ᫨ d ,  䫨 ᤢ-ᢥ⪠,  ᫨
d  .
   LR(k)- ஥ 筮 LR(0). ⢨  ⢠
{ᤢ, ᢥ⪠, ᯥ, 訡}, 믮塞  ।  蠣
LR-ࠧ,  㭪  ﭨ ⥪ Vk(u)  楯窨
x:
  ᤢ, ᫨ A:b_c|t ᮤন  Vk(u), c!=e, x  EFF(ct);
  ᢥ⪠, ᫨ A:a_|x ᮤন  Vk(u);
  ᯥ, ᫨ S:A|e ᮤন  Vk(u);
  訡  ⠫ .

       LR(1)-  ࠬ⨪ S:A; A:AaAb|e.
   Ŀ
    䨪       ⢨              室       
            a      b      e       a      b           
   Ĵ
   0 e      .0, 訡 .0,  訡 訡 1     
   1 A        訡 ᯥ   2      訡 訡
   2 Aa     .0, .0, 訡  訡 訡 3     
   3 AaA        訡  4      5      訡
   4 AaAa   .0, .0, 訡  訡 訡 6     
   5 AaAb   .4, 訡 .4,  訡 訡 訡
   6 AaAaA      訡  4      7      訡
   7 AaAaAb .4, .4, 訡  訡 訡 訡
   
   ࠦ: ணࠬ  LR(k)-⠡.

    ࠪ⨪ LR(k)-ࠬ⨪  k>1  ਬ.   
  稭. ࢠ: 祭 讥 ᫮  LR(k)  
ﭨ. :   몠,  ।塞  LR(k)-ࠬ
,  LR(1)-ࠬ⨪;  ⮣,   
஢ -몠  LR(1)-ࠬ⨪.
   ᫮ LR(1)-ﭨ  ࠪ᪨    ࠬ⨪
⠪ 쬠 . LR(0) ᢮⢮ ⠪ ࠬ⨪  
।.  ࠪ⨪  ᥣ ᯮ ஬  
LR(0)    LR(1)  ⮤,      ﬨ  SLR(1)  
LALR(1).

                 SLR(1)  LALR(1) ࠬ⨪.

    ᭮   ⮤      . ந
⢮ ᪨  LR(0)-ﭨ  ࠬ⨪.  ᫨  
⢮  ᮤন 䫨⮢,   ਬ LR(0)-
.  ⠥ ࠧ 訥 䫨, ᬠ
  ᨬ  楯.  㣨  ᫮,  ஡㥬
ந LR(1)   ⢮ LR(0)-ﭨ.
    SLR(1) ࠬ⨪ (Simple LR(1) -  LR(1)-ࠬ
)  ࠧ襭 䫨⮢ ᯮ ⢮ FOLLOW(X)
- ⢮ ନ,  ᫥ X. ᫨  ﭨ
  A:b_, ᢥ⪠ ᪠, ᫨ ⮫쪮 
窠 ਭ FOLLOW(A).
   ࠬ⨪  SLR(1)-ࠬ⨪, ᫨    
LR(0) 権   ﭨ A:a_b    B:c_d  믮
  ᫥ ᫮:
      - b!=e, d!=e (䫨 , ॡ ᤢ);
      - b=d=e  FOLLOW(A)  ᥪ  FOLLOW(B) (䫨
        "ᢥ⪠/ᢥ⪠"   ࠭  ⮬  
        窨);
      - b=e, d<>e  FOLLOW(A)  ᥪ  EFF(tFOLLOW(B))
        (䫨 "ᤢ/ᢥ⪠"   ࠭   ⮬
        楯窨).
   ந LR(0)-ﭨ  ࠬ⨪ 䬥᪨  
: S:E; E:E+T|T; T:T*F|F; F:(E)|a.
0  V(e)  ={ S:_E; E:_E+T, E:_T, T:_T*F, T:_F, F_a, F:_(E) }
1  V(E)  ={ S:E_, E:E_+T }
2  V(T)  ={ E:T_, T:T_*F,
3  V(F)  ={ T:F_ }
4  V(a)  ={ F:a_ }
5  V(()  ={ F:(_E); E:_E+T, E:_T, T:_T*F, T:_F, F_a, F:_(E) }
6  V(E+) ={ E:E+_T; T:_T*F, T:_F, F_a, F:_(E) }
7  V(T*) ={ T:T*_F; F:_a, F:_(E) }
8  V((E) ={ F:(E_), E:E_+T }       (T=T;  (F=F;  (a=a;  ((=(
9  V(E+T)={ E:E+T_, T:T_*F }             E+F=F; E+a=a; E+(=(
10 V(T*F)={ T:T*F_ }                            T*a=a; T*(=(
11 V((E))={ F:(E)_ }               (+=+; +*=*

LR(0)-䫨   ﭨ 1,2,9, 
    1:  FOLLOW(S) = {},      FIRST(+T) = {+}
    2:  FOLLOW(E) = {+,),e}   FIRST(*F) = {*}
    9:  FOLLOW(E) = {+,),e}   FIRST(*F) = {*},
᫥⥫쭮, 䫨 ࠧ    ᯮ짮  SLR(1)
孨  ࠬ⨪  SLR(1)-ࠬ⨪.

   SLR(1)-  ࠬ⨪ 䬥᪨ 
Ŀ
         ⢨                 室                  
   e   +   *      (   )    +   *      (   )   E   T   F  
Ĵ
0                 4   5     1   2   3  
1             6                
2  1,E 1,E      1,E    7              
3  1,T 1,T 1,T     1,T                 
4  1,F 1,F 1,F     1,F                 
5                 4   5     8   2   3  
6                 4   5       9   3  
7                 4   5         10 
8             6         11       
9  3, 3,       3,    7              
10 3, 3, 3,     3,                 
11 3,F 3,F 3,F     3,F                 


   LALR(1)-⮤ (Look Ahead - 뢠 ।) 砥
 ᫥饬.   ⢥ LR(1)-権 ⭮襭  
⭮: 㤥    樨  묨,  ᫨
  ࠧ  ⮫쪮  楯窠.   ਬ,   樨
A:Aa_Ab|e  A:Aa_Ab|a . ந ᪮  
⢮ LR(1)-ﭨ  ꥤ ﭨ, 騥  
⢠  権.
   ਬ, LR(1) ﭨ 2  4 ࠬ⨪ S:A; A:AaAb|e 
:
    2 V1(Aa)    = { A:Aa_Ab|e,a;   A:_AaAb|a,b, A:_|a,b }
    4 V1(AaAa)  = { A:Aa_Ab|a,b;   A:_AaAb|a,b, A:_|a,b }
   ꥤ   ﭨ
  2+4 V1(Aa)    = { A:Aa_Ab|e,a,b; A:_AaAb|a,b, A:_|a,b }
  ﭨ 3,6  5,7 ⮩ ࠬ⨪.
   ᫨  祭  ⢮  ﭨ    ᮤন   LR(1)
䫨⮢, , ᫥⥫쭮,  ந LR(1)-,
 ,  ࠬ⨪  ᢮⢮ LALR(1).
   ਬ, ࠬ⨪ S:A; A:AaAb|e  LALR(1),

      LALR(1)-  ࠬ⨪ S:A; A:AaAb|e.
  Ŀ
     䨪       ⢨              室       
             a      b      e       a      b           
  Ĵ
    0 e      .0, 訡 .0,  訡 訡 1     
    1 A        訡 ᯥ   2      訡 訡
  2+4 Aa     .0, .0, 訡  訡 訡 3+6   
  3+6 AaA        訡  4      5+7    訡
  5+7 AaAb   .4, .4, .4,  訡 訡 訡
  

   ⨬,   ᫨ﭨ ᪨ LR(1)-ﭨ,  ࠧ
 ⮫쪮 楯窠, 砥  ⢮  
᪨ LR(0)-ﭨ,   樨 ண  ᫥
⢮ ⨬  楯祪  (!).  ⥫쭮,
SLR(1)  LALR(1) ⮤  ᯥ譮 ਬ  
⠡ . ⮤ LALR(1) ਬ   ப 
ࠬ⨪, 祬  SLR(1).      ⥬,    ⭮襭
FOLLOW(A), ਬ塞  ᫥ ⨬ 楯祪  
SLR(1)-⮤  ᯮ  㯭 ଠ -    
   ⥪ ࠢ  A:...  ⢨⥫쭮,  
 LALR(1)- ࠬ⨪,  ਭ騥  SLR(1).
   ࠦ: ,  ࠬ⨪  LALR(1),  
SLR(1): S:L=R|R; L:*R|a; R:L
   ࠦ:   ⨯ ਭ ᫥騥 ࠬ⨪?
 1) S:Aa|dAb|cb|dca;   A:c;
 2) S:Aa|dAb|Bb|dBa;   A:c; B:c
 3) S:Aa|dAb|Bb|dBa|c; A:c; B:c

                -  ਠ  樨 6 -
