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 yapp 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 35.5.1   Análizador LR

push(s0);
 b = yylex();
 for( ; ; ;) {
   s = top(0); a = b;
   switch (action[s][a]) {
     case "shift t" : 
       push(t); 
       b = yylex();
       break;
     case "reduce A ->alpha" : 
       eval(Sub{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. Denotamos por sub_{reduce A -> alpha} el código de la acción 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 yapp la construcción de las tablas de acciones y gotos se realiza mediante el algoritmo LALR.