PDF de programación - Análisis sintáctico I / Gramáticas

ANÁLISIS SINTÁCTICO I

GRAMÁTICAS





ANÁLISIS SINTÁCTICO I

GRAMÁTICAS

© Todos los derechos de propiedad intelectual de esta obra pertenecen en exclusiva a la Universidad
Europea de Madrid, S.L.U. Queda terminantemente prohibida la reproducción, puesta a disposición del
público y en general cualquier otra forma de explotación de toda o parte de la misma.

La utilización no autorizada de esta obra, así como los perjuicios ocasionados en los derechos de
propiedad intelectual e industrial de la Universidad Europea de Madrid, S.L.U., darán lugar al ejercicio
de las acciones que legalmente le correspondan y, en su caso, a las responsabilidades que de dicho
ejercicio se deriven.

2





Índice

Presentación

Introducción

Gramáticas independientes del contexto

Árboles de derivación

¿Qué es una derivación?

¿Qué es un árbol de derivación?

Ejemplo de árbol de derivación

Limpieza de gramáticas

Símbolos superfluos

Símbolos inaccesibles

Orden de limpieza de gramáticas

Ambigüedades

Eliminar la recursividad a izquierdas

Eliminar varias alternativas que comienzan igual

Gramáticas ambiguas

Precedencia y asociatividad

El problema del else ambiguo

Resumen

ANÁLISIS SINTÁCTICO I

GRAMÁTICAS

4

5

7

9

9

9

11

15

15

15

16

18

18

18

20

21

23

25

3
© Univ ersidad Europea de Madrid. Todos los derechos reserv ados.





Presentación

ANÁLISIS SINTÁCTICO I

GRAMÁTICAS

El objetivo de este tema es aprender a diseñar gramáticas a partir de un conjunto de reglas
que estas deben cumplir. Para ello, vamos a ampliar algunos conceptos necesarios para las
gramáticas tipo 2 de la jerarquía de Chomsky, a la vez que se revisan conceptos sobre

ambigüedades vistos anteriormente.

También es importante aprender a validar una sentencia para saber si pertenece a una
gramática determinada o no, además de aprender a reconocer cuándo una gramática no está
limpia y qué orden hay que seguir para limpiarla.

Los objetivos a conseguir en este tema son:

Entender la motivación de las Gramáticas Independientes del Contexto (GIC).

Conocer el funcionamiento de los árboles de derivación.

Cómo limpiar una gramática.

Cuál es el orden de limpieza de gramáticas.

Identificar las ambigüedades y las gramáticas ambiguas.

Conocer los conceptos de precedencia y asociatividad.

El problema del else ambiguo.

4
© Univ ersidad Europea de Madrid. Todos los derechos reserv ados.





Introducción

ANÁLISIS SINTÁCTICO I

GRAMÁTICAS

Es importante dominar conceptos como qué es una gramática, cómo se especifica de una
manera formal, qué es el lenguaje generado por una gramática, los tipos de gramáticas
que existen (jerarquía de Chomsky) para construir los conceptos que veremos en este tema.
También necesitamos conceptos como el de token o componentes léxico junto con el de las

expresiones regulares (gramáticas tipo 3 de la jerarquía de Chomsky).

La manera formal de describir una gramática es mediante cuatro términos: el

alfabeto de los símbolos terminales (∑T), el alfabeto de los símbolos no terminales

(∑N), el axioma o símbolo inicial de la gramática (S) y un conjunto de producciones

(P).

Se denota mediante G = {∑T, ∑N, S, P} , y su forma de representarla es mediante la notación
denominada Forma de Backus-Naur (notación BNF), como vemos en la siguiente producción E

→ E + E, donde el único símbolo terminal es +, el no terminal es E, que a su vez es el axioma de

la gramática.

La independencia de una gramática respecto del contexto

También es importante validar que esa gramática es capaz de reconocer sentencias del lenguaje
que se ha definido previamente, y para ello utilizamos unas estructuras denominadas árboles de
derivación o árboles sintácticos.

Por todo lo anterior, las gramáticas nos proporcionan las siguientes ventajas (Aho et al, 1986):

1. Proporcionan una especificación sintáctica precisa y fácil de entender de un lenguaje

de programación.

2. 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 o no.

3. 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.

4. Se pueden añadir mejoras al lenguaje fácilmente.

5
© Univ ersidad Europea de Madrid. Todos los derechos reserv ados.





ANÁLISIS SINTÁCTICO I

GRAMÁTICAS

En detalle

La independencia de una gramática respecto del contexto

Principalmente, debemos ser capaces de construir una gramática a partir de la

especificación de un lenguaje y, una vez obtenida, comprobar que no tiene errores ni

ambigüedades y dejarla preparada para su utilización por un analizador sintáctico.

Para ello, debemos saber distinguir cuándo una gramática es independiente del
contexto (gramáticas tipo 2 de la jerarquía de Chomsky) y cuándo no lo es.

