analizador LL
En informática , un analizador LL ( derivación de izquierda a derecha, más a la izquierda ) es un analizador de arriba hacia abajo para un lenguaje restringido libre de contexto . Analiza la entrada de izquierda a derecha, realizando la derivación más a la izquierda de la oración.
Un analizador LL se denomina analizador LL( k ) si utiliza k tokens de anticipación al analizar una oración. Una gramática se denomina gramática LL( k ) si se puede construir un analizador LL( k ) a partir de ella. Un lenguaje formal se llama lenguaje LL( k ) si tiene una gramática LL( k ). El conjunto de lenguajes LL( k ) está propiamente contenido en el de lenguajes LL( k +1), para cada k ≥ 0. [1] Un corolario de esto es que no todos los lenguajes libres de contexto pueden ser reconocidos por un LL( k ) analizador.
Un analizador LL se llama LL-regular si analiza precisamente la clase de lenguajes LL-regulares . [ aclaración necesaria ] [2] [3] [4] Las gramáticas LLR son un superconjunto adecuado de gramáticas LL(k) para cualquier k. Para cada gramática LLR existe un analizador LLR que analiza la gramática en tiempo lineal.
Dos tipos de analizadores de valores atípicos nomenclativos son LL(*) y LL(finito). Un analizador se denomina LL(*)/LL(finito) si utiliza la estrategia de análisis LL(*)/LL(finito). [5] [6] Los analizadores LL(*) y LL(finitos) son funcionalmente más parecidos a los analizadores PEG . Un analizador LL (finito) puede analizar una gramática LL (k) arbitraria de manera óptima en la cantidad de búsqueda anticipada y comparaciones anticipadas. La clase de gramáticas analizables por la estrategia LL(*) abarca algunos lenguajes sensibles al contexto debido al uso de predicados sintácticos y semánticos y no ha sido identificada. Se ha sugerido que los analizadores LL(*) se consideran mejor como analizadores TDPL . [7]Contra el concepto erróneo popular, los analizadores LL(*) no son LLR en general, y están garantizados por la construcción para funcionar peor en promedio (superlineal frente a tiempo lineal) y mucho peor en el peor de los casos (exponencial frente a tiempo lineal).
Las gramáticas LL, particularmente las gramáticas LL(1), son de gran interés práctico, ya que los analizadores para estas gramáticas son fáciles de construir, y muchos lenguajes de programación están diseñados para ser LL(1) por este motivo. [8] Los analizadores LL son analizadores basados en tablas, [ cita requerida ] similares a los analizadores LR . Las gramáticas LL también se pueden analizar mediante analizadores descendentes recursivos . Según Waite y Goos (1984), [9] las gramáticas LL( k ) fueron introducidas por Stearns y Lewis (1969). [10]
Para una gramática libre de contexto dada , el analizador intenta encontrar la derivación más a la izquierda . Dada una gramática de ejemplo :
