gramática LL

Tipo de gramática libre de contexto

La gramática C ^[1] no es LL(1): la parte inferior muestra un analizador que ha digerido los tokens " int v;main(){" y está a punto de elegir una regla para derivar el no terminal " Stmt". Al observar únicamente el primer token de anticipación " v", no puede decidir cuál de ambas alternativas Stmtelegir para " ", ya que son posibles dos continuaciones de entrada. Se pueden discriminar mirando la segunda ficha de anticipación (fondo amarillo).

En la teoría del lenguaje formal , una gramática LL es una gramática libre de contexto que puede ser analizada por un analizador LL , que analiza la entrada de izquierda a derecha y construye una derivación más a la izquierda de la oración (de ahí que LL, en comparación con el analizador LR que construye una derivación más a la derecha). Un idioma que tiene una gramática LL se conoce como idioma LL . Estos forman subconjuntos de gramáticas deterministas libres de contexto (DCFG) y lenguajes deterministas libres de contexto (DCFL), respectivamente. Se dice que una gramática o un idioma determinado "es una gramática/lenguaje LL" o simplemente "es LL" para indicar que está en esta clase.

Los analizadores LL son analizadores basados ​​en tablas, similares a los analizadores LR. Alternativamente, las gramáticas LL se pueden caracterizar precisamente como aquellas que pueden ser analizadas por un analizador predictivo (un analizador de descenso recursivo sin retroceso ) y que pueden escribirse fácilmente a mano. Este artículo trata sobre las propiedades formales de las gramáticas LL; para el análisis, consulte Analizador LL o analizador de descenso recursivo .

Definicion formal

caso finito

Dado un número natural , una gramática libre de contexto es una gramática LL(k) si ${\displaystyle k\geq 0}$ ${\displaystyle G=(V,\Sigma ,R,S)}$

• para cada cadena de símbolos de terminal de longitud hasta símbolos, ${\displaystyle w\in \Sigma ^{*}}$ ${\displaystyle k}$
• para cada símbolo no terminal , y ${\displaystyle A\in V}$
• para cada cadena de símbolos de terminal , ${\displaystyle w_{1}\in \Sigma ^{*}}$

hay como máximo una regla de producción tal que para algunas cadenas de símbolos terminales , ${\displaystyle r\in R}$ ${\displaystyle w_{2},w_{3}\in \Sigma ^{*}}$

• la cadena se puede derivar del símbolo de inicio , ${\displaystyle w_{1}Aw_{3}}$ ${\displaystyle S}$
• ${\displaystyle w_{2}}$se puede derivar después de aplicar por primera vez la regla , y ${\displaystyle A}$ ${\displaystyle r}$
• los primeros símbolos de y de concuerdan. ^[2] ${\displaystyle k}$ ${\displaystyle w}$ ${\displaystyle w_{2}w_{3}}$

Una definición formal alternativa, pero equivalente, es la siguiente: es una gramática LL(k) si, para derivaciones arbitrarias ${\displaystyle G=(V,\Sigma ,R,S)}$

${\displaystyle {\begin{array}{ccccccc}S&\Rightarrow ^{L}&w_{1}A\chi &\Rightarrow &w_{1}\nu \chi &\Rightarrow ^{*}&w_{1}w_{2}w_{3}\\S&\Rightarrow ^{L}&w_{1}A\chi &\Rightarrow &w_{1}\omega \chi &\Rightarrow ^{*}&w_{1}w'_{2}w'_{3},\\\end{array}}}$

cuando los primeros símbolos de concuerdan con los de , entonces . ^{[3] [4]} ${\displaystyle k}$ ${\displaystyle w_{2}w_{3}}$ ${\displaystyle w'_{2}w'_{3}}$ ${\displaystyle \nu =\omega }$

De manera informal, cuando un analizador ha derivado , con su no terminal más a la izquierda y ya consumido de la entrada, al observarlo y observar los siguientes símbolos de la entrada actual, el analizador puede identificar con certeza la regla de producción para . ${\displaystyle w_{1}Aw_{3}}$ ${\displaystyle A}$ ${\displaystyle w_{1}}$ ${\displaystyle w_{1}}$ ${\displaystyle k}$ ${\displaystyle w}$ ${\displaystyle r}$ ${\displaystyle A}$

Cuando la identificación de reglas es posible incluso sin considerar la entrada pasada , entonces la gramática se denomina gramática LL(k) fuerte . ^[5] En la definición formal de una gramática LL( k ) fuerte, el cuantificador universal for se omite y se agrega al cuantificador "para algunos" for . Para cada gramática LL( k ), se puede construir una gramática LL( k ) fuerte estructuralmente equivalente . ^[6] ${\displaystyle w_{1}}$ ${\displaystyle w_{1}}$ ${\displaystyle w_{1}}$ ${\displaystyle w_{2},w_{3}}$

