Analizador sintáctico LL
| ||||
Analizador sintáctico 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 éste 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).
Sumario
Introducción
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, aunque es bastante restrictiva, éstas son muy populares porque los analizadores LL correspondientes sólo necesitan 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
Lo siguiente describe un derivaciones por la izquierda por un analizador basado en una tabla descendente (analiza de arriba hacia abajo).
Caso general
El trabajo del analizador sobre una cadena de gramática particular.
El análisis consiste de:
- Una 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
Proceso de análisis sintáctico LL.
Una técnica para traducir gramáticas independientes del contexto a autómatas de pila es seguir el proceso de construcción que produce un autómata de pila que analiza su cadena de entrada marcando antes el fondo de la pila e insertando en la pila el símbolo inicial de la gramática. Luego se aplica:
- Si la cima de la pila contiene un no terminal de la gramática se reemplaza de acuerdo con una de las reglas de reescritura de la gramática.
- Si la cima de la pila contiene un terminal, se elimina de la pila si es el que se lee en la entrada. Sino se declara cadena ilegal.
- Si aparece la marca de fondo de pila, se elimina y se acepta la porción de la cadena de entrada procesada hasta el momento.
Este proceso analiza la sintaxis de la cadena de entrada produciendo una derivación por la izquierda, conforma lee de izquierda a derecha. Por lo que actúa como un programa obtenido de la traducción directa del autómata. Los analizadores sintácticos desarrollados de esta manera se conocen como analizadores sintácticos LL.
La primera L denota que lee su entrada de izquierda a derecha; la segunda indica que el objetivo del analizador sintáctico es producir una derivación por la izquierda.
Estos analizadores tienen el problema del no determinismo cuando tienen que elegir entre dos posibles formas de reescribir el mismo no terminal y cuentan sólo con una información. Estas opciones se dan en las gramáticas que deben generar lenguajes que contienen más de una cadena (una gramática independiente del contexto que sólo ofrece una manera de reescribir un no terminal sólo puede generar una cadena). Por ello la actividad básica de los analizadores sintácticos LL es predecir cuál de las distintas reglas de escritura se debe usar para procesar los símbolos de entrada restantes, por ello, a estos analizadores se les llama analizadores sintácticos predictivos.
Aplicando el principio de preanálisis, se pueden resolver muchos de los problemas que se presentan en los analizadores sintácticos predictivos. Existe una jerarquía para los analizadores sintácticos LL cuya característica distintiva es el número de símbolos de entrada que comprende su sistema de preanálisis. Estos se llaman analizadores sintácticos LL(k), donde k es un entero que indica el número de símbolos preanalizados.
Tablas de análisis sintáctico.
Una tabla de análisis sintáctico para un analizador sintáctico LL(k) es una matriz bidimensional. Las filas se etiquetan con los no terminales y las columnas con los terminales de la gramática sobre la cual se basa el analizador sintáctico. Se añade la columna adicional FDC (fin de cadena). El elemento (m, n) de la tabla indica la acción que se debe seguir cuando el no terminal m aparece en la cima de la pila y el símbolo de preanálisis es n.
Las tablas de análisis sintáctico simplifican la escritura del programa que efectúa el análisis y permite normalizar su algoritmo.
