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 y libre de contexto . 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 llama gramática LL( k ) si se puede construir un analizador LL( k ) a partir de ella. Un lenguaje formal se llama lenguaje LL( k ) si tiene una gramática LL( k ). El conjunto de lenguajes LL( k ) está contenido propiamente 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 LL( k ) analizador.

Un analizador 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 LLR que analiza la gramática en tiempo lineal. ^{[ cita necesaria ]}

Dos tipos de analizadores de valores atípicos nomenclativos son LL(*) y LL(finito). Un analizador se llama LL(*)/LL(finito) si utiliza la estrategia de análisis LL(*)/LL(finito). ^{[5] [6]} Los analizadores LL(*) y LL(finito) están funcionalmente más cerca de los analizadores PEG . Un analizador LL (finito) puede analizar una gramática LL (k) arbitraria de manera óptima en la cantidad de comparaciones anticipadas y anticipadas. 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 es mejor considerar los analizadores LL(*) como analizadores TDPL . ^[7] Contra la idea errónea popular, los analizadores LL(*) no son LLR en general, y la construcción garantiza que funcionarán 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 para estas gramáticas son fáciles de construir y muchos lenguajes informáticos están diseñados para ser LL(1) por este motivo. ^[8] Los analizadores LL pueden estar basados ​​en tablas, ^{[ cita requerida ]} es decir, similares a los analizadores LR , pero las gramáticas LL también pueden ser analizadas mediante analizadores de descenso recursivos . Según Waite y Goos (1984), ^[9] Stearns y Lewis (1969) introdujeron las gramáticas LL( k ). ^[10]

Descripción general

Para una determinada gramática libre de contexto , 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 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)}$

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 aplica la regla 2 o la regla 3:

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

Para ser eficiente, el analizador debe poder hacer esta elección de manera determinista cuando sea posible, sin retroceder. Para algunas gramáticas, puede hacerlo echando un vistazo a la entrada no leída (sin leer). 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 (}$

Generalmente, un analizador puede mirar hacia adelante los símbolos. Sin embargo, dada una gramática, el problema de determinar si existe un analizador que la reconozca es indecidible. Para cada uno , hay un idioma que no puede ser reconocido por un analizador, 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 sólo 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 inicial y cualquier no terminal. Las entradas ya derivadas , y aún no leídas , son cadenas de terminales. Las letras griegas , y representan cualquier cadena tanto de terminales como de no terminales (posiblemente vacía). La longitud del prefijo corresponde al tamaño del búfer de anticipación 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

El analizador es un autómata pushdown determinista con la capacidad de echar un vistazo a los siguientes símbolos de entrada sin leer. Esta capacidad de vista previa se puede emular almacenando el contenido del búfer de anticipación en el espacio de estado finito, 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 poderoso, 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 de terminal (entrada) con un símbolo especial de fin de entrada (EOI) . ${\displaystyle \$}$

La pila del analizador contiene inicialmente el símbolo inicial encima del 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 saca de la pila, si . En este caso, se lee un símbolo de entrada y, si es así , 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 dan explícitamente; en su lugar , 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 anticipación ${\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 hacer la tabla más compacta, normalmente solo se muestran las filas que no son 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 analiza la siguiente entrada:

(una + una)

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 señalar como máximo 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 el no terminal 'S' y el 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 usa la tabla de análisis para procesar su entrada.

Procedimiento de análisis

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 de la parte superior de la pila coinciden, el analizador los descarta a ambos, dejando solo los símbolos que no coinciden en el flujo de entrada y en la pila.

Por lo tanto, 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 la pila- símbolo superior 'S'; esta celda contiene '2', que indica al analizador que aplique la regla (2). El analizador tiene que reescribir 'S' en ' ( S + F ) ' en la pila eliminando 'S' de la pila. y empujando ')', 'F', '+', 'S', '(' en la pila, y esto escribe la regla número 2 en la salida. La pila luego 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 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 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. Como son iguales, lo elimina del flujo de entrada y lo saca de la parte superior de la pila. Luego, el analizador tiene un ' +' en el flujo de entrada y '+' está en la parte superior de la pila, lo que significa que, como con 'a', se extrae de la pila y se elimina del flujo de entrada. Esto resulta en:

[ F, ) , $ ]

En los siguientes tres pasos, 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. Por lo tanto, el analizador termina con ' $' tanto en su pila como en su flujo de entrada.

En este caso, el analizador informará que aceptó 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:

