Analizador sintáctico LALR

Zaraos Vázquez Jorge Alejandro

aleh.kz@hotmail.com

Resumen

En este reporte se definirán los conceptos teóricos

previos necesarios sobre la teoría de analizadores

sintácticos para luego dar paso a estos tomando como

punto de partida “parser LR” hasta llegar al objetivo

del reporte que es “parser LALR” su funcionamiento,

cuando y como se presenta además de su mejora en

comparación de los demás analizadores sintácticos.

1. Cuerpo

1.1. Marco teórico

1.1.1. Lookahead. Es el término genérico para un sub-

procedimiento que trata de prever los efectos de la

elección de una ramificación de variables para evaluar

o uno de sus valores. Los dos objetivos principales de

lookahead han de seleccionar una variable para evaluar

siguiente y el orden de valores para asignar a la misma.

Lookahead establece los símbolos máximos

entrantes que un analizador sintáctico puede utilizar

para decidir qué regla debe utilizar. Lookahead es

especialmente relevante para LL , LR , y analizadores

LALR, donde a menudo se indica explícitamente

mediante la colocación de la búsqueda hacia delante

para el nombre del algoritmo en paréntesis, tales como

LALR (1).

Los resultados de mirar hacia adelante se utiliza para

decidir la siguiente variable a evaluar y el orden de

valores para dar a esta variable. En particular, para

cualquier variable y el valor asignado, las estimaciones

de pre-análisis los efectos de establecer la variable de

ese valor. Lookahead tiene dos ventajas.

a). Ayuda a que el analizador tome la acción correcta

en caso de conflictos.

b). Elimina muchos estados duplicados y alivia la carga

de una pila adicional. [5]

1.1.2. Backtracking. El algoritmo de backtracking

enumera un conjunto de candidatos parciales que, en

principio, podría ser completado en varias formas de

dar todas las soluciones posibles para el problema

dado. La realización se lleva a cabo incrementalmente,

por una secuencia de pasos de extensión candidatas.

Conceptualmente, los candidatos parciales son los

nodos de una estructura de árbol, el árbol de búsqueda

potencial. Cada candidato parcial es el padre de los

candidatos que difieren de él por una única etapa de

extensión; las hojas del árbol son los candidatos

parciales que no se pueden extender más lejos. El

algoritmo de backtracking atraviesa este árbol de

búsqueda de forma recursiva, de la raíz hacia abajo, en

la profundidad de primer orden. En cada nodo C, el

algoritmo comprueba si c se puede completar a una

solución válida. Si no puede, el conjunto sub-árbol con

raíz en c se omite. De lo contrario, el algoritmo (1)

comprueba si C en sí es una solución válida, y si es así

lo informa al usuario, y (2) de forma recursiva enumera

todos los sub-árboles de C. Las dos pruebas y los hijos

de cada nodo se definen por los procedimientos

indicados por el usuario. [10]

1.1.3. Shift-reduce. En ciencias de la computación,

Shift-reduce parsing es una categoría de la tabla,

eficiente y orientada a bottom-up parsing métodos para

lenguajes de programación y otras notaciones definidas

formalmente por una gramática. [2]

Un shift-reduce explora y analiza el texto de

entrada en un paso hacia adelante en el texto, sin dar

marcha atrás esa dirección de avance es generalmente

de izquierda a derecha dentro de una línea, y de arriba

a abajo para las entradas de varias líneas. En cualquier

punto de este paso, el analizador se ha acumulado una

lista de sub-árboles o frases del texto de entrada que ya

se han analizado. Estos sub-árboles aún no se unen

entre sí porque el analizador aún no ha alcanzado el

extremo de la derecha del patrón de sintaxis que

combinarlos. [7]

Figura 1. Shift-reduce árbol de análisis construido con

bottom-up enumerados

Un desplazamiento y reducción, analizador haciendo

una combinación de pasos de desplazamiento y

reducir, de ahí el nombre.

a). Un Shift avanza paso a paso en el flujo de entrada

de un símbolo. Ese símbolo desplazado convierte en un

nuevo árbol de análisis de un único nodo.

b).Un Reduce paso se aplica una regla gramatical

completado a algunos de los últimos árboles de análisis

sintáctico, uniéndose a ellos juntos como un árbol con

un nuevo símbolo de raíz.

El analizador continúa con estos pasos hasta que

todos los de la entrada se ha consumido y todos los

árboles de análisis sintáctico se han reducido a un solo

árbol que representa una entrada legal entero. [7]

1.1.4. Analizador sintáctico descendente recursivo.

En ciencias de la computación, un parser descendente

recursivo es una especie de top-down parser construido

a partir de un conjunto de mutuamente

recursivas procedimientos, donde cada uno de

dichos procedimientos generalmente implementa una

de las normas de producción de la gramática. Así, la

