Conceptos Básicos para el Análisis Sintáctico

Suponemos que el lector de esta sección ha realizado con éxito un curso en teoría de autómatas y lenguajes formales (computabilidad). Las siguientes definiciones repasan los conceptos mas importantes.

Definición 2.1.1   Dado un conjunto $A$, se define $A^*$ el cierre de Kleene de $A$ como: $A^* = \cup_{n=0}^{\infty} A^n$

Se admite que $A^0 = \{ \epsilon \}$, donde $\epsilon$ denota la palabra vacía, esto es la palabra que tiene longitud cero, formada por cero símbolos del conjunto base $A$.

Definición 2.1.2   Una gramática $G$ es una cuaterna $G =(\Sigma,V,P,S)$. $\Sigma$ es el conjunto de terminales. $V$ es un conjunto (disjunto de $\Sigma$) que se denomina conjunto de variables sintácticas o categorías gramáticales, P es un conjunto de pares de $V \times (V \cup \Sigma )^*$. En vez de escribir un par usando la notación $(A, \alpha) \in P$ se escribe $A \rightarrow \alpha$. Un elemento de $P$ se denomina producción. Por último, $S$ es un símbolo del conjunto $V$ que se denomina símbolo de arranque.

Definición 2.1.3   Dada una gramática $G =(\Sigma,V,P,S)$ y $\mu = \alpha A \beta \in (V \cup \Sigma)^*$ una frase formada por variables y terminales y $A \rightarrow \gamma$ una producción de $P$, decimos que $\mu$ deriva en un paso en $\alpha \gamma \beta$. Esto es, derivar una cadena $\alpha A \beta$ es sustituir una variable sintáctica $A$ de $V$ por la parte derecha $\gamma$ de una de sus reglas de producción. Se dice que $\mu$ deriva en $n$ pasos en $\delta$ si deriva en $n-1$ pasos en una cadena $\alpha A \beta$ la cual deriva en un paso en $\delta$. Se escribe entonces que $\mu \stackrel{*}{\Longrightarrow} \delta$. Una cadena deriva en 0 pasos en si misma.

Definición 2.1.4   Dada una gramática $G =(\Sigma,V,P,S)$ se denota por $L(G)$ o lenguaje generado por $G$ al lenguaje:

$L(G) = \{ x \in \Sigma^* : S \stackrel{*}{\Longrightarrow} x \}$

Esto es, el lenguaje generado por la gramática $G$ esta formado por las cadenas de terminales que pueden ser derivados desde el símbolo de arranque.

Definición 2.1.5   Una derivación que comienza en el símbolo de arranque y termina en una secuencia formada por sólo terminales de $\Sigma$ se dice completa.

Una derivación $\mu \stackrel{*}{\Longrightarrow} \delta$ en la cual en cada paso $\alpha A x$ la regla de producción aplicada $A \rightarrow \gamma$ se aplica en la variable sintáctica mas a la derecha se dice una derivación a derechas

Una derivación $\mu \stackrel{*}{\Longrightarrow} \delta$ en la cual en cada paso $x A \alpha$ la regla de producción aplicada $A \rightarrow \gamma$ se aplica en la variable sintáctica mas a la izquierda se dice una derivación a izquierdas

Definición 2.1.6   Observe que una derivación puede ser representada como un árbol cuyos nodos están etiquetados en $V \cup \Sigma$. La aplicación de la regla de producción $A \rightarrow \gamma$ se traduce en asignar como hijos del nodo etiquetado con $A$ a los nodos etiquetados con los símbolos $X_1 \ldots X_n$ que constituyen la frase $\gamma = X_1 \ldots X_n$. Este árbol se llama árbol sintáctico concreto asociado con la derivación.

Definición 2.1.7   Observe que, dada una frase $x \in L(G)$ una derivación desde el símbolo de arranque da lugar a un árbol. Ese árbol tiene como raíz el símbolo de arranque y como hojas los terminales $x_1 \ldots x_n$ que forman $x$. Dicho árbol se denomina árbol de análisis sintáctico concreto de $x$. Una derivación determina una forma de recorrido del árbol de análisis sintáctico concreto.

Definición 2.1.8   Una gramática $G$ se dice ambigua si existe alguna frase $x \in L(G)$ con al menos dos árboles sintácticos. Es claro que esta definición es equivalente a afirmar que existe alguna frase $x \in L(G)$ para la cual existen dos derivaciones a izquierda (derecha) distintas.

Ejercicio

Dada la gramática con producciones:

program $\rightarrow$ declarations statements $\vert$ statements

declarations $\rightarrow$ declaration ';' declarations $\vert$ declaration ';'

declaration $\rightarrow$ INT idlist $\vert$ STRING idlist

statements $\rightarrow$ statement ';' statements $\vert$ statement

statement $\rightarrow$ ID '=' expression $\vert$ P expression

expression $\rightarrow$ term '+' expression $\vert$ term

term $\rightarrow$ factor '*' term $\vert$ factor

factor $\rightarrow$ '(' expression ')' $\vert$ ID $\vert$ NUM $\vert$ STR

idlist $\rightarrow$ ID ',' idlist $\vert$ ID

En esta gramática, $\Sigma$ esta formado por los caracteres entre comillas simples y los símbolos cuyos identificadores están en mayúsculas. Los restantes identificadores corresponden a elementos de $V$. El símbolo de arranque es $S =$ program.

Conteste a las siguientes cuestiones:

1. Describa con palabras el lenguaje generado.
2. Construya el árbol de análisis sintáctico concreto para cuatro frases del lenguaje.
3. Señale a que recorridos del árbol corresponden las respectivas derivaciones a izquierda y a derecha en el apartado 2.
4. ¿Es ambigua esta gramática?. Justifique su respuesta.