En informática , los analizadores LR son un tipo de analizador ascendente que analiza lenguajes deterministas libres de contexto en tiempo lineal. [1] Hay varias variantes de análisis de LR: SLR analizadores , LALR analizadores , Canonical LR (1) analizadores , LR Minimal (1) programas de análisis , GLR analizadores . Los analizadores sintácticos LR pueden ser generados por un generador de analizadores sintácticos a partir de una gramática formal que define la sintaxis del lenguaje que se va a analizar. Son muy utilizados para el procesamiento de lenguajes informáticos..
Un LR analizador ( L eft a derecha, R derivación ightmost a la inversa) lee el texto de entrada de izquierda a derecha sin realizar copias de seguridad (esto es cierto para la mayoría de programas de análisis), y produce una derivación por la derecha a la inversa: se hace un bottom-up analizar : no un análisis LL de arriba hacia abajo o un análisis ad-hoc. El nombre LR suele ir seguido de un calificador numérico, como en LR (1) o, a veces, LR ( k ) . Para evitar retroceder o adivinar, el analizador LR puede mirar adelante a k símbolos de entrada de búsqueda anticipada antes de decidir cómo analizar los símbolos anteriores. Normalmente, k es 1 y no se menciona. El nombre LR suele ir precedido de otros calificadores, como en SLR y LALR . La LR ( k ) condición para una gramática fue sugerido por Knuth para representar "traducible de izquierda a derecha con cota k ". [1]
Los analizadores sintácticos LR son deterministas; producen un solo análisis correcto sin conjeturas ni retrocesos, en tiempo lineal. Esto es ideal para lenguajes de computadora, pero los analizadores LR no son adecuados para lenguajes humanos que necesitan métodos más flexibles pero inevitablemente más lentos. Algunos métodos que pueden analizar lenguajes arbitrarios libres de contexto (p. Ej., Cocke – Younger – Kasami , Earley , GLR ) tienen el peor rendimiento de tiempo O ( n 3 ). Otros métodos que retroceden o producen múltiples análisis pueden incluso llevar un tiempo exponencial cuando adivinan mal. [2]
Las propiedades anteriores de L , R , y k son en realidad compartidos por todos los programas de análisis de reducción por desplazamiento , incluyendo los analizadores de precedencia . Pero por convención, el nombre LR representa la forma de análisis sintáctica inventada por Donald Knuth y excluye los métodos de precedencia anteriores menos potentes (por ejemplo , analizador de precedencia de operador ). [1] Los analizadores sintácticos LR pueden manejar una gama más amplia de lenguajes y gramáticas que los analizadores sintácticos de precedencia o el análisis sintáctico LL descendente . [3] Esto se debe a que el analizador LR espera hasta que ha visto una instancia completa de algún patrón gramatical antes de comprometerse con lo que ha encontrado. Un analizador LL tiene que decidir o adivinar lo que ve mucho antes, cuando solo ha visto el símbolo de entrada más a la izquierda de ese patrón.
Descripción general
Árbol de análisis de abajo hacia arriba, por ejemplo A * 2 + 1
Un analizador LR escanea y analiza el texto de entrada en una pasada hacia adelante sobre el texto. El analizador genera el árbol de análisis de forma incremental, de abajo hacia arriba y de izquierda a derecha, sin adivinar ni retroceder. En cada punto de esta pasada, el analizador ha acumulado una lista de subárboles o frases del texto de entrada que ya se han analizado. Esos subárboles aún no están unidos porque el analizador aún no ha alcanzado el extremo derecho del patrón de sintaxis que los combinará.
En el paso 6 de un análisis de ejemplo, sólo se ha analizado "A * 2", de forma incompleta. Solo existe la esquina inferior izquierda sombreada del árbol de análisis. Ninguno de los nodos del árbol de análisis con el número 7 o superior existe todavía. Los nodos 3, 4 y 6 son las raíces de subárboles aislados para la variable A, el operador * y el número 2, respectivamente. Estos tres nodos raíz se mantienen temporalmente en una pila de análisis. La parte restante sin analizar del flujo de entrada es "+ 1".
Cambiar y reducir acciones
Al igual que con otros analizadores de reducción de cambios, un analizador de LR funciona mediante una combinación de pasos de cambio y pasos de reducción.
- Un paso de cambio avanza en el flujo de entrada en un símbolo. Ese símbolo cambiado se convierte en un nuevo árbol de análisis de un solo nodo.
- Un paso Reducir aplica una regla gramatical completa a algunos de los árboles de análisis recientes, uniéndolos como un árbol con un nuevo símbolo de raíz.
Si la entrada no tiene errores de sintaxis, el analizador continúa con estos pasos hasta que se ha consumido toda la entrada y todos los árboles de análisis se han reducido a un solo árbol que representa una entrada legal completa.
Los analizadores sintácticos LR se diferencian de otros analizadores sintácticos de reducción de cambios en la forma en que deciden cuándo reducir y cómo elegir entre reglas con terminaciones similares. Pero las decisiones finales y la secuencia de pasos de cambio o reducción son las mismas.
Gran parte de la eficiencia del analizador sintáctico LR se debe a que es determinista. Para evitar adivinar, el analizador LR a menudo mira hacia adelante (hacia la derecha) en el siguiente símbolo escaneado, antes de decidir qué hacer con los símbolos escaneados previamente. El analizador léxico trabaja con uno o más símbolos antes que el analizador. Los símbolos de anticipación son el "contexto de la derecha" para la decisión de análisis. [4]
Pila de análisis ascendente
Al igual que otros analizadores de reducción de cambios, un analizador LR espera perezosamente hasta que ha escaneado y analizado todas las partes de alguna construcción antes de comprometerse con la construcción combinada. Luego, el analizador actúa inmediatamente sobre la combinación en lugar de esperar más. En el ejemplo del árbol de análisis sintáctico, la frase A se reduce a Valor y luego a Productos en los pasos 1-3 tan pronto como se ve el avance *, en lugar de esperar más tarde para organizar esas partes del árbol de análisis sintáctico. Las decisiones sobre cómo manejar A se basan solo en lo que el analizador y el analizador ya han visto, sin considerar las cosas que aparecen mucho más tarde a la derecha.
Las reducciones reorganizan los elementos analizados más recientemente, inmediatamente a la izquierda del símbolo de anticipación. Entonces, la lista de cosas ya analizadas actúa como una pila . Esta pila de análisis crece hacia la derecha. La base o parte inferior de la pila está a la izquierda y contiene el fragmento de análisis más antiguo y más a la izquierda. Cada paso de reducción actúa solo en los fragmentos de análisis más nuevos y más a la derecha. (Esta pila de análisis acumulativa es muy diferente de la pila de análisis predictiva que crece hacia la izquierda que utilizan los analizadores de arriba hacia abajo ).
Pasos de análisis de abajo hacia arriba, por ejemplo, A * 2 + 1
Paso | Analizar pila | Sin analizar | Cambiar / Reducir |
---|---|---|---|
0 | vacío | A * 2 + 1 | cambiar |
1 | identificación | * 2 + 1 | Valor → id |
2 | Valor | * 2 + 1 | Productos → Valor |
3 | Productos | * 2 + 1 | cambiar |
4 | Productos * | 2 + 1 | cambiar |
5 | Productos * int | + 1 | Valor → int |
6 | Productos * Valor | + 1 | Productos → Productos * Valor |
7 | Productos | + 1 | Sumas → Productos |
8 | Sumas | + 1 | cambiar |
9 | Sumas + | 1 | cambiar |
10 | Sumas + int | eof | Valor → int |
11 | Sumas + Valor | eof | Productos → Valor |
12 | Sumas + Productos | eof | Sumas → Sumas + Productos |
13 | Sumas | eof | hecho |
El paso 6 aplica una regla gramatical con varias partes:
- Productos → Productos * Valor
Esto coincide con la parte superior de la pila que contiene las frases analizadas "... Productos * Valor". El paso de reducción reemplaza esta instancia del lado derecho de la regla, "Productos * Valor" por el símbolo del lado izquierdo de la regla, aquí un Productos más grande. Si el analizador genera árboles de análisis completo, los tres árboles para Productos internos, * y Valor se combinan mediante una nueva raíz de árbol para Productos. De lo contrario, los detalles semánticos de los Productos y el Valor internos se envían a algún paso del compilador posterior, o se combinan y guardan en el nuevo símbolo de Productos. [5]
Pasos de análisis LR, por ejemplo, A * 2 + 1
En los analizadores sintácticos LR, las decisiones de cambio y reducción se basan potencialmente en la pila completa de todo lo que se ha analizado previamente, no solo en un único símbolo de pila superior. Si se hace de una manera poco inteligente, eso podría llevar a analizadores muy lentos que se vuelven cada vez más lentos para entradas más largas. Los analizadores sintácticos LR hacen esto con velocidad constante, al resumir toda la información relevante del contexto izquierdo en un solo número llamado estado del analizador sintáctico LR (0) . Para cada método de análisis gramatical y LR, hay un número fijo (finito) de tales estados. Además de contener los símbolos ya analizados, la pila de análisis también recuerda los números de estado alcanzados por todo hasta esos puntos.
En cada paso de análisis, todo el texto de entrada se divide en una pila de frases analizadas previamente, un símbolo de búsqueda anticipada actual y el texto restante sin analizar. La siguiente acción del analizador está determinada por su número de estado actual LR (0) (más a la derecha en la pila) y el símbolo de anticipación. En los pasos siguientes, todos los detalles en negro son exactamente los mismos que en otros analizadores sintácticos con reducción de cambios que no son LR. Las pilas de analizador LR agregan la información de estado en violeta, resumiendo las frases negras a su izquierda en la pila y qué posibilidades de sintaxis esperar a continuación. Los usuarios de un analizador LR generalmente pueden ignorar la información de estado. Estos estados se explican en una sección posterior.
Paso | Estado de la pila de análisis [ estado del símbolo ] * | Mirar hacia adelante | Sin escanear | Acción del analizador | Regla gramátical | Estado siguiente |
---|---|---|---|---|---|---|
0 | 0 | identificación | * 2 + 1 | cambiar | 9 | |
1 | 0 id 9 | * | 2 + 1 | reducir | Valor → id | 7 |
2 | 0 Valor 7 | * | 2 + 1 | reducir | Productos → Valor | 4 |
3 | 0 Productos 4 | * | 2 + 1 | cambiar | 5 | |
4 | 0 Productos 4 * 5 | En t | + 1 | cambiar | 8 | |
5 | 0 Productos 4 * 5 int 8 | + | 1 | reducir | Valor → int | 6 |
6 | 0 Productos 4 * 5 Valor 6 | + | 1 | reducir | Productos → Productos * Valor | 4 |
7 | 0 Productos 4 | + | 1 | reducir | Sumas → Productos | 1 |
8 | 0 Sumas 1 | + | 1 | cambiar | 2 | |
9 | 0 Sumas 1 + 2 | En t | eof | cambiar | 8 | |
10 | 0 Sumas 1 + 2 int 8 | eof | reducir | Valor → int | 7 | |
11 | 0 Sumas 1 + 2 Valor 7 | eof | reducir | Productos → Valor | 3 | |
12 | 0 Sumas 1 + 2 Productos 3 | eof | reducir | Sumas → Sumas + Productos | 1 | |
13 | 0 Sumas 1 | eof | hecho |
En el paso inicial 0, el flujo de entrada "A * 2 + 1" se divide en
- una sección vacía en la pila de análisis,
- texto anticipado "A" escaneado como un símbolo de identificación , y
- el texto restante sin escanear "* 2 + 1".
La pila de análisis comienza manteniendo solo el estado inicial 0. Cuando el estado 0 ve el ID de búsqueda anticipada , sabe cambiar ese ID a la pila, escanear el siguiente símbolo de entrada * y avanzar al estado 9.
En el paso 4, el flujo de entrada total "A * 2 + 1" se divide actualmente en
- la sección analizada "A *" con 2 frases apiladas Productos y * ,
- texto anticipado "2" escaneado como un símbolo int , y
- el texto restante sin escanear "+ 1".
Los estados correspondientes a las frases apiladas son 0, 4 y 5. El estado actual, más a la derecha en la pila es el estado 5. Cuando el estado 5 ve el int de búsqueda anticipada , sabe cambiar ese int a la pila como su propia frase, y escanee el siguiente símbolo de entrada + y avance al estado 8.
En el paso 12, se ha consumido todo el flujo de entrada, pero solo se ha organizado parcialmente. El estado actual es 3. Cuando el estado 3 ve el eof anticipado , sabe aplicar la regla gramatical completa
- Sumas → Sumas + Productos
combinando las tres frases más a la derecha de la pila para Sumas, + y Productos en una sola cosa. El estado 3 en sí mismo no sabe cuál debería ser el siguiente estado. Esto se encuentra volviendo al estado 0, justo a la izquierda de la frase que se reduce. Cuando el estado 0 ve esta nueva instancia completa de Sums, avanza al estado 1 (nuevamente). Esta consulta de estados más antiguos es la razón por la que se mantienen en la pila, en lugar de mantener solo el estado actual.
Gramática para el ejemplo A * 2 + 1
Los analizadores sintácticos LR se construyen a partir de una gramática que define formalmente la sintaxis del lenguaje de entrada como un conjunto de patrones. La gramática no cubre todas las reglas del lenguaje, como el tamaño de los números o el uso consistente de nombres y sus definiciones en el contexto de todo el programa. Los analizadores sintácticos LR utilizan una gramática libre de contexto que se ocupa únicamente de los patrones locales de símbolos.
La gramática de ejemplo que se usa aquí es un pequeño subconjunto del lenguaje Java o C:
- r0: Objetivo → Sumas eof
- r1: Sumas → Sumas + Productos
- r2: Sumas → Productos
- r3: Productos → Productos * Valor
- r4: Productos → Valor
- r5: Valor → int
- r6: Valor → id
Los símbolos terminales de la gramática son los símbolos de varios caracteres o 'tokens' que un escáner léxico encuentra en el flujo de entrada . Aquí, estos incluyen + * e int para cualquier constante entera, id para cualquier nombre de identificador y eof para el final del archivo de entrada. A la gramática no le importan los valores int o la ortografía id , ni los espacios en blanco o los saltos de línea. La gramática usa estos símbolos terminales pero no los define. Siempre son nodos de hojas (en el extremo inferior tupido) del árbol de análisis.
Los términos en mayúscula como Sums son símbolos no terminales . Estos son nombres para conceptos o patrones en el idioma. Se definen en la gramática y nunca aparecen en el flujo de entrada. Siempre son nodos internos (arriba de la parte inferior) del árbol de análisis. Solo ocurren como resultado de que el analizador aplica alguna regla gramatical. Algunos no terminales se definen con dos o más reglas; estos son patrones alternativos. Las reglas pueden referirse a sí mismas, que se denominan recursivas . Esta gramática usa reglas recursivas para manejar operadores matemáticos repetidos. Las gramáticas para lenguajes completos usan reglas recursivas para manejar listas, expresiones entre paréntesis y declaraciones anidadas.
Cualquier lenguaje informático dado puede describirse mediante varias gramáticas diferentes. Un analizador LR (1) puede manejar muchas pero no todas las gramáticas comunes. Por lo general, es posible modificar manualmente una gramática para que se ajuste a las limitaciones del análisis sintáctico LR (1) y la herramienta generadora.
La gramática de un analizador LR debe ser inequívoca en sí misma, o debe ser aumentada por reglas de precedencia de desempate. Esto significa que solo hay una forma correcta de aplicar la gramática a un ejemplo legal dado del idioma, lo que da como resultado un árbol de análisis único con un solo significado y una secuencia única de acciones de cambio / reducción para ese ejemplo. El análisis sintáctico LR no es una técnica útil para lenguajes humanos con gramáticas ambiguas que dependen de la interacción de palabras. Los lenguajes humanos se manejan mejor con analizadores como el analizador LR generalizado , el analizador Earley o el algoritmo CYK que pueden calcular simultáneamente todos los árboles de análisis sintáctico posibles en una sola pasada.
Parse tabla para la gramática de ejemplo
La mayoría de los analizadores de LR están controlados por tablas. El código del programa del analizador es un bucle genérico simple que es el mismo para todas las gramáticas y lenguajes. El conocimiento de la gramática y sus implicaciones sintácticas se codifican en tablas de datos invariables llamadas tablas de análisis sintáctico (o tablas de análisis sintáctico ). Las entradas en una tabla muestran si cambiar o reducir (y por qué regla gramatical), para cada combinación legal de estado del analizador y símbolo de anticipación. Las tablas de análisis también indican cómo calcular el siguiente estado, dado solo un estado actual y un siguiente símbolo.
Las tablas de análisis son mucho más grandes que la gramática. Las tablas LR son difíciles de calcular a mano con precisión para gramáticas grandes. Por lo tanto, se derivan mecánicamente de la gramática mediante alguna herramienta generadora de analizadores sintácticos como Bison . [6]
Dependiendo de cómo se generen los estados y la tabla de análisis, el analizador resultante se denomina analizador SLR (LR simple) , analizador LALR (LR anticipado) o analizador LR canónico . Los analizadores LALR manejan más gramáticas que los analizadores SLR. Los analizadores sintácticos canónicos LR manejan aún más gramáticas, pero usan muchos más estados y tablas mucho más grandes. La gramática de ejemplo es SLR.
Las tablas de análisis sintáctico LR son bidimensionales. Cada estado actual del analizador LR (0) tiene su propia fila. Cada símbolo siguiente posible tiene su propia columna. Algunas combinaciones de estado y siguiente símbolo no son posibles para flujos de entrada válidos. Estas celdas en blanco desencadenan mensajes de error de sintaxis.
La mitad de Acción izquierda de la tabla tiene columnas para símbolos de terminales de búsqueda anticipada. Estas celdas determinan si la siguiente acción del analizador es cambiar (al estado n ) o reducir (según la regla gramatical r n ).
La mitad derecha de la tabla Ir a tiene columnas para símbolos no terminales. Estas celdas muestran a qué estado avanzar, después de que el lado izquierdo de alguna reducción haya creado una nueva instancia esperada de ese símbolo. Esto es como una acción de cambio pero para no terminales; el símbolo de la terminal de búsqueda anticipada no se modifica.
La columna de la tabla "Reglas actuales" documenta el significado y las posibilidades de sintaxis para cada estado, según lo elaborado por el generador del analizador sintáctico. No se incluye en las tablas reales utilizadas en el momento del análisis. El marcador • (punto rosa) muestra dónde está el analizador ahora, dentro de algunas reglas gramaticales parcialmente reconocidas. Las cosas a la izquierda de • se han analizado, y las cosas a la derecha se esperan pronto. Un estado tiene varias de estas reglas actuales si el analizador aún no ha reducido las posibilidades a una sola regla.
Curr | Mirar hacia el futuro | LHS Goto | ||||||||
---|---|---|---|---|---|---|---|---|---|---|
Expresar | Reglas actuales | En t | identificación | * | + | eof | Sumas | Productos | Valor | |
0 | Objetivo → • Sumas eof | 8 | 9 | 1 | 4 | 7 | ||||
1 | Objetivo → Sumas • e de Sumas → Sumas • + Productos | 2 | hecho | |||||||
2 | Sumas → Sumas + • Productos | 8 | 9 | 3 | 7 | |||||
3 | Sumas → Sumas + Productos • Productos → Productos • * Valor | 5 | r1 | r1 | ||||||
4 | Sumas → Productos • Productos → Productos • * Valor | 5 | r2 | r2 | ||||||
5 | Productos → Productos * • Valor | 8 | 9 | 6 | ||||||
6 | Productos → Productos * Valor • | r3 | r3 | r3 | ||||||
7 | Productos → Valor • | r4 | r4 | r4 | ||||||
8 | Valor → int • | r5 | r5 | r5 | ||||||
9 | Valor → id • | r6 | r6 | r6 |
En el estado 2 anterior, el analizador acaba de encontrar y desplazar el + de la regla gramatical
- r1: Sumas → Sumas + • Productos
La siguiente frase esperada es Productos. Los productos comienzan con los símbolos de terminal int o id . Si la búsqueda anticipada es cualquiera de esos, el analizador los cambia y avanza al estado 8 o 9, respectivamente. Cuando se ha encontrado un producto, el analizador avanza al estado 3 para acumular la lista completa de sumandos y encontrar el final de la regla r0. Los productos también pueden comenzar con un valor no terminal. Para cualquier otra búsqueda anticipada o no terminal, el analizador anuncia un error de sintaxis.
En el estado 3, el analizador acaba de encontrar una frase de Productos, que podría ser de dos posibles reglas gramaticales:
- r1: Sumas → Sumas + Productos •
- r3: Productos → Productos • * Valor
La elección entre r1 y r3 no se puede decidir simplemente mirando hacia atrás en frases anteriores. El analizador tiene que comprobar el símbolo de anticipación para saber qué hacer. Si la búsqueda anticipada es * , está en la regla 3, por lo que el analizador cambia en * y avanza al estado 5. Si la búsqueda anticipada es eof , está al final de la regla 1 y la regla 0, por lo que el analizador está listo.
En el estado 9 anterior, todas las celdas sin blanco y sin error son para la misma reducción r6. Algunos analizadores ahorran tiempo y espacio en la tabla al no marcar el símbolo de anticipación en estos casos simples. Los errores de sintaxis se detectan un poco más tarde, después de algunas reducciones inofensivas, pero aún antes de la siguiente acción de cambio o decisión del analizador.
Las celdas individuales de la tabla no deben contener múltiples acciones alternativas, de lo contrario, el analizador no sería determinista con conjeturas y retrocesos. Si la gramática no es LR (1), algunas celdas tendrán conflictos de cambio / reducción entre una posible acción de cambio y acción de reducción, o reducirán / reducirán conflictos entre múltiples reglas gramaticales. Los analizadores sintácticos LR (k) resuelven estos conflictos (cuando sea posible) comprobando símbolos de anticipación adicionales más allá del primero.
Bucle de analizador LR
El analizador LR comienza con una pila de análisis casi vacía que contiene solo el estado de inicio 0, y con la búsqueda anticipada que contiene el primer símbolo escaneado del flujo de entrada. Luego, el analizador repite el siguiente paso de bucle hasta que termina o se atasca en un error de sintaxis:
El estado superior en la pila de análisis es un estado s , y la búsqueda anticipada actual es un símbolo de terminal t . Busque la siguiente acción del analizador de la fila sy la columna t de la tabla Lookahead Action. Esa acción es Mayús, Reducir, Terminado o Error:
- Cambio n :
- Mueva la terminal coincidente t a la pila de análisis y escanee el siguiente símbolo de entrada en el búfer de búsqueda anticipada.
- Empuje el siguiente estado n en la pila de análisis como el nuevo estado actual.
- Reducir r m : Aplicar la regla gramatical r m : Lhs → S 1 S 2 ... S L
- Elimine los símbolos L superiores coincidentes (y los árboles de análisis y los números de estado asociados) de la pila de análisis.
- Esto expone un estado previo p que esperaba una instancia del símbolo Lhs.
- Une los árboles de análisis sintáctico L juntos como un árbol de análisis sintáctico con el nuevo símbolo de raíz Lhs.
- Busque el siguiente estado n de la fila py la columna Lhs de la tabla LHS Goto.
- Inserte el símbolo y el árbol de Lhs en la pila de análisis.
- Empuje el siguiente estado n en la pila de análisis como el nuevo estado actual.
- El flujo de entrada y de anticipación permanecen sin cambios.
- Hecho: Lookahead t es el marcador eof . Fin del análisis. Si la pila de estado contiene solo el estado de inicio, informe de éxito. De lo contrario, informe un error de sintaxis.
- Error: informe de un error de sintaxis. El analizador finaliza o intenta recuperarse.
La pila del analizador LR generalmente almacena solo los estados del autómata LR (0), ya que los símbolos gramaticales pueden derivarse de ellos (en el autómata, todas las transiciones de entrada a algún estado están marcadas con el mismo símbolo, que es el símbolo asociado con este estado) . Además, estos símbolos casi nunca son necesarios ya que el estado es lo único que importa al tomar la decisión de análisis. [7]
Análisis del generador LR
La mayoría de los usuarios de generadores de analizadores sintácticos LR pueden omitir esta sección del artículo.
Estados LR
El estado 2 en la tabla de análisis de ejemplo es para la regla analizada parcialmente
- r1: Sumas → Sumas + • Productos
Esto muestra cómo llegó aquí el analizador, al ver Sums y luego + mientras buscaba Sums más grandes. El marcador • ha avanzado más allá del comienzo de la regla. También muestra cómo el analizador espera completar eventualmente la regla, encontrando a continuación un producto completo. Pero se necesitan más detalles sobre cómo analizar todas las partes de esos Productos.
Las reglas analizadas parcialmente para un estado se denominan sus "elementos básicos LR (0)". El generador de analizador agrega reglas o elementos adicionales para todos los siguientes pasos posibles en la creación de los Productos esperados:
- r3: Productos → • Productos * Valor
- r4: Productos → • Valor
- r5: Valor → • int
- r6: Valor → • id
El marcador • está al comienzo de cada una de estas reglas agregadas; el analizador aún no ha confirmado ni analizado ninguna parte de ellos. Estos elementos adicionales se denominan "cierre" de los elementos básicos. Para cada símbolo no terminal que sigue inmediatamente a • , el generador agrega las reglas que definen ese símbolo. Esto añade más • marcadores, y posiblemente diferentes símbolos de seguidor. Este proceso de cierre continúa hasta que se hayan expandido todos los símbolos de seguidores. Los no terminales seguidores del estado 2 comienzan con Productos. Luego, se agrega valor mediante el cierre. Los terminales seguidores son int e id .
Los elementos de núcleo y cierre juntos muestran todas las posibles formas legales de pasar del estado actual a estados futuros y frases completas. Si un símbolo de seguidor aparece en un solo elemento, conduce al siguiente estado que contiene solo un elemento principal con el marcador • avanzado. Entonces int lleva al siguiente estado 8 con core
- r5: Valor → int •
Si el mismo símbolo de seguidor aparece en varios elementos, el analizador aún no puede decir qué regla se aplica aquí. De modo que ese símbolo lleva al siguiente estado que muestra todas las posibilidades restantes, nuevamente con el marcador • avanzado. Los productos aparecen tanto en r1 como en r3. Así que Products lleva al siguiente estado 3 con core
- r1: Sumas → Sumas + Productos •
- r3: Productos → Productos • * Valor
En palabras, eso significa que si el analizador ha visto un solo producto, podría estar hecho, o podría tener aún más cosas para multiplicar. Todos los elementos básicos tienen el mismo símbolo antes del • marcador; todas las transiciones a este estado son siempre con el mismo símbolo.
Algunas transiciones serán a núcleos y estados que ya se han enumerado. Otras transiciones conducen a nuevos estados. El generador comienza con la regla del objetivo de la gramática. A partir de ahí, sigue explorando estados y transiciones conocidos hasta que se han encontrado todos los estados necesarios.
Estos estados se denominan estados "LR (0)" porque utilizan una búsqueda anticipada de k = 0, es decir, sin anticipación. La única verificación de los símbolos de entrada se produce cuando el símbolo se desplaza hacia adentro. La verificación de las búsquedas anticipadas para las reducciones se realiza por separado mediante la tabla de análisis sintáctico, no mediante los estados enumerados en sí.
Máquina de estados finitos
La tabla de análisis describe todos los posibles estados LR (0) y sus transiciones. Forman una máquina de estados finitos (FSM). Un FSM es un motor simple para analizar lenguajes simples no anidados, sin usar una pila. En esta aplicación LR, el "lenguaje de entrada" modificado del FSM tiene símbolos tanto terminales como no terminales, y cubre cualquier instantánea de pila parcialmente analizada del análisis LR completo.
Recuerde el paso 5 del ejemplo de pasos de análisis:
Paso | Analizar Pila estado Símbolo de estado ... | Mirar hacia adelante | Sin escanear |
---|---|---|---|
5 | 0 Productos 4 * 5 int 8 | + | 1 |
La pila de análisis muestra una serie de transiciones de estado, desde el estado inicial 0, al estado 4 y luego al 5 y al estado actual 8. Los símbolos de la pila de análisis son los símbolos de cambio o goto para esas transiciones. Otra forma de ver esto es que la máquina de estados finitos puede escanear la secuencia "Productos * int + 1" (sin usar otra pila más) y encontrar la frase completa más a la izquierda que debería reducirse a continuación. ¡Y ese es de hecho su trabajo!
¿Cómo puede un simple FSM hacer esto cuando el lenguaje original sin analizar tiene anidamiento y recursividad y definitivamente requiere un analizador con una pila? El truco es que todo lo que está a la izquierda de la parte superior de la pila ya se ha reducido por completo. Esto elimina todos los bucles y anidamientos de esas frases. El FSM puede ignorar todos los comienzos más antiguos de frases y rastrear solo las frases más nuevas que podrían completarse a continuación. El nombre oscuro para esto en la teoría LR es "prefijo viable".
Conjuntos de anticipación
Los estados y las transiciones brindan toda la información necesaria para las acciones de desplazamiento y las acciones de goto de la tabla de análisis. El generador también necesita calcular los conjuntos de anticipación esperados para cada acción de reducción.
En los analizadores SLR , estos conjuntos de anticipación se determinan directamente a partir de la gramática, sin tener en cuenta los estados y las transiciones individuales. Para cada S no terminal, el generador SLR calcula Follows (S), el conjunto de todos los símbolos de terminal que pueden seguir inmediatamente a alguna ocurrencia de S. En la tabla de análisis, cada reducción a S usa Follow (S) como su LR (1 ) conjunto de anticipación. Estos conjuntos de seguimiento también los utilizan los generadores de analizadores sintácticos de arriba hacia abajo LL. Una gramática que no tiene cambios / reducir o reducir / reducir conflictos cuando se utilizan conjuntos de seguimiento se denomina gramática SLR.
Los analizadores LALR tienen los mismos estados que los analizadores SLR, pero utilizan una forma más complicada y precisa de calcular la reducción mínima necesaria para cada estado individual. Dependiendo de los detalles de la gramática, esto puede resultar ser el mismo que el conjunto de seguimiento calculado por los generadores de analizadores de SLR, o puede resultar ser un subconjunto de las búsquedas anticipadas de SLR. Algunas gramáticas están bien para los generadores de analizadores sintácticos LALR, pero no para los generadores de analizadores sintácticos SLR. Esto sucede cuando la gramática tiene conflictos falsos de shift / reduce o reduce / reduce usando conjuntos de seguimiento, pero no hay conflictos cuando se usan los conjuntos exactos calculados por el generador LALR. La gramática se llama entonces LALR (1) pero no SLR.
Un analizador SLR o LALR evita tener estados duplicados. Pero esta minimización no es necesaria y, a veces, puede crear conflictos de anticipación innecesarios. Los analizadores LR canónicos utilizan estados duplicados (o "divididos") para recordar mejor el contexto izquierdo y derecho del uso de un no terminal. Cada aparición de un símbolo S en la gramática se puede tratar de forma independiente con su propio conjunto de anticipación, para ayudar a resolver los conflictos de reducción. Esto maneja algunas gramáticas más. Desafortunadamente, esto magnifica enormemente el tamaño de las tablas de análisis si se hace para todas las partes de la gramática. Esta división de estados también se puede realizar de forma manual y selectiva con cualquier analizador SLR o LALR, haciendo dos o más copias con nombre de algunos no terminales. Una gramática libre de conflictos para un generador LR canónico pero que tiene conflictos en un generador LALR se llama LR (1) pero no LALR (1) y no SLR.
Los analizadores SLR, LALR y LR canónicos realizan exactamente el mismo cambio y reducen las decisiones cuando el flujo de entrada es el idioma correcto. Cuando la entrada tiene un error de sintaxis, el analizador LALR puede hacer algunas reducciones adicionales (inofensivas) antes de detectar el error que el analizador LR canónico. Y el analizador SLR puede hacer aún más. Esto sucede porque los analizadores SLR y LALR están usando una generosa aproximación de superconjunto a los verdaderos símbolos mínimos de anticipación para ese estado en particular.
Recuperación de errores de sintaxis
Los analizadores LR pueden generar mensajes de error algo útiles para el primer error de sintaxis en un programa, simplemente enumerando todos los símbolos de terminal que podrían haber aparecido a continuación en lugar del símbolo de búsqueda anticipada inesperada. Pero esto no ayuda al analizador a averiguar cómo analizar el resto del programa de entrada para buscar más errores independientes. Si el analizador se recupera mal del primer error, es muy probable que analice mal todo lo demás y produzca una cascada de mensajes de error falsos inútiles.
En los generadores de analizadores sintácticos yacc y bison, el analizador tiene un mecanismo ad hoc para abandonar la declaración actual, descartar algunas frases analizadas y tokens de anticipación que rodean el error y resincronizar el análisis en algún delimitador de nivel de declaración confiable como punto y coma o llaves. Esto a menudo funciona bien para permitir que el analizador y el compilador revisen el resto del programa.
Muchos errores de codificación sintáctica son simples errores tipográficos u omisiones de un símbolo trivial. Algunos analizadores LR intentan detectar y reparar automáticamente estos casos comunes. El analizador enumera todas las posibles inserciones, eliminaciones o sustituciones de un solo símbolo en el punto de error. El compilador hace un análisis de prueba con cada cambio para ver si funcionó bien. (Esto requiere retroceder a las instantáneas de la pila de análisis sintáctico y el flujo de entrada, que normalmente el analizador no necesita). Se elige la mejor reparación. Esto da un mensaje de error muy útil y resincroniza bien el análisis. Sin embargo, la reparación no es lo suficientemente confiable como para modificar permanentemente el archivo de entrada. La reparación de errores de sintaxis es más fácil de hacer de manera consistente en analizadores (como LR) que tienen tablas de análisis y una pila de datos explícita.
Variantes de analizadores sintácticos LR
El generador de analizador LR decide qué debe suceder para cada combinación de estado del analizador y símbolo de anticipación. Estas decisiones generalmente se convierten en tablas de datos de solo lectura que impulsan un bucle de analizador genérico que es independiente de la gramática y el estado. Pero también hay otras formas de convertir esas decisiones en un analizador activo.
Algunos generadores de analizadores sintácticos LR crean un código de programa individual y personalizado para cada estado, en lugar de una tabla de análisis sintáctico. Estos analizadores pueden ejecutarse varias veces más rápido que el bucle de analizador genérico en analizadores controlados por tablas. Los analizadores más rápidos utilizan código ensamblador generado.
En la variación del analizador sintáctico de ascenso recursivo , la estructura de la pila de análisis explícito también se reemplaza por la pila implícita utilizada por las llamadas a subrutinas. Las reducciones terminan varios niveles de llamadas a subrutinas, lo cual es torpe en la mayoría de los idiomas. Por lo tanto, los analizadores sintácticos ascendentes recursivos son generalmente más lentos, menos obvios y más difíciles de modificar manualmente que los analizadores sintácticos descendentes recursivos .
Otra variación reemplaza la tabla de análisis por reglas de coincidencia de patrones en lenguajes no procedimentales como Prolog .
Los analizadores sintácticos LR generalizados de GLR utilizan técnicas ascendentes de LR para encontrar todos los análisis posibles del texto de entrada, no solo un análisis correcto. Esto es esencial para gramáticas ambiguas como las que se utilizan para los lenguajes humanos. Los múltiples árboles de análisis válidos se calculan simultáneamente, sin retroceso. GLR a veces es útil para lenguajes de computadora que no se describen fácilmente con una gramática LALR (1) libre de conflictos.
Los analizadores sintácticos de la esquina izquierda LC utilizan técnicas ascendentes LR para reconocer el extremo izquierdo de las reglas gramaticales alternativas. Cuando las alternativas se han reducido a una única regla posible, el analizador cambia a técnicas LL (1) descendentes para analizar el resto de esa regla. Los analizadores LC tienen tablas de análisis más pequeñas que los analizadores LALR y mejores diagnósticos de errores. No hay generadores de uso generalizado para analizadores de LC deterministas. Los analizadores sintácticos LC de análisis múltiple son útiles con lenguajes humanos con gramáticas muy extensas.
Teoría
Los analizadores sintácticos LR fueron inventados por Donald Knuth en 1965 como una generalización eficiente de analizadores sintácticos de precedencia . Knuth demostró que los analizadores sintácticos LR eran los analizadores sintácticos más generales posibles que seguirían siendo eficientes en el peor de los casos. [ cita requerida ]
- "Las gramáticas LR ( k ) se pueden analizar de manera eficiente con un tiempo de ejecución esencialmente proporcional a la longitud de la cadena". [8]
- Para cada k ≥1, "un lenguaje puede ser generado por una gramática LR ( k ) si y solo si es determinista [y libre de contexto], si y solo si puede ser generado por una gramática LR (1)". [9]
En otras palabras, si un idioma fuera lo suficientemente razonable como para permitir un analizador sintáctico eficiente de una sola pasada, podría describirse mediante una gramática LR ( k ). Y esa gramática siempre podría transformarse mecánicamente en una gramática LR (1) equivalente (pero más grande). Entonces, un método de análisis sintáctico LR (1) era, en teoría, lo suficientemente poderoso como para manejar cualquier lenguaje razonable. En la práctica, las gramáticas naturales de muchos lenguajes de programación están cerca de ser LR (1). [ cita requerida ]
Los analizadores sintácticos canónicos LR descritos por Knuth tenían demasiados estados y tablas de análisis muy grandes que eran imprácticamente grandes para la memoria limitada de las computadoras de esa época. El análisis sintáctico LR se volvió práctico cuando Frank DeRemer inventó los analizadores sintácticos SLR y LALR con muchos menos estados. [10] [11]
Para obtener detalles completos sobre la teoría LR y cómo los analizadores sintácticos LR se derivan de las gramáticas, consulte La teoría del análisis, traducción y compilación, Volumen 1 (Aho y Ullman). [7] [2]
Los analizadores sintácticos Earley aplican las técnicas y • la notación de los analizadores sintácticos LR a la tarea de generar todos los análisis sintácticos posibles para gramáticas ambiguas, como para lenguajes humanos.
Mientras que las gramáticas LR ( k ) tienen el mismo poder generativo para todo k ≥1, el caso de las gramáticas LR (0) es ligeramente diferente. Un lenguaje L se dice que tiene la propiedad de prefijo si no hay palabra en L es un prefijo adecuado de otra palabra en L . [12] Un lenguaje L tiene una gramática LR (0) si y solo si L es un lenguaje determinista libre de contexto con la propiedad de prefijo. [13] Como consecuencia de ello, un lenguaje L es libre de contexto determinista si y sólo si L $ tiene un (0) gramática, LR donde "$" no es un símbolo de L ‘s alfabeto . [14]
Ejemplo adicional 1 + 1
Este ejemplo de análisis sintáctico LR utiliza la siguiente gramática pequeña con el símbolo de objetivo E:
- (1) E → E * B
- (2) E → E + B
- (3) E → B
- (4) B → 0
- (5) B → 1
para analizar la siguiente entrada:
- 1 + 1
Tablas de acción y goto
Las dos tablas de análisis sintáctico LR (0) para esta gramática tienen el siguiente aspecto:
Expresar | acción | ir | |||||
* | + | 0 | 1 | PS | mi | B | |
0 | s1 | s2 | 3 | 4 | |||
1 | r4 | r4 | r4 | r4 | r4 | ||
2 | r5 | r5 | r5 | r5 | r5 | ||
3 | s5 | s6 | acc | ||||
4 | r3 | r3 | r3 | r3 | r3 | ||
5 | s1 | s2 | 7 | ||||
6 | s1 | s2 | 8 | ||||
7 | r1 | r1 | r1 | r1 | r1 | ||
8 | r2 | r2 | r2 | r2 | r2 |
La tabla de acciones está indexada por un estado del analizador y un terminal (incluido un terminal especial $ que indica el final del flujo de entrada) y contiene tres tipos de acciones:
- shift , que se escribe como 's n ' e indica que el siguiente estado es n
- reducir , que se escribe como 'r m ' e indica que una reducción con regla gramatical m se debe realizar
- accept , que está escrito como 'acc' e indica que el analizador acepta la cadena en el flujo de entrada.
La tabla goto está indexada por un estado del analizador y un no terminal y simplemente indica cuál será el siguiente estado del analizador si ha reconocido un determinado no terminal. Esta tabla es importante para conocer el siguiente estado después de cada reducción. Después de una reducción, el siguiente estado se encuentra buscando la entrada de la tabla Goto para la parte superior de la pila (es decir, el estado actual) y el LHS de la regla reducida (es decir, no terminal).
Pasos de análisis
La siguiente tabla ilustra cada paso del proceso. Aquí, el estado se refiere al elemento en la parte superior de la pila (el elemento más a la derecha), y la siguiente acción se determina consultando la tabla de acciones anterior. Se agrega un $ a la cadena de entrada para indicar el final de la secuencia.
Expresar | Flujo de entrada | Flujo de salida | Apilar | Proxima accion |
---|---|---|---|---|
0 | 1 + 1 $ | [0] | Turno 2 | |
2 | + 1 $ | [0,2] | Reducir 5 | |
4 | + 1 $ | 5 | [0,4] | Reducir 3 |
3 | + 1 $ | 5,3 | [0,3] | Turno 6 |
6 | 1 $ | 5,3 | [0,3,6] | Turno 2 |
2 | PS | 5,3 | [0,3,6,2] | Reducir 5 |
8 | PS | 5,3,5 | [0,3,6,8] | Reducir 2 |
3 | PS | 5,3,5,2 | [0,3] | Aceptar |
Tutorial
El analizador comienza con la pila que contiene solo el estado inicial ('0'):
- [ 0 ]
El primer símbolo de la cadena de entrada que ve el analizador es '1'. Para encontrar la siguiente acción (cambiar, reducir, aceptar o error), la tabla de acciones se indexa con el estado actual (el "estado actual" es lo que esté en la parte superior de la pila), que en este caso es 0, y el símbolo de entrada actual, que es '1'. La tabla de acciones especifica un cambio al estado 2, por lo que el estado 2 se empuja a la pila (nuevamente, toda la información del estado está en la pila, por lo que "cambiar al estado 2" es lo mismo que empujar 2 a la pila). La pila resultante es
- [ 0 '1' 2 ]
donde la parte superior de la pila es 2. En aras de la explicación, se muestra el símbolo (por ejemplo, '1', B) que provocó la transición al siguiente estado, aunque estrictamente hablando no es parte de la pila.
En el estado 2, la tabla de acciones dice reducir con la regla gramatical 5 (independientemente de la terminal que vea el analizador en el flujo de entrada), lo que significa que el analizador acaba de reconocer el lado derecho de la regla 5. En este caso, el el analizador escribe 5 en el flujo de salida, saca un estado de la pila (ya que el lado derecho de la regla tiene un símbolo) y empuja en la pila el estado de la celda en la tabla goto para el estado 0 y B, es decir , estado 4. La pila resultante es:
- [ 0 B 4 ]
Sin embargo, en el estado 4, la tabla de acciones dice que el analizador ahora debería reducir con la regla 3. Por lo tanto, escribe 3 en el flujo de salida, saca un estado de la pila y encuentra el nuevo estado en la tabla goto para los estados 0 y E, que es el estado 3. La pila resultante:
- [ 0 E 3 ]
La siguiente terminal que ve el analizador es un '+' y, de acuerdo con la tabla de acciones, debe ir al estado 6:
- [ 0 E 3 '+' 6 ]
La pila resultante se puede interpretar como la historia de un autómata de estado finito que acaba de leer una E no terminal seguida de una terminal '+'. La tabla de transición de este autómata está definida por las acciones de cambio en la tabla de acciones y las acciones de ir a la tabla de ir.
La siguiente terminal ahora es '1' y esto significa que el analizador realiza un cambio y pasa al estado 2:
- [ 0 E 3 '+' 6 '1' 2 ]
Al igual que el '1' anterior, este se reduce a B dando la siguiente pila:
- [ 0 E 3 '+' 6 B 8 ]
La pila se corresponde con una lista de estados de un autómata finito que ha leído un E no terminal, seguido de un '+' y luego un no terminal B. En el estado 8, el analizador siempre realiza una reducción con la regla 2. Los 3 estados superiores en el La pila se corresponde con los 3 símbolos en el lado derecho de la regla 2. Esta vez sacamos 3 elementos de la pila (ya que el lado derecho de la regla tiene 3 símbolos) y buscamos el estado goto para E y 0 , empujando así el estado 3 de nuevo a la pila
- [ 0 E 3 ]
Finalmente, el analizador lee un '$' (final del símbolo de entrada) del flujo de entrada, lo que significa que de acuerdo con la tabla de acciones (el estado actual es 3) el analizador acepta la cadena de entrada. Los números de regla que luego se habrán escrito en el flujo de salida serán [5, 3, 5, 2], que de hecho es una derivación del extremo derecho de la cadena "1 + 1" a la inversa.
Construcción de tablas de análisis sintáctico LR (0)
Artículos
La construcción de estas tablas de análisis se basa en la noción de elementos LR (0) (simplemente llamados elementos aquí) que son reglas gramaticales con un punto especial agregado en algún lugar del lado derecho. Por ejemplo, la regla E → E + B tiene los siguientes cuatro elementos correspondientes:
- E → • E + B
- E → E • + B
- E → E + • B
- E → E + B •
Las reglas de la forma A → ε tienen un solo elemento A → • . El elemento E → E • + B, por ejemplo, indica que el analizador ha reconocido una cadena correspondiente con E en el flujo de entrada y ahora espera leer un '+' seguido de otra cadena correspondiente a B.
Conjuntos de artículos
Por lo general, no es posible caracterizar el estado del analizador con un solo elemento porque es posible que no sepa de antemano qué regla utilizará para la reducción. Por ejemplo, si también hay una regla E → E * B, los elementos E → E • + B y E → E • * B se aplicarán después de leer una cadena correspondiente a E. Por lo tanto, es conveniente caracterizar el estado del analizador mediante un conjunto de elementos, en este caso el conjunto {E → E • + B, E → E • * B}.
Ampliación del conjunto de elementos mediante ampliación de no terminales
Un elemento con un punto antes de un no terminal, como E → E + • B, indica que el analizador espera analizar el no terminal B a continuación. Para asegurarse de que el conjunto de elementos contiene todas las reglas posibles que el analizador puede estar en medio del análisis, debe incluir todos los elementos que describen cómo se analizará B en sí. Esto significa que si hay reglas como B → 1 y B → 0, el conjunto de elementos también debe incluir los elementos B → • 1 y B → • 0. En general, esto se puede formular de la siguiente manera:
- Si hay un elemento de la forma A → v • Bw en un conjunto de elementos y en la gramática hay una regla de la forma B → w ', entonces el elemento B → • w' también debería estar en el conjunto de elementos.
Cierre de conjuntos de artículos
Por lo tanto, cualquier conjunto de elementos se puede ampliar agregando recursivamente todos los elementos apropiados hasta que se tengan en cuenta todos los no terminales precedidos por puntos. La extensión mínima se denomina cierre de un conjunto de elementos y se escribe clos ( I ) donde I es un conjunto de elementos. Son estos conjuntos de elementos cerrados los que se toman como estados del analizador, aunque solo los que son realmente accesibles desde el estado inicial se incluirán en las tablas.
Gramática aumentada
Antes de que se determinen las transiciones entre los diferentes estados, la gramática se aumenta con una regla adicional
- (0) S → E eof
donde S es un nuevo símbolo de inicio y E el antiguo símbolo de inicio. El analizador utilizará esta regla para la reducción exactamente cuando haya aceptado toda la cadena de entrada.
Para este ejemplo, la misma gramática anterior se aumenta así:
- (0) S → E eof
- (1) E → E * B
- (2) E → E + B
- (3) E → B
- (4) B → 0
- (5) B → 1
Es por esta gramática aumentada que se determinarán los conjuntos de elementos y las transiciones entre ellos.
Construcción de la mesa
Encontrar los conjuntos de elementos accesibles y las transiciones entre ellos
El primer paso para construir las tablas consiste en determinar las transiciones entre los conjuntos de elementos cerrados. Estas transiciones se determinarán como si estuviéramos considerando un autómata finito que puede leer tanto terminales como no terminales. El estado inicial de este autómata es siempre el cierre del primer elemento de la regla agregada: S → • E:
- Conjunto de elementos 0
- S → • E eof
- + E → • E * B
- + E → • E + B
- + E → • B
- + B → • 0
- + B → • 1
El " + " en negrita delante de un elemento indica los elementos que se agregaron para el cierre (no debe confundirse con el operador matemático '+' que es una terminal). Los elementos originales sin un " + " se denominan núcleo del conjunto de elementos.
Comenzando en el estado inicial (S0), ahora se determinan todos los estados que se pueden alcanzar desde este estado. Las posibles transiciones para un conjunto de elementos se pueden encontrar observando los símbolos (terminales y no terminales) que se encuentran después de los puntos; en el caso del conjunto de elementos 0, esos símbolos son los terminales '0' y '1' y los no terminales E y B. Para encontrar el conjunto de elementos que cada símboloconduce, se sigue el siguiente procedimiento para cada uno de los símbolos:
- Tome el subconjunto, S , de todos los elementos del conjunto de elementos actual donde hay un punto delante del símbolo de interés, x .
- Para cada elemento de S , mueva el punto a la derecha de x .
- Cierre el conjunto de elementos resultante.
Para el terminal '0' (es decir, donde x = '0') esto da como resultado:
- Conjunto de elementos 1
- B → 0 •
y para el terminal '1' (es decir, donde x = '1') esto da como resultado:
- Conjunto de elementos 2
- B → 1 •
y para el no terminal E (es decir, donde x = E) esto da como resultado:
- Conjunto de elementos 3
- S → E • eof
- E → E • * B
- E → E • + B
y para el no terminal B (es decir, donde x = B) esto da como resultado:
- Conjunto de elementos 4
- E → B •
El cierre no agrega nuevos elementos en todos los casos; en los nuevos conjuntos anteriores, por ejemplo, no hay no terminales después del punto.
El procedimiento anterior se continúa hasta que no se encuentren más conjuntos de elementos nuevos. Para los conjuntos de elementos 1, 2 y 4 no habrá transiciones ya que el punto no está delante de ningún símbolo. Sin embargo, para el conjunto de elementos 3, tenemos puntos delante de los terminales '*' y '+'. Por símbolola transición va a:
- Conjunto de elementos 5
- E → E * • B
- + B → • 0
- + B → • 1
y para la transición va a:
- Conjunto de elementos 6
- E → E + • B
- + B → • 0
- + B → • 1
Ahora comienza la tercera iteración.
Para el conjunto de elementos 5, se deben considerar los terminales '0' y '1' y el no terminal B, pero los conjuntos de elementos cerrados resultantes son iguales a los conjuntos de elementos 1 y 2 ya encontrados, respectivamente. Para el no terminal B, la transición va a:
- Conjunto de elementos 7
- E → E * B •
Para el conjunto de elementos 6, se deben considerar el terminal '0' y '1' y el no terminal B, pero como antes, los conjuntos de elementos resultantes para los terminales son iguales a los conjuntos de elementos 1 y 2 ya encontrados. la transición va a:
- Conjunto de elementos 8
- E → E + B •
Estos conjuntos de elementos finales 7 y 8 no tienen símbolos más allá de sus puntos, por lo que no se agregan más conjuntos de elementos nuevos, por lo que el procedimiento de generación de elementos está completo. El autómata finito, con conjuntos de elementos como sus estados, se muestra a continuación.
La tabla de transición para el autómata ahora tiene el siguiente aspecto:
Conjunto de elementos | * | + | 0 | 1 | mi | B |
---|---|---|---|---|---|---|
0 | 1 | 2 | 3 | 4 | ||
1 | ||||||
2 | ||||||
3 | 5 | 6 | ||||
4 | ||||||
5 | 1 | 2 | 7 | |||
6 | 1 | 2 | 8 | |||
7 | ||||||
8 |
Construyendo las tablas de acción e ir a
A partir de esta tabla y los conjuntos de elementos encontrados, la acción y la tabla goto se construyen de la siguiente manera:
- Las columnas de los no terminales se copian en la tabla Ir a.
- Las columnas de los terminales se copian en la tabla de acciones como acciones de cambio.
- Se agrega una columna adicional para '$' (final de la entrada) a la tabla de acciones que contiene acc para cada conjunto de elementos que contiene un elemento de la forma S → w • eof.
- Si un conjunto de elementos i contiene un elemento de la forma A → w • y A → w es la regla m con m > 0, entonces la fila para el estado i en la tabla de acciones está completamente llena con la acción de reducción r m .
El lector puede verificar que esto da como resultado la acción e ir a la tabla que se presentaron anteriormente.
Una nota sobre el análisis sintáctico de LR (0) versus SLR y LALR
Solo el paso 4 del procedimiento anterior produce acciones de reducción, por lo que todas las acciones de reducción deben ocupar una fila completa de la tabla, lo que hace que la reducción se produzca independientemente del siguiente símbolo en el flujo de entrada. Esta es la razón por la que estas son tablas de análisis LR (0): no hacen ninguna búsqueda anticipada (es decir, miran hacia adelante cero símbolos) antes de decidir qué reducción realizar. Una gramática que necesita anticipación para eliminar la ambigüedad de las reducciones requeriría una fila de la tabla de análisis que contenga diferentes acciones de reducción en diferentes columnas, y el procedimiento anterior no es capaz de crear tales filas.
Los refinamientos del procedimiento de construcción de la tabla LR (0) (como SLR y LALR ) son capaces de construir acciones de reducción que no ocupan filas enteras. Por lo tanto, son capaces de analizar más gramáticas que los analizadores sintácticos LR (0).
Conflictos en las tablas construidas
El autómata está construido de tal manera que se garantiza que es determinista. Sin embargo, cuando se agregan acciones de reducción a la tabla de acciones, puede suceder que la misma celda se llene con una acción de reducción y una acción de cambio (un conflicto de cambio-reducción ) o con dos acciones de reducción diferentes (un conflicto de reducción-reducción ). Sin embargo, se puede demostrar que cuando esto sucede, la gramática no es una gramática LR (0). Un ejemplo clásico del mundo real de un conflicto de reducción de cambios es el problema de los demás pendientes .
Un pequeño ejemplo de una gramática que no es LR (0) con un conflicto shift-reduce es:
- (1) E → 1 E
- (2) E → 1
Uno de los conjuntos de elementos encontrados es:
- Conjunto de elementos 1
- E → 1 • E
- E → 1 •
- + E → • 1 E
- + E → • 1
Hay un conflicto de cambio-reducción en este conjunto de elementos: al construir la tabla de acciones de acuerdo con las reglas anteriores, la celda para [conjunto de elementos 1, terminal '1'] contiene s1 (cambio al estado 1) y r2 (reducir con gramática regla 2).
Un pequeño ejemplo de una gramática que no es LR (0) con un conflicto de reducir-reducir es:
- (1) E → A 1
- (2) E → B 2
- (3) A → 1
- (4) B → 1
En este caso se obtiene el siguiente conjunto de elementos:
- Conjunto de elementos 1
- A → 1 •
- B → 1 •
Hay un conflicto de reducción-reducción en este conjunto de elementos porque en las celdas de la tabla de acciones para este conjunto de elementos habrá una acción de reducción para la regla 3 y otra para la regla 4.
Ambos ejemplos anteriores se pueden resolver dejando que el analizador utilice el siguiente conjunto (ver analizador LL ) de un A no terminal para decidir si va a utilizar una de las reglas de A para una reducción; Sólo utilizará la regla A → w para una reducción si el siguiente símbolo del flujo de entrada está en el conjunto de seguimiento A . Esta solución da como resultado los denominados analizadores sintácticos LR simples .
Ver también
- Analizador LR canónico
- LR simple
- Look-Ahead LR
- LR generalizado
Referencias
- ↑ a b c Knuth, DE (julio de 1965). "Sobre la traducción de idiomas de izquierda a derecha" (PDF) . Información y control . 8 (6): 607–639. doi : 10.1016 / S0019-9958 (65) 90426-2 . Archivado desde el original (PDF) el 15 de marzo de 2012 . Consultado el 29 de mayo de 2011 .
- ^ a b Aho, Alfred V .; Ullman, Jeffrey D. (1972). La teoría del análisis, traducción y compilación (Volumen 1: Análisis) (Repr. Ed.). Englewood Cliffs, Nueva Jersey : Prentice Hall . ISBN 978-0139145568.
- ^ Comparación de la teoría del lenguaje de las gramáticas LL y LR
- ^ Ingeniería de un compilador (segunda edición), por Keith Cooper y Linda Torczon, Morgan Kaufmann 2011.
- ^ Elaboración y compilador, por Charles Fischer, Ron Cytron y Richard LeBlanc, Addison Wesley 2009.
- ^ Flex & Bison: herramientas de procesamiento de texto, por John Levine, O'Reilly Media 2009.
- ^ a b Compiladores: principios, técnicas y herramientas (segunda edición), por Alfred Aho, Monica Lam, Ravi Sethi y Jeffrey Ullman, Prentice Hall 2006.
- ^ Knuth (1965), p.638
- ^ Knuth (1965), p.635. Knuth no mencionó la restricción k ≥1 allí, pero es requerida por sus teoremas a los que se refirió, a saber. en la p.629 y p.630. De manera similar, la restricción a los lenguajes libres de contexto se entiende tácitamente a partir del contexto.
- ^ Traductores prácticos para idiomas LR (k), por Frank DeRemer, disertación de doctorado del MIT 1969.
- ^ Gramáticas simples de LR (k), por Frank DeRemer, Comm. ACM 14: 7 1971.
- ^ Hopcroft, John E .; Ullman, Jeffrey D. (1979). Introducción a la teoría, los lenguajes y la computación de los autómatas . Addison-Wesley. ISBN 0-201-02988-X. Aquí: Ejercicio 5.8, p.121.
- ^ Hopcroft, Ullman (1979), Teorema 10.12, p.260
- ^ Hopcroft, Ullman (1979), Corolario p.260
Otras lecturas
- Chapman, Nigel P., Análisis de LR: teoría y práctica , Cambridge University Press , 1987. ISBN 0-521-30413-X
- Pager, D., Un método general práctico para construir analizadores LR (k). Acta Informatica 7, 249 - 268 (1977)
- "Construcción del compilador: principios y práctica" por Kenneth C. Louden. ISBN 0-534-939724
enlaces externos
- dickgrune.com , Técnicas de análisis - Una guía práctica 1ª Ed. La página web del libro incluye pdf descargable.
- Simulador de análisis Este simulador se utiliza para generar tablas de análisis LR y para resolver los ejercicios del libro.
- Elementos internos de un analizador LALR (1) generado por GNU Bison - Problemas de implementación
- Notas del curso sobre análisis sintáctico LR
- Shift-reduce y Reduce-reduce conflictos en un analizador LALR
- Un ejemplo de analizador LR
- Construcción práctica del analizador LR (k)
- El algoritmo de Honalee LR (k)