estructura del programa resultante refleja fielmente la

de la gramática se reconoce.

Descendente recursivo con marcha atrás es una

técnica que determina el que la producción de usar al

tratar cada producción, a su vez. Descendente recursivo

con retroceso no se limita a las gramáticas LL (k), pero

no está garantizada para terminar a menos que la

gramática es LL (k). Incluso cuando se terminan, los

analizadores que utilizan descendente recursivo con

retrocesos pueden requerir un tiempo exponencial.

Programas de análisis predictivos se pueden

representar utilizando diagramas de transición para

cada símbolo no terminal, donde los bordes entre la

inicial y final de los estados son etiquetados por los

símbolos (terminales y no terminales) del lado derecho

de la regla de producción. [1]

1.1.5. Recursividad izquierda. Una gramática es

recursiva por la izquierda si podemos encontrar algo de

un no terminal que eventualmente derivar una forma

posicional.

a). Recursividad izquierda inmediata se produce en

reglas de la forma

A → Aα | β

Donde α y β son secuencias de no terminales y

terminales, y β no comienzan con A. Un analizador

sintáctico descendente recursivo sería caer en una

recursión infinita cuando se trata de analizar una

gramática que contiene esta regla.

b). Recursividad indirecta izquierda. Repetición

indirecta izquierda en su forma más simple se puede

definir como:

A → βα | C

A → Aβ | D

Posiblemente dando la derivación A ⇒ βα ⇒ Aβα ⇒

En términos más generales, para los no terminales

la repetición indirecta izquierda se puede

definir como de la forma:

…

Donde son secuencias de no terminales y

terminales. [6]

1.1.6. Bottom-up. Identifica y procesa a más bajo

nivel los pequeños detalles del texto en primer lugar,

antes de que sus estructuras de nivel medio y dejando

la estructura general de más alto nivel al último.

Figura 2. Árbol de análisis Bottom-up

El nombre de bottom-up viene del concepto de un

árbol de análisis sintáctico, en el que las partes más

detalladas se encuentran en la parte inferior espeso del

árbol, y las estructuras más grandes compuesta a partir

de ellos se encuentran en capas sucesivamente más

altas, hasta que en la parte superior o "raíz" del árbol

de una sola unidad describe toda la secuencia de

entrada. Un análisis sintáctico ascendente descubre y

procesa ese árbol desde el extremo inferior izquierdo, y

trabaja gradualmente su camino hacia arriba y hacia la

derecha. Bottom-up parsing espera perezosamente

hasta que haya explorado y analizado todas las partes

de alguna construcción antes de comprometerse con lo

que el constructo combinado. [2]

1.1.7. Reduce-reduce. Un error Reduce-reduce es una

causa cuando una gramática permite que dos o más

normas diferentes que se reduzcan al mismo tiempo,

por la misma razón. Cuando esto sucede, la gramática

se convierte en ambigüa desde un programa puede ser

interpretado más de una manera. Este error puede ser

causado cuando la misma regla se alcanza por más de

un camino. [l]

1.2. Parsers

1.2.1. LR. Son un tipo de analizadores de abajo hacia

arriba que manejan deterministas lenguajes libres de

contexto. Los analizadores LALR y SLR son variantes

comunes de los analizadores LR.

El nombre de LR es un acrónimo. La L significa que

el analizador lee el texto de entrada en una dirección

sin hacer copias de seguridad, esa dirección es

típicamente izquierda a derecha en cada línea, y de

arriba abajo a través de las líneas del fichero de entrada

completo. La R significa que el analizador produce

un invertido derivación invertida mas ala derecha, sino

que hace un análisis sintáctico de abajo hacia arriba, no

un análisis sintáctico LL arriba hacia abajo. El nombre

LR suele ir seguida de un calificativo numérico, como

en LR (1) o, a veces LR(k) . Para evitar dar marcha

atrás o adivinar, el analizador LR se deja mirar

adelante a k búsqueda hacia delante símbolos de

entrada antes de decidir cómo analizar los símbolos

anteriores.

Parsers LR son deterministas, sino que producen un

solo análisis sintáctico correcto sin conjeturas o

retroceso, en tiempo lineal, no son muy adecuados para

las lenguas humanas que necesitan métodos más

flexibles pero más lento. LR espera hasta que ha visto

todo un ejemplo de algún patrón gramática antes de

comprometerse con lo que ha encontrado. Un

analizador LL tiene que decidir o adivinar lo que está

viendo mucho antes, cuando sólo ha visto el símbolo

de la entrada de la izquierda de ese patrón. LR también

es mejor en el informe de errores. Detecta errores de

sintaxis lo antes posible en el flujo de entrada como sea

posible. [3]

1.2.2. SLR. Analizador SLR es un tipo de analizador

LR con pequeñas tablas de análisis sintáctico Al igual

