martes, 3 de mayo de 2011

UN TRADUCTOR SIMPLE ORIENTADO A LA SINTAXIS

UN TRADUCTOR SIMPLE ORIENTADO A LA SINTAXIS

En estos capítulos se muestra información acerca de la interpretación de códigos para un programa y de manera simple lo que cada término significa.

La sintaxis de un lenguaje describe a un formato apropiado y la semántica define lo que significa; es decir lo que hace cuando se ejecuta. Además de especificar la sintaxis, se puede utilizar una gramática libre de contexto para ayudar a guiar la traducción de los programas.

Un analizador léxico permite que un traductor maneje instrucciones de varios caracteres como identificadores que se describen como secuencia de caracteres conocidas como tokens durante el análisis sintáctico.

Sintaxis: Una gramática describe la forma natural la estructura jerárquica de la mayoría de las instrucciones de un lenguaje de programación.

Gramática: Se compone de cuatro elementos

1.- Un conjunto de símbolos terminales (“tokens”) en donde estos son símbolos definidos por la gramática.

2.- Un conjunto de no terminales (“variables sintácticas”). En donde cada conjunto de no terminales representa un conjunto de cadenas o terminales.

3.- Un conjunto de producciones que consiste en un no terminal llamada encabezado o lado izquierdo de la producción, una flecha y una secuencia de terminales y no terminales se llama cuerpo o lado derecho de la producción.

4.- Una asignación de una de los no terminales como el símbolo inicial.

Derivaciones: Una gramática deriva empezando con el símbolo inicial sustituyendo en forma repetida un no terminal.

Ejemplo: la lista de parámetros en la llamada a una función.

Arboles de análisis sintáctico

  • -Un árbol consiste en uno o más nodos. Los nodos pueden tener etiquetas que serán símbolos de la gramatica
  • -Solo uno de los nodos es la raíz en donde este tiene un padre pero la raíz no, la raíz es el nodo más alto.
  • -N es el padre del nodo M (hijo de N), los hijos de nuestros nodo se llaman hermanos.
  • Un nodo sin hijos se llama hoja y los otros son nodos interiores.

Un árbol de análisis sintáctico muestra, en forma la manera en el que el símbolo inicial de una gramatica deriva una cadena en el lenguaje. A que tiene una producción Aà XYZ deberá tener un nodo interior etiquetado como A con tres hijos.

Aàsus hijos serían X, Y, Z

Ambigüedad: Una gramatica puede tener más de un árbol de análisis sintáctico que genere una cadena dada de terminales. Se dice que dicha gramatica es ambigua. Para mostrar que una gramatica es ambigua es buscar una cadena de terminales que sea la derivación de más de un árbol de análisis sintáctico.

Asociatividad de los operadores

Cuando un operador como 5 tiene operadores a su izquierda y a su derecha se requiere convenciones para decidir que operador se aplica a ese operando. El operador + se asocia por la izquierda, porque un operando con signos positivos en ambos lados de el pertenece al operador que esta a su izquierda. Los cuatro operadores (suma, resta, multiplicación y división) son asociativos por la izquierda. El operador de asignación = en C y sus descendientes es asociativo por la derecha; es decir, la expresión a=b=c se trata de la misma forma que la expresión a=(b=c).

Procedencia de operadores: En la siguiente expresión (9+5)*2 o 9+ (5*2) se aplican de la misma manera por lo que por lo que en este caso no se resuelve la ambigüedad. Las reglas que definen la precedencia relativa de los operadores son necesarias cuando hay más de un tipo de operador presente. Decimos que * tiene mayor precedencia +, si * recibe sus operandos antes que +.

Con esto creamos dos no terminales llamadas expr y term para los dos niveles de procedencia, y un no terminal adicional llamado factor para generar unidades básicas en las expresiones.

Factor à digito | (expr)

