UNIDAD VIII.-Generación de código intermedio.
8.1.- Funciones del generador de código intermedio.
La tarea de síntesis suele comenzar generando un código intermedio. El código intermedio no es el lenguaje de programación de ninguna máquina real, sino que corresponde a una máquina abstracta, que se debe de definir lo más general posible, de forma que sea posible traducir este código intermedio a cualquier máquina real. El objetivo del código intermedio es reducir el número de programas necesarios para construir traductores, y permitir más fácilmente la transportabilidad de unas máquinas a otras. Supóngase que se tienen n lenguajes, y se desea construir traductores entre ellos. Sería necesario construir n*(n-1) traductores. Sin embargo si se construye un lenguaje intermedio, tan sólo son necesarios 2*n traductores. Así por ejemplo un fabricante de compiladores puede construir un compilador para diferentes máquinas objeto con tan sólo cambiar las dos últimas fases de la tarea de síntesis.
8.2.- Ventajas y desventajas.
Ventajas: dentro de las ventajas de la generación de código intermedio se encuentran que: permite abstraer la máquina, separar operaciones de alto nivel de su implementación a bajo nivel, permite la reutilización de los front-ends y back-ends; y permite optimizaciones generales.
Desventajas: implica una pasada más para el compilador (no se puede utilizar el modelo de una pasada), dificulta llevar a cabo optimizaciones específicas de la arquitectura destino; y suele ser ortogonal a la máquina destino, la traducción a una arquitectura específica será más larga e ineficiente.
8.3.- Tipos de código intermedio.
AST (AbstractSyntaxTrees): forma condensada de árboles de análisis, con sólo nodos semánticos y sin nodos para símbolos terminales (se supone que el programa es sintácticamente correcto).
DAG (DirectedAcyclicGraphs): árboles sintácticos concisos.
TAC (Three-AddressCode): secuencia de instrucciones de la forma: operando, operador, operando, requieren varias instrucciones y permite la reorganización de código, manejo de ensamblador, utiliza direcciones de memoria y nemotécnicos, pueden ser instrucciones de 2, 3 o 4 por cada operación.
UNIDAD VII.-Manejo de errores.
7.1.-Función de manejo de errores.
Los errores encontrados en las distintas fases de análisis se envían a un módulo denominado manejo de errores. En el caso más sencillo puede ser un subprograma al que se le invoca enviándole el código de error, y que se encarga de escribir un mensaje con el error correspondiente, y el número de línea donde se ha producido, así como de cortar el proceso de traducción. Si se desea construir un tratamiento de errores más completo, por ejemplo detectando todos los errores del programa fuente, el módulo se complica dado que los analizadores deben proseguir su trabajo con falta de datos.
7.2.- Errores léxicos.
Los errores léxicos se detectan cuando el analizador léxico intenta reconocer componentes léxicos y la cadena de caracteres de la entrada no encaja con ningún patrón. Son situaciones en las que usa un carácter inválido (@, $,",>,...), que no pertenece al vocabulario del lenguaje de programación, al escribir mal un identificador, palabra reservada u operador.
Algunos de los errores léxicos típicos son:
Nombre ilegales de identificadores: un nombre contiene caracteres inválidos.
Números incorrectos: un número contiene caracteres inválidos o no está formado correctamente.
Errores en palabras reservadas: caracteres omitidos, adicionales o cambiados de sitio.
Fin de archivo: se detecta un fin de archivo a la mitad de un componente léxico.
Los errores léxicos se deben a descuidos del programador. En general, la recuperación de errores léxicos es sencilla y siempre se traduce en la generación de un error de sintaxis que sería detectado más tarde por el analizador sintáctico cuando el analizador léxico devuelve un componente léxico que el analizador sintáctico no espera en esa posición.
Los métodos de recuperación de errores léxicos se basan bien en saltarse caracteres en la entrada hasta que un patrón se ha podido reconocer; o bien usar otros métodos más sofisticados que incluyen la inserción, borrado, sustitución de un carácter en la entrada o intercambio de dos caracteres consecutivos.
7.3.- Errores sintácticos.
El manejo de errores de sintaxis es el más complicado desde el punto de vista de la creación de compiladores. Nos interesa que cuando el compilador encuentre un error, se recupere y siga buscando errores. Por lo tanto el manejador de errores de un analizador sintáctico debe tener como objetivos: indicar los errores de forma clara y precisa, aclarar el tipo de error y su localización, recuperarse del error, para poder seguir examinando la entrada, no ralentizar significativamente la compilación.
Existen varias formas de corregir errores sintácticos y así evitar todos los problemas que generaría un error no detectado en esta fase y cuando se encuentra en fases más avanzadas
Ignorar el problema (Panic mode): consiste en ignorar el resto de la entrada hasta llegar a una condición de seguridad.
Recuperación a nivel de frase: intenta recuperar el error una vez descubierto. Hay que tener cuidado con este método, pues puede dar lugar a recuperaciones infinitas.
Reglas de producción adicionales para el control de errores: la gramática se puede aumentar con las reglas que reconocen los errores más comunes.
Corrección global: dada una secuencia completa de tokens a ser reconocida, si hay algún error por el que no se puede reconocer, consiste en encontrar la secuencia completa más parecida que sí se pueda reconocer. Es decir, el analizador sintáctico le pide toda la secuencia de tokens al léxico, y lo que hace es devolver lo más parecido a la cadena de entrada pero sin errores, así como el árbol que lo reconoce.
7.4.- Errores semánticos.
En cierto modo, este tipo de error es el más difícil de depurar, ya que ni el compilador ni el sistema proporcionan información sobre qué está fallando. Lo único cierto es que el programa no se está comportando como debería.
Un error semántico se produce cuando la sintaxis del código es correcta, pero la semántica o significado no es el que se pretendía. La construcción obedece las reglas del lenguaje, y por ello el compilador o intérprete no detectan los errores semánticos. Los compiladores e intérpretes sólo se ocupan de la estructura del código que se escribe, y no de su significado.
Un error semántico puede hacer que el programa termine de forma anormal, con o sin un mensaje de error. Hablando en términos coloquiales, puede hacer que el equipo se quede "colgado".
Sin embargo, no todos los errores semánticos se manifiestan de una forma tan obvia. Un programa puede continuar en ejecución después de haberse producido errores semánticos, pero su estado interno puede ser distinto del esperado. Eventualmente, la consecuencia será un resultado incorrecto. Estos errores se denominan lógicos, ya que aunque el programa no se bloquea, la lógica que representan contiene un error.
El primer paso para corregirlo es intentar encontrar una correspondencia entre el código del programa y el comportamiento que se observa. Quizá las variables no contengan los datos correctos, o bien es posible que el programa siga un camino distinto del pretendido.
UNIDAD VI.-Análisis semántico.
6.1.-Funciones del análisis semántico.
El analizador semántico detecta la validez semántica de las sentencias aceptadas por el analizador sintáctico. El analizador semántico suele trabajar simultáneamente al analizador sintáctico y en estrecha cooperación. Se entiende por semántica como el conjunto de reglas que especifican el significado de cualquier sentencia sintácticamente correcta y escrita en un determinado lenguaje.
Las rutinas semánticas deben realizar la evaluación de los atributos de las gramáticas siguiendo las reglas semánticas asociadas a cada producción de la gramática. El análisis sintáctico es la fase en la que se trata de determinar el tipo de los resultados intermedios, comprobar que los argumentos que tiene un operador pertenecen al conjunto de los operadores posibles, y si son compatibles entre sí, etc. En definitiva, comprobará que el significado de lo que se va leyendo es válido.
La salida “teórica” de la fase de análisis semántico sería un árbol semántico. Consiste en un árbol sintáctico en el que cada una de sus ramas ha adquirido el significado que debe tener.
En el caso de los operadores polimórficos (un único símbolo con varios significados), el
análisis semántico determina cuál es el aplicable.
Se compone de un conjunto de rutinas independientes, llamadas por los analizadores morfológico y sintáctico. El análisis semántico utiliza como entrada el árbol sintáctico detectado por el análisis sintáctico para comprobar restricciones de tipo y otras limitaciones semánticas y preparar la generación de código. Las rutinas semánticas suelen hacer uso de una pila (la pila semántica) que contiene la información semántica asociada a los operandos (y a veces a los operadores) en forma de registros semánticos.
6.2.- Reglas semánticas.
Son el conjunto de normas y especificaciones que definen al lenguaje de programación y están dadas por la sintaxis del lenguaje, las reglas semánticas asignan un significado lógico a ciertas expresiones definidas en la sintaxis del lenguaje.
La evaluación de las reglas semánticas define los valores de los atributos en los nodos del árbol de análisis sintáctico para la cadena de entrada. Una regla semántica también puede tener efectos colaterales, por ejemplo, imprimir un valor o actualizar una variable global.
6.3.- Compatibilidad de tipos.
Durante la fase de análisis semántico, el compilador debe verificar que los tipos y valores asociados a los objetos de un programa se utilizan de acuerdo con la especificación del lenguaje. Además debe detectar conversiones implícitas de tipos para efectuarlas o insertar el código apropiado para efectuarlas así como almacenar información relativa a los tipos de los objetos y aplicar las reglas de verificación de tipos.
La compatibilidad básica de tipos puede ser de la siguiente manera:
Equivalencia: determina cuándo dos objetos pueden considerarse del mismo tipo.
Compatibilidad: determina cuándo un objeto de cierto tipo puede ser usado en un cierto contexto.
Inferencia: derivación del tipo de un objeto a partir de sus componentes.
Conversión: permitir y efectuar un cambio de tipo.
Coerción: conversión automática de un tipo a otro.
Flujo de control: Las proposiciones que hacen que el flujo del control abandone una construcción deben tener algún lugar a dónde transferir el flujo de control.
Nombres: en ocasiones, el mismo nombre debe aparecer dos o más veces en un mismo bloque de instrucciones, el compilador debe comprobar que se utilice el mismo nombre en ambos sitios.
6.4.- Sistemas de tipos.
Un sistema de tipos es una serie de reglas para asignar expresiones de tipos a las distintas partes de un programa y verificar su corrección. En concreto, formarán el sistema de tipos las definiciones y reglas que permiten comprobar cuál es el dominio asignado a una variable, y en qué contextos puede ser usada. Un sistema de tipos puede tener comprobaciones tanto estáticas como dinámicas.
Los tipos básicos que están definidos en un sistema de tipos son:
Tipos primitivos: son todos aquellos que están definidos por el lenguaje y son las expresiones más simples que existen, dentro de estas se encuentran:
booleano: un byte, 0 (false), 1 (true)
carácter: un byte, ASCII Java: dos bytes, UNICODE
entero: dos bytes...
real: coma fija, coma flotante
Constructores: son construcciones de datos que permiten generar datos complejos en base a los tipos de datos primitivos. Cada elemento construido debe ser independiente de los demás, deben poder usarse en cualquier combinación y deben tener coherencia y sentido.
Algunos ejemplos de construcciones son:
enumerados: orden total
sub rangos: intervalos
registros: tuplas o filas de datos
vectores: secuencias de datos agrupadas en localidades de memoria adjuntas
conjuntos: selección de datos que forman parte de un todo
punteros: referencias a memoria.
listas: secuencias sin indexado
ficheros: secuencias de código con posición.
funciones: genera un valor y realizan ciertas acciones dentro del programa.
6.5.- Comprobación estática y dinámica de tipos.
La comprobación sirve para manejar y descubrir errores en el código y como resultado mínimo, se espera que el compilador informe la naturaleza y la posición del error. Es mejor que el comprobador de tipos se recupere de los errores, para que pueda comprobar el resto de la entrada. Como el manejo de errores afecta a las reglas de comprobación de tipos, tiene que diseñarse como parte del sistema de tipos desde el principio; las reglas tienen que servir para tratar los errores.
La inclusión del manejo de errores puede dar como resultado un sistema de tipos que vaya más allá del necesario para especificar programas correctos. Como ya se menciono puede ser de 2 tipos: estática y dinámica.
Comprobación estática: es llevada a cabo durante la compilación y antes de la ejecución, para ello toda la información necesaria debe estar disponible al momento de la compilación, durante está etapa no se genera código.
Comprobación dinámica: es llevada a cabo durante la ejecución, por lo cual puede encontrar errores por referencia a variables que aún no tienen valor o por el uso de punteros NULL, los programas que implementan está técnica de comprobación generalmente son poco eficientes y tardan más en realizar su ejecución, esta comprobación es usada por los intérpretes .
6.6.- Comprobación de tipos en expresiones, sentencias y funciones.
A partir de reglas semánticas se desarrolla la comprobación de tipos para expresiones, sentencias y funciones. El comprobador de tipos es un esquema de traducción que sintetiza el tipo de cada expresión a partir de los tipos de las subexpresiones. El comprobador de tipos puede manejar matrices, apuntadores, proposiciones y funciones.
6.7.- Conversiones de tipos, sobrecarga de funciones y operadores, funciones polimórficas.
Conversiones de tipos: se usan cuando los tipos de datos no coinciden entre si y se quiere hacer una operación entre ellos como una asignación o una suma, para ello el compilador válida los tipos de dato primero y después hace una conversión siempre que sea posible para poder llevar a cabo la operación, en algunos lenguajes esto es conocido como “casting”.
Coerciones: en este caso la conversión entre tipos está implícita si el compilador lo realiza automáticamente, esta condición limita a muchos lenguajes a situaciones donde en algunos casos no se pierde información pero en otros si, por ejemplo si es viable convertir un entero aun real pero no al contrario.
Sobrecarga de funciones y operadores: se origina cuando una variable, método o función tiene varios contextos o definiciones en su contexto, por ejemplo cuando en un programa una variable es declarada global como doble y localmente como entero, o cuando una función tiene el mismo nombre (polimorfismo) pero recibe parámetros distintos y los valores que utiliza son también distintos. Este “problema” se resuelve asignando un solo valor y significado a cada variable.
Funciones polimórficas: es cuando una función es definida varias veces, pero en cada definición está posee diversos parámetros de diversos tipos, esto no solo se aplica a funciones, también a variables y otras partes de código.
UNIDAD V.- Traducción dirigida por la sintaxis.
5.1.- Traducción o definición dirigida por sintaxis.
Una definición dirigida por sintaxis es una gramática de contexto libre en la que cada símbolo gramatical (terminales y no terminales) tiene un conjunto de atributos asociados, dividido en dos subconjuntos llamados atributos sintetizados y atributos heredados de dicho símbolo gramatical.
Un atributo puede representar cualquier cosa. El valor de un atributo en un nodo de un árbol de análisis sintáctico se define mediante una regla semántica asociada a la regla de producción utilizada en dicho nodo. El valor de un atributo sintetizado de un nodo se calcula a partir de los valores de los atributos hijos de dicho nodo en el árbol de análisis sintáctico; el valor de un atributo heredado se calcula a partir de los valores de los atributos en los hermanos y el padre de dicho nodo.
Las reglas semánticas establecen las dependencias entre los atributos que serán representadas mediante un grafo. Del grafo de dependencias se obtiene un orden de evaluación de las reglas semánticas. La evaluación de las reglas semánticas define los valores de los atributos en los nodos del árbol de análisis sintáctico para la cadena de entrada.
5.2.-Forma de una traducción dirigida por sintaxis.
En una definición dirigida por sintaxis, cada regla de producción A Ú . tiene asociado un conjunto de reglas semánticas de la forma b:=f(c1, c2, ..., ck), donde f es una función, y, o bien
1. b es un atributo sintetizado de A y c1, c2, ..., ck son atributos de los símbolos de ., o
Bien
2. b es un atributo heredado de uno de los símbolos de . , y c1, c2, ..., ck son atributos de los restantes símbolos de . o bien de A.
En cualquier caso, se dice que el atributo b depende de los atributos c1, c2, ..., ck.
Una gramática con atributos es una definición dirigida por sintaxis en la que las funciones en las reglas semánticas no pueden tener efectos colaterales.
En una definición dirigida por sintaxis, se asume que los terminales sólo tienen atributos sintetizados, ya que la definición no proporciona ninguna regla semántica para los terminales.
El analizador léxico es el que proporciona generalmente los valores de los atributos de los terminales. Además se asume que el símbolo inicial no tiene ningún atributo heredado, a menos que se indique lo contrario.
5.3.- Atributos sintetizados.
Los atributos sintetizados son muy utilizados en la práctica. Una definición dirigida por sintaxis que usa atributos sintetizados exclusivamente se denomina definición con atributos sintetizados. Siempre se puede anotar un árbol de análisis sintáctico para una definición con atributos sintetizados mediante la evaluación de las reglas semánticas para los atributos en cada nodo de forma ascendente, de las hojas a la raíz.
5.4.- Atributos heredados.
Un atributo heredado es uno cuyo valor en un nodo de un árbol de análisis sintáctico está definido a partir de los atributos en el padre y/o de los hermanos de dicho nodo. Los atributos heredados sirven para expresar la dependencia de una construcción de un lenguaje de programación en el contexto en el que aparece.
5.5.- Grafo de dependencias y evaluación de orden.
Las interdependencias entre los atributos heredados y sintetizados en los nodos de un árbol de análisis sintáctico se pueden representar mediante un grafo dirigido llamado grafo de dependencias. El grafo de dependencias se construye como se indica más arriba. A partir de un ordenamiento topológico del grafo de dependencias, se obtiene un orden de evaluación para las reglas semánticas. La evaluación de las reglas semánticas en este orden produce la traducción de la cadena de entrada.
5.6.- Gramática L-atribuida.
También llamada atribuida por la izquierda, o definición con atributos por la izquierda. En toda regla A Ú X1 X2 ... Xn, cada atributo heredado de Xj 1 j n depende sólo de:
1. Los atributos (sintetizados o heredados) de los símbolos X1 X2 ... Xj-1.
2. Los atributos heredados de A.
Este tipo de gramáticas no producen ciclos y además admiten un orden de evaluación en profundidad.
5.7.- Gramática S-atribuida.
Es una gramática atribuida que sólo contiene atributos sintetizados Una gramática S- atribuida es también L-atribuida. Los atributos sintetizados se pueden evaluar con un analizador sintáctico ascendente conforme la entrada es analizada.
UNIDAD IV.- Herramientas básicas para generar compiladores.
Para la creación de código, es importante considerar los siguientes aspectos: la arquitectura de software para la cual se va a desarrollar el generador de código, las características especificas del lenguaje de programación para el cual se hará el generador, el lenguaje con el que se desarrollará el propio generador.
Afortunadamente para cada lenguaje de programación para el cual se vaya a desarrollar un compilador, existen variadas herramientas que pueden ayudar a su construcción. Estas herramientas pueden hacer muchas de las tareas que realizan los compiladores, tales como la búsqueda de patrones, la escritura de código, el análisis sintáctico, el análisis léxico y la optimización de código
4.1.- Herramientas tradicionales.
Lex/yacc: es un programa para generar analizadores léxicos, se utiliza comúnmente con el programa yacc que se utiliza para generar análisis sintáctico. Lex, escrito originalmente por Eric Schmidt y Mike Lesk, es el analizador léxico estándar en los sistemas Unix, y se incluye en el estándar de POSIX. Lex toma como entrada una especificación de analizador léxico y devuelve como salida el código fuente implementando el analizador léxico en C.
Yacc: es una herramienta general para describir la entrada a un programa de computadora. El usuario especifica las estructuras de su entrada, junto con el código que puede invocarse como cada estructura como se reconoce y yacc devuelve una subrutina que controla el proceso de entrada, con frecuencia, es conveniente y apropiado que la mayor parte del flujo de control en la aplicación del usuario al cargo de este subprograma. Fue desarrollado por Stephen C. Johnson en para Unix. El nombre es un acrónimo de " Sin embargo, otro compilador de compiladores . " Se genera un programa de análisis (por parte de un compilador que intenta darle sentido sintáctico del código fuente), y genera código para C.
Flex: herramienta que implementa un analizador léxico. Es una herramienta para generar escáneres: programas que reconocen patrones léxicos en un texto. Flex lee los ficheros de entrada dados, o la entrada estándar si no se le ha indicado ningún nombre de fichero, con la descripción de un escáner a generar. La descripción se encuentra en forma de parejas de expresiones regulares y código C, denominadas reglas. Flex genera como salida un fichero fuente en C
Bison: herramienta que implementa un analizador sintáctico. Es un generador de analizadores sintácticos de propósito general perteneciente al proyecto GNU disponible para prácticamente todos los sistemas operativos. Bison convierte la descripción formal de un lenguaje, escrita como una gramática libre de contexto LALR, en un programa en C, C++, o Java que realiza análisis sintáctico. GNU bison tiene compatibilidad con Yacc.
PCyacc.
PClex.
4.2.-Herramientas de nueva generación.
ANTLR (ANother Tool for Language Recognition – otra herramienta para reconocimiento de lenguajes): es una herramienta creada principalmente por Terence Parr, que opera sobre lenguajes, proporcionando un marco para construir reconocedores (parsers), intérpretes, compiladores y traductores de lenguajes a partir de las descripciones gramaticales de los mismos (conteniendo acciones semánticas a realizarse en varios lenguajes de programación). ANTLR genera un programa que determina si una sentencia o palabra pertenece a dicho lenguaje (reconocedor), utilizando algoritmos LL(*) de parsing. Si a dicha gramática, se le añaden acciones escritas en un lenguaje de programación, el reconocedor se transforma en un traductor o interprete. Además, proporciona facilidades para la creación de árboles sintácticos y estructura para recorrerlos. ANTLR es un proyecto bajo licencia BSD, viniendo con todo el código fuente disponible, y preparado para su instalación bajo plataformas Linux, Windows y Mac OS X.
Actualmente ANTLR genera código Java, C, C++, C#, Python, Perl, Delphi, Ada95, JavaScript y Objective-C.
JavaCC (Java Compiler Compiler): es un generador de analizadores sintácticos de código abierto para el lenguaje de programación Java, es similar a Yacc en que genera un parser para una gramática presentada en notación BNF, con la diferencia de que la salida es en código Java y genera analizadores descendentes. Además agrega un constructor de árboles conocido como: JJTree, construye árboles de abajo hacia arriba.
4.3.- Otras herramientas.
BYACC/JAVA: es una extensión de YACC para generar código JAVA en vez de C/C++, que genera ficheros de especificaciones igual que YACC y sus salidas son código y declaraciones de lenguaje escritos en JAVA.
COCO/JAVA: es una herramienta de distribución de Java para Linux, es un generador de compiladores que a partir de la descripción del lenguaje mediante una gramática LL genera un analizador sintáctico y un analizador léxico para dicho lenguaje o sea es un meta compilador.
CUP: versión LEX/YACC para JAVA (su forma de trabajo es análoga).
JELL: es un generador de analizadores sintácticos que genera analizadores descendentes a partir de gramáticas LL, también es un meta compilador.
4.4.- Kits para la construcción de compiladores.
COKTAIL: conjunto de herramientas para construir compiladores
REXàgenerador de analizadores léxicos.
LALRàgenerador de analizadores sintácticos.
ELLàgenerador de analizadores sintácticos.
ASTàgenerador de árboles sintácticos.
AGàpermite procesar gramáticas atribuidas.
ELI: combina una variedad de herramientas estándar para implementar potentes estrategias en la construcción de compiladores. Se pueden generar automáticamente implementaciones de lenguajes completos a partir de las especificaciones de la aplicación. Contiene librerías de especificaciones reusables.
PCCT: Escrito inicialmente en C++ para generar compiladores en C++. Portado a JAVA y llamado ANTLR. Consta de 3 herramientas:
ANTLRàgenerador de analizadores de sintácticos
DLGàgenerador de analizadores léxicos
SORCERERàgenerador de árboles sintácticos
UNIDAD III.- Analizador sintáctico.
3.1.-Función del análisis sintáctico.
El análisis sintáctico tiene como función principal generar un árbol de análisis sintáctico a partir de los componentes léxicos obtenidos en la etapa anterior.
El análisis sintáctico (en inglés parser) es un análisis a nivel de sentencias, y es mucho más complejo que el análisis léxico. Su función es tomar el programa fuente en forma de tokens, que recibe del analizador léxico y determinar la estructura de las sentencias del programa.
El análisis sintáctico agrupa a los tokens en clases sintácticas (denominadas no terminales en la definición de la gramática), tales como expresiones, procedimientos, etc., y obtiene un árbol sintáctico (u otra estructura equivalente) en la cual las hojas son los tokens y cualquier nodo, que no sea una hoja, representa un tipo de clase sintáctica.
Tipos de analizadores sintácticos.
Hay distintas clases de analizadores o reconocedores sintácticos, en general se clasifican en dos grandes grupos: analizadores sintácticos ascendentes y analizadores sintácticos descendentes.
Análisis sintáctico descendente: construyen el árbol sintáctico a partir del símbolo inicial de la gramática, hasta llegar a los distintos tokens, que constituyen la sentencia a analizar. Es decir, se parte del símbolo inicial de la gramática y se van aplicando las distintas producciones hasta llegar a formar la sentencia. El orden de derivación es importante, siempre se deriva primero el no terminal situado más a la izquierda según se mira el árbol (derivaciones más a la izquierda).
Los principales problemas que se plantean en el análisis sintáctico descendente son dos: el retroceso (en inglés backtracking) y la recursividad a izquierdas.
Análisis sintáctico con retroceso: el retroceso, se produce cuando se eligen mal las producciones para alcanzar la sentencia a analizar, y debe de darse marcha atrás en el proceso de análisis, para elegir otra alternativa. El retroceso se repite hasta que se ha elegido la alternativa correcta; evidentemente esto ralentiza enormemente el proceso de análisis.
Análisis sintáctico LL: son usados para evitar el retroceso y la recursividad a izquierda, se deriva de que en general se elige el criterio de tomar siempre en primera opción la alternativa más a la izquierda. Para ello, las gramáticas deben de cumplir unas determinadas propiedades, dando lugar a una clasificación de las gramáticas. Los lenguajes de programación que se pueden describir mediante uno de estos tipos de gramáticas, llamadas LL (Libres de contexto)(k), aquí se realiza el análisis descendente determinista, por medio del reconocimiento de la cadena de entrada de izquierda a derecha (Left to right) y que va tomando las derivaciones más a la izquierda con sólo mirar los k tokens situados a continuación de donde se halla.
Análisis sintáctico ascendente: construyen el árbol sintáctico a partir de las hojas, paso a paso hasta llegar a la raíz. Es decir parten de los distintos tokens de la sentencia a analizar, y por medio de reducciones llegan al símbolo inicial de la gramática. Se llaman reducciones, para indicar que se efectúan en sentido contrario a las producciones de la gramática.
Análisis ascendente con retroceso: El principal problema que se plantea en el análisis ascendente es el del retroceso, que se traduce en la elección de un pivote para realizar la reducción.
Análisis sintáctico LR: Para evitar el problema del retroceso, se definieron distintos tipos de gramáticas entre las cuales las más utilizadas son las LR (k). Los analizadores sintácticos ascendentes que reconocen lenguajes descritos por gramáticas LR (k), toman sus decisiones en función de los k tokens inspeccionados por delante de cada vez en la cadena de entrada, tomados de izquierda a derecha, realizándose el análisis por derivaciones más a la derecha en sentido inverso . Las gramáticas LR (k) describen la mayor parte de los lenguajes libres de contexto, y son mucho menos restrictivas que las gramáticas LL (k).
Análisis sintáctico por precedencia de operadores: se utilizan para una pequeña clase de operadores y sus gramáticas, las cuales tienen la propiedad de que ningún lado derecho de las producciones es vacío ni tienen 2 terminales adyacentes.
3.2.- Gramáticas independientes de contexto.
También llamadas gramáticas libres de contexto, según la jerarquía de Chomsky, es un tipo de gramática formal que generalmente engloba a los lenguajes de programación y cuyas normas de producción son:
Exp.àx
Donde: Exp es un símbolo no terminal, x es una cadena de terminales y/o no terminales. El término independiente del contexto se refiere al hecho de que el no terminal Exp puede siempre ser sustituido por x sin tener en cuenta el contexto en el que ocurra.
Una gramática de este tipo, consta de 4 elementos básicos:
Símbolos terminales: elementos que no generan nada, son los símbolos con los que puede terminar una cadena o producción.
No terminales: elementos del lado izquierdo de una producción, antes de la flecha "->"
Producciones: sentencias que se escriben en la gramática, especifican las reglas para de la gramática para obtener un resultado, cada producción consta de un no terminal seguido de una flecha y una cadena de terminales y no terminales.
Símbolo inicial: primer elemento de la gramática, es un no terminal.
3.3.- Escritura de una gramática.
Toda construcción que se pueda describir mediante una expresión regular también se puede describir por medio de una gramática, por lo tanto todo conjunto regular es un lenguaje independiente de contexto.
Las reglas de sintaxis de un lenguaje a menudo son bastante sencillas, y para describirlas no se necesita una notación tan poderosa como las gramáticas, por ello se utilizan reglas de sintaxis de gramáticas para que se proporcione una notación más concisa y más fácil de entender para los componentes léxicos y al mismo tiempo separar la estructura sintáctica de un lenguaje en partes léxicas y no léxicas proporciona una forma conveniente de modular la etapa inicial de un compilador en dos componentes de tamaño razonable y además describir estructuras anidadas, estructuras de control, etc.
3.4.- Gramáticas ambiguas.
Una gramática es ambigua si permite construir dos o más árboles de derivación distintos para la misma cadena. Por lo tanto, para demostrar que una gramática es ambigua lo único que se necesita es encontrar una cadena que tenga más de un árbol de derivación.
Una gramática en la cual, para toda cadena generada w, todas las derivaciones de w tienen el mismo árbol de derivación es no ambigua.
En algunos casos, dada una gramática ambigua, se puede encontrar otra gramática que produzca el mismo lenguaje pero que no sea ambigua.
Si todas las gramáticas independientes del contexto para un lenguaje son ambiguas, se dice que el lenguaje es un lenguaje independiente del contexto inherentemente ambiguo.
Suscribirse a:
Entradas (Atom)