Def. Una gramática libre de contexto (context free grammar) es un cuadruplo G =, en donde, V n...

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 R3. S 1 R5. S 1S1 R2. S 0 R4. S 0S0

b). {ai bi | i0} R1. S 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.


• Ejemplo:Jack was given a book by Hemingway


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


Problemas1. Sea G la gramática siguiente:

S S A B | A a A | a

B b B | a. Obtenga la derivación de más a la izquierda de abbaab.b. Muestre dos derivaciones de aa.c. Construya el árbol de derivación del inciso (a).d. Obtenga una expresión regular que defina L(G).

2. Defina el lenguaje generado por la gramática: S a S b b | A A c A | c

3. Construya una gramática sobre {a, b} cuyo lenguaje sea {ambian | i = n + m }4. Construya una gramática sobre {a, b, c} cuyo lenguaje sea

{anbmc2n+m | n, m > 0}

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

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>

• Eliminación de la recursividad izquierdaUna 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ónE T E´ ; T F T´ ; F ( E ) | id

E´ + T E´ | ; T´ * F T´ |

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 ChomskyUna 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 BCb. 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 GreibachUna 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ásicas1. El símbolo inicial no podrá ser usado en una

secuencia recursiva. Ej. S a S2. 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 a A a | B | C

B b B | b

C c C |

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 a A | a | B

B b B | b | C

C c C | 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 * wEn donde u, v ( V )* y w *. Un símbolo que no es útil, es llamado inútil.

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.


El rol del analizador sintáctico:

parserlexicalanalyser

rest of front end

Tabla de Símbolos

Get next token

token parse tree

• 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.


Def. Una gramática libre de contexto (context free grammar) es un cuadruplo G =, en donde, V n...

Documents

Transcript of Def. Una gramática libre de contexto (context free grammar) es un cuadruplo G =, en donde, V n...