#incluye <iostream> #incluye <mapa> #incluye <pila>   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 , // simbolo no valido  // Símbolos no terminales: NTS_S , // S NTS_F // F };/* Convierte un token válido al símbolo de terminal correspondiente */ Símbolos lexer ( char c ) { switch ( c ) { case '(' : return TS_L_PARENS ; case ')' : return TS_R_PARENS ; caso 'a' : devuelve TS_A ; caso '+' : devuelve TS_PLUS ; caso '\0' : devuelve TS_EOS ; // final de la pila: el símbolo del terminal $ predeterminado : devuelve TS_INVALID ; } }                     int main ( int argc , char ** argv ) { usando el espacio de nombres std ;      if ( argc < 2 ) { cout << "uso: \n\t ll '(a+a)'" << endl ; devolver 0 ; }        // tabla del analizador LL, asigna <no terminal, terminal> par al mapa de acciones < Símbolos , mapa < Símbolos , int >> tabla ; pila < Símbolos > ss ; // pila de símbolos char * p ; // buffer de entrada      // inicializa la pila de símbolos ss . empujar ( TS_EOS ); // terminal, $ ss . empujar ( NTS_S ); // no terminal, S// inicializa el cursor del flujo de símbolos p = & argv [ 1 ][ 0 ];  // configura la tabla de análisis table [ 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 . estallido (); } else { cout << "Regla" << tabla [ ss . arriba ()][ lexer ( * p )] << endl ; switch ( table [ ss . top ()][ lexer ( * p )]) { caso 1 : // 1. S → F ss . estallido (); ss . empujar ( NTS_F ); // F romper ;                    caso 2 : // 2. S → (S + F) ss . estallido (); ss . empujar ( TS_R_PARENS ); // ) ss . empujar ( NTS_F ); // F ss . empujar ( TS_PLUS ); // + ss . empujar ( NTS_S ); // Sss . empujar ( TS_L_PARENS ); // ( romper ; caso 3 : // 3. F → a ss . estallido (); ss . empujar ( TS_A ); // un descanso ; predeterminado : cout << "tabla de análisis predeterminada" << endl ; devolver 0 ; } } }     cout << "análisis finalizado" << endl ;    devolver 0 ; } 

Implementación del analizador en Python

# Todas las constantes están indexadas desde 0 TERM  =  0 RULE  =  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 )],  [( TERM ,  T_LPAR ),  ( REGLA ,  N_S ),  ( TERM ,  T_PLUS ),  ( REGLA ,  N_F ),  ( TERM ,  T_RPAR )],  [( TERM ,  T_A )] ]pila  =  [( TERMINO ,  T_END ),  ( REGLA ,  N_S )]def  análisis_léxico ( cadena de entrada :  cadena )  ->  lista :  imprimir ( "Análisis léxico" )  tokens  =  []  para  c  en  cadena de entrada :  si  c  ==  "+" :  tokens . agregar ( T_PLUS )  elif  c  ==  "(" :  tokens . agregar ( T_LPAR )  elif  c  ==  ")" :  tokens . agregar ( T_RPAR )  elif  c  ==  "a" :  tokens . agregar ( T_A )  más :  tokens . añadir tokens ( T_INVALID )  . agregar ( T_END ) imprimir ( tokens ) devolver tokens   def  análisis_sintáctico ( tokens :  lista )  ->  Ninguno :  print ( "Análisis sintáctico" )  posición  =  0  mientras  len ( pila )  >  0 :  ( tipo ,  valor )  =  pila . pop ()  token  =  tokens [ posición ]  if  estilo  ==  TÉRMINO :  if  svalue  ==  token :  posición  +=  1  print ( "pop" ,  svalue )  if  token  ==  T_END :  ​​print ( "entrada aceptada" )  else :  print ( "término incorrecto en la entrada:" ,  token )  romper  tipo elif  == REGLA : imprimir ( "valor" , svalor , "token" , token ) regla = tabla [ valor ][ token ] imprimir ( "regla" , regla ) para r en reversa ( REGLAS [ regla ]): pila . agregar ( r ) imprimir ( "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 la parte superior es un no terminal, entonces 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 debe 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, entonces 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 la parte superior es $ y en el flujo de entrada también hay $, entonces 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.

Construyendo una tabla de análisis LL(1)

Para llenar la tabla de análisis, tenemos que establecer qué regla gramatical debe 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 ₁ ,…, An _→ 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. agregue 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 ε que no está en Fi ( A )
   • Fi( Aw' ) = ( Fi ( A ) \ { ε }) ∪ Fi( w' ) para cada A no terminal con ε en Fi ( A )
   • Fi(ε) = { ε }
3. agregue 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 de Fi permanezcan iguales.

El resultado es la solución de punto mínimo fijo del 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 conjuntos de palabras U y V, el producto truncado se define por , y w:1 denota el prefijo inicial de longitud-1 de las palabras w de longitud 2 o más, o w, en sí, 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 una w del lado derecho de una regla podría finalmente reescribirse en la cadena vacía. Entonces, 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 de seguimiento de A , escrito aquí como Fo ( A ), que se define como el conjunto de terminales a tal que hay una cadena de símbolos αAaβ que se pueden derivar del símbolo inicial. Usamos $ como terminal especial que indica el final del flujo de entrada y S como símbolo de inicio.

