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 subconjunto de lenguajes libres de contexto . Se analiza el aporte de L EFT a derecha, realizando L derivación eftmost de la frase.
Un analizador LL se denomina analizador LL ( k ) si utiliza k tokens de búsqueda anticipada 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 llama lenguaje LL ( k ) si tiene una gramática LL ( k ). El conjunto de idiomas LL ( k ) está contenido correctamente en el de los idiomas LL ( k +1), para cada k ≥ 0. [1] Un corolario de esto es que no todos los idiomas libres de contexto pueden ser reconocidos por un LL ( k ) analizador.
Un analizador de LL se llama LL-regular si analiza con precisión la clase de lenguajes LL-regulares [2] [3] [4] Las gramáticas LLR son un superconjunto apropiado de las gramáticas LL (k) para cualquier k. Para cada gramática LLR existe un analizador de LLR que analiza la gramática en tiempo lineal.
Dos tipos de analizador 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 sintácticos LL (*) y LL (finitos) son funcionalmente más parecidos a los analizadores sintácticos 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 que se pueden analizar mediante la estrategia LL (*) abarca algunos lenguajes sensibles al contexto debido al uso de predicados sintácticos y semánticos y no se ha identificado. Se ha sugerido que los analizadores sintácticos LL (*) se consideran mejor analizadores TDPL . [7] En contra de la idea errónea popular, los analizadores de LL (*) no son LLR en general, y la construcción garantiza que su rendimiento sea peor en promedio (superlineal contra tiempo lineal) y mucho peor en el peor de los casos (exponencial contra 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 de LL son analizadores basados en tablas, [ cita requerida ] similares a los analizadores de LR . Las gramáticas LL también se pueden analizar mediante analizadores sintácticos descendentes recursivos . Según Waite y Goos (1984), [9] Stearns y Lewis (1969) introdujeron las gramáticas LL ( k ). [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:
la derivación más a la izquierda para es:
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:
Para ser eficiente, el analizador debe poder hacer esta elección de manera determinista cuando sea posible, sin retroceder. Para algunas gramáticas, puede hacer esto mirando 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.
Generalmente, un el analizador puede mirar hacia adelante en símbolos. Sin embargo, dada una gramática, el problema de determinar si existe una analizador para algunos que lo reconoce es indecidible. Para cada, hay un idioma que no puede ser reconocido por un analizador, pero puede ser por un .
Podemos utilizar el análisis anterior para dar la siguiente definición formal:
Dejar ser una gramática libre de contexto y . Nosotros decimos eso es , si y solo si para dos derivaciones más a la izquierda:
se cumple la siguiente condición: el prefijo de la cadena de longitud es igual al prefijo de la cadena de longitud implica .
En esta definición, es el símbolo de inicio y cualquier no terminal. La entrada ya derivada, y aún no leído 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 de palabras diferentes.
Analizador
La parser es un autómata pushdown determinista con la capacidad de echar un vistazo a la siguientesímbolos de entrada sin leer. Esta capacidad de visualización se puede emular almacenando el contenido del búfer de búsqueda anticipada 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.
El alfabeto de la pila es , dónde:
- es el conjunto de no terminales;
- el conjunto de símbolos de terminal (entrada) con un símbolo especial de fin de entrada (EOI) .
La pila del analizador contiene inicialmente el símbolo de inicio sobre el EOI: . Durante la operación, el analizador reemplaza repetidamente el símbolo en la parte superior de la pila:
- Con algo , Si y hay una regla ;
- con (en algunas notaciones ), es decir se saca de la pila, si . En este caso, un símbolo de entrada se lee y si , el analizador rechaza la entrada.
Si el último símbolo que se eliminará de la pila es el EOI, el análisis se realiza correctamente; 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) utilizando una tabla de análisis más conveniente en su lugar. La tabla proporciona el siguiente mapeo:
- fila: símbolo de la parte superior de la pila
- columna: contenido del búfer anticipado
- celda: número de regla para o
Si el analizador no puede realizar una transición válida, la entrada se rechaza (celdas vacías). Para hacer que la tabla sea más compacta, normalmente solo se muestran las filas que no son terminales, ya que la acción es la misma para los terminales.
Ejemplo concreto
Configurar
Para explicar el funcionamiento de un analizador sintáctico LL (1), consideraremos la siguiente gramática pequeña LL (1):
- S → F
- S → (S + F)
- F → a
y analizar la siguiente entrada:
- (a + a)
Una tabla de análisis sintáctico 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 usa 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 'S' no terminal y la terminal '(' apunta a la regla número 2:
( ) a + PS S 2 - 1 - - F - - 3 - -
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 no coincidentes 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' a ' ( S + F ) ' en la pila quitando 'S' de la pila y presionando ')', 'F', '+', 'S', '(' en la pila, y esto escribe la regla número 2 en la salida. La pila 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' en 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 se convierte en:
[F, + , F, ) , $ ]
El analizador ahora tiene una ' a' en su flujo de entrada y una 'F' en la parte superior de su 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 su pila. Debido a que son iguales, lo elimina del flujo de entrada y lo saca de la parte superior de la pila. El analizador luego 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á la ' a' y ' )' tanto de la pila como del flujo de entrada. Por 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 regla 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 #include #include 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 , // simbolo no valido// Símbolos no terminales: NTS_S , // S NTS_F // F };/ * Convierte un token válido en el símbolo de terminal correspondiente * / Symbols 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' : retorno TS_EOS ; // fin de la pila: el símbolo $ terminal predeterminado : return 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 ; return 0 ; }// tabla LL analizador, mapas par a la acción mapa < Símbolos , mapa < Símbolos , int > > mesa ; apilar < Símbolos > ss ; // pila de símbolos char * p ; // búfer 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 ];// configurar la tabla de análisis sintáctico 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" << tabla [ ss . top ()] [ lexer ( * p )] << endl ; switch ( tabla [ ss . top ()] [ lexer ( * p )]) { caso 1 : // 1. S → F ss . pop (); ss . empujar ( NTS_F ); // F romper ;caso 2 : // 2. S → (S + F) ss . pop (); ss . empujar ( TS_R_PARENS ); //) ss . empujar ( NTS_F ); // F ss . empujar ( TS_PLUS ); // + ss . empujar ( NTS_S ); // S ss . empujar ( TS_L_PARENS ); // ( romper ;caso 3 : // 3. F → a ss . pop (); ss . empujar ( TS_A ); // un descanso ;predeterminado : cout << "tabla de análisis por defecto" << endl ; return 0 ; } } }cout << "terminado de analizar" << endl ;return 0 ; }
Implementación del analizador en Python
# Todas las constantes están indexadas desde 0 TERM = 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# Parse table table = [[ 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 = [( TERM , T_END ), ( REGLA , N_S )]def lexical_analysis ( inputtring ): print ( "Análisis léxico" ) tokens = [] para c en inputtring : if c == "+" : tokens . append ( T_PLUS ) elif c == "(" : tokens . append ( T_LPAR ) elif c == ")" : tokens . append ( T_RPAR ) elif c == "a" : tokens . añadir ( T_A ) else : tokens . añadir tokens ( T_INVALID ) . añadir ( T_END ) imprimir ( tokens ) devolver tokens def syntactic_analysis ( tokens ): impresión ( "Análisis sintáctico" ) posición = 0 mientras que len ( pila ) > 0 : ( stype , SValue ) = pila . pop () token = tokens [ posición ] if stype == TERM : if svalue == token : posición + = 1 print ( "pop" , svalue ) if token == T_END : print ( "entrada aceptada" ) else : print ( "mal término en la entrada:" , token ) romper elif stype == REGLA : print ( "svalue" , svalue , "token" , token ) regla = tabla [ svalue ] [ token ] print ( "regla" , regla ) para r al revés ( REGLAS [ regla ]): apilar . append ( r ) print ( "apilar" , apilar )inputtring = "(a + a)" syntactic_analysis ( lexical_analysis ( inputtring ))
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, sobre la base de 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, 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 la parte 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.
Construir una tabla de análisis de 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 1 → w 1 ,…, A n → w n , podemos calcular Fi ( w i ) y Fi ( A i ) para cada regla de la siguiente manera:
- inicializar cada Fi ( A i ) con el conjunto vacío
- 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 ε no en Fi ( A )
- Fi ( Aw ' ) = ( Fi ( A ) \ {ε}) ∪ Fi ( w' ) para cada A no terminal con ε en Fi ( A )
- Fi (ε) = {ε}
- agregue Fi ( w i ) a Fi ( A i ) para cada regla A i → w i
- siga los pasos 2 y 3 hasta que todos los conjuntos de Fi permanezcan iguales.
El resultado es la solución de punto fijo menos 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 los conjuntos de palabras U y V, el producto truncado se define por U · V = {(uv): 1: u ∈ U, v ∈ V}, y w: 1 denota el prefijo inicial de longitud-1 de las palabras w de longitud 2 o más, o w, en sí mismo, si w tiene una longitud de 0 o 1.
Desafortunadamente, los primeros conjuntos no son suficientes para calcular la tabla de análisis. Esto se debe a que el lado derecho w de una regla podría finalmente reescribirse en la cadena vacía. Por lo que el analizador también debe utilizar la regla A → w si ε es en internet ( w ) y se ve en la entrada de transmitir un símbolo que podría seguir una . 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 de inicio. Usamos $ como 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 hacer de la siguiente manera:
- inicializar Fo ( S ) con { $ } y cada otro Fo ( A i ) con el conjunto vacío
- si hay una regla de la forma A j → wA i w ' , entonces
- si el terminal a está en Fi ( w ' ), agregue a a Fo ( A i )
- si ε está en Fi ( w ' ), agregue Fo ( A j ) a Fo ( A i )
- si w ' tiene longitud 0, agregue Fo ( A j ) a Fo ( A i )
- 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 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 solo 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 debe usar y, por lo tanto, puede analizar cadenas sin retroceder. Es precisamente en este caso que la gramática se llama un LL (1) gramática .
Construir una tabla de análisis de LL ( k )
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 U · V = {(uv): k: u ∈ U, v ∈ V}, donde w: k denota el prefijo inicial de longitud-k de palabras de longitud> k, o w, sí mismo, si w tiene una longitud k o menos,
- Fo ( S ) = { $ k }
donde una entrada tiene el sufijo k end-markers $ , para tener en cuenta completamente el contexto k lookahead.
Hasta mediados de la década de 1990, se creía ampliamente que el análisis sintáctico de LL ( k ) (para k > 1) no era práctico, [ cita requerida ] ya que la tabla del analizador sintáctico tendría un tamaño exponencial en k en el peor de los casos. Esta percepción cambió gradualmente después del lanzamiento del conjunto de herramientas de construcción del compilador Purdue alrededor de 1992, cuando se demostró que muchos lenguajes de programación pueden ser analizados de manera eficiente 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 búsqueda anticipada 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 anticipación 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 de 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 [11]
Sea A un no terminal. PRIMER ( A ) es (definido a ser) el conjunto de terminales que pueden aparecer en la primera posición de cualquier secuencia derivada de A . SIGUE ( A ) es la unión sobre: (1) PRIMERO ( B ) donde B es cualquier no terminal que sigue inmediatamente a A en el lado derecho de una regla de producción , y (2) SIGUE ( B ) donde B es cualquier cabeza de una regla de la forma B → wA .
LL (1) conflictos
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) FIRST / FIRST:
S -> E | E 'a'E -> 'b' | ε
PRIMER ( E ) = { b , ε} y FIRST ( E un ) = { b , a }, así que cuando se dibuja la tabla, hay conflicto bajo terminal de b de regla de producción S .
Caso especial: recursividad por la izquierda
La recursividad a la izquierda provocará un conflicto FIRST / FIRST con todas las alternativas.
E -> E '+' término | alt1 | alt2
Conflicto PRIMERO / SEGUIMIENTO
El primer y el siguiente conjunto 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 ahora es { a , ε} y el SIGUIENTE conjunto { a }.
Soluciones a conflictos LL (1)
Factorización izquierda
Un factor de izquierda común es "factorizado".
A -> X | XYZ
se convierte en
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) usando el ejemplo de conflicto FIRST / FIRST anterior:
S -> E | E 'a'E -> 'b' | ε
se convierte en (fusionándose en un solo no terminal)
S -> 'b' | ε | 'b' 'a' | 'a'
luego, a través de la factorización izquierda, se convierte en
S -> 'b' E | miE -> 'a' | ε
Sustitución
Sustituir una regla por otra para eliminar conflictos indirectos o FIRST / FOLLOW. Tenga en cuenta que esto puede causar un conflicto PRIMERO / PRIMERO.
Eliminación de recursividad izquierda [12]
Para obtener un método general, consulte eliminar la recursividad izquierda . Un ejemplo simple para eliminar la recursividad por la izquierda: la siguiente regla de producción ha dejado la recursividad en E
E -> E '+' TE -> T
Esta regla no es más que una lista de "Yoes" separados por "+". En una forma de expresión regular T ('+' T) *. Entonces la regla podría reescribirse como
E -> TZZ -> '+' TZZ -> ε
Ahora no hay recursividad 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
Notas
- ^ Rosenkrantz, DJ; Stearns, RE (1970). "Propiedades de las gramáticas de arriba hacia abajo deterministas" . Información y control . 17 (3): 226–256. doi : 10.1016 / s0019-9958 (70) 90446-8 .
- ^ Jarzabek, Stanislav; Krawczyk, Tomasz (1974). "LL-Gramáticas regulares". Instytutu Maszyn Matematycznych : 107-119.
- ^ 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 .
- ^ David A. Poplawski (agosto de 1977). Propiedades de LL-Lenguajes Regulares (Informe Técnico). Universidad Purdue , Departamento de Ciencias de la Computación.
- ^ Parr, Terence y Fisher, Kathleen (2011). "LL (*) la base del generador analizador ANTLR". Avisos ACM SIGPLAN . 46 (6): 425–436. doi : 10.1145 / 1993316.1993548 .CS1 maint: varios nombres: lista de autores ( enlace )
- ^ Belcak, Peter (2020). "La estrategia de análisis sintáctico LL (finito) para un análisis sintáctico óptimo de LL (k)". arXiv : 2010.07874 [ cs.PL ].
- ^ 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 .
- ^ Pat Terry (2005). Compilando con C # y Java . Educación Pearson. págs. 159-164. ISBN 9780321263605.
- ^ 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í: Sect. 5.3.2, pág. 121-127; en particular, p. 123.
- ^ Richard E. Stearns y PM Lewis (1969). "Gramáticas de propiedad y máquinas de tabla" . Información y control . 14 (6): 524–549. doi : 10.1016 / S0019-9958 (69) 90312-X .
- ^ "Copia archivada" (PDF) . Archivado (PDF) desde el original el 18 de junio de 2010 . Consultado el 11 de mayo de 2010 .CS1 maint: copia archivada como título ( enlace )
- ^ 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 para resolver los ejercicios del libro.
- Analizador de DSL PEG LL (1) (marco del kit de herramientas)
- Comparación de la teoría del lenguaje de las gramáticas LL y LR
- LL (k) Teoría de análisis