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

• Como es habitual, $\vert x\vert$ denota la longitud de la cadena $x$.
• La función 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, el cual desde el punto de vista del programador esta asociado con el correspondiente símbolo de la parte derecha de la regla. Nótese que cada estado que está en la pila es el resultado de una transición con un símbolo. El atributo de ese símbolo es guardado en el objeto estado cada vez que ocurre una transición.

• Denotamos por Sem {reduce A -> alpha} el código de la acción semántica asociada con la regla $A \rightarrow \alpha$.

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.