Calcular los conjuntos de seguimiento para los no terminales en una gramática se puede hacer de la siguiente manera:

1. inicializa Fo ( S ) con { $ } y cada dos 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 suma Fo ( A _j ) a Fo ( A _i )
   • si w' tiene longitud 0, entonces agregue Fo ( A _j ) a Fo ( A _i )
3. repita el paso 2 hasta que todos los conjuntos de Fo permanezcan iguales.

Esto proporciona la solución de punto menos fijo 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 y en qué parte 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 ).

De manera equivalente: 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 tiene que usar y, por lo tanto, podrá analizar cadenas sin retroceder. Es precisamente en este caso que la gramática recibe el nombre de gramática LL (1) .

Construyendo una tabla de análisis LL( k )

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

• se define el producto truncado , donde w:k denota el prefijo de longitud-k inicial de palabras de longitud > k, o w, en sí mismo, si w tiene una longitud k o menos, ${\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 el sufijo k marcadores finales $ , para tener en cuenta completamente el contexto k de anticipación. Este enfoque elimina 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 ) ^{[ aclarar ]} (para k > 1) no era 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 ser analizados eficientemente por un analizador LL( k ) sin desencadenar el peor comportamiento del analizador. Además, en ciertos casos el análisis de LL es factible incluso con una anticipación ilimitada. Por el contrario, los generadores de analizadores tradicionales como yacc utilizan 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 LL(1) reconocen lenguajes que tienen gramáticas LL(1), que son un caso especial de gramáticas libres de contexto; Los analizadores LL(1) no pueden reconocer todos los lenguajes libres de contexto. Los lenguajes LL(1) son un subconjunto adecuado de los lenguajes LR(1), que a su vez son un subconjunto adecuado 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. FIRST( A ) es (definido como) el conjunto de terminales que pueden aparecer en la primera posición de cualquier cadena derivada de A . SEGUIR( 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. SEGUIR( B ) donde B es cualquier principio de una regla de la forma B → wA .

Conflictos LL(1)

Hay dos tipos principales de conflictos LL(1):

PRIMER/PRIMER 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 | mi'a'mi -> 'b' | ε

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

Caso especial: recursión izquierda

La recursividad hacia la izquierda provocará un conflicto PRIMERO/PRIMERO con todas las alternativas.

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

Conflicto PRIMERO/SEGUIDOR

El conjunto PRIMERO y SIGUIENTE de una regla gramatical se superponen. Con una cadena vacía (ε) en el PRIMER conjunto, se desconoce 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 conjunto SIGUIENTE es { a }.

Soluciones a conflictos LL(1)

factorización izquierda

Un factor izquierdo común se "excluye".

A->X | XYZ

se convierte

A -> XBB -> YZ | ε

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

Otro ejemplo (más complejo) que utiliza el PRIMER/PRIMERO ejemplo de conflicto anterior:

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

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

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

luego, mediante factorización izquierda, se convierte

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

Sustitución

Sustituir una regla por otra regla para eliminar conflictos indirectos o PRIMERO/SEGUIDOR. Tenga en cuenta que esto puede causar un conflicto PRIMERO/PRIMERO.

Eliminación de recursividad izquierda

Ver. ^[13]

Para conocer un método general, consulte Eliminación de la recursividad izquierda . Un ejemplo sencillo para la eliminación de la recursividad por la izquierda: la siguiente regla de producción ha dejado la recursividad en E

mi -> mi '+' tmi->t

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

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

Ahora no hay recursividad 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 | 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.

Ver también

• Comparación de generadores de analizadores
• árbol de análisis
• Análisis de arriba hacia abajo
• Análisis ascendente

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 Purdue , Departamento de Ciencias de la Computación.
5. Parr, Terence y Fisher, Kathleen (2011). "LL (*) la base del generador de analizador ANTLR". Avisos ACM SIGPLAN . 46 (6): 425–436. doi :10.1145/1993316.1993548.{{cite journal}}: Mantenimiento CS1: varios nombres: lista de autores ( enlace )
6. Belcak, Peter (2020). "La estrategia de análisis de LL (finito) para un análisis de 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 ACM SIGPLAN . doi : 10.1145/982962.964011.
8. Pat Terry (2005). Compilando con C# y Java. Educación Pearson. págs. 159-164. ISBN 9780321263605.
9. William M. Waite y Gerhard Goos (1984). Construcción del compilador . Textos y Monografías en Informática. Heidelberg: Springer. ISBN 978-3-540-90821-0.Aquí: Secc. 5.3.2, pág. 121-127; en particular, pág. 123.
10. Richard E. Stearns y PM Lewis (1969). "Gramáticas de propiedades y máquinas de mesa". 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). Construcción del compilador: Quinta Conferencia Internacional, CC '94, Edimburgo, Reino Unido, 7 al 9 de abril de 1994. Actas . Medios de ciencia y negocios de Springer. 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 de gramáticas LL y LR
• Teoría del análisis LL (k)