Gramáticas Libres de Contexto
Def. Una gramática libre de contexto (context free grammar) es un cuadruplo
G = <Vnt, , S, P>, en donde, Vn conjunto de símbolos terminales,  alfabeto,
S símbolo inicial y en la cual las producciones P son de la forma:
A
en donde A es una categoría sintáctica y  una cadena de símbolos
terminales o categorías sintácticas.
Las gramáticas libres de contexto generan lenguajes libres de contexto.
Ejemplos de lenguajes libres de contexto:
a). Los palíndromes que son palabras que se leen igual si se leen en cualquier
dirección. Para un vocabulario de 0’s y 1’s:
{, 0, 1, 00, 11, 010, 000, 101, 111, ...} ( es la cadena vacía)
R1. S  
R2. S  0
b). {ai bi | i0}
R3. S  1
R4. S  0S0
R1. S  
R5. S  1S1
R2.
S  aSb
Gramáticas Libres de Contexto
Def. El lenguaje definido por una gramática es el conjunto de
cadenas formadas por símbolos terminales que pueden ser
derivadas a partir del símbolo inicial.
Def. Una derivación es el resultado de aplicar una de las
reglas de la gramática a la cadena.
Teorema. Toda cadena en el lenguaje definido por una
gramática, es derivable bajo el método de la derivación de
más a la izquierda (leftmost derivation).
Def. Una gramática libre de contexto G es ambigua, si existe
una cadena   L(G), tal que  puede ser derivada
utilizando dos derivaciones de más a la izquierda.
Gramáticas Libres de Contexto
• Ejemplo:
Jack was given a book by Hemingway
Gramáticas Libres de Contexto
Ejemplo:
R1.
R2.
R3.
R4-5.
R6-7.
R8-9.
R10-12.
EC;
EV
EV=E ;
EE*E|E/E ;
EE+E|E–E ;
Vx|y;
C  12 | 25 | 500 ;
Problema: Muestre que la cadena “X = 500 + 25 * 12” es una oración válida del
lenguaje generado por esta gramática.
Gramáticas Libres de Contexto
Solución:
Leftmost derivation
E R3 V = E R8 x = E R6 x = E + E R1 x = C + E R12
x = 500 + E R4 x = 500 + E * E R1 x = 500 + C * E R11
x = 500 + 25 * E R1 x = 500 + 25 * C R10 x = 500 + 25 * 12
Rightmost derivation
E R3 V = E R6 V = E + E R4 V = E + E * E R1 V = E + E * C
R12 V =E + E * 12 R1 V =E + C * 12 R11 V =E + 25 * 12 R1
R1 V =E + 25 * 12 R1 V = C + 25 * 12 R10 V = 500 + 25 * 12
R8 x = 500 + 25 * 12
Gramáticas Libres de Contexto
Problemas
1.
Sea G la gramática siguiente:
a.
b.
c.
d.
2.
S SAB|
AaA|a
BbB|
Obtenga la derivación de más a la izquierda de abbaab.
Muestre dos derivaciones de aa.
Construya el árbol de derivación del inciso (a).
Obtenga una expresión regular que defina L(G).
Defina el lenguaje generado por la gramática:
SaSbb|A
AcA|c
3.
4.
Construya una gramática sobre {a, b} cuyo lenguaje sea {ambian | i = n + m }
Construya una gramática sobre {a, b, c} cuyo lenguaje sea
{anbmc2n+m | n, m > 0}
Análisis Sintáctico
Cada lenguaje de programación posee reglas que prescriben la estructura
sintáctica de los programas bien-formados.
La sintaxis de las construcciones de programas puede ser descrita
utilizando una gramática libre de contexto CFG.
Análisis Sintáctico
Ejemplo:
<stat>  <if_stat> | <while_stat> | <repeat_st> |
<proc_call> | <assignment> ;
<if_stat  if <cond> then <stat_seq> else <stat_seq> |
if <cond> then <stat_seq> ;
<while_Stat>  while <cond> do <stat_seq> end ;
<repeat_stat>  repeat <stat_seq> until <cond> ;
<proc_call  <name> “(” <expr_seq> “)” ;
<assignment>  <name> = <exp>
<stat_seq>  <stat> | <stat_seq> “;” <stat>
<expr_seq>  <expr> | <expr_seq> “,” <expr>
Analizador Sintáctico
• Eliminación de la recursividad izquierda
Una gramática tiene recursividad izquierda si contiene un no-terminal A tal
que existe una derivación A+A para alguna cadena .
– Un parser del tipo top-down no puede manejar la recursividad a a la
izquierda.
Ej. Elimine la recursividad izquierda de la siguiente gramática:
A A|
Solución: A  A´ ; A´ A´| 
– Problema: elimine la recursividad izq. de la siguiente gramática:
EE+T | T
TT*F|F
F  ( E ) | id
Analizador Sintáctico
• Solución
E  T E´ ;
T  F T´
E´ + T E´ |  ;
T´ * F T´ | 
;
F  ( E ) | id
Formas Normales
• Una forma normal se define imponiendo restricciones a la forma
permitida de las reglas de una gramática.
• Las gramáticas en forma normal, generan la totalidad de lenguajes
libres de contexto.
• Dos formas normales importantes son:
– La forma normal de Chomsky
– La forma normal de Greibach
• Las transformaciones mostradas a continuación convierten cualquier
gramática a una gramática equivalente en forma normalizada.
• Las restricciones impuestas para las reglas de reescritura, aseguran
que la gramática tenga ciertas propiedades importantes: como la
garantía de que el algoritmo de reconocimiento sintáctico terminará.
Formas Normales
Forma Normal de Chomsky
Una gramática libre de contexto G = < V, , S, P> esta en la Forma
Normal de Chomsky si cada regla tiene alguna de las siguientes
formas:
a. A  BC
b. A  a
c. S  
En donde B, C  V – {S}
Teorema. Toda gramática libre de contexto puede ser
convertida a una gramática equivalente en la forma
normal de Chomsky.
Formas Normales
Forma Normal de Greibach
Una gramática libre de contexto G = < V, , S, P> esta en la Forma
Normal de Greibach si cada regla tiene alguna de las siguientes
formas:
a. A  a A1A2…An
b. A  a
c. S  
En donde a   y Ai  V – {S} para i = 1,2, … n
Teorema. Toda gramática libre de contexto puede ser
convertida a una gramática equivalente en la forma
normal de Greibach.
Formas Normales
Transformaciones básicas
1. El símbolo inicial no podrá ser usado en una
secuencia recursiva. Ej. S  a S
2. Eliminación de la palabra vacía.
– Una variable que deriva una cadena nula, es llamada
nulificable.
– Una gramática sin variables nulificables es llamada una
gramática sin-contracciones, ya que la aplicación de una
regla nunca hará decrecer la longitud de la forma sentencial.
– Sólo el símbolo inicial puede reescribirse como la palabra
vacía .
Formas Normales
Ejemplo:
(a) Transforme la gramática mostrada a continuación en una
gramática sin variables nulificables (excepto probablemente S).
G: S  A C A
AaAa|B|C
BbB|b
CcC|
Formas Normales
3. Eliminación de reglas encadenadas
–
–
Una regla de la forma A B, tan solo renombra variables.
Reglas de esta forma son llamadas reglas encadenadas. Su
eliminación simplifica la gramática.
La eliminación de las reglas encadenadas incrementa el
número de reglas en la gramática pero reduce la longitud de las
derivaciones.
Ejemplo:
AaA|a|B
BbB|b|C
CcC|c
Formas Normales
4. Símbolos Inútiles
– En una gramática, cada variable debe contribuir a la generación
de las oraciones del lenguaje.
– La construcción de gramáticas grandes básicamente haciendo
modificaciones a otras gramáticas ya existentes, genera
invariablemente símbolos inútiles.
Def. Sea G una gramática libre de contexto.
Un símbolo x  (V  ) es útil si existe una derivación:
S * u x v * w
En donde u, v  ( V   )* y w  *.
Un símbolo que no es útil, es llamado inútil.
Formas Normales
Ejemplo:
Sea G la gramática con las siguientes reglas:
S  AC | BS | B
D  aD | BD | C
A  aA | aF
E  aA | BSA
B  CF | b
F  bB | b
C  cC | D
a). Defina el lenguaje generado por la gramática L(G).
b). Elimine los símbolos inútiles.
Ejercicios
1.
Sea G la gramática:
S  aABC | a
A  aA | a
B  bcB | bc
C  cC | c
Transformarla a Forma Normal de Chomsky y a Forma Normal de Greibach..
2. Sea la Gramática AE: V={S, A, T}, ={b,+, (, )}
P: S  A
AT
AA+T
Tb
T  (A)
Transformar a la Forma Normal de Chomsky.
Ejercicios (cont.)
3. Construya las formas normales de Chomsky y Greibach
para la gramática:
S  SaB | aB
B  bB | 
Diseñando un Gramática
• Las gramáticas pueden describir la mayor parte, pero no toda la
sintaxis de un lenguaje de programación.
• Una porción limitada del análisis sintáctico es desarrollada por el
analizador lexicográfico que genera secuencias de átomos (tokens).
• Algunas restricciones sobre la entrada, no se pueden analizar
utilizando una gramática libre de contexto. Por ejemplo las
siguientes:
– Todos los identificadores deben ser declarados al inicio del programa.
– El número de parámetros de una subrutina o procedimiento debe
coincidir en número y tipo con los argumentos con los que se invoca el
mismo.
Analizador Sintáctico
El rol del analizador sintáctico:
token
lexical
analyser
parser
Get next
token
Tabla de
Símbolos
parse
tree
rest of
front end
Analizador Sintáctico
• Métodos de parsing
– Top-down parsers: Construyen el árbol sintáctico (parse tree) a
partir de la raiz.
– Bottom-up parsers: Construyen el árbol sintáctico a partir de las
hojas.
Normalmente ambos tipos de parser recorren la entrada de izquierda
a derecha barriendo un símbolo a la vez.
Descargar

Análisis Sintáctico