Hispanopedia Wiki
Articulo de referencia

Analizador LL

En informática , un analizador LL es un analizador descendente para un lenguaje libre de contexto restringido . Analiza la entrada de izquierda a derecha, realizando la derivaci...

Hispanopedia WikiContenido en espanolLectura gratuita

En informática , un analizador LL es un analizador descendente para un lenguaje libre de contexto restringido . Analiza la entrada de izquierda a derecha, realizando la derivación más a la izquierda de la oración.

Un analizador LL se denomina analizador LL( k ) si utiliza k tokens de anticipación al analizar una oración. Una gramática se denomina gramática LL( k ) si se puede construir un analizador LL( k ) a partir de ella. Un lenguaje formal se denomina lenguaje LL( k ) si posee una gramática LL( k ). El conjunto de lenguajes LL( k ) está propiamente contenido en el de lenguajes LL( k +1), para cada k  ≥  0. [ 1 ] Una consecuencia de esto es que no todos los lenguajes libres de contexto pueden ser reconocidos por un analizador LL( k ).

Un analizador LL se denomina LL-regular (LLR) si analiza un lenguaje LL-regular . [ 2 ] [ 3 ] [ 4 ] La clase de gramáticas LLR contiene toda gramática LL( k ) para cada k . Para cada gramática LLR existe un analizador LLR que analiza la gramática en tiempo lineal.

Dos tipos de analizadores atípicos nomenclaturales son LL(*) y LL(finito). Un analizador se llama LL(*)/LL(finito) si usa la estrategia de análisis LL(*)/LL(finito). [ 5 ] [ 6 ] Los analizadores LL(*) y LL(finito) son funcionalmente más cercanos a los analizadores PEG . Un analizador LL(finito) puede analizar una gramática LL( k ) arbitraria de manera óptima en la cantidad de búsquedas anticipadas y comparaciones de búsqueda anticipada. La clase de gramáticas analizables por la estrategia LL(*) abarca algunos lenguajes sensibles al contexto debido al uso de predicados sintácticos y semánticos y no ha sido identificada. Se ha sugerido que los analizadores LL(*) se entienden mejor como analizadores TDPL . [ 7 ] Contrariamente a la idea errónea popular, los analizadores LL(*) no son LLR en general, y están garantizados por construcción para tener un rendimiento peor en promedio (superlineal frente a tiempo lineal) y mucho peor en el peor de los casos (exponencial frente a tiempo lineal).

Las gramáticas LL, en particular las gramáticas LL(1), son de gran interés práctico, ya que los analizadores sintácticos para estas gramáticas son fáciles de construir, y muchos lenguajes de programación están diseñados para ser LL(1) por esta razón. [ 8 ] Los analizadores sintácticos LL pueden estar basados ​​en tablas, [ 9 ] es decir, similares a los analizadores sintácticos LR , pero las gramáticas LL también pueden ser analizadas por analizadores sintácticos de descenso recursivo . Según Waite y Goos (1984), [ 10 ] las gramáticas LL( k ) fueron introducidas por Stearns y Lewis (1969). [ 11 ]

Descripción general

Para una gramática libre de contexto dada , el analizador intenta encontrar la derivación más a la izquierda . Dada una gramática de ejemplo G :

  1. S→mi{\displaystyle S\to E}
  2. mi→(mi+mi){\displaystyle E\to (E+E)}
  3. mi→i{\displaystyle E\to i}

la derivación más a la izquierda paraw=((i+i)+i){\displaystyle w=((i+i)+i)}es:

S ⇒(1) mi ⇒(2) (mi+mi) ⇒(2) ((mi+mi)+mi) ⇒(3) ((i+mi)+mi) ⇒(3) ((i+i)+mi) ⇒(3) ((i+i)+i){\displaystyle S\ {\overset {(1)}{\Rightarrow }}\ E\ {\overset {(2)}{\Rightarrow }}\ (E+E)\ {\overset {(2)}{\Rightarrow }}\ ((E+E)+E)\ {\overset {(3)}{\Rightarrow }}\ ((i+E)+E)\ {\overset {(3)}{\Rightarrow }}\ ((i+i)+E)\ {\overset {(3)}{\Rightarrow }}\ ((i+i)+i)}

Generalmente, existen múltiples posibilidades al seleccionar una regla para expandir el no terminal más a la izquierda. En el paso 2 del ejemplo anterior, el analizador debe elegir si aplicar la regla 2 o la regla 3:

S ⇒(1) mi ⇒(¿) ¿{\displaystyle S\ {\overset {(1)}{\Rightarrow }}\ E\ {\overset {(?)}{\Rightarrow }}\ ?}

Para ser eficiente, el analizador debe poder tomar esta decisión de forma determinista cuando sea posible, sin retroceder . Para algunas gramáticas, puede hacerlo echando un vistazo a la entrada no leída (sin leerla). En nuestro ejemplo, si el analizador sabe que el siguiente símbolo no leído es ( , la única regla correcta que se puede usar es 2.

En general, un analizador LL( k ) puede anticipar k símbolos. Sin embargo, dada una gramática, el problema de determinar si existe un analizador LL( k ) para algún k que la reconozca es indecidible . Para cada k , existe un lenguaje que no puede ser reconocido por un analizador LL( k ), pero sí por un analizador LL( k +1) .

Podemos utilizar el análisis anterior para dar la siguiente definición formal:

Sea G una gramática libre de contexto y k ≥ 1. Decimos que G es LL( k ) si para cualesquiera dos derivaciones más a la izquierda:

  1. S ⇒ ⋯ ⇒ wAα ⇒ ⋯ ⇒ wβα ⇒ ⋯ ⇒ wtú{\displaystyle S\ \Rightarrow \ \cdots \ \Rightarrow \ wA\alpha \ \Rightarrow \ \cdots \ \Rightarrow \ w\beta \alpha \ \Rightarrow \ \cdots \ \Rightarrow \ wu}
  2. S ⇒ ⋯ ⇒ wAα ⇒ ⋯ ⇒ wγα ⇒ ⋯ ⇒ wv{\displaystyle S\ \Rightarrow \ \cdots \ \Rightarrow \ wA\alpha \ \Rightarrow \ \cdots \ \Rightarrow \ w\gamma \alpha \ \Rightarrow \ \cdots \ \Rightarrow \ wv}

Se cumple la siguiente condición: el prefijo de la cadenatú{\displaystyle u}de longitudk{\displaystyle k}es igual al prefijo de la cadenav{\displaystyle v}de longitud k implicaβ=γ{\displaystyle \beta =\gamma}.

En esta definición,S{\displaystyle S}es el símbolo de inicio yA{\displaystyle A}cualquier no terminal. La entrada ya derivadaw{\displaystyle w}y aún sin leertú{\displaystyle u}yv{\displaystyle v}son cadenas de terminales. Las letras griegasα{\displaystyle \alpha },β{\displaystyle \beta }yγ{\displaystyle \gamma }Representa cualquier cadena compuesta por terminales y no terminales (posiblemente vacía). La longitud del prefijo corresponde al tamaño del búfer de anticipación, y la definición indica que este búfer es suficiente para distinguir entre dos derivaciones cualesquiera de palabras diferentes.

Analizador sintáctico

El analizador LL( k ) es un autómata de pila determinista con la capacidad de previsualizar los siguientes k símbolos de entrada sin necesidad de leerlos. Esta capacidad de previsualización se puede emular almacenando el contenido del búfer de anticipación en el espacio de estados finito, dado que tanto el búfer como el alfabeto de entrada tienen un tamaño finito. En consecuencia, esto no aumenta la potencia del autómata, sino que constituye una abstracción conveniente.

El alfabeto de pila esΓ=norte∪Σ{\displaystyle \Gamma =N\cup \Sigma }, dónde:

  • norte{\displaystyle N}es el conjunto de no terminales;
  • Σ{\displaystyle \Sigma }el conjunto de símbolos terminales (de entrada) con un símbolo especial de fin de entrada (EOI) $ .

La pila del analizador contiene inicialmente el símbolo inicial encima del EOI: [ S $ ] . Durante la operación, el analizador reemplaza repetidamente el símboloincógnita{\displaystyle X}en la parte superior de la pila:

  • con algunosα{\displaystyle \alpha }, siincógnita∈norte{\displaystyle X\in N}y hay una reglaincógnita→α{\displaystyle X\to \alpha };
  • conϵ{\displaystyle \epsilon }(en algunas notaciones)λ{\displaystyle \lambda }), es decirincógnita{\displaystyle X}se extrae de la pila, siincógnita∈Σ{\displaystyle X\in \Sigma }En este caso, un símbolo de entradaincógnita{\displaystyle x}se lee y siincógnita≠incógnita{\displaystyle x\neq X}, el analizador rechaza la entrada.