Ahora conoceremos los operadores binarios, * y /, que tienen la mayor procedencia. Como estos operadores asocian por la izquierda, las producciones son similares a las de las listas que asocian por la izquierda.

De manera similar, expr genera listas de términos separados por los operadores aditivos:

Expr à expr + term

| expr – term

Traducción orientada a la sintaxis: Esta se utilice uniendo reglas o fragmentos de un programa a las producciones en una gramatica, en donde si se utiliza; expr à expr1 + term en donde la suma es la expr de las dos funciones. Como ejemplo tenemos los datos de las expresiones, el número de instrucciones

Notación postfija: La notación postfija para una expresión E se define de manera inductiva; por ejemplo si e es una variable, su notación postfija será ella misma y así siempre que la pongamos con sub índices o en paréntesis será siempre ella misma

Análisis sintáctico (parsing): Es el proceso de determinar como puede generarse una cadena de terminales mediante una gramatica. Esto quiere decir que se construye un árbol de análisis sintáctico aun cuando el compilador tal vez no lo construya en la práctica aunque este deberá ser capaz de construir el árbol en principio en caso contrario no se garantiza la traducción correcta. A este método también se le conoce como “descenso recursivo” al cual se utiliza también en análisis sintáctico o implementación de traductores orientados a la sintaxis.

Sintaxis abstracta y concreta: Cuando se hace la representación de sintaxis abstracta se debe realizar un árbol en donde cada nodo interior representa un operador y los hijos nodos serian los operandos del operador. En donde los operandos se tratan como componentes con significado semántico de esa construcción.

lunes, 2 de mayo de 2011

capitulo 2 Un traductor simple orientado a la sintaxis

En el principio es una introducción a las técnicas de compilación en los capítulos 3 a 6 .Presenta técnicas mediante el desarrollo de un programa funcional en java que traduce instrucciones representativas de un lenguaje de programación en un código de 3 direcciones, una representación intermedia. En este capitulo se hace énfasis en el fronted de un compilador, en especial en el análisis de léxico, el análisis sintactico(parsing), y la generación de código intermedio. En los capítulos 7 y 8 veremos como generar las instrucciones de maquina a travez de un código de tres instrucciones.

Se empieza con algo pekeño, creando un traductor orientado a la sintaxis que asigna expresines aritméticas fijo a expresiones posfijo, después se entiende ese traductor para que asigne fragmentos de códigos a un código de 3 direcciones.

Un Traductor Simple Orientado a la sintaxis

INTRODUCCIÓN

En esta lectura podemos observar que nos habla sobre las diferentes técnica de compilación para con ello desarrollar un analizador los cuales existen tres tipos de analizadores:


  • analizador léxico


  • analizador sintáctico


  • analizador semántico


la fase de análisis de un compilador descompone un programa fuente en piezas componentes y a su ves produce una representación interna, a la cual se le conoce como código intermedio. También observaremos que el análisis se organiza de acuerdo con la sintaxis del lenguaje que se va a compilar, la sintaxis del lenguaje de programacion asigna el formato adecuado de el programa , mientras que la semántica define lo que los programas significan o hacen el programa al ejecutarse, Una técnica de compilacion orientada a la gramática , se e conoce como traducción orientada a la sintaxis.



DESARROLLO


Bueno primeramente al abarcar este tema tenemos que tener encuenta conceptos que se requieren para el entendimiento de lo que trataremos primeramente sabemos que un :



compilador es un programa que traduce un programa fuente como faltón al lenguaje ensamblador o código maquina de la computadora.



Analizador léxico permite que un traductor maneje instrucciones de varios caracteres como identificadores, que se describen como secuencias de caracteres.



Analizador Sintáctico El análisis sintáctico es el proceso de determinar cómo puede generarse una cadena le terminales mediante una gramática.



Analizador semántico esta compuesto por un conjunto de rutinas independientes, llamadas por los analizadores léxico y sintáctico.


