Gramática LL

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

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)}$

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 ^ {*}}$

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)}$

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

La gramática C ^[1] no es LL (1): La parte inferior muestra un analizador que ha digerido los tokens " int v ;main(){" y se trata de elegir una regla para derivar el no terminal " Stmt". Mirando solo el primer token de anticipación " v", no puede decidir cuál de las dos alternativas para " Stmt" elegir, ya que son posibles dos continuaciones de entrada. Se pueden discriminar mirando el segundo token de anticipación (fondo amarillo).