my $parse = shift; my @stack; my $s0 = $parse->startstate; push(@stack, $s0); my $b = $parse->yylex(); FOREVER: { my $s = top(0); my $a = $b; switch ($parse->action[$s->state][$a]) { case "shift t" : my $t; $t->{state} = t; $t->{attr} = $a->{attr}; push($t); $b = $parse->yylex(); break; case "reduce A ->alpha" : my $r; $r->{attr} = $parse->Semantic{A ->alpha}->(top(|alpha|-1)->attr, ... , top(0)->attr); pop(|alpha|); # Saquemos length(alpha) elementos de la pila $r->{state} = $parse->goto[top(0)][A]; push($r); break; case "accept" : return ($s->attr); default : $parse->yyerror("syntax error"); } redo FOREVER; }
top(k)
devuelve el elemento que ocupa la
posición k
desde el top de la pila (esto es, está a profundidad k
).
La función pop(k)
extrae k
elementos de la pila.
La notación state->attr
hace referencia al atributo
asociado con cada estado. Denotamos por $Semantic{A->alpha}
el código de la acción asociada con la regla
.
Todos los analizadores LR comparten, salvo pequeñas
exepciones, el mismo algoritmo
de análisis. Lo que más los diferencia es la forma en
la que construyen las tablas.
En eyapp
la construcción de las tablas de acciones y gotos
se realiza mediante el algoritmo LALR.
1 pl@nereida:~/LEyapp/examples$ use_aSb.pl 2 ---------------------------------------- 3 In state 0: 4 Stack:[0] 5 aabb 6 Need token. Got >a< 7 Shift and go to state 2. 8 ---------------------------------------- 9 In state 2: 10 Stack:[0,2] 11 Need token. Got >a< 12 Shift and go to state 2. 13 ---------------------------------------- 14 In state 2: 15 Stack:[0,2,2] 16 Need token. Got >b< 17 Reduce using rule 1 (S --> /* empty */): S -> epsilon 18 Back to state 2, then go to state 4. 19 ---------------------------------------- 20 In state 4: 21 Stack:[0,2,2,4] 22 Shift and go to state 5. 23 ---------------------------------------- 24 In state 5: 25 Stack:[0,2,2,4,5] 26 Don't need token. 27 Reduce using rule 2 (S --> a S b): S -> a S b 28 Back to state 2, then go to state 4. 29 ---------------------------------------- 30 In state 4: 31 Stack:[0,2,4] 32 Need token. Got >b< 33 Shift and go to state 5. 34 ---------------------------------------- 35 In state 5: 36 Stack:[0,2,4,5] 37 Don't need token. 38 Reduce using rule 2 (S --> a S b): S -> a S b 39 Back to state 0, then go to state 1. 40 ---------------------------------------- 41 In state 1: 42 Stack:[0,1] 43 Need token. Got >< 44 Shift and go to state 3. 45 ---------------------------------------- 46 In state 3: 47 Stack:[0,1,3] 48 Don't need token. 49 Accept. |
pl@nereida:~/LEyapp/examples$ cat -n aSb.output 1 Rules: 2 ------ 3 0: $start -> S $end 4 1: S -> /* empty */ 5 2: S -> 'a' S 'b' 6 7 States: 8 ------- 9 State 0: 10 11 $start -> . S $end (Rule 0) 12 13 'a' shift, and go to state 2 14 15 $default reduce using rule 1 (S) 16 17 S go to state 1 18 19 State 1: 20 21 $start -> S . $end (Rule 0) 22 23 $end shift, and go to state 3 24 25 State 2: 26 27 S -> 'a' . S 'b' (Rule 2) 28 29 'a' shift, and go to state 2 30 31 $default reduce using rule 1 (S) 32 33 S go to state 4 34 35 State 3: 36 37 $start -> S $end . (Rule 0) 38 39 $default accept 40 41 State 4: 42 43 S -> 'a' S . 'b' (Rule 2) 44 45 'b' shift, and go to state 5 46 47 State 5: 48 49 S -> 'a' S 'b' . (Rule 2) 50 51 $default reduce using rule 2 (S) 52 53 54 Summary: 55 -------- 56 Number of rules : 3 57 Number of terminals : 3 58 Number of non-terminals : 2 59 Number of states : 6 |