6
© Univ ersidad Europea de Madrid. Todos los derechos reserv ados.





ANÁLISIS SINTÁCTICO I

GRAMÁTICAS

Gramáticas independientes del contexto

Una gramática independiente del contexto (GIC) es una especificación para la estructura

sintáctica de un lenguaje de programación (Louden, 2004). Dependiendo del autor, también se
las denomina gramáticas libres de contexto.

¿Por qué se llaman independientes del contexto?

Un ejemplo de gramática tipo 1 es el siguiente: aBc → aJc, donde para transformar B en J,
tienen que tener a su izquierda a y a su derecha c, por tanto tienen que tener una parte común,

es decir, importa el contexto puesto que dependen de él.

En las GIC, la parte izquierda de las producciones solo pueden tener un símbolo no terminal y

para transformar una palabra en otra, el símbolo no terminal que se sustituye no depende de lo
que haya a su izquierda o a su derecha. Un ejemplo de producción puede ser: A → Bc.

Otro ejemplo de producción podría ser A→ Bc | aBd. A las producciones de la gramática
también se les denomina reglas gramaticales.

Notación BNF

Veamos otro ejemplo mas concreto. Una declaración de variables está formada por

el tipo de la variable y las variables, que pueden ser una variable o varias (una lista

de identificadores), es decir uno o varios identificadores. Los tipos de las variables

pueden ser enteros (int), reales (real) o de tipo caracter (char).

¿Cómo lo especificamos en esta notación?

La declaración la sustituimos por el no terminal D, las variables por el no terminal V y los tipos

posibles por el no terminal T. Los tipos posibles serán int, real o char.

Resultado

7
© Univ ersidad Europea de Madrid. Todos los derechos reserv ados.





ANÁLISIS SINTÁCTICO I

GRAMÁTICAS

En detalle

¿Por qué se llaman independientes del contexto?

Son las gramáticas tipo 2 de la jerarquía de Chomsky y se denominan independientes del

contexto, en contraposición con las de tipo 1, que se denominan dependientes del contexto

o sensibles al contexto.

Algunos autores a las gramáticas de tipo 1 las denominan gramáticas de contexto libre, que

es justo lo contrario de lo que significan.

Ejemplo

Notación BNF

Para especificar esta última producción hemos utilizado la notación BNF, en la que el

primer símbolo es un no terminal (A) que es el nombre de la estructura o producción, el

segundo símbolo es el metasímbolo "→" y este símbolo viene seguido por una cadena de

símbolos que pueden ser:

No terminales (en este caso B, puesto que establecimos un convenio por el que las

letras mayúsculas representaban no terminales).

Símbolos terminales (o símbolos del alfabeto y se representan mediante letras

minúsculas, en esta producción c).

El metasímbolo "|", indicando que hay otra alternativa.

En detalle

Resultado

D → T V.

T → int | real | char.

V → id; | id, V.

Nota1: El punto y coma ";" y la coma "," son terminales, al igual que int o id.

Nota 2: Es importante entender el concepto de recursividad que encierra la producción V
→ id, V. La recursividad es una característica esencial de las GIC y nos permite expresar
el concepto de un identificador seguido de uno o más identificadores. Este concepto de

recursividad no lo hubiéramos podido expresar con una expresión regular.

8
© Univ ersidad Europea de Madrid. Todos los derechos reserv ados.





Árboles de derivación

ANÁLISIS SINTÁCTICO I

GRAMÁTICAS

Ahora necesitamos validar que una sentencia pertenece a esta gramática y para ello necesitamos

una herramienta denominada árbol de derivación o árbol de análisis sintáctico.
¿Qué es una derivación?
Se representa por x ==> y y es la aplicación de una regla de producción a→b a una cadena x
para convertirla en otra cadena o palabra y.

En el ejemplo anterior, partiendo de D → T V, si aplicamos la producción T → int, se deriva
directamente D → int V.

Es importante entender que decimos directamente porque es lo que se obtiene a partir de la

aplicación directa de la producción T → int.

Cuando lo que se aplica es una secuencia de producciones a una cadena se representa por x
==>* y, queriendo indicar que llegamos a otra cadena en más de un paso. En el ejemplo anterior,
D → T V ==>* int a, b, c;, y realizamos, por tanto, derivaciones en más de un paso para
obtener la cadena final.

Derivaciones por la izquierda y la derecha

¿Qué es un árbol de derivación?
Es una representación utilizada para describir el proceso de derivación de una sentencia, donde

se cumple lo siguiente:

La raíz del árbol es el símbolo inicial de la gramática.

Los nodos intermedios del árbol son los no terminales de las producciones que se utilizan.

Estos nodos intermedios tendrán tantos hijos como elementos tenga el lado derecho de la

producción.

Los nodos hoja serán los terminales.