GRAMÁTICAS LIBRES DE CONTEXTO

Definición

Convenciones

Derivaciones

Definición Lenguaje Libre de Contexto

Ejemplo

Tipos de derivación

Ejercicio• Sea G1 = < Vn1, Vt1,P1, exp> una GLC. Demuestre que

G1 es ambigua.

Solución

• Podemos construir más de una derivación por la izq para “5-8*2”.

Ambigüedad• La ambigüedad significa que una expresión del lenguaje

puede tener más de una interpretación, lo cual no esta permitido.

• En el ejemplo, la ambigüedad está asociada con los operadores “*” y “-”, por lo que se debe establecer su asociatividad y precedencia para evitar la ambigüedad.

Ejercicios

Ejercicios• Construya una GLC que genere cada uno de los

siguientes lenguajes:1.Listas de dígitos separados por comas.2.Cadenas que representen números en punto flotante al

estilo de Pascal o C.3.Identificadores (i.e. secuencias de letras ó dígitos que

incian siempre por una letra) en lenguaje tipo C o Pascal.4.Palabras palíndromas (que se leen de igual forma en

ambos sentidos) sobre el alfabeto {a,b}.5.El conjunto de todas las palabras sobre el alfabeto {a,b}

que tienen 2 veces más a’s que b’s.6.Números impares en binario.

Ejercicio• Obtener la gramática que representa al lenguaje {anb2n|

n>=0}

Solución• S→aSbb | abb | Ɛ