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 I eft a derecha y construye una derivación L eftmost de la oración (por lo tanto, 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 libres de contexto deterministas (DCFG) y lenguajes libres de contexto deterministas.(DCFL), respectivamente. Se dice que una determinada gramática o idioma "es una gramática / idioma 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 como precisamente aquellas que pueden ser analizadas por un analizador predictivo , un analizador de descenso recursivo sin retroceso , y estas pueden escribirse fácilmente a mano. Este artículo trata sobre las propiedades formales de las gramáticas LL; para analizar, consulte el analizador LL o el 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
- para cada cadena de símbolo de terminal de longitud hasta simbolos
- para cada símbolo no terminal , y
- para cada cadena de símbolo de terminal ,
hay como máximo una regla de producción tal que para algunas cadenas de símbolos terminales ,
- la cuerda se puede derivar del símbolo de inicio ,
- puede derivarse de después de aplicar la regla por primera vez , y
- el primero símbolos de y de estar de acuerdo. [2]
Una definición formal alternativa, pero equivalente, es la siguiente: es una gramática LL (k) si, para derivaciones arbitrarias
cuando el primero símbolos de de acuerdo con los de , luego . [3] [4]
De manera informal, cuando un analizador ha derivado , con su no terminal más a la izquierda y ya consumido de la entrada, luego mirando eso y mirando a escondidas a la siguiente simbolos de la entrada actual, el analizador puede identificar con certeza la regla de producción por .
Cuando la identificación de reglas es posible incluso sin considerar la entrada pasada , entonces la gramática se llama gramática LL (k) fuerte . [5] En la definición formal de una gramática LL ( k ) fuerte , el cuantificador universal para se omite, y se agrega al cuantificador "para algunos" para . Por cada LL ( k gramática), un LL fuerte (equivalentes estructuralmente k ) gramática puede ser construido. [6]
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 algunos k . También se puede decidir 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) sin ε 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 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 o no ser LALR (1). [9]
Las gramáticas LL no pueden tener reglas que contengan recursividad por la izquierda . [10] Cada gramática LL ( k ) que es libre de ε se puede transformar en una gramática LL ( k ) equivalente en la forma normal de Greibach (que por definición no tiene reglas con recursión por la izquierda). [11]
Caso regular
Dejar ser un alfabeto terminal. Subconjunto dees un conjunto regular si es un idioma regular sobre. Una partición de se llama una partición regular si para cada el conjunto es regular.
Dejar ser una gramática libre de contexto y dejar ser una partición regular de . Nosotros decimos esoes un LL) gramática si, para derivaciones arbitrarias
tal que resulta que . [12]
Se dice que una gramática G es LL-regular (LLR) si existe una partición regular detal que G es LL ().
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 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, que sería necesario para encontrar una partición regular para G , puede reducirse al problema de correspondencia posterior .
Cada gramática LLR es LR-regular (LRR, el equivalente correspondiente a 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 sintáctico 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 sintácticos LLR pueden manejar una clase de gramáticas estrictamente más grande que los analizadores sintácticos LL ( k ) al mismo tiempo que 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 analizadores sintácticos LL ( k ) y LR ( k ), el problema de generar un analizador sintáctico 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 la 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 la forma normal de Greibach (es decir, cada regla tiene la forma), y
- diferentes lados derechos para el mismo no terminal siempre comience con diferentes terminales .
Un conjunto de cadenas se denomina lenguaje determinista simple, o simplemente lenguaje 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 é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 por analizadores LL o por analizadores sintácticos descendentes recursivos, y muchos lenguajes de computadora [ aclarar ] están diseñados para ser LL (1) para esto. razón. Los lenguajes basados en gramáticas con un alto valor de k han sido tradicionalmente considerados [ cita requerida ] difíciles de analizar, aunque esto es menos cierto ahora dada la disponibilidad y uso generalizado [ cita requerida ] de generadores de analizadores sintácticos que soportan gramáticas LL ( k ) para arbitrario k .
Ver también
- Comparación de generadores de analizadores sintácticos para una lista de analizadores sintácticos LL (k) y LL (*)
Notas
- ^ Kernighan & Ritchie 1988 , Apéndice A.13 "Gramática", p.193 y siguientes. La parte superior de la imagen muestra un extracto simplificado en unanotación similar a EBNF .
- ^ Rosenkrantz y Stearns (1970 , p. 227). Def.1. Los autores no consideran el caso k = 0.
- ^ donde ""denota derivabilidad por derivaciones más a la izquierda, y , , y
- ^ Waite y Goos (1984 , p. 123) Def. 5.22
- ^ Rosenkrantz y Stearns (1970 , p. 235) Def.2
- ^ Rosenkrantz y Stearns (1970 , p. 235) Teorema 2
- ^ Rosenkrantz & Stearns (1970 , p. 246–247): Usando ""para denotar" o ", el conjunto de cadenas tiene un , pero no ε-free gramática, para cada .
- ^ Rosenkrantz y Stearns (1970 , págs. 254-255)
- ^ Beatty (1982)
- ^ Rosenkrantz y Stearns (1970 , págs. 241) Lema 5
- ^ Rosenkrantz y Stearns (1970 , p. 242) Teorema 4
- ^ Poplawski, David (1977). "Propiedades de LL-Lenguajes Regulares". Universidad de Purdue. Cite journal requiere
|journal=
( ayuda ) - ^ a b David A. Poplawski (agosto de 1977). Propiedades de LL-Lenguajes Regulares (Informe Técnico). Universidad Purdue , Departamento de Ciencias de la Computación.
- ↑ a b Korenjak y Hopcroft (1966)
- ↑ a b Hopcroft & Ullman (1979 , p. 229) Ejercicio 9.3
- ^ Rosenkrantz y Stearns (1970 , p. 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 .
- Hopcroft, John E .; Ullman, Jeffrey D. (1979). Introducción a la teoría, los lenguajes y la computación de los 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.). Acantilados de Englewood / Nueva Jersey: Prentice Hall. ISBN 978-013110362-7.
- Korenjak, AJ; Hopcroft, JE (1966). "Lenguajes deterministas simples". Conf. IEEE Rec. 7th Ann. Symp. sobre la teoría de la conmutación y los autómatas (SWAT) . IEEE Pub. No. 16-C-40. págs. 36–46. doi : 10.1109 / SWAT.1966.22 .
- Parr, T .; Fisher, K. (2011). "LL (*): La base del generador 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 de arriba hacia abajo deterministas" . 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 de análisis: análisis de LR (k) y LL (k) . Springer Science & Business Media. ISBN 978-3-540-51732-0.