LENGUAJES Y AUTÓMATAS CS51
EQUIPO:
ANTONIO REYES
OSCAR
POSADAS MARTINEZ WENDI ADRIANA
RODRÍGUEZ ALEMAN MAGDALENA
ROSAS GOMEZ LIZZETH DEL CARMEN
ROSAS HERNÁNDEZ JOSE ALBERTO
ANALIZADOR SINTACTICO DE
ALGORITMOS
OBJETIVO:
El objetivo principal de este proyecto es el
de analizar por sintaxis un algoritmo.
Al momento de seleccionar el algoritmo este
nos mostrara si la sintaxis que se muestra esta escrita correctamente.
MARCO TEORICO
El proceso de análisis sintáctico y la
ejecución son ahora dos pasos completamente separados, no se procederá a la
ejecución del código de cualquier archivo hasta que éste en su totalidad, así
como todo el código requerido se haya analizado completa y satisfactoriamente.
Uno de los nuevos requisitos introducidos
con esta separación es que todos los archivos requeridos y de inclusión tienen
que ser sintácticamente completos ahora. Ya no es permitida la separación de
diferentes segmentos de una estructura de control a través de varios archivos.
Esto quiere decir que ahora no puede iniciar un ciclo for o while, una sentencia if o un bloque switch en un archivo, y
tener el final del ciclo, sentencias else, endif, case o break en un archivo diferente.
ANALIZADOR SINTÁCTICO
Para obtener en lógica el rigor y precisión
deseados, se introduce un lenguaje formal. Éste es un lenguaje artificial, con
unas reglas gramaticales explícitas que indican qué sucesiones de signos del
alfabeto son fórmulas y unas reglas semánticas también explícitas, que
determinan cuando una fórmula es verdadera bajo una determinada interpretación.
Éste lenguaje, pues, se utiliza como vehículo para el razonamiento.
El análisis
sintáctico es una aplicación que resulta del estudio de la Teoría de Autómatas
y Lenguajes Formales. El análisis sintáctico es la base del Demostrador de
Teoremas, ya que le permite analizar los componentes léxicos y sintácticos que
forman una fórmula para después poderla evaluar, o no en caso de error,
correctamente.
GRAMÁTICAS
Una Gramática es
la definición de un lenguaje. Lenguaje es la colección (finita o no) de
palabras de un alfabeto (representado por å ), por ejemplo, cualquier
subconjunto de å * (conjunto de todas las posibles palabras definidas sobre un
alfabeto). El alfabeto del lenguaje L de la lógica proposicional contiene dos
tipos de signos: los conectores y las letras proposicionales. Se utilizarán: ¬,
v, Ù , ® , « como conectores y p, q, r, s, t, ... como letras proposicionales.
Se utilizarán también los paréntesis como signos impropios.
Las fórmulas de
L se construyen siguiendo unas sencillas reglas de formación. Dichas reglas
extraen del conjunto de filas de signos del alfabeto aquellas a las que
llamamos fórmulas.
La definición de
Gramática formal viene dada por la:
Cuádrupla G=( å
t, å n, S, P).
Donde:
å t: es el alfabeto de símbolos Terminales.
å n: es el alfabeto de símbolos No Terminales.
S: es el axioma o símbolo inicial de la gramática.
P: es conjunto finito de producciones xAy::=z /
x,y,z eå * Aeån.
Permite, por tanto, la especificación formal de las reglas de
generación de los programas.
AUTÓMATA
Los autómatas permiten realizar análisis de programas.
Primera fase del proceso de compilación.
Permite comprobar la corrección de los programas.
ANÁLISIS
Es el proceso que permite determinar si una cadena puede ser generada por
una gramática. En nuestro caso es el proceso que permite determinar si una
fórmula está bien generada o no. Este proceso es fundamental en el Demostrador
de Teoremas ya que una cadena que no sea una fórmula no servirá para realizar
los razonamientos o pruebas. Por tanto es importante definir precisamente un
analizador para esta tarea.
Desde el punto de vista formal un analizador es un Autómata equivalente
a una gramática.
Analizador léxico
Una analizador léxico es un Autómata finito que reconoce los componentes
léxicos de una cadena de símbolos del alfabeto.
Analizador sintáctico
Una analizador sintáctico es un Autómata de pila que reconoce la
estructura de una cadena de componentes léxicos.
Objetivos del
analizador sintáctico (AS)
El
AS es la parte principal de un compilador. Las funciones de AS son:
Principales:
·
·
Comprobar si el programa es
sintácticamente correcto.
·
·
Generar las estructuras de
datos (árboles sintácticos u otras estructuras) que representan el programa y
sirven para el analizador semántico y el generador de código.
·
·
En el caso de compilación
dirigida por sintaxis -- llamar al analizador semántico y al generador de
código.
Otras:
·
·
Reaccionar frente a los
errores e intentar acotar la propagación de los errores (intentar evitar que un
error produzca muchos mensajes de error).
·
·
Hacer los siguientes pasos del
compilador más independientes de la sintaxis del lenguaje.
CÓMO FUNCIONA (TEORÍA EN LA QUE SE BASA)
El analizador sintáctico, que
se utilizara en esta práctica, será de tipo LL1 o SLR. Se pueden aplicar
también técnicas mixtas, analizando, por ejemplo, las sentencias aritméticas
con un analizador de lenguajes de precedencia y el resto del programa con LL1 o
SLR. Si se utilizan herramientas de generación automática (compiladores de
compiladores como yacc y bison) el lenguaje será del tipo LARL.
LL1:
Definición:
Se agrupan todas las clausuras
con idéntica parte izquierda. Es decir todas las clausuras del tipo:
A -> B C D
A -> E F G
......
A ->X Y Z
Si no existen dos clausuras con
idéntica parte izquierda que pueden empezar con un mismo símbolo terminal, y no
existe recursividad a la izquierda, el lenguaje es LL1.
Nota:
1.
1.
No es necesario que la
clausura empiece con símbolos terminales diferentes. Lo único que es necesario
comprobar es si puede o no empezar con un símbolo terminal.
2.
2.
Para cualquier lenguaje
independiente del contexto se puede definir la función FIRST(a), definida para
todas las formas sentenciales, cuyo valor es un conjunto de los símbolos
terminales con los que puede empezar a. Si aàl en el conjunto se incluye
también la sentencia vacía l. Si l está en FIRST(a), entonces la clausura A->a puede
también empezar con todos los símbolos terminales que pueden seguir a A,
denominado FOLLOW(A). FOLLOW puede incluir también el símbolo de End-Of-File $.
El cálculo de la función FOLLOW(A) es también esencial para el analizador SLR.
3.
3.
Para los lenguajes LL1 es
posible construir un autómata finito a pila, con un solo estado que analice el
lenguaje. Las decisiones del autómata se toman sólo a partir del último
elemento de la pila y el símbolo de entrada.
Hay dos variantes del analizador morfológico LL1: con llamadas a funciones y
con tabla. Estos casos se consideran en los apéndices (no son obligatorios).
SLR:
El mayor inconveniencia de los
analizadores LL1 es el conjunto bastante limitado de los lenguajes LL1. Un
conjunto bastante más amplio, que incluye casi todos los lenguajes de
programación, es el SLR.
Definición:
Un lenguaje de tipo SLR si
existe un analizador SLR que permita analizarlo.
Comentario:
Al igual que el analizador SLR,
éste se construye siguiendo un algoritmo, por lo tanto no podemos hablar de
tautología.
Un algoritmo para construir
SLR, orientado a "ejecutarse" a mano se encuentra descrito en el
apartado 2.
Qué
hace
En general, un analizador
sintáctico es un autómata a pila. El analizador sintáctico:
·
·
Inicializa el compilador y AS
en particular.
·
·
Para cada símbolo de entrada
llama al analizador morfológico y el AM proporciona el siguiente símbolo de
entrada.
·
·
Analizando el símbolo, la pila
y el estado del autómata, el AS produce las estructuras necesarias para la
siguiente etapa y en el caso de compilación dirigida por la sintaxis -- invoca
llamadas directas al analizador semántico y al generador de código.
·
·
Escribe mensajes de errores y
trata de limitar el efecto de estos errores.
Elección de algoritmos. Consideración de
las diferencias, ventajas y desventajas.
Como se ha dicho, existen por
lo menos cuatro maneras de hacer el analizador morfológico:
A.
A.
utilizando herramientas
especializadas yacc/bison,
B.
B.
utilizando analizador del tipo
SLR.
C.
C.
utilizando analizador LL1 con
llamadas a funciones.
D.
D.
utilizando analizador LL1 con
tabla.
Técnicas mixtas etc.
Se analiza la elección de los
algoritmos en el plan de desarrollo.
Plan
de desarrollo
Etapas:
1.
1.
Elegir el tipo del analizador
sintáctico.
2.
2.
Trasformar el lenguaje al tipo
correspondiente. Calcular las tablas correspondientes.
3.
3.
Escribir el programa del
analizador sintáctico sin acciones ni producción de código.
4.
4.
Añadir al analizador atributos
y acciones (en la parte del analizador sintáctico -- solo la producción de la
salida, tal como se explica en los requisitos de prueba).
5.
5.
Añadir al analizador generador
de código.
Propiamente hablando, sólo el segundo y el
tercer punto forman el analizador sintáctico por sí. El resto es analizador
semántico y el generador de código. En todos los modos se requiere una vista
general al definir como vamos a realizar el analizador sintáctico.
Argumentos: Los principales
objetivos al escribir cualquier programa son:
1.
1.
Funcionamiento correcto. Es
decir cumplir los requisitos. En este caso construir un analizador correcto.
Una parte de este punto es que el programa debe ser verificable.
2.
2.
Minimizar la probabilidad de
error en el programa. Esto significa que en cada etapa del desarrollo, el
programa debe de ser manejable. Se considera en detalles.
3.
3.
Escribir el programa que
funciona eficiente en todo el rango de datos posibles.
4.
4.
Escribir el programa que
funciona en entornos diferentes (SO) o por lo menos que sea fácil de pasarlo a
otro entorno.
5.
5.
Escribir el programa en manera
que sus partes son fáciles de reutilizar.
Minimizar la
probabilidad de error
En el caso de analizador
sintáctico, los errores se cometen en todas las etapas, pero los errores al
trasformar el lenguaje son los más frecuentes y difíciles de detectar y
reparar.
Errores al trasformar el
lenguaje:
·
·
El lenguaje puede
transformarse en algo no equivalente.
·
·
El lenguaje puede
transformarse en algo que no corresponde al tipo de lenguaje requerido (LL1 o
SLR).
Por lo tanto los principales objetivos son:
·
·
Transformar el lenguaje lo
menos posible.
·
·
Encontrar manera de comprobar
el analizador.
Errores al calcular las tablas:
Equivocarse en el calculo. El
cálculo debe ser lo más fácil posible y fácil de comprobar. Mejor hacerlo con
programas y no a mano.
Añadir acciones y
atributos:
Esta parte no es un componente
del analizador sintáctico, pero es esencial para el desarrollo del generador de
código y el analizador semántico. Por lo tanto, hay que escribir el analizador
sintáctico en manera que permite implementación fácil de los siguientes etapas,
es decir hacer el programa abierto para ampliaciones.
El moral está claro -- si
sabemos yacc, no utilizaremos otra cosa.
Plan de desarrollo del programa
-- partes específicas: <
1. LL1 con tabla, SLR:
El programa fuente el pequeño,
el tipo de desarrollo es GRANT -- planificar atentamente los prototipos de las
funciones, escribir los prototipos y escribir el programa. Al tener en cuenta
que el programa cambiara al añadir el analizador semántico y el generador de
código, el tipo de desarrollo en el curso de la práctica es evolutivo.
Se estima que el analizador
sintáctico (sin acciones ni generación de código) se puede realizar con 5-10
funciones de total tamaño 150-200 líneas. Las tablas ocuparan en el caso del
LL1 un número de líneas igual al número de las clausuras del lenguaje (40-50) y
en el caso del SLR -- el número de los estados del autómata (unos 100).
1) LL1 basado a llamadas de
funciones
La longitud del programa será de unas
300-500 líneas, pero el código se ejecutara sólo al encontrar estas clausuras
que corresponden al código. Por lo tanto, el modelo de desarrollo debe ser
evolutivo. Al añadir las siguientes etapas el código doblara el tamaño.
2) Con yacc/bison.
Al realizar el analizador con yacc/bison,
el tamaño será unas 60-70 líneas (solo tabla). El tiempo de aprendizaje de
bison es de una semana.
Comprobación
del programa
El objetivo de las pruebas
consiste en comprobar que el analizador sintáctico funciona correctamente con
cualquier fichero fuente.
Comprobación de casos
elementales
Se compruebe cada construcción
del lenguaje por separado.
Comprobación de casos
‘normales’
Se comprueban casos de
programas simples o de medio tamaño. Se comprueban también programas
especialmente deseñados para comprobar el analizador sintáctico.
Comprobación de casos
‘extremos’
Se comprueban programas vacíos,
programas muy largos (10-20 MB), construcciones con miles de if anidadas etc.
Comprobación estadística
Un error puede escapar las
pruebas anteriores, se comprueba el analizador con programas de prueba, que
generan programas aleatorios, sintácticamente correctos.
Comprobación del parte del
profesor
El analizador sintáctico, es un
programa de línea de comandos. Como argumento de la línea de comandos él recibe
el nombre del fichero de entrada. El programa no requiere otro tipo de entrada.
La salida a producir será la siguiente:
1.
1.
Una línea para cada clausura
sintáctica del lenguaje. La línea contendrá un numero único para cada clausura
(lo más fácil es un contador). El siguiente elemento de la línea de salida es
la posición (el padre en el caso de LL1) de la clausura que se reduce/analiza,
y el texto de la clausura. Si la clausura contiene terminales, que se reducen
al analizar, a esta clausura se da el valor de estos terminales.
Ejemplo
-- analizando A+5*B el analizador puede producir:
234
230.3: <expr> -> <expr>+<term>
235 234.1: <expr> -> <term>
236 235.1: <term> -> <id> [A]
237 234.2: <sum> -> '+'
238 234.3: <term> -> <term> * <term>
239 238.1: <term> -> <const>
240 239.1: <const> -> <const2> [5]
241 239.2: <mult> -> '*'
242 239.3: <term> -> <id> [B]
2.
2.
En caso de analizar id y const
-> se escribe ID o CONST y el nombre del variable o el valor de la constante
en [ ].
3.
3.
Para cada error sintáctico:
Un mensaje de error en stderr
con el siguiente formato
<file_name>:LineNo.pos:Error sintactico:
explicación del error: que acción ha tomado el compilador
Ejemplo:
Testasp.asp: 23:12 : Error sintáctico --
falta else. Asumiendo else.
Comportamiento del analizador sintáctico
El proceso de análisis
sintáctico y la ejecución son ahora dos pasos completamente separados, no se
procederá a la ejecución del código de cualquier archivo hasta que éste en su
totalidad, así como todo el código requerido se haya analizado completa y
satisfactoriamente_
Uno de los nuevos requisitos
introducidos con esta separación es que todos los archivos requeridos y de
inclusión tienen que ser sintácticamente completos ahora_ Ya no es permitida la
separación de diferentes segmentos de una estructura de control a través de
varios archivos_ Esto quiere decir que ahora no puede iniciar un ciclo for o while, una sentencia if o un bloque switch
en un archivo, y tener el final del ciclo, sentencias else, endif, case
o break en un archivo diferente_
Aun es perfectamente legal
incluir código adicional al interior de ciclos u otras estructuras de control,
únicamente las palabras claves de control y los corchetes correspondientes {___} tienen que estar en la misma unidad de
compilación (archivo o cadena procesada por eval())_
Esto no debe generar una
repercusión significativa ya que separar el código de esta manera debe ser
considerado como muy mal estilo, en cualquier caso_
Algo más que ya no es posible,
aunque es rara veces visto en código PHP 3, es devolver valores desde un
archivo requerido_ Devolver un valor desde un archivo de inclusión es posible
aun_
Un
analizador sintáctico, tal y como se ha enfocado en esta librería es una clase
que recibe lo siguiente:
1.
1.
Una clase donde se almacenarán
los atributos de cada símbolo.
2.
2.
Una gramática libre de
contexto donde el símbolo de inicio solo produce una variable.
3.
3.
Una función de síntesis para
cada producción, encargada de sintetizar los atributos necesarios.
4.
4.
Para cada producción una
opcional regla para deshacer ambigüedades.
5.
5.
Una instancia de una clase de
léxico que derive de la clase abstracta de léxico básico.
6.
6.
Una opcional función de error
para manejarlos y recuperarse en la medida de lo posible.
El analizador ira leyendo del
léxico y aplicando las reducciones necesarias (llamando a las funciones de
síntesis proporcionadas). El resultado habitual es un árbol sintáctico
construido de manera ascendente. Cada nodo de ese árbol es del tipo genérico
que se le pasa como parámetro al parser mencionado en la lista anterior.
EL TIPO DE LOS NODOS
El tipo de los nodos solo tiene un requisito de base. Es
necesario que tenga un campo llamado ``text'' accesible con el operador ``.''
para que el sintáctico almacene los tokens en las hojas del árbol. Este campo
no contendrá datos en los nodos superiores a menos que las funciones de
síntesis lo usen para algo.
Como normalmente se aplica el
patrón visitor, el tipo de los nodos sera algo como esto:
struct lval_t{string text;
nodeTree *node;};
La clase nodeTree sera de un tipo abstracto
que derivará en los distintos tipos de construcciones sintácticas. Las
funciones de síntesis serán las encargadas de construir estos nodos a partir de
los hijos. Estas tienen el siguiente prototipo:
V join_copia(vector<V>::iterator v);
Donde V es el tipo de los nodos, como por
ejemplo el ``lval_t'' definido antes.
Como se ve, una función de síntesis toma un
iterador a un vector de nodos. Este vector es realmente la pila de valores. La
razón por la que se pasa un iterador es porque este apunta ya directamente a la
parte de arriba de la pila que se tiene que reducir. Con la STL, este iterador
se comporta como un vector, así que en realidad es como si estuviéramos pasando
un vector de nodos hijos del que se va a construir. Un ejemplo sería el
siguiente: imaginemos que tenemos una producción como la que sigue:
Su función de síntesis podría ser la siguiente:
lval_t join_suma(vector<lval_t>::iterator v){ lval_t resultado; resultado.node=new nodeSuma(v[0],v[2]); //aqui v[1] seria el '+' en el campo text, no se usa return resultado;}
Conviene usar siempre punteros en la
estructura ``lval_t'' o como se la llame para que no se tengan que hacer copias
de los objetos.
FUNCIÓN DEL ANÁLISIS SINTÁCTICO.
Analizar sintácticamente una tira o
cadena de tokens no es más que encontrar para ella el árbol sintáctico o de
derivación que tiene como raíz el axioma de la gramática, y como nodos
terminales la sucesión ordenada de símbolos que componen la cadena analizada.
En caso de no existir este árbol sintáctico, la cadena no pertenecerá al
lenguaje, y el analizador sintáctico ha de emitir el correspondiente mensaje de
error.
Existen dos formas de analizar
sintácticamente una cadena:
·
·
Análisis descendente: Partiendo del axioma inicial de la
gramática se va descendiendo utilizando las derivaciones izquierdas, hasta
llegar a construir la cadena analizada.
·
·
Análisis ascendente: Se va construyendo el árbol desde sus
nodos terminales. Es decir, se construye desde los símbolos de la cadena hasta
llegar al axioma de la gramática. En este caso, se emplean normalmente las
derivaciones más a la derecha hasta la localización de la raíz.
Los principales métodos de análisis
sintáctico son:
o
o
Análisis descendente:
§
§
Análisis descendente con retroceso.
§
§
Análisis de gramáticas LL.
o
o
Análisis ascendente:
§
§
Análisis
ascendente con retroceso.
§
§
Análisis de gramáticas de
precedencia simple.
§
§
Análisis de gramáticas de
precedencia generalizada.
§
§
Análisis de gramáticas por el
método mixto.
§
§
Análisis de gramáticas de
precedencia de operador.
§
§
Análisis
de gramáticas LR.
Los análisis con retroceso se basan en
la prueba sistemática de todas las alternativas posibles, dando marcha atrás
tan pronto como se detecte que el camino seguido es erróneo. Pueden usarse para
cualquier gramática de contexto libre, aunque tienen tres grandes
inconvenientes: Primero, emplean mucho más tiempo para el análisis que
los demás analizadores, dependiendo éste incluso de la ordenación de las reglas
gramáticales; Segundo, no dan un buen diagnóstico de los errores que
encuentran; Tercero, complican la generación de código cuando ésta se
realiza al par que el análisis sintáctico.
Los métodos más eficientes de análisis
(tanto ascendente como descendente) no funcionan para todas las gramáticas de
contexto libre, sino sólo para las gramáticas que cumplen unas determinadas
condiciones.
Afortunadamente, en la mayoría de los
casos, pueden encontrase para los lenguajes de programación gramáticas de tipo LL
o LR
que los generen.
Para representar el árbol sintáctico que
conduce hasta una cadena se asigna a cada regla de la gramática un número. Se
define el parse como la secuencia ordenada de números (de reglas)
aplicadas para construir dicho árbol.
Hay dos tipos de parse, que son:
·
·
El parse-izquierdo: Son
los números de las reglas de derivacion izquierda utilizadas para generar la
cadena a partir del axioma, por tanto correspondiente a un análisis
descendente.
·
·
El parse-derecho: Son los
números de las reglas de derivación derecha utilizadas para generar la cadena a
partir del axioma, en orden inverso. El tomar el orden inverso viene
condicionado por ser el análisis ascendente el que normalmente utiliza las
reglas de derivación derecha, con lo que el orden en el que aparecen al
realizar el análisis es invertido.
Ejemplos:
|
Dada la
gramática 1.
1.
E
--> T 2.
2.
E
--> T+E 3.
3.
T --> F 4.
4.
T --> F*T 5.
5.
F --> a 6.
6.
F --> b 7.
7.
F
--> (E) y la sentencia
"a*(a+b)" El parse
izquierdo es: 1-4-5-3-7-2-3-5-1-3-6 y el derecho: 5-5-3-6-3-1-2-7-3-4-1 |
|
Simultáneamente a la fase de análisis
sintáctico, además de reconocer las secuencias de tokens, y analizar su
estructura, pueden realizarse una serie de tareas adicionales, como:
·
Recopilar información de los distintos tokens y almacenarla en la tabla
de símbolos.
·
Realizar algun tipo de análisis
semántico, tal como la comprobación de tipos.
·
Generar código intermedio.
·
Avisar de los errores que se detecten.
GRAFICA DE GRANT