Bueno al hablar de traductor simple orientado a la sintaxis hablamos de la spropiedasdes que tiene como son:


la cadena que representa la traduccion del no terminal en el encabezado de cada produccion es a concatenacion de la straducciones de los no terminales en el cuerpo de la produccion , en el mismo orden que en la produccion con halgunas cadenas adicionales opcionales entrelazadas. Esta propiedad se denomina como simple.


hablamo del análisis sintáctico que es el proceso de determinar cómo puede generarse una cadena le terminales mediante una gramática. también el análisis sintáctico de arriba-abajo el cual se concidera na gramática que se adapta bien a esta clase de métodos.


el análisis sintáctico predictivo es un método de análisis descendente en el cual se utiliza un conjunto de procedimientos recursivos para procesar la entrada.
el análisis semántico utiliza como entrada el árbol sintáctico detectando por el análisis sintáctico el cual comprueba las restricciones de tipo y las limitaciones sematicas y preparar la generación de código.


los arboles de análisis sintáctico muestra , en forma gráfica la manera en que el símbolo inicial de una gramática derivada a una cadena en el lenguaje.


CONCLUSION


Bueno como conclusión para este tema es bueno ay que con ayuda de las diferentes herramientas como las cuales son los analizadores nos ayuda a comprender mejor acerca de los compiladores , también las herramientas como son los arboles la las derivaciones etc herramientas que van de la mano con este tema nos ayuda a comprender un poco mas de ello aun que es un poco complicado pero básicamente da la idea u el objetivo de ello.


Bueno con estas herramientas nos ayuda a crear un buen compilador y no tener errores en la traducción del código.

Traductor simple Orientado a la sintaxis

INTRODUCCION

Este texto habla sobre las diferentes técnicas de compilación y su importancia para el desarrollo de una analizador ya sea léxico o sintáctico , de igual forma trata de cómo generar instrucciones de la maquina a partir de código, se describe la diferencia que existe entre la sintaxis y la semántica la cual cada una al realizar su función puede llevarse a cabo lo que se quiere realizar y la sintaxis únicamente nos sirve para darle un formato a correcto a nuestro programa.

Tipos de Analizadores

- Léxico

- Sintáctico

- Semántico

El analizador Léxico permite que un traductor maneje instrucciones de varios caracteres como identificadores este permite que aparezcan numero, identificadores y espacios en blanco.

El analizado sintáctico: este analizador determina como puede generarse una cadena de terminales mediante una gramática. Para cualquier gramática libre de contexto hay un analizador sintáctico que se tarda, como máximo un tiempo en analizar una cadena de n terminales.

El analizador Semántico: Se compone de un conjunto de rutinas independientes, llamadas por los analizadores léxico 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.

Conclusión:

Con ayuda de cada una de estas herramientas podemos desarrollar nuestro compilador y este nos ayudara a verificar cada una de las cadenas de texto que tenemos y verificar si son correctas o no y mostrar cada uno de los errores que podemos tener de igual forma traduce del código fuente al código objeto nuestro programa y así poder verificar si realiza lo deseado o no.

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

Capitulo 2.- Un traductor simple orientado a la síntesis

Introduccion: La sintaxis de un lenguaje de programación descibe el formato apropiado de sus programas, mientras que la semántica del lenguaje define lo que sus programas significan, es decir, lo que hace cada programa cuando se ejecutan.




Desarrollo:




Un modelo de una front-end de un compilador:


1.- programa fuente


2.-"Analizador léxico"


3.- tokens


4.-"Analizador sintáctico (parser)"


5.-árbol sintáctico


6.-"Generado de código intermedio"


7.- Código de tres direcciones


8.- En globa a las 7 caracteristicas anteriores una "Tabla de símbolos".




Analisador léxico: Lee una secuencia de caracteres del programa fuente, caracter por caracter y los agrupa paraformar unidades con un caracter propio componentes léxicos "Tokens". Opera bajo la petición del analizador sintáctico devolviendo un componente léxico con forme lo va necesitando el analaizador sintactico para avanzar en la gramatica.




