next up previous
Next: About this document ...



LR(1)-et csinálunk és majd rámutatunk, hogy mért nem LR(0).

$\mathbf{T_0=\epsilon}$ T0S=T1 T1a=T2
     
$S'\ensuremath{\rightarrow}\ensuremath{\mathbf{.}} S,\;\epsilon$ $S'\ensuremath{\rightarrow} S\ensuremath{\mathbf{.}} ,\;\epsilon$ $S\ensuremath{\rightarrow} Sa\ensuremath{\mathbf{.}} Sb,\;\epsilon\vert a$
$S\ensuremath{\rightarrow}\ensuremath{\mathbf{.}} SaSb,\;\epsilon\vert a$ $S\ensuremath{\rightarrow} S\ensuremath{\mathbf{.}} aSb,\;\epsilon\vert a$ $S\ensuremath{\rightarrow}\ensuremath{\mathbf{.}} SaSb,\;
b\vert a$
$S\ensuremath{\rightarrow}\ensuremath{\mathbf{.}} ,\;\epsilon\vert a$   $S\ensuremath{\rightarrow}\ensuremath{\mathbf{.}} ,\;a\vert b$
     
T2S=T3 T3a=T4 T3b=T5
     
$S\ensuremath{\rightarrow} SaS\ensuremath{\mathbf{.}} b,\;\epsilon\vert a$ $S\ensuremath{\rightarrow} Sa\ensuremath{\mathbf{.}} Sb,\;b\vert a$ $S\ensuremath{\rightarrow} SaSb\ensuremath{\mathbf{.}} ,\;\epsilon\vert a$
$S\ensuremath{\rightarrow} S\ensuremath{\mathbf{.}} aSb,\;b\vert a$ $S\ensuremath{\rightarrow}\ensuremath{\mathbf{.}} SaSb,\;
b\vert a$  
  $S\ensuremath{\rightarrow}\ensuremath{\mathbf{.}} ,\;b\vert a$  
     
T4S=T6 T6b=T7 T6a=T4
     
$S\ensuremath{\rightarrow} SaS\ensuremath{\mathbf{.}} b,\;b\vert a$ $S\ensuremath{\rightarrow} SaSb\ensuremath{\mathbf{.}} ,\;b\vert a$  
$S\ensuremath{\rightarrow} S\ensuremath{\mathbf{.}} aSb,\;b\vert a$    



Ha LR(0)-val próbálkoztunk volna, akkor láttuk volna, hogy nem jön ki, például már T1-ben is ellentmondás lenne: $S'\ensuremath{\rightarrow} S\ensuremath{\mathbf{.}} $ szerint Accept lenne, a másik szerint meg Shift.



A táblázat:



  a b $\epsilon$ S a b
T0 2   2 T1    
T1 S   A   T2  
T2 2 2   T3    
T3 S S     T4 T5
T4 2 2   T6    
T5 1   1      
T6 S S     T4 T7
T7 1 1        




És egy elemzés:
$(T_0\;,\;ababab\;,\;\epsilon)\ensuremath{\rightarrow} $
$(T_0ST_1\;,\;ababab\;,\;2)\ensuremath{\rightarrow} $
$(T_0ST_1aT_2\;,\;babab\;,\;2)\ensuremath{\rightarrow} $
$(T_0ST_1aT_2ST_3\;,\;babab\;,\;22)\ensuremath{\rightarrow} $
$(T_0ST_1aT_2ST_3bT_5\;,\;abab\;,\;22)\ensuremath{\rightarrow} $
$(T_0ST_1\;,\;abab\;,\;221)\ensuremath{\rightarrow} $
$(T_0ST_1aT_2\;,\;bab\;,\;221)\ensuremath{\rightarrow} $
$(T_0ST_1aT_2ST_3\;,\;bab\;,\;2212)\ensuremath{\rightarrow} $
$(T_0ST_1aT_2ST_3bT_5\;,\;ab\;,\;2212)\ensuremath{\rightarrow} $
$(T_0ST_1\;,\;ab\;,\;22121)\ensuremath{\rightarrow} $
$(T_0ST_1aT_2\;,\;b\;,\;22121)\ensuremath{\rightarrow} $
$(T_0ST_1aT_2ST_3\;,\;b\;,\;221212)\ensuremath{\rightarrow} $
$(T_0ST_1aT_2ST_3bT_5\;,\;\epsilon\;,\;221212)\ensuremath{\rightarrow} $
$(T_0ST_1\;,\;\epsilon\;,\;2212121)\ensuremath{\rightarrow} $Accept.



 
next up previous
Next: About this document ...
Judit Csima
2000-04-27