Analizador sintáctico LL

De Wikipedia, la enciclopedia libre
Saltar a: navegación, búsqueda

El analizador sintático LL es un analizador sintáctico descendente, por un conjunto de gramática libre de contexto. En éste analizador las entradas son de izquierda a derecha, y construcciones de derivaciones por la izquierda de una sentencia o enunciado. La clase de gramática que es analizable por este método es conocido como gramática LL.

El resto de este artículo se describe en el cuadro de base del tipo de analizador sintáctico, la alternativa comienza con ser un intérprete de ascendencia recursiva que normalmente son codificados a mano (aunque no siempre; por ejemplo, ANTLR para un LL(*) - (generador de analizador ascendencia recursiva).

Introducción[editar]

Un analizador LL es llamado un analizador LL (k) si usa k tokens cuando el analizador ve hacia delante de la sentencia. Si existe tal analizador para cierta gramática y puede analizar sentencias de ésta gramática sin marcha atrás, entonces es llamada una gramática LL (k). De ésta gramáticas, la gramática LL(1), aunque es bastante restrictiva, éstas son muy populares porque los analizadores LL correspondientes sólo necesita ver el siguiente token para hacer el análisis de sus decisiones. Lenguajes mal diseñados usualmente suelen tener gramáticas con un alto nivel de k, y requieren un esfuerzo considerable a analizar.

Existe controversia entre la escuela europea del diseño del lenguaje, quien prefiere gramática basada en LL, y los otros países prefieren predominantemente gramática basada en LR. Esto se debe en gran parte a la influencia de Niklaus Wirth en la ETH Zürich en Suiza, cuya investigación ha descrito una serie de maneras de optimizar lenguajes y compiladores LL(1).

Arquitectura de un analizador LL[editar]

Lo siguiente describe un derivaciones por la izquierda por un analizador basado en una tabla descendente (analiza de arriba hacia abajo).

Caso general[editar]

El trabajo del analizador sobre una cadena de gramática particular.

El análisis consiste en:

  • un búfer de entrada, una cadena de gramática
  • una pila sobre la cual se almacenan los símbolos terminales y no-terminales de la gramática aún sin analizar
  • una tabla de análisis

Véase también[editar]