| INSTITUTO POLITÉCNICO NACIONAL ESCUELA SUPERIOR DE CÓMPUTO |

Introducción | Contenido | Bibliografía

Introducción
Contenido
UNIDAD I Introducción 1.1 Lenguajes y Gramáticas 1.2 Clasificación de las Gramáticas 1.3 Derivaciones y Reducciones

1.4 Árboles de sintaxis

1.5 Gramáticas Ambiguas

1.6 Formas de Backus-Naur (BNF)

UNIDAD II
UNIDAD III
UNIDAD IV
UNIDAD V
UNIDAD VI
UNIDAD VII
UNIDAD VIII
UNIDAD IX
PROBLEMARIO
Bibliografía

1.4 Árboles de Sintaxis

> Un árbol de derivación es aquel en el cual cada producción tiene su correspondiente objeto, por tal razón, la salida del análisis sintáctico es un árbol que puede ser un árbol de derivación o un árbol de sintaxis.

> Es la representación gráfica de la derivación de una cadena, se crea utilizando el símbolo inicial como la raíz, los símbolos N representan los nodos del árbol y los símbolos T las hojas del árbol.

> A través de los árboles de derivación se puede verificar la sintaxis de un lenguaje así como comprobar el significado de las palabras.

> Un árbol D es un árbol de derivación para una gramática G = (Vn, Vt, S, P), si:

> a) La raíz del árbol está rotulada como S.

> b) Cada nodo es rotulado con un símbolo de VN VT {λ}.

> c) Si un nodo interior es rotulado A, y sus descendientes directos son rotulados x1..xn, entonces existe en G una producción A → x1..xn.

> Ejemplo:

> Desarrollar el árbol de derivación para la cadena ‘()()’, a partir de la gramática:

> G = (Vn,Vt, S, P),

> Vn = {S},

> Vt = {(, )},

> P = {S → (), S → SS, S → (S) }

> El árbol de la cadena derivada es el siguiente: ( ) ( ).

> Aplicando las reglas que se presentaron, tenemos:

> Por S → SS
> Por S → () Por S → ()

> Ejemplo:

> Desarrollar el árbol de derivación para la cadena aaabbb, a partir de la gramática:

> G = (Vn,Vt, S, P),

> Vn = {S,R},

> Vt = {b,a},
> P = {S → λ, S → R, R → aRb , R → ab }

> El árbol para la gramática que se pide en este ejercicio, se muestra en la siguiente figura:

> Ejemplo:

> Obtener la cadena de caracteres aaa, y sea G la siguiente gramática, con la que queremos derivar a3 = aaa.

> G = (Vn, Vt, S, P),

> Vn = {S},

> Vt = {a},

> P = {S → aS, S → Sa , S → a}

> El árbol de la gramática que pide es el siguiente:

> Un árbol sintáctico es una representación de la consecución de tokens, en la que éstos aparecen como nodos hoja y los internos son derivaciones de la gramática asociada. Una simplificación del árbol sintáctico que represente toda la información necesaria para el resto de las fases, recibe el nombre de árbol de sintaxis abstracta (AST), la salida del analizador sintáctico del procesador de varias pasadas (la entrada del semántico) es un AST.
> Un AST puede verse como el árbol sintáctico de una gramática, lo cual corresponde a la gramática abstracta del lenguaje original.

> El Teorema de árboles para Gramáticas Libres de Contexto (GLC), es:

> Sea G = (Vn, Vt, S, P) una GLC. Entonces para toda cadena w L(G), se cumple que:

> S w , si existe un árbol de derivación a partir de G con raíz en S cuya frontera es w.

> Este teorema nos asegura que toda cadena de un lenguaje libre de contexto puede derivarse con árboles de derivación, y que si algo se sigue vía un árbol de derivación, entonces pertenece a algún lenguaje libre de contexto.

> Atrás Siguiente

##### Introducción / Contenido / Unidad I / Unidad II / Unidad III / Unidad IV / Unidad V / Unidad VI / Unidad VII / Unidad VIII / Unidad IX / Problemario / Bibliografía

##### Inicio

##### Créditos

José Sánchez Juárez, Andrés Ortigoza Campos, Fabiola Ocampo Botello