Si el último símbolo que se elimina de la pila es el EOI, el análisis sintáctico es exitoso; el autómata acepta a través de una pila vacía.

Los estados y la función de transición no se dan explícitamente; se especifican (generan) mediante una tabla de análisis sintáctico más conveniente . La tabla proporciona la siguiente correspondencia:

  • fila: símbolo de la parte superior de la pilaincógnita{\displaystyle X}
  • columna: | w | ≤ k contenido del búfer de anticipación
  • celda: número de regla paraincógnita→α{\displaystyle X\to \alpha }oϵ{\displaystyle \epsilon }

Si el analizador no puede realizar una transición válida, la entrada se rechaza (celdas vacías). Para que la tabla sea más compacta, generalmente solo se muestran las filas no terminales, ya que la acción es la misma para las filas terminales.

Ejemplo concreto

Configuración

Para explicar el funcionamiento de un analizador LL(1), consideraremos la siguiente gramática LL(1) pequeña:

  1. S → F
  2. S → ( S + F )
  3. F → a

y analizar la siguiente entrada:

( a + a )

Una tabla de análisis LL(1) para una gramática tiene una fila para cada uno de los no terminales y una columna para cada terminal (incluido el terminal especial, representado aquí como $ , que se utiliza para indicar el final del flujo de entrada).

Cada celda de la tabla puede apuntar a lo sumo a una regla de la gramática (identificada por su número). Por ejemplo, en la tabla de análisis sintáctico para la gramática anterior, la celda para la 'S' no terminal y la terminal '(' apunta a la regla número 2:

El algoritmo para construir una tabla de análisis sintáctico se describe en una sección posterior, pero primero veamos cómo el analizador sintáctico utiliza la tabla de análisis sintáctico para procesar su entrada.

Procedimiento de análisis sintáctico

En cada paso, el analizador lee el siguiente símbolo disponible del flujo de entrada y el símbolo superior de la pila. Si el símbolo de entrada y el símbolo superior de la pila coinciden, el analizador los descarta ambos pasando al siguiente símbolo de entrada y extrayendo el símbolo superior de la pila. Este proceso se repite hasta que el símbolo de entrada y el símbolo superior de la pila no coincidan.

Así, en su primer paso, el analizador lee el símbolo de entrada '(' y el símbolo superior de la pila 'S'. La instrucción de la tabla de análisis proviene de la columna encabezada por el símbolo de entrada '(' y la fila encabezada por el símbolo de la parte superior de la pila 'S'; esta celda contiene '2', lo que indica al analizador que aplique la regla (2). El analizador tiene que reescribir 'S' a '( S + F )' en la pila quitando 'S' de la pila y apilando ')', 'F', '+', 'S', '(' en la pila, y esto escribe la regla número 2 en la salida. La pila queda entonces así:

[ ( , S, + , F, ) , $ ]

En el segundo paso, el analizador elimina el '(' de su flujo de entrada y de su pila, ya que ahora coinciden. La pila ahora se convierte en:

[ S, + , F, ) , $ ]

Ahora el analizador tiene una ' a' en su flujo de entrada y una 'S' como la parte superior de su pila. La tabla de análisis le indica que aplique la regla (1) de la gramática y escriba la regla número 1 en el flujo de salida. La pila queda así:

[ F, + , F, ) , $ ]

El analizador sintáctico ahora tiene una ' a' en su flujo de entrada y una 'F' como la parte superior de su pila. La tabla de análisis sintáctico le indica que aplique la regla (3) de la gramática y escriba la regla número 3 en el flujo de salida. La pila queda de la siguiente manera:

[ a , + , F, ) , $ ]

El analizador ahora tiene un 'a' en el flujo de entrada y un 'a' en la parte superior de su pila. Debido a que son iguales, lo elimina del flujo de entrada y lo extrae de la parte superior de la pila. El analizador entonces tiene un '+' en el flujo de entrada y '+' está en la parte superior de la pila, lo que significa que, al igual que con 'a', se extrae de la pila y se elimina del flujo de entrada. Esto da como resultado:

[ F, ) , $ ]

