Gramática LL

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

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

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

• la cuerda${\displaystyle w_{1}Aw_{3}}$puede derivarse del símbolo inicial${\displaystyle S}$,
• ${\displaystyle w_{2}}$puede derivarse de${\displaystyle A}$después de aplicar primero la regla${\displaystyle r}$, y
• la primera${\displaystyle k}$símbolos de${\displaystyle w}$y de${\displaystyle w_{2}w_{3}}$De acuerdo. ^{[ 2 ]}

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

${\displaystyle {\begin{array}{cccccc}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 el primero${\displaystyle k}$símbolos de${\displaystyle w_{2}w_{3}}$estoy de acuerdo con los de${\displaystyle w'_{2}w'_{3}}$, entonces${\displaystyle \nu =\omega }$. ^{[ 3 ] [ 4 ]}

De manera informal, cuando un analizador sintáctico se ha derivado${\displaystyle w_{1}Aw_{3}}$, con${\displaystyle A}$su no terminal más a la izquierda y${\displaystyle w_{1}}$ya consumido de la entrada, entonces al mirar eso${\displaystyle w_{1}}$y echando un vistazo al siguiente${\displaystyle k}$símbolos${\displaystyle w}$A partir de la entrada actual, el analizador puede identificar con certeza la regla de producción.${\displaystyle r}$para${\displaystyle A}$.

Cuando la identificación de reglas es posible incluso sin considerar la entrada anterior${\displaystyle w_{1}}$, 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 para${\displaystyle w_{1}}$se omite y${\displaystyle w_{1}}$se agrega al cuantificador "para algunos" para${\displaystyle w_{2},w_{3}}$Para cada gramática LL( k ), se puede construir una gramática LL( k ) fuerte estructuralmente equivalente . ^{[ 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 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 tanto vacías como 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 o no ser LALR(1). ^{[ 9 ]}

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

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

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

${\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${\displaystyle x\equiv y\mod \pi }$resulta que${\displaystyle \nu =\omega }$. ^{[ 12 ]}

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

Las gramáticas LLR no son ambiguas y no pueden ser recursivas por 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${\displaystyle \pi }$, una gramática dada es LL(${\displaystyle \pi }$Sin embargo, no es decidible si una gramática arbitraria G es LLR. Esto se debe a que decidir si una gramática G genera un lenguaje regular, lo cual sería necesario para encontrar una partición regular para G , se puede reducir al problema de correspondencia de Post .

Toda gramática LLR es LR-regular (LRR, el equivalente 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 surgieron tras 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 procesar la entrada transducida en tiempo lineal. Por lo tanto, los analizadores LLR pueden manejar una clase de gramáticas estrictamente mayor que los analizadores LL( k ) con la misma eficiencia. A pesar de ello, la teoría LLR no tiene aplicaciones importantes. Una posible y muy plausible razón es que, si bien existen algoritmos generativos para analizadores LL( k ) y LR( k ), el problema de generar un analizador LLR/LRR es indecidible a menos que se haya construido previamente una partición regular. Pero incluso el problema de construir una partición regular adecuada dada la gramática es indecidible.

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${\displaystyle Z\rightarrow aY_{1}\ldots Y_{n},n\geq 0}$), y
• diferentes lados derechos para el mismo no terminal${\displaystyle Z}$Siempre comienza con terminales diferentes.${\displaystyle a}$.

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

La clase de lenguajes que poseen 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 lenguajes incluye los conjuntos regulares que no contienen ε. ^{[ 15 ]} La equivalencia es decidible para ella, mientras que la inclusión no lo es. ^{[ 14 ]}