Gramaticas Independientes del Contexto, ejemplos y ejercicios 1.1 2008/05/27 16:33:54.828 GMT-5 2008/05/29 10:12:27.297 GMT-5 Carlos Arturo Cortés Fuentes carcorfu@yahoo.com Carlos Arturo Cortés Fuentes carcorfu@yahoo.com Backus-Naur form BNF Compiladores GIC gramaticas gramaticas independientes del contexto gramaticas libres del contexto Las gramáticas libres de contexto permiten describir la mayoría de los lenguajes de programación, de hecho, la síntaxis de la mayoría de lenguajes de programación está definida mediante gramáticas libres de contexto. Por otro lado, estas gramáticas son suficientemente simples como para permitir el diseño de eficientes algoritmos de análisis sintáctico que, para una cadena de caracteres dada determinen como puede ser generada desde la gramática Gramáticas Independientes del Contexto, ejemplos y ejercicios Una Gramática independientes del contexto (GIC) es una gramática formal en la que cada regla de producción es de la forma: Exp → x Donde Exp es un símbolo no terminal y x es una cadena de terminales y/o no terminales. El término independiente del contexto se refiere al hecho de que el no terminal Exp puede siempre ser sustituido por x sin tener en cuenta el contexto en el que ocurra. Un lenguaje formal es independiente de contexto si hay una gramática libre de contexto que lo genera, este tipo de gramática fue creada por Backus-Naur y se utiliza para describir la mayoría de los lenguajes de programación. Una GIC está compuesta por 4 elementos: 1. Símbolos terminales (elementos que no generan nada) 2. No terminales (elementos del lado izquierdo de una producción, antes de la flecha "->") 3. Producciones (sentencias que se escriben en la gramática) 4. Símbolo inicial (primer elemento de la gramática) Ejemplo 1: Teniendo un lenguaje que genera expresiones de tipo: 9 + 5 – 2 Para determinar si una GIC esta bien escrita se utilizan los arboles de analisis sintáctico , así: Producciones: lista -> lista + digito lista -> lista - digito lista -> digito digito -> 0|1|2|3|4|5|6|7|8|9 Arbol de analisis sintactico:

La gramática es correcta siempre y cuando el símbolo inicial este al lado izquierdo de las producciones y sea la raíz del árbol. Ejemplo 2: Hacer una gramática que genere el número 5 Símbolo inicial (no terminal): Exp y Símbolo terminal: 5 Exp -> 5 Ejemplo 3: Hacer una gramática que genere un dígito. Exp -> 0|1|2|3|4|5|6|7|8|9 Arbol de analisis sintactico:Exp | 3 Ejemplo 4: Hacer una gramática que repita muchas veces el número 5 Exp -> Exp 5|5 Prueba con el número 555

Ejemplo 5: Gramática que genera muchos dígitos Exp -> Exp dig | dig dig -> 0|1|2|3|4|…|9 Prueba:

Aunque esta producción puede generar expresiones como 0000, para evitar errores como este: dig -> 1 Exp | 1 Exp -> Exp 0 | Exp 1 | 0 | 1 Nota 1: El símbolo inicial siempre debe estar en la primera producción de la gramática. Nota 2: Expresiones de tipo, Exp -> Exp 0 | 1, genera potencias de 10, ejemplo

Ejemplo 7: Hacer una gramática que genere un conjunto de 1 seguido de un conjunto de 0, donde el número 1 debe ser impar y el número de 0 debe ser par. Exp -> unos ceros ceros -> ceros 00 | 00 unos -> unos 11 | 1

Ejemplo 8: ¿Cuál es el lenguaje de la siguiente producción? Pal -> Pal letras | letras Letras -> a | b | c | d | e | f | g | … | z R/ Es una GIC que genera palabras escritas en minúsculas. Ejemplo 9: Hacer una GIC que genere una frase cuya letra inicial de cada palabra sea mayúscula. Frase -> Frase Exp pal | pal Exp -> “ “ Pal -> may | pal min min -> a | b | c | d | … | z may -> A | B | C | D | … | Z

Ejercicios 1. Hacer una gramática independiente del contexto (G.I.C), que genere nombres de persona, mínimo un nombre y un apellido, máximo dos nombres y dos apellidos. Cada nombre y apellido debe comenzar por mayúscula. Nota: Se tiene en cuenta que Є=vacio; no se aceptan apellidos compuestos. nombre → nom nom2 esp nom nom2 nom2 → esp nom │Є nom → nom min │may may → A│B│C│D│…│Z min → a│b│c│d│…│z esp → “ “ Árbol de análisis sintáctico

2. Hacer una gramática independiente del contexto (G.I.C), que genere frases cuyas palabras empiecen en una vocal mayúscula y terminen en una consonante minúscula. En medio de la vocal mayúscula y la consonante pueden haber letras minúsculas. frase → frase esp pal2│pal2 esp → “ “ pal2 → pal1 conmin pal1 → pal2 min│vocmay vocmay → A│E│I│O│U min → conmin│vocmin conmin → b│c│d│f│g│…│z vocnim → a│e│i│o│u 3. Hacer una gramática independiente del contexto (G.I.C), que genere la sentencia condicional if con las siguientes restricciones: Siempre se va a comparar una variable con un número entero o una variable con otra variable. Los operadores relacionales son: <│>│≤│≥│==│!= Las variables deben empezar en una letra y después de esa letra pueden haber cualquier cantidad de números o letras. Los números solamente van a ser enteros de cualquier cantidad de dígitos. Un número no debe empezar en cero, pero puede ser cero. Se pueden utilizar los operadores lógicos && (and) y II (or). Solamente se van a utilizar los paréntesis después del if y al final del if. Solución 1 if2 → if1 term if1 → if cond5│inicio cond5 → cond5 oprlog cond4 cond4 → cond1│ cond2│ cond3 cond3 → var opr var cond2 → var opr cero cond1 → var opr num2 oprlog → '&&'│'II' opr → <│>│≤│≥│==│!= var → var todo│letras todo → A│B│C│D│...│Z│0│1│2│...│9 letras → A│B│C│D│...│Z num2 → num2 num1│num3 num1 → num3│cero num3 → 1│2│3│4│5│...│9 cero → 0 inicio → if ( term → ) Solución 2 si → if (exp) exp → comp│comp oplog exp comp → var oprel num│var oprel var oprel → <│>│≤│≥│==│!= oplog → '&&'│'II' var → var numero│var letra│letra letra → a│b│c│d│...│z│A│B│C│D│...│Z numero → num│0 num → num dig│num 0│dig dig → 1│2│3│4│5│6│7│8│9