Analizador sintáctico LR

Los analizadores sintácticos LR, también conocidos como Parser LR, son un tipo de dispositivos para manipular algunas gramáticas libres de contexto. Pertenecen a la familia de los analizadores ascendentes, ya que constituyen el árbol sintáctico de las hojas hacia la raíz. Utilizan la técnica de análisis por desplazamiento de reducción. Existen tres tipos de parsers LR: SLR (K), LALR (K) y LR (K) canónico. Un analizador LR consta de: 1. * Un programa conductor 2. * Una entrada 3. * Una salida 4. * Una tabla de análisis sintáctico, compuesta de dos partes (ACCIÓN y GOTO). Cabe acotar que el programa conductor es siempre igual, variando solo la tabla de análisis sintáctico para cada lenguaje. El algoritmo para reconocer cadenas es el siguiente: dado el primer carácter de la cadena y el estado inicial de la tabla, buscar qué acción corresponde en la tabla de acción. Si el estado es shiif n (n ∈ N), se coloca el carácter y el número de estado n en la pila, se lee el siguiente carácter y se repite el procedimiento, solo que esta vez buscando en el estado correspondiente. Si ACCIÓN = REDUCE n (n ∈ N), se sacan de la pila tantas tuplas (estado, símbolo) como el largo de la cola de la producción en el n-ésimo lugar y se reemplaza por la cabeza de esta producción. Se obtiene el nuevo estado al buscar en la tabla GOTO mediante el uso del número de estado que quedó en el tope de la pila, y el no terminal en la cabeza. En la tabla ACCIÓN también se encontrará ACEPTAR (que toma la cadena como válida) y se termina el análisis o ERROR (que rechaza la cadena).