En los próximos tres pasos, el analizador reemplazará 'F' en la pila por 'a', escriba la regla número 3 en el flujo de salida y elimine la 'a' y ')' tanto de la pila como del flujo de entrada. Por lo tanto, el analizador termina con '$'tanto en su pila como en su flujo de entrada.

En este caso, el analizador informará que ha aceptado la cadena de entrada y escribirá la siguiente lista de números de reglas en el flujo de salida:

[ 2, 1, 3, 3 ]

Esta es, de hecho, una lista de reglas para una derivación más a la izquierda de la cadena de entrada, que es:

S → ( S + F ) → ( F + F ) → ( a + F ) → ( a + a )

Implementación del analizador sintáctico en C++

A continuación se muestra una implementación en C++ de un analizador LL basado en tablas para el lenguaje de ejemplo:

#include <iostream> #include <map> #include <stack>​​​enum Symbols { // los símbolos: // Símbolos de terminal: TS_L_PARENS , // ( TS_R_PARENS , // ) TS_A , // a TS_PLUS , // + TS_EOS , // $, en este caso corresponde a '\0' TS_INVALID , // token no válido// Símbolos no terminales: NTS_S , // S NTS_F // F };/* Convierte un token válido al símbolo terminal correspondiente */ Symbols lexer ( char c ) { switch ( c ) { case '(' : return TS_L_PARENS ; case ')' : return TS_R_PARENS ; case 'a' : return TS_A ; case '+' : return TS_PLUS ; case '\0' : return TS_EOS ; // fin de pila: el símbolo terminal $ default : return TS_INVALID ; } }int main ( int argc , char ** argv ) { using namespace std ;if ( argc < 2 ) { cout << "uso: \n\t ll '(a+a)'" << endl ; return 0 ; }// Tabla del analizador LL, asigna pares <no terminal, terminal> a acciones map < Symbols , map < Symbols , int > > table ; stack < Symbols > ss ; // pila de símbolos char * p ; // búfer de entrada// inicializar la pila de símbolos ss.push ( TS_EOS ) ; // terminal, $ ss.push ( NTS_S ); // no terminal, S// inicializar el cursor de flujo de símbolos p = & argv [ 1 ][ 0 ];// configurar la tabla de análisis tabla [ NTS_S ][ TS_L_PARENS ] = 2 ; tabla [ NTS_S ][ TS_A ] = 1 ; tabla [ NTS_F ][ TS_A ] = 3 ;while ( ss . size () > 0 ) { if ( lexer ( * p ) == ss . top ()) { cout << "Símbolos coincidentes: " << lexer ( * p ) << endl ; p ++ ; ss . pop (); } else { cout << "Regla " << table [ ss . top ()][ lexer ( * p )] << endl ; switch ( table [ ss . top ()][ lexer ( * p )]) { case 1 : // 1. S → F ss . pop (); ss . push ( NTS_F ); // F break ;caso 2 : // 2. S → ( S + F ) ss . pop (); ss . push ( TS_R_PARENS ); // ) ss . push ( NTS_F ); // F ss . push ( TS_PLUS ); // + ss . push ( NTS_S ); // S ss . push ( TS_L_PARENS ); // ( break ;caso 3 : // 3. F → a ss . pop (); ss . push ( TS_A ); // a break ;predeterminado : cout << "tabla de análisis predeterminada" << endl ; return 0 ; } } }cout << "análisis finalizado" << endl ;devolver 0 ; }

Implementación de analizador sintáctico en Python

