Vorgegebene Grammatik (E aus technischen Gründen durch S ersetzt)

Regeln:
 S::=S+S  (R1)
 S::=S*S  (R2)
 S::=a    (R3)

Die Grammatik ist nicht eindeutig, und kann deswegen auch 
nicht LR(1)-Grammatik sein.

Das sieht man auch bei den LR(1)-Auskünften:

Ik(epsilon)= [S-> . S+S, ], [S-> . S*S, ], [S-> . a, ], [S-> . S+S, +], [S-> . S*S, +], [S-> . a, +], [S-> . S+S, *], [S-> . S*S, *], [S-> . a, *], 

Ik(S)= [S->S . +S, ], [S->S . *S, ], [S->S . +S, +], [S->S . *S, +], [S->S . +S, *], [S->S . *S, *], 

Ik(a)= [S->a . , ], [S->a . , +], [S->a . , *], 

Ik(S*)= [S->S* . S, ], [S->S* . S, +], [S->S* . S, *], [S-> . S+S, ], [S-> . S*S, ], [S-> . a, ], [S-> . S+S, +], [S-> . S*S, +], [S-> . a, +], [S-> . S+S, *], [S-> . S*S, *], [S-> . a, *],

Ik(S+)= [S->S+ . S, ], [S->S+ . S, +], [S->S+ . S, *], [S-> . S+S, ], [S-> . S*S, ], [S-> . a, ], [S-> . S+S, +], [S-> . S*S, +], [S-> . a, +], [S-> . S+S, *], [S-> . S*S, *], [S-> . a, *], 

Ik(S*S)= [S->S*S . , ], [S->S*S . , +], [S->S*S . , *], [S->S . +S, ], [S->S . *S, ], [S->S . +S, +], [S->S . *S, +], [S->S . +S, *], [S->S . *S, *], 

  --------> shift/reduce Konflikt für Lookahead '+':
          [S->S*S . , +]  ==> reduce R2
          [S->S . +S, +]  ==> shift

...


Wir müssen also eine eindeutige aequivalente Grammatik suchen,
das ist z.Bsp. die Grammatik mit 

Regeln:
 S::=S+E  (r1)
 S::=E    (r2)
 E::=E*a  (r3)
 E::=a    (r4)
k=1
Anfänge:
 Lk(S) = a  
 Lk(E) = a  
 Lk(+) = +  
 Lk(*) = *  
 Lk(a) = a  


ergeben sich die Zustände bzw. LR-1-Informationen:

(0) Ik(epsilon)= [S-> . S+E, ], [S-> . E, ], [S-> . S+E, +  ], [S-> . E, +  ], [E-> . E*a, ], [E-> . a, ], [E-> . E*a, +], [E-> . a, +], [E-> . E*a, *], [E-> . a, *], 

(1) Ik(S)= [S->S . +E, ], [S->S . +E, +  ], 

(2) Ik(E)= [S->E . , ], [S->E . , +  ], [E->E . *a, ], [E->E . *a, +], [E->E . *a, *], 

(3) Ik(a)= [E->a . , ], [E->a . , +], [E->a . , *], 

(4) Ik(S+)= [S->S+ . E, ], [S->S+ . E, +  ], [E-> . E*a, ], [E-> . a, ], [E-> . E*a, +], [E-> . a, +], [E-> . E*a, *], [E-> . a, *], 

(5) Ik(E*)= [E->E* . a, ], [E->E* . a, +], [E->E* . a, *], 


(6) Ik(S+E)= [S->S+E . , ], [S->S+E . , +  ], [E->E . *a, ], [E->E . *a, +], [E->E . *a, *], 

(7) Ik(E*a)= [E->E*a . , ], [E->E*a . , +], [E->E*a . , *], 


Ik(S+a)= Ik(a)
Ik(S+E*)= Ik(E*)
Ik(S+E*a)= Ik(E*a)


und somit Gotofunktion g, und Analyseaktionsfunktion f mit

g  S  E  a  +  *         f| eps |  a  |  +  |  *  |
-|--|--|--|--|--|        ---------------------------
0|1 |2 | 3|- |- |        0|     |  sh |     |     |
-|--|--|--|--|--|        ---------------------------
1|  |  |  | 4|  |        1|     |     | sh  |     |
-|--|--|--|--|--|        ---------------------------
2|  |  |  |  |5 |        2| r2  |     | r2  | sh  |
-|--|--|--|--|--|        ---------------------------
3|  |  |  |  |  |        3| r4  |     | r4  | r4  |
-|--|--|--|--|--|        ---------------------------
4|  | 6|3 |  |  |        4|     |  sh |     |     |
-|--|--|--|--|--|        ---------------------------
5|  |  |7 |  |  |        5|     |  sh |     |     |
-|--|--|--|--|--|        ---------------------------
6|  |  |  |  |5 |        6| r1  |     |  r1 | sh  |
-|--|--|--|--|--|        ---------------------------
7|  |  |  |  |  |        7| r3  |     |  r3 | r3  |


Analyse von a*a+a:

W=a*a+a, K=$0	f(0,a) = sh
W=*a+a, K=$0a	g(0,a) = 3
W=*a+a, K=$0a3	f(3,*) = r4
W=*a+a, K=$0E	g(0,E) = 2
W=*a+a, K=$0E2	f(2,*) = sh
W=a+a, K=$0E2*	g(2,*) = 5
W=a+a, K=$0E2*5	f(5,a) = sh
W=+a, K=$0E2*5a	g(5,a) = 7
W=+a, K=$0E2*5a7	f(7,+) = r3
W=+a, K=$0E	g(0,E) = 2
W=+a, K=$0E2	f(2,+) = r2
W=+a, K=$0S	g(0,S) = 1
W=+a, K=$0S1	f(1,+) = sh
W=a, K=$0S1+	g(1,+) = 4
W=a, K=$0S1+4	f(4,a) = sh
W=, K=$0S1+4a	g(4,a) = 3
W=, K=$0S1+4a3	f(3,eps) = r4
W=, K=$0S1+4E	g(4,E) = 6
W=, K=$0S1+4E6	f(6,eps) = r1
W=, K=$0S	-> fertig, a*a+a akzeptiert.