Algoritmo de Análisis LR

Algoritmo 8.25.1 Análizador LR

 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;
 }

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