Arboles de sintaxis

 Fecha: 24-febrero-2013








Universidad de Guadalajara

Centro Universitario de Ciencias Exactas e Ingenierías
Licenciatura en informática
Lenguajes deprogramación comparados




Nombre:Martínez Tapia Mario Alberto 211373046








Arboles de sintaxis
Un árbol de sintaxis es un árbol binario completo, en el cual los nodos interiores sonoperadores y las hojas, operandos, y representa, sin ambigüedad, una expresión aritmética.
Ejemplo

A continuación se presenta el árbol de sintaxis correspondiente a algunas expresiones aritméticasen notación infija:
A
( A + B )
( ( A + B ) - ( C * 5 ) )
( ( ( A - B ) - C ) - D )





ÁRBOL grafo dirigido acíclico.
 Los nodos no terminales (nodos interiores) están rotulados por lossímbolos no terminales.
 Los nodos terminales (nodos hojas) están rotulados por los símbolos terminales.
 Las reglas de producción de la gramática relacionan cada nodo no terminal y sus hijos.
Sea Guna gramática libre de contexto un árbol de sintaxis de G es un árbol rotulado y ordenado, con las siguientes propiedades:
 para cualquier símbolo no terminal N de G, un N-árbol tiene un nodo raízrotulado por N. Sus subárboles pueden ser un X1-árbol, ......, Xn-árbol (de izquierda a derecha) solamente si N::= X1..... Xn es una regla de producción de G. (si la regla de producción es N::= , elN-árbol no tiene subárboles
  Para cualquier símbolo terminal t de G, un t-árbol es un único nodo terminal rotulado por t.



Ejemplo
Dado el comando ‘3*9=’ y teniendo en cuenta las reglas deproducción para formar comandos y expresiones (Ejemplo de la calculadora), el árbol de sintaxis correspondiente es:











FRASES, SENTENCIAS y LENGUAJE
Sea G una Gramática Libre deContexto.
 Una frase de G es una cadena de símbolos terminales, los que forman una N-frase de G para cada símbolo no terminal N de G.
 Una sentencia de G, es una S-frase de G, donde S es el...