Algoritmo de Análisis LR

Asi pues la tabla de transiciones del autómata nos genera dos tablas: la tabla de acciones y la de saltos. El algoritmo de análisis sintáctico LR en el que se basa jison utiliza una pila y dos tablas para analizar la entrada. Como se ha visto, la tabla de acciones contiene cuatro tipo de acciones:
  1. Desplazar (shift)
  2. Reducir (reduce)
  3. Aceptar
  4. Error
El algoritmo utiliza una pila en la que se guardan los estados del autómata. De este modo se evita tener que ``comenzar'' el procesado de la forma sentencial derecha resultante después de una reducción (antiderivación).

Algoritmo 34.9.1   Análizador LR
 push(s0);
 b = yylex();
 for( ; ; ;) {
   s = top(0); a = b;
   switch (action[s][a]) {
     case "shift t" : 
       t.attr = a.attr;
       push(t); 
       b = yylex();
       break;
     case "reduce A ->alpha" : 
       eval(Sem{A -> alpha}(top(|alpha|-1).attr, ... , top(0).attr)); 
       pop(|alpha|); 
       push(goto[top(0)][A]); 
       break;
     case "accept" : return (1); 
     default : yyerror("syntax error");
   }
 }

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 jison la construcción de las tablas de acciones y gotos se realiza por defecto mediante el algoritmo LALR.

Casiano Rodríguez León
2013-04-23