Traductores e Intérpretes UCAB : Algoritmo de Análisis Sintáctico LR
This page last changed on Jan 27, 2008 by carlos.gonzalez.
El algoritmo consta de una entrada, una salida, una pila, un programa conductor y una tabla de análisis sintáctico con dos partes (acción y transición). Lo que varía en todos los métodos LR es la tabla de análisis. Cada Xi es un símbolo gramatical y cada Si es un símbolo llamado estado. La tabla consta de dos partes, la función acción, que indica una acción del analizador y la función transición, que indica las transiciones entre estados. La operaciones se basan en el estado en el tope de la pila Sm y el símbolo aI de la entrada; existen cuatro operaciones:
AlgoritmoENTRADA: una cadena w y una tabla para la gramática G SALIDA: si w pertenece a L(G), es un análisis ascendente de w, de lo contrario se indica error MÉTODO: inicialmente la pila contiene So, donde So es el estado inicial y w$ esta en el buffer. apuntar ae al primer símbolo de w$ apuntar ae al primer símbolo de w$ while(1) { if (accion[S,a]==desplazar S') { Ejemplo:
y la tabla: para la cadena w = id * id + id la corrida sería la siguiente: ![]() ![]() ![]() |
![]() |
Document generated by Confluence on Oct 04, 2010 11:24 |