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

Definición 4.5.1 Dado un conjunto , se define el cierre de Kleene de 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 .

Definición 4.5.2 Una gramática es una cuaterna $G =(\Sigma,V,P,S)$ . $\Sigma$ es el conjunto de terminales. 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 se denomina producción. Por último, es un símbolo del conjunto que se denomina símbolo de arranque.

Definición 4.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 , 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 de por la parte derecha $\gamma$ de una de sus reglas de producción. Se dice que $\mu$ deriva en pasos en $\delta$ si deriva en 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 4.5.4 Dada una gramática $G =(\Sigma,V,P,S)$ se denota por o lenguaje generado por al lenguaje:

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

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

Definición 4.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 4.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 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 4.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 . Dicho árbol se denomina árbol de análisis sintáctico concreto de . Una derivación determina una forma de recorrido del árbol de análisis sintáctico concreto.

Definición 4.5.8 Una gramática 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.