que con otros tipos de analizador LR (1), un analizador

SLR es muy eficiente en la búsqueda de abajo hacia

arriba en un solo barrido de izquierda a derecha sobre

el flujo de entrada, sin conjeturas o retroceso.

Una gramática se dice que es SLR(1) si y solo si,

para cada estado S en SLR ninguna de las siguientes

condiciones es violada.

Para cualquier regla reducible A → a.Xb en el

estado s (donde X es algún terminal), no debe

existir alguna norma irreductible, B → a. en el

mismo estado S de manera que el seguimiento

conjunto de B contiene el terminal X. En

términos más formales, la intersección de

conjunto que contiene el terminal X y el

seguimiento conjunto de B debe estar

vacía. La violación de esta norma es un

conflicto de Shift-reduce.

Para cualquiera de los dos elementos

completos A → a. y B → b. en S, seguir

(A) y seguir (B) son disjuntos (su intersección

es el conjunto vacío). La violación de esta

norma es un conflicto de Reduce-reduce.

Generadores SLR calculan que lookahead por un

método de aproximación simple basada directamente

en la gramática, ignorando los detalles de estados del

analizador individuales y transiciones. Esto ignora el

contexto particular del estado actual del analizador. Si

un símbolo no terminal S se utiliza en varios lugares de

la gramática, SLR trata a aquellos lugares de la misma

forma individual en lugar de manejarlos de forma

individual.

El generador SLR funciona Siga (S), el conjunto de

todos los símbolos terminales que pueden seguir de

inmediato alguna ocurrencia de S. En la mesa de

análisis, cada reducción de S utiliza Siga (S) como (1)

conjunto lookahead LR. Tales conjuntos de

seguimiento también son utilizados por los generadores

de analizadores sintácticos LL arriba hacia abajo. Una

gramática que no tiene desplazamiento / reducción o

disminuir / reducir los conflictos cuando se utilizan

conjuntos Siguiente se denomina gramática SLR. [8]

1.3. LALR

Un analizador LALR o Look-Ahead LR parser es

una versión simplificada de un analizador LR canónico

para analizar (por separado y analizar) un texto de

acuerdo con un conjunto de reglas de producción

especificadas por una gramática formal para un equipo

idioma.

Formalmente el analizador LALR generalmente se

refiere a la LALR (1) analizador, denota lookahead una

razón, para resolver las diferencias entre los patrones

de reglas durante el análisis. Del mismo modo, hay una

(2) analizador LALR con dos tokens lookahead y

analizador LALR (k) con k-token lookup, pero estos

son poco frecuentes en el uso real.

El analizador LALR se basa en la (0) analizador

sintáctico LR, por lo que también puede ser denotado

LALR(1) = LA(1)LR(0) (1 señal de búsqueda hacia

delante, LR (0)) o, más generalmente LALR(k) =

LA(k)LR(0) (k tokens de lookahead, LR (0)). De

hecho, hay una de dos parámetros de la familia de

analizadores LA(k)LR(j) para todas las combinaciones

de j y k , se pueden derivar del analizador LR ( j + k ).

Al igual que con otros tipos de analizadores LR, un

analizador LALR es muy eficiente en la búsqueda

correcta bottom-up en un solo barrido de izquierda a

derecha sobre el flujo de entrada, ya que no es

necesario utilizar backtracking. Siendo analizador

lookahead por definición, siempre utiliza un

lookahead, con LALR (1) es el caso más común. [4]

1.3.1. Antecedentes históricos. Donald Knuth (1965).

Inventó el analizador sintáctico Izquierda a derecha, de

derivación mas ala derecha.

El parser LR puede reconocer cualquier lenguaje

libre de contexto determinista en tiempo lineal acotada.

La derivación más a la derecha tiene los requisitos

de memoria muy grandes y la implementación de un

analizador LR era impracticable debido a la limitada

memoria de los ordenadores en ese momento. Para

hacer frente a esta deficiencia, en 1969, Frank

DeRemer propuso dos versiones simplificadas del

analizador LR, a saber, la Look-Ahead LR (LALR) y

el analizdor SLR que tenía los requisitos de memoria

mucho más bajos en el costo de menos de

reconocimiento de idioma poder, con el analizador

LALR siendo la alternativa más poderosa. [5].

1.3.2. Aplicación. Debido a que el analizador LALR

realiza una derivación derecha en lugar de la

derivación más intuitiva izquierda, es muy difícil

entender cómo funciona.

Esto hace que el proceso de encontrar un correcto y

eficiente gramática LALR muy exigente y requiere

mucho tiempo. Por la misma razón, de notificación de

errores puede ser muy difícil debido a errores del

analizador LALR no siempre pueden ser interpretados

en los mensajes con los términos de alto nivel

significativo para el usuario final.