La clase de lenguajes LL( k ) forma una secuencia estrictamente creciente de conjuntos: LL(0) ⊊ LL(1) ⊊ LL(2) ⊊…. ^[7] Es decidible si una gramática dada G es LL( k ), pero no es decidible si una gramática arbitraria es LL( k ) para algún k . También es decidible si una gramática LR( k ) dada es también una gramática LL( m ) para alguna m . ^[8]

Cada gramática LL( k ) es también una gramática LR( k ). Una gramática LL(1) libre de ε también es una gramática SLR(1). Una gramática LL(1) con símbolos que tienen derivaciones vacías y no vacías también es una gramática LALR(1). Una gramática LL(1) con símbolos que solo tienen la derivación vacía puede ser LALR(1) o no. ^[9]

Las gramáticas LL no pueden tener reglas que contengan recursividad hacia la izquierda . ^[10] Cada gramática LL( k ) que es libre de ε se puede transformar en una gramática LL( k ) equivalente en forma normal de Greibach (que por definición no tiene reglas con recursividad hacia la izquierda). ^[11]

Caso normal

Sea un alfabeto terminal. Una partición de se llama partición regular si para cada uno el lenguaje es regular. ${\displaystyle \Sigma }$ ${\displaystyle \pi }$ ${\displaystyle \Sigma ^{*}}$ ${\displaystyle R\in \pi }$ ${\displaystyle R}$

Sea una gramática libre de contexto y una partición regular de . Decimos que es una gramática LL( ) si, para derivaciones arbitrarias ${\displaystyle G=(V,\Sigma ,R,S)}$ ${\displaystyle \pi =\{R_{1},\dotso ,R_{n}\}}$ ${\displaystyle \Sigma ^{*}}$ ${\displaystyle G}$ ${\displaystyle \pi }$

${\displaystyle {\begin{array}{ccccccc}S&\Rightarrow ^{L}&w_{1}A\chi _{1}&\Rightarrow &w_{1}\nu \chi _{1}&\Rightarrow ^{*}&w_{1}x\\S&\Rightarrow ^{L}&w_{2}A\chi _{2}&\Rightarrow &w_{2}\omega \chi _{2}&\Rightarrow ^{*}&w_{2}y,\\\end{array}}}$

tal que se deduce que . ^[12] ${\displaystyle x\equiv y\mod \pi }$ ${\displaystyle \nu =\omega }$

Se dice que una gramática G es LL-regular (LLR) si existe una partición regular tal que G sea LL( ). Un lenguaje es LL-regular si es generado por una gramática LL-regular. ${\displaystyle \Sigma ^{*}}$ ${\displaystyle \pi }$

Las gramáticas LLR son inequívocas y no pueden ser recursivas a la izquierda.

Cada gramática LL( k ) es LLR. Toda gramática LL( k ) es determinista, pero existe una gramática LLR que no es determinista. ^[13] Por lo tanto, la clase de gramáticas LLR es estrictamente mayor que la unión de LL( k ) para cada k .

Es decidible si, dada una partición regular , una gramática determinada es LL( ). Sin embargo, no se puede decidir si una gramática arbitraria G es LLR. Esto se debe al hecho de que decidir si una gramática G genera un lenguaje regular, lo cual sería necesario para encontrar una partición regular para G , puede reducirse al problema de correspondencia postal . ${\displaystyle \pi }$ ${\displaystyle \pi }$

