next up previous contents index practicapracticaPP2moodleLHPmoodlepserratacpanmodulospauseperlgoogleetsiiullpcgull
Sig: Ejercicio Sup: La Estructura de los Ant: Repaso: Pruebas en el Err: Si hallas una errata ...


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 11.5.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 11.5.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 11.5.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 11.5.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 11.5.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 11.5.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$.

Definición 11.5.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 11.5.8   Una gramática $ G$ se dice ambigua si existe alguna frase $ x \in L(G)$ con al menos dos árboles sintácticos.



Subsecciones
next up previous contents index practicapracticaPP2moodleLHPmoodlepserratacpanmodulospauseperlgoogleetsiiullpcgull
Sig: Ejercicio Sup: La Estructura de los Ant: Repaso: Pruebas en el Err: Si hallas una errata ...
Casiano Rodríguez León
2006-02-21