Analizador LL

Analizador de arriba hacia abajo que analiza la entrada de izquierda a derecha

En informática , un analizador LL ( derivación de izquierda a derecha, más a la izquierda ) es un analizador de arriba hacia abajo para un lenguaje restringido e independiente del contexto . Analiza la entrada de izquierda a derecha y realiza la derivación más a la izquierda de la oración.

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

Un analizador sintáctico LL se denomina LL-regular (LLR) si analiza un lenguaje LL-regular . ^{[ aclaración necesaria ] [2] [3] [4]} La clase de gramáticas LLR contiene cada gramática LL(k) para cada k. Para cada gramática LLR existe un analizador sintáctico LLR que analiza la gramática en tiempo lineal. ^{[ cita necesaria ]}

Dos tipos de analizadores sintácticos atípicos nomenclativos son LL(*) y LL(finite). Un analizador sintáctico se denomina LL(*)/LL(finite) si utiliza la estrategia de análisis sintáctico LL(*)/LL(finite). ^{[5] [6]} Los analizadores sintácticos LL(*) y LL(finite) son funcionalmente más cercanos a los analizadores sintácticos PEG . Un analizador sintáctico LL(finite) puede analizar una gramática LL(k) arbitraria de manera óptima en la cantidad de comparaciones de lookahead y lookahead. 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 sintácticos LL(*) se consideran mejor analizadores sintácticos TDPL . ^[7] Contrariamente a la idea errónea popular, los analizadores LL(*) no son LLR en general, y se garantiza por construcción que tienen un peor desempeño 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, particularmente 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 computadora están diseñados para ser LL(1) por esta razón. ^[8] Los analizadores sintácticos LL pueden estar basados ​​en tablas, ^{[ cita requerida ]} 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), ^[9] las gramáticas LL( k ) fueron introducidas por Stearns y Lewis (1969). ^[10]

Descripción general

Para una gramática libre de contexto dada , el analizador intenta encontrar la derivación más a la izquierda . Dado un ejemplo de gramática : ${\displaystyle G}$

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