Analisador sintáctico:Este se divide en niveles jerarquicos, que tiene una sintaxis, derivaciones, arboles , asociatividad de los operadores así mismo como precedencia de operadores.


Un analizador sintáctico debe se capaz de construir el arbol en principio, o de lo contrario no se puede garantizar que la traduccion sea correcta.




a) Árboles de análisis sintácticos: Muestra en forma grafica, la manera en que el símbolo inicial de una gramática derivada de 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 una terminal.


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 etiquetas de los hijos de ese nodo de izquierda a derecha, entonces debe haber una produccion a--> x1,x2,...xn representa un simbolo.




b)Asociatividad de los operadores: Decimos que el operador + se asocia por la izquierda. En la moyoria de los lenguajes de programación los cuatro operadores aritmeticos (suma, resta, multiplicación y divisón) son asociativos por la izquierda.




c)Precedencia de operadores: Las reglas de asociativas para + y * se aplican a las concurrencias del mismo operador, por lo que nos resuelven esta ambigüedad.



asociativo por la izquierda + -


asociativa por la derecha * /



Conclusión: Para que un traductor simple orientado a la sintesis es necesario pasar por varios paso (niveles jerarquicos), así como saber como tienen que ir asociados o distribuidos para lograr una traduccion perfecta ya que en este tipo se tiene que realizar paso a paso para que no haya errores en su compilacion y esta se perfecta


Yazmin Gracía Mendoza Grupo 5S21

:::::Un Traductor Simple Orientado a la Sintaxis::::::

Ensayo.

Dentro de el tema del capitulo 2 encontramos que toma con un mayor énfacis lo que se refiere a el Análisis Léxico, el Análisis Sintáctico y Generacion de Codigo Intermedio. En el cual al principio nos habla de una descomposición de un programa fuente el cual genera componentes de este codigo que en cierto momento seran analizados por separado por un analizador para verificar que estos esten dentro de el codigo.

Nos muestra la definicion de sintaxis y la gramatica que debe seguir cada componente los cuales tienen caracteristicas que se deben tomar en cuenta como son:
*Conjunto de simbolos.
*conjunto de no terminales (variables sintacticas).
*Conjunto de producciones (encabezado o lado izquierdo de la produccion).

Ademas de definir un analisis sintactico que toma una cadena de terminos y la deriva a partir de un simbolo inicial de la gramatica que se maneja un gran ejemplo que nos muestra son los Árboles de análisis sintácticos que es la forma grafica de observar como el simbolo inicial de una gramatica deriva a una cadena en un lenguaje.

Nos define los recorridos de los árboles que evalua los atributos de la cadena en especifico, en el cual el recorrido empieza en la raiz y visita cada nodo del árbol en un cierto orden en el cual nos muestra que tambien utilizamos los llamados Esquemas de Traducción que nos dice que es como una definicion orientada a la sintaxis, pero esta la evalua de una forma explisita.

Y para finalizar nos muestra que dentro de los analizadores se utiliza de una forma remarcada la recursividad que pueden ser a la derecha, a la izquierda, de abajo hacia arriba dando en algunos casos secuencias de recursividad infinita que es que la seguencua de un arbol al pasar por cada nodo en ocaciones tiende a regresar a la raiz y realizar nuevamente el recorrido de una forma ciclica y sin un fin.

En conclusión, cada tema que toca el capitulo nos da fracmentos de conocimiento especifico que podemos usar para implementarlas en nuesto analizador lexico como lo es en el caso tal de los ejemplos de recursividada y de el recorrido de los árboles sintacticos y no solo eso si no que ademas nos muesta algunos esquemas sintacticos que podemos seguir.

Rivera Solano Juan Diego. Grupo 5s21 Programacion de Sistemas.