- INTRODUCCIÓN
- ANÁLISIS SINTÁCTICO
- METODO TOP-DAWN
- RECURSIVO DESCENDENTE
- BOTTOM-UP
- DE PROCEDENCIA SIMPLE
- MATRICES DE TRANSICIÓN
- GRAMÁTICAS LIBRES DE CONTEXTO
- ÁRBOLES DE DERIVACIÓN
- FORMA NORMAL DE CHOMSKY
- CONCLUSIÓN
- BIBLIOGRAFIA
INTRODUCCIÓN.
Todo lenguaje de programación obedece a unas reglas que describen la estructura sintáctica de los programas bien formados que acepta. En pascal, por ejemplo, un programa se compone de bloques; un bloque, de sentencias; una sentencia, de expresiones; una expresión, de componentes léxicos; y así sucesivamente hasta llegar a los caracteres básicos. Se puede describir la sintaxis de las construcciones de los lenguajes de programación por medio de gramáticas de contexto libre o utilizando notación BNF (Backus-Naur Form). Las gramáticas formales ofrecen ventajas ignificativas a los diseñadores de lenguajes y a los desarrolladores de compiladores.
Una gramática da una especificación sintáctica precisa y fácil de entender de un lenguaje de programación.
A partir de algunas clases de gramáticas se puede construir automáticamente un analizador sintáctico eficiente que determine si un programa fuente está sintácticamente bien formado. Otra ventaja es que el proceso de construcción del analizador que de otro modo podrían pasar sin detectar en la fase inicial de diseño de un lenguaje y de su compilador.
Una gramática diseñada adecuadamente imparte una estructura a un lenguaje de programación útil para la traducción de programas fuente a código objeto correcto y para la detección de errores. Existen herramientas para convertir descripciones de traducciones basadas en gramáticas en programas operativos.
Los lenguajes evolucionan con el tiempo, adquiriendo nuevas construcciones y realizando tareas adicionales. Estas nuevas construcciones se pueden añadir con más facilidad a un lenguaje cuando existe una aplicación basada en una descripción gramatical del lenguaje.
La mayor parte del presente trabajo está dedicada a los componentes del análisis sintáctico, así como los conceptos básicos y otros temas de gran interés.
¿Qué es el Analizador Sintáctico?
Es la fase del analizador que se encarga de chequear el texto de entrada en base a una
gramática dada. Y en caso de que el programa de entrada sea válido, suministra el árbol
sintáctico que lo reconoce.
En teoría, se supone que la salida del analizador sintáctico es alguna representación del
árbol sintáctico que reconoce la secuencia de tokens suministrada por el analizador léxico.
En la práctica, el analizador sintáctico también hace:
• Acceder a la tabla de símbolos (para hacer parte del trabajo del analizador
semántico).
• Chequeo de tipos (del analizador semántico).
• Generar código intermedio.
• Generar errores cuando se producen.
En definitiva, realiza casi todas las operaciones de la compilación. Este método de trabajo
da lugar a los métodos de compilación dirigidos por sintaxis.
El análisis sintáctico convierte el texto de entrada en otras estructuras (comúnmente árboles), que son más útiles para el posterior análisis y capturan la jerarquía implícita de la entrada. Un analizador léxico crea tokens de una secuencia de caracteres de entrada y son estos tokens los que son procesados por el analizador sintáctico para construir la estructura de datos, por ejemplo un árbol de análisis o árboles abstractos de sintaxis.
El análisis sintáctico también es un estado inicial del análisis de frases de lenguaje natural. Es usado para generar diagramas de lenguajes que usan flexión gramatical, como los idiomas romances o el latín. Los lenguajes habitualmente reconocidos por los analizadores sintácticos son los lenguajes libres de contexto. Cabe notar que existe una justificación formal que establece que los lenguajes libres de contexto son aquellos reconocibles por un autómata de pila, de modo que todo analizador sintáctico que reconozca un lenguaje libre de contexto es equivalente en capacidad computacional a un autómata de pila.
Los analizadores sintácticos fueron extensivamente estudiados durante los años 70 del siglo XX, detectándose numerosos patrones de funcionamiento en ellos, cosa que permitió la creación de programas generadores de analizadores sintáticos a partir de una especificación de la sintaxis del lenguaje en forma Backus-Naur por ejemplo, tales y como yacc, GNU bison y javacc.
TIPOS DE ANALIZADORES SNTACTICOS.
Existen dos tipos básicos de analizadores para las gramáticas libres de contexto: los <
(Top-down).
Se puede considerar un analizador descendente como una técnica que intenta encontrar una derivación <
Consideremos el siguiente fragmento de gramática, que describe la estructura de un lenguaje dado:
Dada la cadena de entrada siguiente,
Module d ; d ; p ; end
Para construir el árbol sintáctico descendente correspondiente, creamos inicialmente un árbol que consiste en un único nodo etiquetado con el símbolo inicial: PROG. Entonces usamos la primera para expandir el árbol y obtenemos:
PROG
____________________________________________________________
Module DECLS ; PROCS end
•Para una secuencia de palabras, construye un árbol de análisis sintáctico desde la raíz a las hojas.
RECURSIVO DESCENDETE.
Una gramática permite la implementación de formas de analizadores sintácticos. La más importante es la recursiva descendente, que vemos a continuación, y en la cual cada no terminal es una llamada a su correspondiente procedimiento analizador.
Un analizador recursivo descendente tiene las características que se desprenden de su nombre: un analizador sintáctico de tipo descendente (top-down) e implementado con un lenguaje recursivo. El mecanismo de análisis es el siguiente:
1.- Existirá un procedimiento o función por cada símbolo no terminal.
2.- Dada una producción, y una vez que estamos en el procedimiento que trata el símbolo no terminal de la parte izquierda, para analizar la parte derecha se hará lo siguiente:
Si hay alternativas, llamar al analizador léxico (si no está ya avanzado), con el fin de obtener un nuevo token del texto fuente. Una vez leído, se compara el token con los símbolos directores de dichas alternativas. Si el token pertenece a uno de esos conjuntos de símbolos directores, sigue el análisis por el procedimiento que trate la alternativa correspondiente. Si no pertenece, se tratara de un error sintáctico.
Si no hay alternativas, o bien ya dentro de una alternativa, el análisis será el siguiente: si el primer símbolo es un no terminal, llamar al procedimiento correspondiente. Si es un terminal, llamar al analizador léxico (si no está avanzado), comparar y seguir el análisis si el token leído coincide con dicho símbolo terminal.
(Bottom-up).
•Para una secuencia de palabras, construye un árbol de análisis sintáctico desde las hojas a la raíz.
Se denominan ascendentes porque pretenden construir un árbol sintáctico parra una determinada cadena de entrada empezando por las hojas y constituyendo el árbol hasta llegar a la raíz. También se puede considerar este proceso como la <
En cada paso del proceso, una cadena que coincida con la parte derecha de la producción se remplaza por el símbolo no terminal de la parte izquierda de dicha producción. Veamos un ejemplo con la siguiente gramática donde aplicaremos IDENT y CONST y el símbolo inicial EXP (abreviaturas de IDENTIFICADOR, CONSTANTE Y EXPRESIÓN). La cadena de entrada es:
3 + a -5
Y la queremos reducir al símbolo de la gramática, que era EXP. Según la definición de la gramática, el símbolo inicial EXP tenía nueve producciones alternativas. Para reducir la cadena dada al símbolo EXP, lo que hacemos es identificar subcadenas que coincidan con la parte derecha de alguna producción de EXP. En nuestro caso, 3, a y 5. Tomamos el de más a la izquierda, 3, y lo sustituimos por su parte derecha en la producción, que era CONST, con lo que la cadena de entrada se nos queda en CONST + a -5. Hacemos lo mismo con a y 5 y la cadena resultante es CONST + IDENT + CONST. Con esta cadena volvemos a realizar el mismo proceso, buscar subcadenas que coincidan con la parte derecha de alguna producción del símbolo inicial EXP. Tanto CONST como IDENT son derivaciones inmediatas de EXP, luego podemos reducir la cadena actual a EXP + EXP – EXP. A su vez, (siguiendo siempre el criterio de tomar las subcadenas de más a la izquierda), tenemos que EXP + EXP se puede reducir a EXP, con lo que nos queda EXP – EXP. Y esta cadena también es una producción de EXP, con lo cual se reduce a EXP. Luego la cadena 3 + a -5 es derivable de EXP y por tanto pertenece al lenguaje generado por la gramática.
Cada reemplazamiento de la parte derecha de una producción se denomina <
3 + a – 5CONST + a – 5CONST +IDENT- 5 CONST+ IDENT – CONST……..
…. EXP +IDENT – CONST EXP + EXP – CONST EXP + EXP –EXP…….
…. EXP – EXP EXP
En los analizadores ascendentes existen problemas cuando la gramática es ambigua, lo que significa que se pueden encontrar dos derivaciones más a la derecha para una misma cadena.
DE PROCEDENCIA SIMPLE.
Este tipo de análisis incluye, en el proceso de construcción del Árbol de Derivación, una serie de reducciones a través de las cuales reemplaza un substring que representa la parte derecha de una producción (handle) por su respectiva parte izquierda. Es decir que va ascendiendo en el árbol desde los descendientes hacia el respectivo nodo padre. Bajo esta técnica separte de la cadena w ∈ Σ a reconocer y se trata de alcanzar el símbolo distinguido S. Al igual que la técnica Top-Down, w ∈ Σ sólo es aceptada si se logra construir el Árbol de derivación para w.
En este caso, la cadena w representa las hojas de un posible Árbol de Derivación para w. El proceso de reducción puede ser visto como la conexión hacia arriba de el o los descendientes con su respectivo nodo padre.
El resultado de la aplicación de esta técnica es la secuencia de reducciones realizadas, que es equivalente a la inversa de una secuencia de derivaciones de más a la derecha para w partiendo de S, también llamado right parser.
Análisis Sintáctico y determinismo.
Cualquiera sea el enfoque que se considere, debemos tener en cuenta que durante el proceso de construcción del Árbol de Derivación, ya sea usando una técnica Top-Down o Bottom-Up, se deben tomar decisiones que eventualmente podrían involucrar más de una alternativa. Por ejemplo, un nodo del árbol (usando un algoritmo Top-Down) podría ser expandido de diferentes maneras, pudiendo llevar a un no determinismo. Desde el punto de vista teórico, esto no tiene implicaciones muy severas. Sin embargo, desde el punto de vista práctico es inadmisible, ya que tornaría a la implementación en un proceso completamente ineficiente en cuanto al tiempo insumido para el reconocimiento de una cadena.
Si bien ambas técnicas de parsing son igualmente importantes, veremos una implementación práctica de la técnica Bottom-up, dado que una implemetación práctica de la técnica Top-dwn es dada en la materia Compiladores. Desde el punto de vista teórico, veremos implementaciones de ambas técnicas usando APD’s a fin de entender gradualmente el concepto de análisis sintáctico.
MATRICES DE TRANSICIÓN.
Se puede utilizar una matriz bidimensional para representar un árbol de análisis sintáctico.
Para obtener los parámetros de la matriz de transmisión a partir de la matriz de impedancia, recordemos la matriz de impedancia para dos puertos y cambiemos el signo para I2 de acuerdo a la grafica (6a):
(71)
Que corresponde a:
(72)
(73)
Reemplazando los voltajes V1 y V2 en las ecuaciones (68) para los parámetros A, B, C, D se obtiene:
(74)
(75)
(76)
(77)
Si la red es reciproca, a partir de estas últimas ecuaciones se llega a que AD – BC =1.
En la siguiente tabla se tienen algunos parámetros ABCD para algunos circuitos de dos puertos
GRAMATICAS LIBRES DE CONTEXTO.
Gramáticas libres de contexto (GLC), o de tipo 2: las reglas son de la forma X a, donde X es una variable y a es una cadena que puede contener variables y constantes.
Estas gramáticas producen los lenguajes libres de contexto (abreviado “LLC”).
Podemos ver que la gramática del español dada arriba es una GLC, pero no podría ser una gramática regular, pues hay varias reglas que no corresponden al formato de las reglas de las gramáticas regulares. Se ve por lo tanto que el formato de las reglas es menos rígido en las GLC que en las gramáticas regulares, y así toda gramática regular es GLC pero no viceversa
.
Por ejemplo, el lenguaje {aⁿbⁿ} –que no es regular, ya que tiene la gramática libre de contexto con las siguientes reglas:
1.- S aSb
2.- S ab
Como vimos en el caso de las gramáticas regulares, aplicar una regla X a de una gramática consiste en remplazar X por a en una palabra. Por ejemplo, la regla S aSb se puede aplicar a una palabra aaSbb para obtener la palabra aaaSbbb, en donde es fácil var que reemplazamos S por aSb.
Al proceso de aplicar una regla se le conoce como “paso de derivación”, y se denota usando una flecha gruesa “”, como en aaSbb aaaSbbb (aplicando una regla S aSb).
Una secuencia de pasos de derivación a partir de una variable especial de la gramatica llamada “símbolo inicial” se llama simplemente derivación. Por ejemplo, una derivación de la palabra “aaabbb” utilizando la gramatica de {aⁿbⁿ} sería (suponiendo que S es el símbolo inicial):
S aSb aaSbb aaabbb
Como un ejemplo adicional, la gramática con las reglas siguientes permite generar expresiones aritméticas con sumas y multiplicaciones de enteros:
1.- E E + T
2.- E T
3.- T T * F
4.- T F
5.- F CF
6.- F C
7.- C 0|1|2|3|4|5|6|7|8|9
El símbolo inicial aquí es E, las constantes son +, * y las cifras 0….9; E, T, F, C son variables.
Con esta gramática podemos generar, por ejemplo, la expresión 25 + 3 * 12 de la manera siguiente:
EXPRESIÓN
JUSTIFICACIÓN
E
Símbolo inicial, inicia derivación
E+T
Aplicación 1ª. regla
T+T
2ª. Regla, sobre la E
F+T
4ª. Regla, sobre la T izquierda
CF+T
5ª. Regla, sobre F
2F+T
7ª. Regla
2C+T
6ª. regla
25+T
7ª. regla
25+T*F
3ª. regla
25+F*F
4ª. regla
25+C*F
6ª. Regla, sobre la F izquierda
25+3*F
7ª. regla
25+3*CF
5ª. regla
25+3*1F
7ª. regla
25+3*1C
6ª. regla
25+3*12
7ª. regla
Más adelante veremos una herramienta, los “arboles de derivación”, que permiten encontrar más fácilmente y visualizar mejor la derivación de las palabras a partir del símbolo inicial, aunque su formalización es menos directa que la simple derivación paso a paso que hemos mostrado.
ARBOLES DE DERIVACIÓN.
S
S S
( S ) ( )
S S
( ) ( )
Figura 4.1: paréntesis bien balanceados.
Las GLC tienen la propiedad de que las derivaciones pueden ser representadas en forma arborescente. Por ejemplo, considérese la gramática siguiente para producir el lenguaje de los paréntesis bien balanceados, que tiene palabras como (()), ()(), (()())(), pero no a (() ni )( :
1.- S SS
2.- S (S)
3.- S ()
Usando esta gramática, la palabra (()())() puede ser derivada de la manera que se ilustra en la figura 4.1. En dicha figura se puede apreciar la estructura que se encuentra implícita en la palabra (()())(). A estas estructuras se les llama árboles de derivación, o también árboles de compilación –por usarse extensivamente en los compiladores- y son de vital importancia para la teoría de los compiladores de los lenguajes de programación.
Se puede considerar que un árbol de derivación es más abstracto que una derivación “lineal” –es decir, una sucesión S … w- en el sentido de que para un solo árbol de derivación puede haber varias derivaciones lineales, según el orden en que se decida “expandir” los no terminales. Por ejemplo, para el árbol de la figura de arriba, hay al menos las derivaciones siguientes (anotamos como subíndice de el número de regla aplicado):
1.- S 1 SS 2 (S) S 3 (S) () 1 (SS) () 3 (S ()) () 3 (() ()) ().
2.- S 1 SS 3 S() 2 (S) () 1 (SS) () 3 (() S) () 3 (() ()) ().
Formalmente, un árbol de derivación es un grafo dirigido arborescente definido de la manera siguiente:
Definición.- Sea G = (V, ∑, R, S) una GLC. Entonces un árbol de derivación cumple las siguientes propiedades:
1.- Cada nodo tiene una etiqueta.
2.- La raíz tiene etiqueta S.
3.- La etiqueta de los nodos que no son hojas debe estar en V, y las de las hojas en ∑U {€}.
4.- Si un nodo n tiene etiqueta A, y los nodos n1,……., nm son sus hijos (de izquierda a derecha), con etiquetas respectivamente A1,….., Am, entonces AA1,…, Am € R.
Definición.- la cadena de caracteres que resulta de concatenar terminales encontradas en las etiquetas de los nodos hoja, en un recorrido en orden del árbol de derivación, se llama el producto del árbol.
Es decir, al efectuar un recorrido en orden del árbol de derivación recuperamos la cadena a partir de la cual se construyó dicho árbol. Así, el problema de “compilar” una cadena de caracteres consiste en construir el árbol de derivación a partir del producto de éste.
FORMA NORMAL DE CHOMSKY.
En ocasiones es necesario expresar una GLC siguiendo un formato más preciso de las reglas que la simple forma Aa. Estos “estándares” reciben el nombre de formas normales.
Vamos a estudiar una de las formas normales más conocidas, la forma normal de Chomsky (FNCH).
La FNCH consiste en que las reglas pueden tener dos formas:
1.- A α, a € ∑
2.- ABC, con B, C € V
Esta forma normal, aparentemente tan arbitraria, tiene por objeto facilitar el análisis sintáctico de una palabra de entrada, siguiendo la estrategia siguiente: Se trata de construir el árbol de derivación de w de arriba hacia abajo (llamado “top-down” en inglés), y por consiguiente se supone inicialmente que el símbolo de entrada w en dos pedazos, w = α β, para luego tomar alguna regla SAB , y tratar de verificar si se puede derivar α a partir de A y b a partir de B, es decir: S … w si:
1.- w € ∑, hay una regla Sw
2.-w = α β, hay una regla SAB, con A…. α, y B….. β
Por ejemplo, considérese la siguiente gramática para el lenguaje de los paréntesis bien balanceados, en forma normal de Chomsky (damos sus reglas):
1.- SXY
2.-X(
3.-YSZ
4.-Z)
5.-SSS
6.-SXZ
Supongamos que tenemos una palabra como (()) (), y queremos verificar si se puede derivar a partir de esta gramática. Hay que “partir” dicha palabra en dos pedazos, y escoger alguna
S
S S
X Y X Z
S Z ( )
X Z )
( )
Figura 4.3: Árbol de la palabra (()) ()
Regla que produzca dos variables. Escogemos la quinta regla, SSS, y partimos la palabra en los pedazos (()) y (). Para que SS pueda generar (()) () ahora se necesitará que la primera S pueda generar (()), y la segunda pueda generar (). Estos son subproblemas muy similares al problema inicial. Tomemos el primero, es decir, a partir de S generar (()). Escogemos la regla SXY, y partimos la palabra en (y ()). Ahora X tiene la responsabilidad de generar (y Y la de generar ()). Por la segunda regla, X genera directamente (. Ahora tomamos el problema de generar ()) a partir de Y. escogemos la regla SSZ, y la separación en los pedazos () y ). Entonces Z produce directamente ), y queda por resolver cómo S produce (). Para ello, escogemos la regla SXZ, y finalmente X produce ( y z se encarga de ), con lo que terminamos el análisis. E árbol de compilación se presenta en la figura 4.3.
CONCLUSIÓN.
El trabajo descrito representa una aportación significativa y original al análisis sintáctico de los lenguajes de adjunción de árboles y por extensión al procesamiento del lenguaje
natural, a la inteligencia artificial, y a la teoría de autómatas y lenguajes formales.
En este trabajo se ha mostrado que es posible establecer un camino evolutivo continuo en el que se sitúan los algoritmos de análisis sintáctico que incorporan las estrategias de análisis más importantes, tanto para el caso de las gramáticas de adjunción de árboles como para el caso de las gramáticas lineales de índices. Los diferentes algoritmos se han definido con esquemas de análisis sintáctico, de tal modo que los algoritmos más complejos se derivan a partir de los menos complejos aplicando una secuencia de transformaciones simples.
En el caso de las gramáticas lineales de índices el resultado es doblemente interesante, pues
si bien se ha esgrimido a su favor su adecuación como formalismo intermedio para el análisis de gramáticas de adjunción de árboles, lo cierto es que numerosas estrategias de análisis para estas últimas no se hallaban incorporadas a ningún algoritmo de análisis sintáctico para gramáticas lineales de índices. En consecuencia, era necesario sacrificar la estrategia de análisis si se optaba por este enfoque, lo que limitaba enormemente su aplicación practica. Con el trabajo desarrollado hemos salvado ese obstáculo definiendo algoritmos de análisis sintáctico para gramáticas lineales de índices que incorporan la versión equivalente de las estrategias de análisis más populares para gramáticas de adjunción de árboles.
En el caso de las gramáticas independientes del contexto es posible optar por un diseño modular en el cual se separa la definición y la ejecución de una determinada estrategia de análisis.
En particular, es posible definir un algoritmo de análisis sintáctico como un conjunto de transiciones de un autómata a pila, probablemente no determinista, el cual puede ser interpretado eficientemente mediante las técnicas de tabulación disponibles. Este enfoque presenta ventajas evidentes, entre la cuales cabe citar la simplificación de las pruebas de corrección de los algoritmos, los cuales son mas fáciles de comprender y, al ser ejecutados en un entorno homogéneo, son fácilmente comparables. En este trabajo hemos adaptado este enfoque a los lenguajes de adjunción de árboles de derivación, proporcionando modelos de autómata con los que describir los algoritmos de análisis y técnicas de tabulación con las que pueden ser ejecutados eficientemente.
Finalmente hemos analizado que dentro de los analizadores sintácticos que vimos, pudimos notar la diferencia entre los que son descendentes y los ascendentes, y sus principales características, viendo también la forma normal de Chomsky que es de gran importancia en el análisis sintáctico.
BIBLIOGRAFIA.
1.-ALFRED V. AHO, RAVI SETHI, JEFFREY D ULLMAN, PEDRO FLORES SUÁREZ, PERE BOTELLA I LÓPEZ.
*Compiladores: Principios, Técnicas y Herramientas: Pearson Education, 1988.
2.- RAMON F. BRENA.
*Autómatas y Lenguajes: Tecnológico de Monterrey, 2003.
3.- SERGIO GÁLVEZ ROJAS, MIGUEL ÁNGEL MORA MATA.
*Java a Tope: Traductores Y Compiladores Con Lex/yacc, Jflex/cup Y Javacc: Universidad de Málaga, 2005.
4.- GONZALO SÁNCHEZ DUEÑAS, SANCHEZ G. VALVERDE, JUAN ANTONIO VALVERDE ANDREU.
* Compiladores e intérpretes: Ediciones Días de Santos, S.A., 1989.