Cualquier tabla LR (k> 0) hace trivial al menos

enumerar los diferentes tokens que habría sido

opciones válidas cuando se produjo un error de

sintaxis, los mensajes de error de bajo nivel. Por esta

razón, el analizador sintactico descendente recursivo a

veces se prefiere sobre el analizador LALR.

Este analizador requiere más código escrito a mano

por su poder de idiomas menor reconocimiento. Sin

embargo, no tiene las dificultades especiales del

analizador LALR, ya que realiza la derivación de

izquierda. [9]

1.3.3. Conjunto lookahead. Para entender las

diferencias entre SLR y LALR, es importante entender

sus similitudes y cómo ambos hacen por

desplazamiento y reducción decisiones.

La única diferencia entre SLR y LALR es cómo sus

generadores calculan los conjuntos de búsqueda hacia

delante de símbolos de entrada que deben aparecer al

lado, siempre que algúna regla de producción se

encuentra y se reduce.

Generadores LALR calcular conjuntos de búsqueda

hacia delante por un método más preciso basado en la

exploración de la gráfica de estados del analizador y

sus transiciones. Este método considera el contexto

particular del estado actual del analizador. Se

personaliza el manejo de cada caso, la gramática de

algunas no terminales.

Los conjuntos de búsqueda hacia delante calculados

por los generadores LALR son un subconjunto de los

conjuntos aproximados calculados por los generadores

de SLR. Si una gramática tiene conflictos de mesa

utilizando SLR seguimiento de conjuntos, pero es libre

de conflictos cuando se utilizan LALR seguimiento

conjuntos, se llama una gramática LALR. [4]

2. Conclusión

Como conclusión antes de haber comprendido lo

que es parser LALR, primero se analizo varias

definiciones previas ya que sin ellas el tema no se

hubiera entendido del todo. Cada uno de los

analizadores sintácticos manejan lo que es el análisis

de izquierda derecha.

Tomando como referencia los analizadores

sintácticos declarados en el apartado 1.2

comparándolos con el apartado 1.3 parser LALR se

llega a la conclusión que este analizador necesita de

más código escrito a mano por sus idiomas.

Este analizador LALR analiza un texto de acuerdo

con un conjunto de reglas establecidas por una

gramática calculan conjuntos de búsqueda hacia

delante por un método más preciso basado en la

exploración de la gráfica de estados del analizador y

sus transiciones, esto es lo que lo hace diferente de los

demás y mejor analizador pero más complicado.

Este analizador posee varias ventajas como que la

recuperación de errores puede estar ya integrado en el

analizador, además de que manda mensajes de error

más generalizadas para poder ir al error, aparte de su

reconocimiento de construcciones del lenguaje sensible

al contexto todo esto ya esto incorporado.

Pero no todo es bueno como todo posee sus

desventajas de las que se puede decir que no es tan

fácil de usar al igual que este reporte se necesita de

conocimientos previos para entender mejor los

conceptos en el caso de LALR sería conocer, o tomarse

un tiempo para así manejarlo, en resumen podría llevar

un poco de tiempo de aprendizaje. De las ventajas que

ofrece de detección de errores puede ser un poco

complicado analizar si el error está en la gramática o

en el código, de ahí que si hay un error en el generador

de análisis esto puede ser difícil de arreglar.

Referencias

[1] Alfred Aho, Monica Lam, Ravi Sethi, Jeffrey Ullman

(1986). Compilers: Principles, Techniques, and Tools.

Addison Wesley. pp. 183.

[2] Alfred Aho, Monica Lam, Ravi Sethi, Jeffrey Ullman

(2006). Compilers: Principles, Techniques, and Tools (2 a

edición). Prentice Hall.

[3] Chapman, Nigel P (1987). LR Parsing: Theory and

practice. Cambridge University Press.

[4] Dick Grune and Ceriel J. H. Jacobs. Parsing Techniques:

A Practical Guide "9.7 LALR(1)". p. 302.

[5] Frank DeRemer, Thomas Pennello (1979), Efficient

Computation of LALR(1) Look-Ahead Sets. Sigplan Notices -

SIGPLAN, vol. 14, no. 8: 176–187.

[6] James Power. Department of computer science national

university of Ireland. Notes of formal language theory and

parsing. Ireland.

[7] Keith Cooper, Linda Torczon, Morgan Kaufman (2011).

Engineering to compiler (2ᵃ edición).

[8] Kenneth C. Compiler Construction: Principles and

practice. Louden.

[9] Knuth, Donald E. (July 1965). On the translation of

languages from left to right. Information and Control 8 (6):

607–639.

[10] Rossi Francesca, Beek Peter Van (Agosto 2006).

Constraint Satisfaction: An Emerging Paradigm. Handbook

of Constraint Programming. Amsterdam: Elsevier. P.14.