ÁRBOLES DE SINTAXIS
ÁRBOL grafo dirigido acíclico.
Los nodos no terminales (nodos interiores) están rotulados por los
sí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.
Árbol de sintaxis de una oración
Oración
Sujeto
Verbo
Objeto
Sustantivo
I
see
the
cat
.
Sea G una 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íz rotulado 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::= , el N-á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
1) Dada la regla de producción
Número ::= Dígito
| Número Dígito
Un número-árbol posible es
Número
Número
Dígito
Dígito
4
0
Ejemplo
2) Dado el comando ‘3*9=’ y teniendo en cuenta las reglas de
producción para formar comandos y expresiones (Ejemplo de la
calculadora), el árbol de sintaxis correspondiente es:
Comando
Expresión
Expresión
Número
Número
Dígito
3
Dígito
*
9
=
FRASES, SENTENCIAS y
LENGUAJE
Sea G una Gramática Libre de Contexto.
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 símbolo de
partida de G.
El lenguaje generado por G, es el conjunto de todas las sentencias de
G.
Por ejemplo :
 “I see the cat .” es una Sentencia-frase de G.
 “I” es un Sujeto-frase
 “see” es un Verbo-frase
 “the cat “es un Objeto-frase.
“I”, “see” y “the cat” son cadenas de símbolos terminales.
En el ejemplo de la
Calculadora:
 “3”, “40” y “365” son Numeros-frases
 “3*9” y “40-3*9” son Expresiones-frases
 “3*9=” y “40-3*9=” son Comandos-frases
INTERPRETACIÓN DE LOS
ÁRBOLES DE SINTAXIS
Los árboles de sintaxis pueden ser usados para darle un significado a
la sentencia, aplicando algún tipo de interpretación de semántica
al mismo.
Sea el comando ' 40 - 3 * 9 = ' en el ejemplo de la calculadora
Comando
Expresión
Expresión
Número
Este árbol sugiere que el
comando se calculará como:
(40-3)*9 =
Expresión Número
Número
40
-
3
*
9
=
AMBIGÜEDAD
El siguiente ejemplo muestra que una gramática diseñada sin cuidado
puede ser ambigua con respecto a alguna sentencia.
Ejemplo: consideremos una variación de la regla de producción de la
gramática G para Expresión en el ejemplo de la calculadora:
Expresión ::=
Número
| Expresión + Expresión
| Expresión - Expresión
| Expresión * Expresión
y mantenemos las otras reglas de producción.
La gramática G resulta ambigua con respecto a algunas de las
expresiones como por ejemplo, la expresión "40 - 3- 9 " puesto
que ésta se corresponde con dos árboles de sintaxis diferentes.
Expresión
Expresión
Expresión
Expresión
Expresión
Expresión
Número
Expresión
Expresión
Número Número
40
Interpretación:
-
3
Expresión
Expresión
Número
Número
-
(40 - 3) - 9
9
40
-
3
Número
-
40 - (3 - 9)
9
Ejemplo 2
Sea la siguiente regla de producción en el lenguaje de programación
L.
Com ::= Var:=Expr
| if Expr then Com
| if Expr then Com else Com
donde:
Com  nombra la clase de comandos.
E y E  expresiones arbitrarias y
C y C  comandos arbitrarios (tales como asignaciones).
Luego el comando
‘if E then if E then C else C’ es ambiguo
Árboles de sintaxis para Com
Com
Expr
Com
Expr
if
E then
if
E’ then
Com
C
Com
else
C’
Com
Expr
Com
Expr
if
E then
if
E’ then
Com
Com
C
else
C’
RECONOCIMIENTO y ANÁLISIS
SINTÁCTICO
El RECONOCIMIENTO de una cadena terminal en una gramática G es
decidir si la cadena es o no una sentencia de G, de acuerdo a las
reglas de G.
El ANÁLISIS SINTÁCTICO o "parsing" de una cadena terminal, en una
gramática G es el reconocimiento más la reconstrucción del(los)
árbol(es) de sintaxis de la cadena, de acuerdo a las reglas de G.
El análisis sintáctico es necesario para deducir cada estructura de
frase de la sentencia y luego determinar su significado.
Ejemplo:
Consideremos las reglas de la gramática del ejemplo de la
calculadora:
Comando
Expresión
=
(a)
Expresión
Expresión - Número
(d)
Expresión
Número
(b)
Expresión
Expresión
+ Número
(c)
Expresión
Expresión * Número
(e)





Analizaremos la cadena terminal:
‘40 - 3 * 9 = ’
(1) ‘40’, ‘3’ y ‘9’ son Número -frases
Número
40
Número
-
3
Número
*
9
=
(2) Hacemos corresponder el número ‘40’con el fragmento del árbol
(b)
Expresión
Número
40
Número
*
3
-
Número
9
=
3) El fragmento de árbol (b), el terminal ‘-’ y el número 3, podemos
corresponderlos con el fragmento de árbol (d)
Expresión
Expresión
Número
40
Número
Número
-
3
*
9
=
(4) El último fragmento de árbol, el terminal ‘*’ y el número ‘9’,
podemos corresponderlos con el fragmento del árbol (e):
Expresión
Expresión
Expresión
Número
Número
40
-
3
Número
*
9
Comando
(5) El último fragmento del árbol y el terminal ‘=’, podemos
corresponderlos con el fragmento de árbol (a)
Comando
Expresión
Expresión
Expresión
Número
Número
Número
40
-
3
*
9
=
AUTOINCLUSIÓN
(Anidamiento)
Las gramáticas Libres de Contexto son muy efectivas para
especificar estructuras de frases anidadas (self-embedded)
Ejemplo: Pascal tiene:
(a) expresiones anidadas:
a - (b + c)
sin (2 * x)
(b) comandos anidados:
if a > b then m := a else m := b
begin x := 0; y := 0 end
Una gramática libre de contexto G es anidada si, para algunos
símbolos no terminales N de G, existe una N-frase  tal que  es
también una N-frase y tal que tanto  como  son cadenas
terminales no vacías.
El anidamiento
Recursividad en las Reglas de producción
Por ejemplo:
Com::= Var:= Expr
| if Expr then Com
| if Expr then Com else Com
Es una regla recursiva.
Descargar

ÁRBOLES DE SINTAXIS