Sig: Parse::Eyapp: Un Generador de Sup: Análisis Sintáctico con Parse::Eyapp Ant: Análisis Sintáctico con Parse::Eyapp 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 8.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 8.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 8.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 $\eta$ la cual deriva en un paso en $\delta$ . Se escribe entonces que $\mu \stackrel{n}{\Longrightarrow} \delta$ . Una cadena deriva en 0 pasos en si misma. Se escribe entonces que $\mu \stackrel{*}{\Longrightarrow} \delta$ .

Definición 8.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 8.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 8.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 8.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 8.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.

Definición 8.1.9   Un esquema de traducción es una gramática independiente del contexto en la cual se han insertado fragmentos de código en las partes derechas de sus reglas de producción.

$A \rightarrow \alpha \{ action \}$

Los fragmentos de código asi insertados se denominan acciones semánticas.

En un esquema de traducción los nodos del árbol sintáctico tienen asociados atributos. Si pensamos que cada nodo del árbol es un objeto, entonces los atributos del nodo son los atributos del objeto. Las reglas semánticas determinan la forma en la que son evaluados los atributos.

Los fragmentos de código de un esquema de traducción calculan y modifican los atributos asociados con los nodos del árbol sintáctico. El orden en que se evalúan los fragmentos es el de un recorrido primero-profundo del árbol de análisis sintáctico. Esto significa que si en la regla $A \rightarrow \alpha \beta$ insertamos un fragmento de código:

$A \rightarrow \alpha \{ action \} \beta$

La acción $\{ action \}$ se ejecutará después de todas las acciones asociadas con el recorrido del subárbol de $\alpha$ y antes que todas las acciones asociadas con el recorrido del subárbol $\beta$ .

Obsérvese que para poder aplicar un esquema de traducción hay que - al menos conceptualmente - construir el árbol sintáctico y después aplicar las acciones empotradas en las reglas en el orden de recorrido primero-profundo. Por supuesto, si la gramática es ambigua una frase podría tener dos árboles y la ejecución de las acciones para ellos podría dar lugar a diferentes resultados. Si se quiere evitar la multiplicidad de resultados (interpretaciones semánticas) es necesario precisar de que árbol sintáctico concreto se esta hablando.

Definición 8.1.10   Un atributo tal que su valor en un nodo puede ser computado en términos de los atributos de los hijos del nodo se dice que es un atributo sintetizado.

El siguiente esquema de traducción recibe como entrada una expresión en infijo y produce como salida su traducción a postfijo para expresiones aritmeticas con sólo restas de números:

$expr \rightarrow expr_1 - NUM$	{ $expr{TRA} = $expr[1]{TRA}." ".$NUM{VAL}." - "}
$expr \rightarrow NUM$	{ $expr{TRA} = $NUM{VAL} }

Que para una entrada 2 - 3 - 7 daría lugar a la siguiente evaluación:

e '2 3 - 7 -'
`-- --- e '2 3 -'
    |   `------ e '2'
    |       |    `-- N 2
    |       |-- '-'
    |       `-- N 3
    |-- '-'
    `-- N 7

Definición 8.1.11   Un atributo heredado es aquel cuyo valor se computa a partir de los valores de sus hermanos y de su padre.

Ejemplo 8.1.1   Un ejemplo de atributo heredado es el tipo de las variables en las declaraciones:

$decl \rightarrow type$ { $list{T} = $type{T} } $list$
$type \rightarrow INT$ { $type{T} = $int }
$type \rightarrow STRING$ { $type{T} = $string }
$list \rightarrow ID$ , { $ID{T} = $list{T}; $list_1{T} = $list{T} } $list_1$
$list \rightarrow ID$ { $ID{T} = $list{T} }

Sig: Parse::Eyapp: Un Generador de Sup: Análisis Sintáctico con Parse::Eyapp Ant: Análisis Sintáctico con Parse::Eyapp Err: Si hallas una errata ...