La derivación más a la izquierda para es: ${\displaystyle w=((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)}$

En general, 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:

${\displaystyle S\ {\overset {(1)}{\Rightarrow }}\ E\ {\overset {(?)}{\Rightarrow }}\ ?}$

Para ser eficiente, el analizador debe poder tomar esta decisión de manera determinista cuando sea posible, sin retroceder. En el caso de 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 utilizar es 2. ${\displaystyle (}$

En general, un analizador sintáctico puede buscar símbolos con antelación. Sin embargo, dada una gramática, el problema de determinar si existe un analizador sintáctico para algún que la reconozca es indecidible. Para cada , hay un lenguaje que no puede ser reconocido por un analizador sintáctico, pero sí por un . ${\displaystyle LL(k)}$ ${\displaystyle k}$ ${\displaystyle LL(k)}$ ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle LL(k)}$ ${\displaystyle LL(k+1)}$

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

Sea una gramática libre de contexto y . Decimos que es , si y solo si para dos derivaciones cualesquiera situadas más a la izquierda: ${\displaystyle G}$ ${\displaystyle k\geq 1}$ ${\displaystyle G}$ ${\displaystyle LL(k)}$

1. ${\displaystyle S\ \Rightarrow \ \cdots \ \Rightarrow \ wA\alpha \ \Rightarrow \ \cdots \ \Rightarrow \ w\beta \alpha \ \Rightarrow \ \cdots \ \Rightarrow \ wu}$
2. ${\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 cadena de longitud es igual al prefijo de la cadena de longitud implica . ${\displaystyle u}$ ${\displaystyle k}$ ${\displaystyle v}$ ${\displaystyle k}$ ${\displaystyle \beta \ =\ \gamma }$

En esta definición, es el símbolo de inicio y cualquier no terminal. La entrada ya derivada , y aún no leída , y son cadenas de terminales. Las letras griegas , y representan cualquier cadena de terminales y no terminales (posiblemente vacía). La longitud del prefijo corresponde al tamaño del búfer de búsqueda anticipada, y la definición dice que este búfer es suficiente para distinguir entre dos derivaciones cualesquiera de palabras diferentes. ${\displaystyle S}$ ${\displaystyle A}$ ${\displaystyle w}$ ${\displaystyle u}$ ${\displaystyle v}$ ${\displaystyle \alpha }$ ${\displaystyle \beta }$ ${\displaystyle \gamma }$

Analizador sintáctico

El analizador es un autómata determinista con la capacidad de echar un vistazo a los siguientes símbolos de entrada sin leerlos. Esta capacidad de echar un vistazo se puede emular almacenando el contenido del búfer de búsqueda anticipada en el espacio de estados finitos, ya que tanto el búfer como el alfabeto de entrada tienen un tamaño finito. Como resultado, esto no hace que el autómata sea más potente, pero es una abstracción conveniente. ${\displaystyle LL(k)}$ ${\displaystyle k}$

El alfabeto de la pila es , donde: ${\displaystyle \Gamma =N\cup \Sigma }$

• ${\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) . ${\displaystyle \$}$

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

• con algunos , si y hay una regla ; ${\displaystyle \alpha }$ ${\displaystyle X\in N}$ ${\displaystyle X\to \alpha }$
• con (en algunas notaciones ), es decir, se extrae de la pila, si . En este caso, se lee un símbolo de entrada y si , el analizador rechaza la entrada. ${\displaystyle \epsilon }$ ${\displaystyle \lambda }$ ${\displaystyle X}$ ${\displaystyle X\in \Sigma }$ ${\displaystyle x}$ ${\displaystyle x\neq X}$

Si el último símbolo que se elimina de la pila es el EOI, el análisis 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 proporcionan explícitamente; se especifican (generan) utilizando una tabla de análisis más conveniente . La tabla proporciona la siguiente asignación:

• fila: símbolo de la parte superior de la pila ${\displaystyle X}$
• Columna: contenido del búfer de búsqueda anticipada ${\displaystyle |w|\leq k}$
• celda: número de regla para o ${\displaystyle X\to \alpha }$ ${\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, normalmente solo se muestran las filas no terminales, ya que la acción es la misma para las terminales.

Ejemplo concreto

Configuración

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

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

y analizar la siguiente entrada:

( un + un )

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 como máximo a una regla de la gramática (identificada por su número). Por ejemplo, en la tabla de análisis de la gramática anterior, la celda para la no terminal 'S' y la terminal '(' apunta a la regla número 2:

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

Procedimiento de análisis

En cada paso, el analizador lee el siguiente símbolo disponible en el flujo de entrada y el símbolo que se encuentra en la parte superior de la pila. Si el símbolo de entrada y el símbolo que se encuentra en la parte superior de la pila coinciden, el analizador los descarta y deja solo los símbolos que no coinciden en el flujo de entrada y en la pila.

Así, en su primer paso, el analizador lee el símbolo de entrada ' ( ' y el símbolo de la parte 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', que instruye al analizador a aplicar la regla (2). El analizador tiene que reescribir 'S' a ' ( S + F ) ' en la pila quitando 'S' de la pila y empujando ')', 'F', '+', 'S', '(' en la pila, y esto escribe la regla número 2 en la salida. La pila entonces se convierte en:

[ ( , 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 su parte superior de la 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 se convierte en:

[ F, + , F, ) , $ ]

El analizador ahora tiene una " a" en su flujo de entrada y una "F" como su parte superior de la pila. La tabla de análisis 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 se convierte en:

[ a , + , F, ) , $ ]

El analizador ahora tiene una ' a' en el flujo de entrada y una 'a' en la parte superior de la pila. Debido a que son iguales, lo elimina del flujo de entrada y lo saca de la parte superior de la pila. El analizador tiene entonces 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 saca de la pila y se elimina del flujo de entrada. Esto da como resultado:

[ F, ) , $ ]

En los tres pasos siguientes, el analizador reemplazará ' F' en la pila por ' a' , escribirá la regla número 3 en el flujo de salida y eliminará ' a' y ' )' tanto de la pila como del flujo de entrada. El analizador, por tanto, 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 ]

De hecho, esta es 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 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 <mapa> #include <pila>   enum Símbolos { // los símbolos: // Símbolos terminales: 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 de terminal correspondiente */ Analizador léxico de símbolos ( 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 la pila: el símbolo de terminal $ predeterminado : return TS_INVALID ; } }                     int main ( int argc , char ** argv ) { usando el espacio de nombres std ;      si ( argc < 2 ) { cout << "uso: \n\t ll '(a+a)'" << fin ; devolver 0 ; }        // Tabla del analizador LL, asigna el par < no terminal, terminal> a la acción map < Symbols , map < Symbols , int > > tabla ; 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// inicializa el cursor del 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 ;      mientras ( ss . size () > 0 ) { si ( lexer ( * p ) == ss . top ()) { cout << "Símbolos coincidentes: " << lexer ( * p ) << endl ; p ++ ; ss . pop (); } de lo contrario { cout << "Regla " << tabla [ ss . top ()][ lexer ( * p )] << endl ; interruptor ( tabla [ ss . top ()][ lexer ( * p )]) { caso 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 ); // un break ; predeterminado : cout << "tabla de análisis predeterminada" << endl ; devolver 0 ; } } }     cout << "análisis finalizado" << endl ;    devuelve 0 ; } 

Implementación del analizador en Python

# Todas las constantes están indexadas desde 0 TÉRMINO  =  0 REGLA  =  1# Terminales T_LPAR  =  0 T_RPAR  =  1 T_A  =  2 T_PLUS  =  3 T_END  =  4 T_INVALID  =  5# No terminales N_S  =  0 N_F  =  1# Analizar tabla tabla  =  [[  1 ,  - 1 ,  0 ,  - 1 ,  - 1 ,  - 1 ],  [ - 1 ,  - 1 ,  2 ,  - 1 ,  - 1 ,  - 1 ]]REGLAS  =  [[( REGLA ,  N_F )],  [( TÉRMINO ,  T_LPAR ),  ( REGLA ,  N_S ),  ( TÉRMINO ,  T_PLUS ),  ( REGLA ,  N_F ),  ( TÉRMINO ,  T_RPAR )],  [( TÉRMINO ,  T_A )]]pila  =  [( TÉRMINO ,  T_FIN ),  ( REGLA ,  N_S )]def  lexical_analysis ( entradastring :  str )  - >  lista :  print ( " Análisis léxico" ) tokens  =  [  ]  for c  in  entradastring  : if  c  ==  "  + " : tokens.append  ( T_PLUS ) elif c == " ( " : tokens.append ( T_LPAR ) elif c == " ) " : tokens.append ( T_RPAR ) elif c == " a " : tokens.append ( T_A ) else : tokens.append ( T_INVALID ) tokens.append ( T_END ) print ( tokens ) return tokens                     def  syntactic_analysis ( tokens :  lista )  ->  None :  print ( " Análisis sintáctico" )  posición  =  0  while  len ( pila )  >  0 :  ( tipo_de_objeto ,  valor_de_objeto )  =  pila.pop () token = tokens [ posición ] if tipo_de_objeto == TÉRMINO : if valor_de_objeto == token : posición += 1 print ( "pop" , valor_de_objeto ) if token == T_END : ​​print ( " entrada aceptada" ) else : print ( "término incorrecto en la entrada:" , token ) break elif tipo_de_objeto == REGLA : print ( " valor_de_objeto" , valor_de_objeto , token ) regla = tabla [ valor_de_objeto ][ token ] print ( " regla" , regla ) for r in reversed ( REGLAS [ regla ] ): pila.append ( r ) print ( " pila" , pila )                                             cadena_de_entrada  =  "(a+a)" análisis_sintáctico ( análisis_léxico ( cadena_de_entrada ))

Observaciones

Como se puede ver 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 extremo superior es un no terminal, el analizador busca en la tabla de análisis, basándose en este no terminal y el símbolo en el flujo de entrada, qué regla de la gramática debería usar para reemplazar el no terminal en la pila. El número de la regla se escribe en el flujo de salida. Si la tabla de análisis indica que no existe tal regla, el analizador informa un error y se detiene.
• Si la parte superior es una terminal, el analizador la 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 valor 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, y luego habrá analizado completamente la entrada y escrito una derivación más a la izquierda en el flujo de salida o habrá informado un error.

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

Para llenar la tabla de análisis, tenemos que establecer qué regla gramatical debería elegir el analizador si ve 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 debería tener la forma A → w y que el lenguaje correspondiente a w debería tener al menos una cadena que comience con a . Para este propósito definimos el Primer-conjunto de w , escrito aquí como Fi ( w ), como el conjunto de terminales que se pueden encontrar al comienzo 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 ₁ , …, A _n → w _n , podemos calcular Fi ( w _i ) y Fi ( A _i ) para cada regla de la siguiente manera:

1. inicializar cada Fi ( A _i ) con el conjunto vacío
2. suma 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 cada A no terminal con ε no en Fi ( A )
   • Fi( Aw' ) = ( Fi ( A ) \ { ε }) ∪ Fi( w' ) para cada A no terminal con ε en Fi ( A )
   • Fi(ε) = { ε }
3. suma Fi( w _i ) a Fi ( A _i ) para cada regla A _i → w _i
4. Realice los pasos 2 y 3 hasta que todos los conjuntos Fi permanezcan iguales.

El resultado es la solución de punto fijo mínimo para el siguiente sistema:

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

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

Desafortunadamente, los primeros conjuntos no son suficientes para calcular la tabla de análisis. Esto se debe a que un lado derecho w de una regla podría finalmente reescribirse en la cadena vacía. Por lo tanto, el analizador también debería 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 siguiente 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 de inicio. Usamos $ como un terminal especial que indica el final del flujo de entrada y S como símbolo de inicio.

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 cada otro Fo ( A _i ) con el conjunto vacío
2. si existe una regla de la forma A _j → wA _i w' , entonces
   • Si la terminal a está en Fi ( w' ), entonces suma a a Fo ( A _i )
   • Si ε está en Fi ( w' ), entonces suma 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 → ... A w

Ahora podemos definir exactamente qué reglas aparecerán en qué lugar de 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 sólo 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, entonces el analizador siempre sabrá qué regla debe utilizar y, por lo tanto, podrá analizar cadenas sin tener que volver atrás. Es precisamente en este caso que la gramática se denomina gramática LL (1) .

Construyendo un LL(a) tabla de análisis

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

• El producto truncado se define como , donde w:k denota el prefijo de longitud inicial k de palabras de longitud > k, o w, en sí mismo, si w tiene una longitud k o menor, ${\displaystyle U\cdot V=\{(uv):k\mid u\in U,v\in V\}}$
• Fo ( S ) = { $ ^k }
• Aplique Fi (αβ) = Fi (α) Fi (β) también en el paso 2 de la construcción Fi dada para LL(1). ${\displaystyle \cdot }$
• 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 ). ${\displaystyle \cdot }$

donde una entrada tiene como sufijo k marcadores finales $ , para tener en cuenta completamente el contexto de búsqueda anticipada k. Este enfoque elimina casos especiales para ε y se puede aplicar igualmente bien en el caso LL(1).

Hasta mediados de la década de 1990, se creía ampliamente que el análisis sintáctico LL( k ) ^{[ aclarar ]} (para k > 1) era poco práctico, ^{[11] : 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 analizarse de manera eficiente mediante un analizador sintáctico LL( k ) sin activar el comportamiento del peor caso del analizador. Además, en ciertos casos, el análisis sintáctico LL es factible incluso con una mirada hacia adelante ilimitada. Por el contrario, los generadores de analizadores sintácticos tradicionales como yacc utilizan tablas de analizadores sintácticos LALR(1) para construir un analizador sintáctico LR restringido con una mirada hacia adelante fija de un token.

Conflictos

Como se describe en la introducción, los analizadores sintácticos LL(1) reconocen los lenguajes que tienen gramáticas LL(1), que son un caso especial de gramáticas libres de contexto; los analizadores sintácticos LL(1) no pueden reconocer todos los lenguajes libres de contexto. Los lenguajes LL(1) son un subconjunto propio de los lenguajes LR(1), que 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, que describimos en esta sección.

Terminología

Sea A un no terminal. PRIMERO( A ) es (definido como) el conjunto de terminales que pueden aparecer en la primera posición de cualquier cadena derivada de A . SIGUIENTE( A ) es la unión sobre: ^​​[12]

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. SIGUE( B ) donde B es cualquier cabeza de una regla de la forma B → wA .

Conflictos LL(1)

Hay dos tipos principales de conflictos LL(1):

PRIMERO/PRIMERO conflicto

Los conjuntos FIRST de dos reglas gramaticales diferentes para el mismo no terminal se intersecan. Un ejemplo de un conflicto FIRST/FIRST de LL(1):

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

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

Caso especial: recursión por la izquierda

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

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

Conflicto PRIMERO/SIGUIENTE

Los conjuntos FIRST y FOLLOW de una regla gramatical se superponen. Con una cadena vacía (ε) en el conjunto FIRST, no se sabe qué alternativa seleccionar. Un ejemplo de un 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 izquierdo común se "factoriza".

A -> X | XYZ

se convierte en

A -> XBB -> YZ | ε

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

Otro ejemplo (más complejo) que utiliza 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, a través de la factorización izquierda, se convierte en

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

Sustitución

Sustitución de una regla en otra regla para eliminar conflictos indirectos o FIRST/FOLLOW. Tenga en cuenta que esto puede provocar un conflicto FIRST/FIRST.

Eliminación de la recursión izquierda

Ver. ^[13]

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

E -> E '+' TE -> T

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

E -> TZZ -> '+' TZZ -> ε

Ahora no hay recursión hacia 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 | BA -> '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

• Comparación de generadores de analizadores sintácticos
• Árbol de análisis
• Análisis de arriba hacia abajo
• Análisis de abajo hacia arriba

Notas

1. Rosenkrantz, DJ; Stearns, RE (1970). "Propiedades de las gramáticas deterministas de arriba hacia abajo". Información y 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 regulares LL (informe técnico). Universidad de Purdue , Departamento de Ciencias de la Computación.
5. Parr, Terence y Fisher, Kathleen (2011). "LL (*) la base del generador de analizador sintáctico ANTLR". Avisos SIGPLAN de la ACM . 46 (6): 425–436. doi :10.1145/1993316.1993548.{{cite journal}}: CS1 maint: varios nombres: lista de autores ( enlace )
6. Belcak, Peter (2020). "La estrategia de análisis LL(finito) para un análisis LL(k) óptimo". arXiv : 2010.07874 [cs.PL].
7. Ford, Bryan (2004). "Análisis de gramáticas de expresión: una base sintáctica basada en el reconocimiento". Avisos SIGPLAN de ACM . doi :10.1145/982962.964011.
8. Pat Terry (2005). Compilación con C# y Java. Pearson Education. págs. 159-164. ISBN 9780321263605.
9. 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í: Sect. 5.3.2, págs. 121-127; en particular, pág. 123.
10. Richard E. Stearns y PM Lewis (1969). "Gramáticas de propiedades y máquinas de tablas". Información y control . 14 (6): 524–549. doi : 10.1016/S0019-9958(69)90312-X .
11. Fritzson, Peter A. (23 de marzo de 1994). Compiler Construction: 5th International Conference, CC '94, Edimburgo, Reino Unido, 7-9 de abril de 1994. Actas . Springer Science & Business Media. ISBN 978-3-540-57877-2.
12. "Gramáticas LL" (PDF) . Archivado (PDF) desde el original el 18 de junio de 2010. Consultado el 11 de mayo de 2010 .
13. Diseño de compilador moderno, Grune, Bal, Jacobs y Langendoen

Enlaces externos

• Un tutorial sobre la implementación de analizadores LL(1) en C# (archivado)
• Simulador de análisis Este simulador se utiliza para generar tablas de análisis LL(1) y resolver los ejercicios del libro.
• Comparación teórica del lenguaje entre las gramáticas LL y LR
• Teoría del análisis sintáctico LL(k)