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 sintáctico que ha digerido los tokens " int v;main(){" y está a punto de elegir una regla para derivar el no terminal " Stmt". Al observar solo el primer token de búsqueda anticipada " v", no puede decidir cuál de las dos alternativas para " Stmt" elegir, ya que son posibles dos continuaciones de entrada. Se pueden discriminar observando el segundo token de búsqueda anticipada (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í LL, en comparación con el analizador LR que construye una derivación más a la derecha). Un lenguaje que tiene una gramática LL se conoce como lenguaje 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 lenguaje determinado "es una gramática/lenguaje LL" o simplemente "es LL" para indicar que está en esta clase.

Los analizadores sintácticos LL son analizadores sintácticos basados ​​en tablas, similares a los analizadores sintácticos LR. Las gramáticas LL pueden caracterizarse alternativamente como aquellas que pueden analizarse mediante un analizador predictivo (un analizador sintáctico descendente 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 sintáctico, consulte analizador sintáctico LL o analizador sintáctico descendente recursivo .

Definición 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 terminales con una longitud de 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ímbolo 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 de después de aplicar la primera 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 desde la entrada, entonces al observar eso y echar un vistazo a 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, se omite el cuantificador universal para y se agrega al cuantificador "para algún" para . 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 algún m . ^[8]

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

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

Caso regular

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

Sea una gramática libre de contexto y sea 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}}}$

de tal manera que se sigue 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 de tal manera que G es 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 hacia la izquierda.

Toda 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 dada es LL( ). Sin embargo, no es decidible 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 que sería necesario para encontrar una partición regular para G , se puede reducir al problema de correspondencia posterior . ${\displaystyle \pi }$ ${\displaystyle \pi }$

Toda gramática LLR es LR-regular (LRR, el equivalente ^{[ clarificador ]} correspondiente para 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 ser igualmente eficientes. A pesar de eso, la teoría de LLR no tiene ninguna aplicación importante. 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 de antemano. Pero incluso el problema de construir una partición regular adecuada dada la gramática es indecidible.

Lenguajes deterministas simples

Una gramática libre de contexto se denomina 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}$
• Los 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 la 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 ella, 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 por analizadores LL o por analizadores descendentes recursivos, y muchos lenguajes de computadora ^{[ aclarar ]} están diseñados para ser LL(1) por esta razón. Los lenguajes basados ​​en gramáticas con un alto valor de k se han considerado tradicionalmente ^{[ cita requerida ]} como difíciles de analizar, aunque esto es menos cierto ahora dada la disponibilidad y el uso generalizado ^{[ cita requerida ]} de generadores de analizadores que admiten gramáticas LL( k ) para k arbitrarios .

Véase también

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

Notas

1. Kernighan & Ritchie 1988, Apéndice A.13 "Gramática", pág. 193 y siguientes. La parte superior de la imagen muestra un extracto simplificado en una notación similar a la EBNF .
2. Rosenkrantz & Stearns (1970, p. 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ág. 235) Def.2
6. Rosenkrantz y Stearns (1970, pág. 235) Teorema 2
7. Rosenkrantz y Stearns (1970, p. 246–247): Al usar " " para denotar "o", el conjunto de cadenas tiene una , pero ninguna gramática libre de ε , para cada . ${\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ág. 242) Teorema 4
12. Poplawski, David (1977). "Propiedades de los lenguajes regulares LL". Universidad de Purdue. {{cite journal}}: Requiere citar revista |journal=( ayuda )
13. David A. Poplawski (agosto de 1977). Propiedades de los lenguajes regulares LL (informe técnico). Purdue University , Departamento de Ciencias de la Computación.
14. Korenjak y Hopcroft (1966)
15. Hopcroft & Ullman (1979, pág. 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) . Journal of the ACM . 29 (4 (Oct)): 1007–1022. doi :10.1145/322344.322350. S2CID  14700480.
• Hopcroft, John E.; Ullman, Jeffrey D. (1979). Introducción a la teoría de autómatas, lenguajes y computación . 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.ª edición). Englewood Cliffs/NJ: Prentice Hall. ISBN 978-013110362-7.
• Korenjak, AJ; Hopcroft, JE (1966). "Lenguajes deterministas simples". IEEE Conf. Rec. 7th Ann. Symp. on Switching and Autómata Theory (SWAT) . IEEE Pub. No. Vol. 16-C-40. págs. 36–46. doi :10.1109/SWAT.1966.22.
• Parr, T.; Fisher, K. (2011). "LL(*): La base del generador de analizadores sintácticos ANTLR" (PDF) . ACM SIGPLAN Notices . 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 de compiladores . Textos y monografías en informática. Heidelberg: Springer. ISBN 978-3-540-90821-0.

Lectura adicional

• 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.