from enum import Enum from collections.abc import Generatorclase Term ( Enum ): pasarclase Regla ( Enum ): pasar# Todas las constantes están indexadas desde 0 clase Terminal ( Term ): LPAR = 0 RPAR = 1 A = 2 PLUS = 3 END = 4 INVALID = 5def __str__ ( self ): return f "T_ { self . name } "clase NonTerminal ( Regla ): S = 0 F = 1def __str__ ( self ): return f "N_ { self . name } "# Analizar tabla tabla = [[ 1 , - 1 , 0 , - 1 , - 1 , - 1 ], [ - 1 , - 1 , 2 , - 1 , - 1 , - 1 ]]REGLAS = [ [ NonTerminal . F ], [ Terminal . LPAR , NonTerminal . S , Terminal . PLUS , NonTerminal . F , Terminal . RPAR , ], [ Terminal . A ], ]pila = [ Terminal . FIN , NoTerminal . S ]def lexical_analysis ( input_string : str ) -> Generator [ Terminal ]: print ( "Análisis léxico" ) for c in input_string : match c : case "a" : yield Terminal . A case "+" : yield Terminal . PLUS case "(" : yield Terminal . LPAR case ")" : yield Terminal . RPAR case _ : yield Terminal . INVALID yield Terminal . ENDdef syntactic_analysis ( tokens : list [ Terminal ]) -> None : print ( "tokens:" , end = " " ) print ( * tokens , sep = ", " ) print ( "Análisis sintáctico" ) position = 0 while stack : svalue = stack . pop () token = tokens [ position ] if isinstance ( svalue , Term ): if svalue == token : position += 1 print ( "pop" , svalue ) if token == Terminal . END : print ( "entrada aceptada" ) else : raise ValueError ( "término incorrecto en la entrada:" , str ( token )) elif isinstance ( svalue , Rule ): print ( f " { svalue = !s} , { token = !s} " ) rule = table [ svalue . value ][ token . valor ] imprimir ( f " { regla = } " ) para r en revertido ( REGLAS [ regla ]): pila . agregar ( r ) imprimir ( "pilas:" , fin = " " ) imprimir ( * pila , sep = ", " )if __name__ == "__main__" : inputstring = "(a+a)" syntactic_analysis ( list ( lexical_analysis ( inputstring )))

Salidas:

Tokens de análisis léxico : T_LPAR, T_A, T_PLUS, T_A, T_RPAR, T_END Análisis sintáctico svalue = N_S, token = T_LPAR regla = 1 pilas: T_END, T_RPAR, N_F, T_PLUS, N_S, T_LPAR pop T_LPAR pilas: T_END, T_RPAR, N_F, T_PLUS, N_S svalue = N_S, token = T_A regla = 0 pilas: T_END, T_RPAR, N_F, T_PLUS, N_F svalue = N_F, token = T_A regla = 2 pilas: T_END, T_RPAR, N_F, T_PLUS, T_A pop T_A pilas: T_END, T_RPAR, N_F, T_PLUS pop T_PLUS pilas: T_END, T_RPAR, N_F svalue = N_F, token = T_A regla = 2 pilas: T_END, T_RPAR, T_A pop T_A pilas: T_END, T_RPAR pop T_RPAR pilas: T_END pop T_END entrada aceptada pilas:

Observaciones

Como se puede observar en el ejemplo, el analizador realiza tres tipos de pasos dependiendo de si la parte superior de la pila es un no terminal, un terminal o el símbolo especial $ :

  • Si el elemento superior no es terminal, el analizador sintáctico busca en la tabla de análisis, basándose en este no terminal y en el símbolo de la secuencia de entrada, la regla de la gramática que debe usar para reemplazar el no terminal en la pila. El número de la regla se escribe en la secuencia de salida. Si la tabla de análisis sintáctico indica que no existe tal regla, el analizador sintáctico informa un error y se detiene.
  • Si el elemento superior es un terminal, el analizador lo compara con el símbolo en el flujo de entrada y, si son iguales, ambos se eliminan. Si no son iguales, el analizador informa un error y se detiene.
  • Si el elemento superior es $ y en el flujo de entrada también hay un $ , el analizador informa que ha analizado correctamente la entrada; de lo contrario, informa un error. En ambos casos, el analizador se detendrá.

Estos pasos se repiten hasta que el analizador se detiene, momento en el que habrá analizado completamente la entrada y escrito una derivación por la izquierda en el flujo de salida, o bien habrá informado de un error.

Construcción de una tabla de análisis sintáctico LL(1)

