Subsecciones


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. Las siguientes definiciones repasan los conceptos mas importantes.

Definición 5.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 5.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 5.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 5.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 5.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 5.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 5.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 5.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 % latex2html id marker 22437
$ 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.

Casiano Rodríguez León
2016-03-27