lunes, 2 de mayo de 2011

UN TRADUCTOR SIMPLE ORIENTADO A LA SINTAXIS

Introducción



En el siguiente presente se hará mención de algunas de las técnicas de compilación, pero más énfasis tendrá lo que respecta al analizador léxico y al front-end de un compilador. Donde la fase de análisis de un compilador descompone un programa fuente en piezas componentes y produce una representación interna, a lo cual se le conoce como código intermedio. En donde el análisis se organiza de acuerdo con la “sintaxis” del lenguaje que se va a compilar. La sintaxis de un lenguaje de programación describe el formato apropiado de sus programas, mientras que la semántica del lenguaje define lo que sus programas significan.


Desarrollo

Analizador léxico: Un analizador léxico permite que un traductor maneje instrucciones de varios caracteres; como identificadores, que se escriben como secuencias de caracteres, pero se tratan como uni­dades conocidas como tokens durante el análisis sintáctico; por ejemplo, en la expresión cuenta+1, el identificador cuenta se trata como una unidad.

Definición de sintaxis: La “gramática” se utiliza para especificar la sintaxis de un lenguaje y a la vez la gramática describe en forma natural la estructura jerárquica de la mayoría de instrucciones de un lenguaje de programación.
La gramática tiene cuatro componentes:
·Un conjunto de símbolos terminales, las terminales son los símbolos elementales del lenguaje definido por la gramática.
·Un conjunto de no terminales, también llamadas “variables sintácticas” cada no terminal representa un conjunto de cadenas o terminales.
·Un conjunto de producciones, en donde cada producción consiste en uno no terminal, llamada encabezado o lado izquierdo de la producción, una flecha y una secuencia de terminales y no terminales. La intención de una producción es especificar una de las formas escritas de una instrucción.
·Una designación de una de los no terminales como el símbolo inicial.

Derivaciones: una gramática deriva cadenas empezando con el símbolo inicial y sustituyendo en forma repetida un no terminal, mediante el cuerpo de una producción para ese no terminal. Las cadenas de terminales que pueden derivarse del símbolo inicial del lenguaje definido por la gramática.

Árboles de análisis sintáctico, muestra en forma grafica, la manera en que el símbolo inicial de una gramática deriva a una cadena en el lenguaje. Tiene las siguientes propiedades:

1. La raíz se etiqueta con el símbolo inicial.
2. Cada hoja se etiqueta con un terminal, o con Є.
3. Cada nodo interior se etiqueta con un no terminal.
4. Si A es el no terminal que etiqueta a cierto nodo interior, y X1, X2,…,Xn son las etiquetas de los hijos de ese nodo de izquierda a derecha.

Ambigüedad
Una gramática puede tener más de un árbol de análisis sintáctico que genere una cadena dada de terminales. Se dice que dicha gramática es ambigua. Para mostrar que una gramática es ambigua, todo lo que debemos hacer es buscar una cadena de terminales que se la derivación de mas de un árbol de análisis sintáctico.



Traducción orientada a la sintaxis
La traducción orientada a la sintaxis se realiza uniendo reglas fragmentos de un programa a las producciones en una gramática. Por ejemplo considere una expresión expr generada por la siguiente producción:


expr ---> expr1 + term


Donde expr es la suma de las dos subexpresiones expr1 y term.



Atributos sintetizados: los atributos pueden evaluar de la siguiente forma. Para cada cadena de entrada x dad, se construye un árbol de análisis sintáctico para x. después, se aplica las reglas semánticas para evaluar los atributos en cada nodo del árbol de análisis sintáctico. Se dice que un atributo esta sintetizado si su valor en el nodo N de un árbol de análisis sintáctico se determina mediante los valores de los atributos del hijo de N y del mismo N.



Definición orientada a la sintaxis: tiene la siguiente propiedad importante: la cadena que representa a la traducción del no terminal en el encabezado de cada producción es la concatenación de las traducciones de los no terminales en el cuerpo de la producción, en el mismo orden que en la producción, con algunas cadenas adicionales opcionales entrelazadas.
Recorridos de arboles: los utilizaremos para describir la evaluación de los atributos y especificar la ejecución de los fragmentos de código en un esquema de traducción. Un recorrido de árbol empieza en la raíz y visita cada nodo del árbol en cierto orden.



Esquema de traducción orientado a la sintaxis: Es una notación para especificar una traducción, uniendo los fragmentos de un programa a las producciones en una gramática.
Analizador sintáctico: El análisis sintáctico (parsing) es el proceso de determinar cómo puede generarse una cadena le terminales mediante una gramática. Al hablar sobre este problema, es más útil pensar en me se va a construir un árbol de análisis sintáctico, aun cuando un compilador tal vez no lo construya en la práctica. No obstante, un analizador sintáctico debe ser capaz de construir el árbol en principio, o de lo contrario no se puede garantizar que la traducción sea correcta.



Métodos de análisis sintáctico

Análisis sintáctico tipo arriba-abajo se considera una gramática que se adapta bien a esta clase de métodos. La construcción descendente de un árbol de análisis sintáctico, se realiza empezando con la raíz, etiquetada con el no terminal inicial instr, y realizando en forma repetida estos 2 pasos:

·En el nodo N, etiquetado con el no termina A, se selecciona una de las producciones para A y se construyen hijos en N para los símbolos en el cuerpo de la producción.
·Se encuentra el siguiente nodo en el que se va a construir un subárbol, por lo general, el no terminal no expandido de más a la izquierda del árbol.

Análisis sintáctico predictivo es un método de análisis sintáctico descendente, en el cual se utiliza un conjunto de procedimientos recursivos para procesar la entrada. Un procedimiento se asocia con cada no terminal de una gramática. Aquí consideraremos una forma simple de análisis sintáctico de descenso recursivo, conocido como análisis sintáctico predictivo, en el cual el símbolo de preanálisis determina sin ambigüedad el flujo de control a través del cuerpo del procedimiento para cada no terminal. El análisis sintáctico predictivo se basa en información acerca de los primeros símbolos que pueden generarse mediante el cuerpo de una producción.




Conclusión



Respecto a todo este tema de un traductor simple orientado a la sintaxis, aunque su nombre diga simple, realmente es un poco complicado ya que deben existir ciertas características para crearlo, en este caso se enfoco más al front-end de un compilador, analizador léxico y se menciono algunos métodos de análisis sintáctico. Conforme se va desarrollando cada característica que debe tener nuestro compilador, se muestra que en cada característica se deben considerar ciertas propiedades. Es decir cada tema tiene ciertos subtemas y estos a la vez se dividen en más y hace que tengas que considerarlos todos, para realizar un buen compilador.
Al crear un analizador sintáctico que este en una forma correcta, nos ayuda para seguir adelante para construir el compilador, por que es una parte importante del el, en cada tema que se vio, si se implemente nos ayudara a crear un mejor analizador léxico.


Jimenez Dominguez Sonia

1 comentario:

  1. Revisado. Tienes que redactar más hacerca de tu comprensión.

    ResponderEliminar