Para completar la tabla de análisis sintáctico, debemos establecer qué regla gramatical debe elegir el analizador si encuentra un no terminal A en la parte superior de su pila y un símbolo a en su flujo de entrada. Es fácil ver que dicha regla debe tener la forma A → w y que el lenguaje correspondiente a w debe tener al menos una cadena que comience con a . Para ello, definimos el primer conjunto de w , escrito aquí como Fi ( w ), como el conjunto de terminales que se pueden encontrar al inicio de alguna cadena en w , más ε si la cadena vacía también pertenece a w . Dada una gramática con las reglas A₁ → w₁ , ..., An → wₙ , podemos calcular Fi ( wᵢ ) y Fi ( Aᵢ ) para cada regla de la siguiente manera :

  1. inicializar cada Fi ( A i ) con el conjunto vacío
  2. sumar Fi( w i ) a Fi ( A i ) para cada regla A i → w i ​​, donde Fi se define de la siguiente manera:
    • Fi( aw ′ ) = { a } para cada terminal a
    • Fi( Aw ′ ) = Fi ( A ) para todo no terminal A con ε que no está en Fi ( A )
    • Fi( Aw ′ ) = ( Fi ( A ) ∖ { ε }) ∪ Fi( w' ) para todo no terminal A con ε en Fi ( A )
    • Fi(ε) = { ε }
  3. agregar Fi( w i ) a Fi ( A i ) para cada regla A i → w i
  4. Repita los pasos 2 y 3 hasta que todos los conjuntos de Fi permanezcan iguales.

El resultado es la solución de mínimos puntos fijos para el siguiente sistema:

  • Fi ( A ) ⊇ Fi ( w ) para cada regla A → w
  • Fi ( a ) ⊇ { a }, para cada terminal a
  • Fi ( w 0 w 1 ) ⊇ Fi ( w 0 )· Fi ( w 1 ), para todas las palabras w 0 y w 1
  • Fi ( ε ) ⊇ { ε }

donde, para conjuntos de palabras U y V , el producto truncado se define porU⋅V={(túv):1∣tú∈U,v∈V}{\displaystyle U\cdot V=\{(uv):1\mid u\in U,v\in V\}}y w:1 denota el prefijo inicial de longitud 1 de las palabras w de longitud 2 o más, o w , mismo, si w tiene longitud 0 o 1.

Desafortunadamente, los conjuntos First no son suficientes para calcular la tabla de análisis. Esto se debe a que un lado derecho w de una regla podría ser finalmente reescrito como una cadena vacía. Por lo tanto, el analizador también debe usar la regla A → w si ε está en Fi ( w ) y ve en el flujo de entrada un símbolo que podría seguir a A . Por lo tanto, también necesitamos el conjunto Follow de A , escrito como Fo ( A ) aquí, que se define como el conjunto de terminales a tales que hay una cadena de símbolos αAaβ que se puede derivar del símbolo inicial. Usamos $ como un terminal especial que indica el final del flujo de entrada, y S como símbolo inicial.

El cálculo de los conjuntos de seguimiento para los no terminales en una gramática se puede realizar de la siguiente manera:

  1. inicializar Fo ( S ) con { $ } y todos los demás Fo ( A i ) con el conjunto vacío
  2. Si existe una regla de la forma A j → wA i w ′ , entonces
    • Si el terminal a está en Fi ( w ′ ), entonces agregue a a Fo ( A i ).
    • si ε está en Fi ( w ′ ), entonces agregue Fo ( A j ) a Fo ( A i )
    • Si w' tiene longitud 0, entonces suma Fo ( A j ) a Fo ( A i ).
  3. Repita el paso 2 hasta que todos los conjuntos Fo permanezcan iguales.

Esto proporciona la solución de punto fijo mínimo para el siguiente sistema:

  • Fo ( S ) ⊇ { $ }
  • Fo ( A ) ⊇ Fi ( w )· Fo ( B ) para cada regla de la forma ⁠B→…Aw{\displaystyle B\to \dots Aw}⁠

Ahora podemos definir exactamente qué reglas aparecerán dónde en la tabla de análisis. Si T [ A , a ] denota la entrada en la tabla para el no terminal A y el terminal a , entonces

T [ A , a ] contiene la regla A → w si y solo si
a está en Fi ( w ) o
ε está en Fi ( w ) y a está en Fo ( A ).

Equivalentemente: T [ A , a ] contiene la regla A → w para cada a ∈ Fi ( w )· Fo ( A ).

Si la tabla contiene como máximo una regla en cada una de sus celdas, el analizador siempre sabrá qué regla debe usar y, por lo tanto, podrá analizar cadenas sin retroceso. Es precisamente en este caso que la gramática se denomina gramática LL(1) .

Construcción de una tabla de análisis LL( k )

La construcción para analizadores LL(1) se puede adaptar a LL( k ) para k > 1 con las siguientes modificaciones:

  • El producto truncado se defineU⋅V={(túv):k∣tú∈U,v∈V}{\displaystyle U\cdot V=\{(uv):k\mid u\in U,v\in V\}}, donde w : k denota el prefijo inicial de longitud k de palabras de longitud > k , o w , mismo, si w tiene longitud k o menos,
  • Fo ( S ) = { $ k }
  • Aplique Fi ( αβ ) = Fi ( α ) ⋅ Fi ( β ) también en el paso 2 de la construcción de Fi dada para LL(1).
  • En el paso 2 de la construcción de Fo , para A j → wA i w ′ simplemente agregue Fi ( w ′ )· Fo ( A j ) a Fo ( A i ).

donde una entrada se complementa con k marcadores de fin $ , para tener en cuenta completamente el contexto de anticipación k . Este enfoque elimina los casos especiales para ε y puede aplicarse igualmente bien en el caso LL(1).

Hasta mediados de la década de 1990, se creía ampliamente que el análisis LL( k ) (para k > 1) era poco práctico, [ 12 ] : 263–265 ya que la tabla del analizador tendría un tamaño exponencial en k en el peor de los casos. Esta percepción cambió gradualmente después del lanzamiento del Purdue Compiler Construction Tool Set alrededor de 1992, cuando se demostró que muchos lenguajes de programación pueden ser analizados eficientemente por un analizador LL( k ) sin desencadenar el comportamiento del peor caso del analizador. Además, en ciertos casos el análisis LL es factible incluso con una anticipación ilimitada. Por el contrario, los generadores de analizadores tradicionales como yacc usan tablas de analizadores LALR(1) para construir un analizador LR restringido con una anticipación fija de un token.

Conflictos

Como se describe en la introducción, los analizadores sintácticos LL(1) reconocen lenguajes que poseen gramáticas LL(1), las cuales son un caso especial de gramáticas libres de contexto; sin embargo, no pueden reconocer todos los lenguajes libres de contexto. Los lenguajes LL(1) constituyen un subconjunto propio de los lenguajes LR(1), los cuales, a su vez, son un subconjunto propio de todos los lenguajes libres de contexto. Para que una gramática libre de contexto sea una gramática LL(1), no deben surgir ciertos conflictos.

Terminología

Sea A un no terminal. FIRST( A ) se define como el conjunto de terminales que pueden aparecer en la primera posición de cualquier cadena derivada de A . FOLLOW( A ) es la unión sobre: ​​[ 13 ]

  1. PRIMERO( B ) donde B es cualquier no terminal que sigue inmediatamente a A en el lado derecho de una regla de producción .
  2. SEGUIR( B ) donde B es cualquier cabeza de una regla de la forma B → wA .

LL(1) conflictos

Existen dos tipos principales de conflictos LL(1):

PRIMER/PRIMERA conflicto

Los PRIMEROS conjuntos de dos reglas gramaticales diferentes para la misma intersección no terminal. Un ejemplo de un conflicto LL(1) PRIMERO/PRIMERO:

S -> E | E 'a' E -> 'b' | ε

FIRST( E ) = { b , ε} y FIRST( E a ) = { b , a } , por lo que cuando se dibuja la tabla, hay un conflicto bajo el terminal b de la regla de producción S .

Caso especial: recursión izquierda

La recursión izquierda provocará un conflicto FIRST/FIRST con todas las alternativas.

E -> E '+' término | alt1 | alt2

PRIMER/SEGUIR conflicto

Los conjuntos PRIMERA y SEGUIDORA de una regla gramatical se superponen. Con una cadena vacía (ε) en el conjunto PRIMERA, se desconoce qué alternativa seleccionar. Un ejemplo de conflicto LL(1):

S -> A 'a' 'b' A -> 'a' | ε

El PRIMER conjunto de A es { a , ε}, y el SIGUIENTE conjunto es { a }.

Soluciones a los conflictos LL(1)

Factorización izquierda

Un factor común de la izquierda se "factoriza fuera".

A -> X | XYZ

se convierte

A -> XB B -> YZ | ε

Se puede aplicar cuando dos alternativas comienzan con el mismo símbolo, como en un conflicto FIRST/FIRST.

Otro ejemplo (más complejo) utilizando el ejemplo de conflicto FIRST/FIRST anterior:

S -> E | E 'a' E -> 'b' | ε

se convierte (fusionándose en un único no terminal)

S -> 'b' | ε | 'b' 'a' | 'a'

luego, mediante factorización izquierda, se convierte en

S -> 'b' E | E E -> 'a' | ε

Sustitución

Sustituir una regla por otra para eliminar conflictos indirectos o de tipo PRIMERO/SIGUIENTE. Tenga en cuenta que esto puede provocar un conflicto de tipo PRIMERO/PRIMERO.

Eliminación de recursión izquierda

Véase [ 14 ]

Para un método general, consulte la eliminación de la recursión izquierda . Un ejemplo sencillo de eliminación de la recursión izquierda: La siguiente regla de producción tiene recursión izquierda en E

E -> E '+' T E -> T

Esta regla no es más que una lista de T separadas por '+'. En forma de expresión regular T ('+' T)*. Por lo tanto, la regla podría reescribirse como

E -> TZ Z -> '+' TZ Z -> ε

Ahora no hay recursión por la izquierda ni conflictos en ninguna de las reglas.

Sin embargo, no todas las gramáticas libres de contexto tienen una gramática LL(k) equivalente, por ejemplo:

S -> A | B A -> 'a' A 'b' | ε B -> 'a' B 'b' 'b' | ε

Se puede demostrar que no existe ninguna gramática LL(k) que acepte el lenguaje generado por esta gramática.

Véase también

Notas

  1. ↑ Rosenkrantz, DJ; Stearns, RE (1970). "Propiedades de las gramáticas deterministas descendentes" . Information and Control . 17 (3): 226– 256. doi : 10.1016/s0019-9958(70)90446-8 .
  2. ↑ Jarzabek, Stanislav; Krawczyk, Tomasz (1974). "LL-Gramáticas regulares". Instytutu Maszyn Matematycznych : 107-119 .
  3. ↑ Jarzabek, Stanislav; Krawczyk, Tomasz (noviembre de 1975). "LL-Gramáticas regulares" . Cartas de procesamiento de información . 4 (2): 31– 37. doi : 10.1016/0020-0190(75)90009-5 .
  4. ↑ David A. Poplawski (agosto de 1977). Propiedades de los lenguajes LL-regulares (Informe técnico). Universidad de Purdue , Departamento de Ciencias de la Computación.
  5. ↑ Parr, Terence; Fisher, Kathleen (2011). "LL (*) la base del generador de analizadores sintácticos ANTLR". ACM SIGPLAN Notices . 46 (6): 425– 436. doi : 10.1145/1993316.1993548 .
  6. ↑ Belcak, Peter (2020). "La estrategia de análisis sintáctico LL(finito) para el análisis sintáctico LL(k) óptimo". arXiv : 2010.07874 [ cs.PL ].
  7. ↑ Ford, Bryan (2004). "Análisis sintáctico de gramáticas de expresiones: una base sintáctica basada en el reconocimiento". ACM SIGPLAN Notices . doi : 10.1145/982962.964011 .
  8. ↑ Pat Terry (2005). Compilación con C# y Java . Pearson Education. págs. 159–164 . ISBN  9780321263605.
  9. ↑ "Construcción de la tabla de análisis sintáctico LL(1)" . 27 de febrero de 2019.
  10. ↑ William M. Waite y Gerhard Goos (1984). Construcción de compiladores . Textos y monografías en informática. Heidelberg: Springer. ISBN 978-3-540-90821-0.Aquí: Sección  5.3.2, págs.  121-127; en particular, pág.  123.
  11. ↑ Richard E. Stearns y PM Lewis (1969). "Gramáticas de propiedades y máquinas de tablas" . Information and Control . 14 (6): 524– 549. doi : 10.1016/S0019-9958(69)90312-X .
  12. ↑ Fritzson, Peter A. (23 de marzo de 1994). Construcción de compiladores: 5.ª Conferencia Internacional, CC '94, Edimburgo, Reino Unido, 7-9 de abril de 1994. Actas . Springer Science & Business Media. ISBN 978-3-540-57877-2.
  13. ↑ "Gramáticas LL" (PDF) . Archivado (PDF) del original el 18-06-2010 . Consultado el 11-05-2010 .
  14. ^ Diseño de compilador moderno , Grune, Bal, Jacobs y Langendoen
  • Tutorial sobre la implementación de analizadores LL(1) en C# (archivado)
  • Simulador de análisis sintáctico Este simulador se utiliza para generar tablas de análisis sintáctico LL(1) y para resolver los ejercicios del libro.
  • Comparación teórica del lenguaje de las gramáticas LL y LR