Cada gramática LLR es LR-regular (LRR, el equivalente ^{[ aclarar ]} correspondiente para las gramáticas LR( k ), pero existe una gramática LR(1) que no es LLR. ^[13]

Históricamente, las gramáticas LLR siguieron a la invención de las gramáticas LRR. Dada una partición regular, se puede construir una máquina de Moore para transducir el análisis de derecha a izquierda, identificando instancias de producciones regulares. Una vez hecho esto, un analizador LL(1) es suficiente para manejar la entrada transducida en tiempo lineal. Por lo tanto, los analizadores LLR pueden manejar una clase de gramáticas estrictamente más grande que los analizadores LL( k ) y al mismo tiempo son igualmente eficientes. A pesar de eso, la teoría de LLR no tiene aplicaciones importantes. Una razón posible y muy plausible es que, si bien existen algoritmos generativos para los analizadores LL( k ) y LR( k ), el problema de generar un analizador LLR/LRR es indecidible a menos que se haya construido una partición regular por adelantado. Pero incluso el problema de construir una partición regular adecuada dada una gramática es indecidible.

Lenguajes deterministas simples

Una gramática libre de contexto se llama determinista simple , ^[14] o simplemente simple , ^[15] si

• está en forma normal de Greibach (es decir, cada regla tiene la forma ), y ${\displaystyle Z\rightarrow aY_{1}\ldots Y_{n},n\geq 0}$
• diferentes lados derechos para el mismo no terminal siempre comienzan con terminales diferentes . ${\displaystyle Z}$ ${\displaystyle a}$

Un conjunto de cadenas se denomina lenguaje determinista simple, o simplemente simple, si tiene una gramática determinista simple.

La clase de lenguajes que tienen una gramática LL(1) libre de ε en forma normal de Greibach es igual a la clase de lenguajes deterministas simples. ^[16] Esta clase de lenguaje incluye los conjuntos regulares que no contienen ε. ^[15] La equivalencia es decidible para él, mientras que la inclusión no lo es. ^[14]

Aplicaciones

Las gramáticas LL, particularmente las gramáticas LL(1), son de gran interés práctico, ya que son fáciles de analizar, ya sea mediante analizadores LL o mediante analizadores de descenso recursivo, y muchos lenguajes informáticos ^{[ aclarar ]} están diseñados para ser LL(1) para esto. razón. Los lenguajes basados ​​en gramáticas con un valor alto de k tradicionalmente se han considerado ^{[ cita necesaria ]} difíciles de analizar, aunque esto es menos cierto ahora dada la disponibilidad y el uso generalizado ^{[ cita necesaria ]} de generadores de analizadores que admiten gramáticas LL ( k ) para arbitrario k .

Ver también

• Comparación de generadores de analizadores para obtener una lista de analizadores LL(k) y LL(*)

Notas

1. Kernighan & Ritchie 1988, Apéndice A.13 "Gramática", p.193 y siguientes. La parte superior de la imagen muestra un extracto simplificado en una notación similar a EBNF .
2. Rosenkrantz y Stearns (1970, pág. 227). Def.1. Los autores no consideran el caso k =0.
3. donde " " denota derivabilidad por derivaciones más a la izquierda, y , y ${\displaystyle \Rightarrow ^{L}}$ ${\displaystyle w_{1},w_{2},w_{3},w'_{2},w'_{3}\in \Sigma ^{*}}$ ${\displaystyle A\in V}$ ${\displaystyle \chi ,\nu ,\omega \in (\Sigma \cup V)^{*}}$
4. Waite y Goos (1984, p. 123) Def. 5.22
5. Rosenkrantz y Stearns (1970, p.235) Def.2
6. Rosenkrantz y Stearns (1970, p. 235) Teorema 2
7. Rosenkrantz & Stearns (1970, p. 246-247): Al utilizar " " para denotar "o", el conjunto de cadenas tiene una gramática libre de ε, pero no , para cada uno . ${\displaystyle +}$ ${\displaystyle \{a^{n}(b^{k}d+b+cc)^{n}:n\geq 1\}}$ ${\displaystyle LL(k+1)}$ ${\displaystyle LL(k)}$ ${\displaystyle k\geq 1}$
8. Rosenkrantz y Stearns (1970, págs. 254-255)
9. Beatty (1982)
10. Rosenkrantz y Stearns (1970, págs. 241) Lema 5
11. Rosenkrantz y Stearns (1970, p. 242) Teorema 4
12. Poplawski, David (1977). "Propiedades de los lenguajes regulares LL". Universidad de Purdue. {{cite journal}}: Citar diario requiere |journal=( ayuda )
13. David A. Poplawski (agosto de 1977). Propiedades de los lenguajes regulares LL (Informe técnico). Universidad Purdue , Departamento de Ciencias de la Computación.
14. Korenjak y Hopcroft (1966)
15. Hopcroft y Ullman (1979, p. 229) Ejercicio 9.3
16. Rosenkrantz y Stearns (1970, pág.243)

Fuentes

• Beatty, JC (1982). "Sobre la relación entre las gramáticas LL(1) y LR(1)" (PDF) . Revista de la ACM . 29 (4 (octubre)): 1007–1022. doi :10.1145/322344.322350. S2CID  14700480.
• Hopcroft, John E.; Ullman, Jeffrey D. (1979). Introducción a la teoría, los lenguajes y la computación de autómatas . Addison-Wesley. ISBN 978-0-201-02988-8.
• Kernighan, Brian W.; Ritchie, Dennis M. (abril de 1988). El lenguaje de programación C. Serie de software de Prentice Hall (2ª ed.). Englewood Cliffs/Nueva Jersey: Prentice Hall. ISBN 978-013110362-7.
• Korenjak, AJ; Hopcroft, JE (1966). "Lenguajes deterministas simples". Conferencia IEEE. Rec. 7mo ann. Síntoma. sobre Teoría de Conmutación y Autómatas (SWAT) . Publicación IEEE. No. vol. 16-C-40. págs. 36–46. doi :10.1109/SWAT.1966.22.
• Parr, T.; Pescador, K. (2011). "LL(*): La base del generador de analizador ANTLR" (PDF) . Avisos ACM SIGPLAN . 46 (6): 425–436. doi :10.1145/1993316.1993548.
• 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 .
• Waite, William M.; Goos, Gerhard (1984). Construcción del compilador . Textos y Monografías en Informática. Heidelberg: Springer. ISBN 978-3-540-90821-0.

Otras lecturas

• Sippu, Seppo; Soisalon-Soininen, Eljas (1990). Teoría del análisis: análisis LR (k) y LL (k) . Medios de ciencia y negocios de Springer. ISBN 978-3-540-51732-0.