Gramaticas Independientes del Contexto, ejemplos y ejercicios
Summary: 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:
|
Ejemplo 6: Hacer una GIC que genere un número binario
Exp -> Exp bin | bin
bin -> 0 | 1
Ó con una sola producción:
Exp -> Exp 0 | Exp 1 | 0 | 1
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
Comments, questions, feedback, criticisms?
Send feedback
- E-mail the author of the module, Gramaticas Independientes del Contexto, ejemplos y ejercicios
Footer
More about this content: Metadata | Version History
This work is licensed by Carlos Arturo Cortés Fuentes under a Creative Commons Attribution License (CC-BY 2.0).
Last edited by Carlos Arturo Cortés Fuentes on May 29, 2008 10:12 am GMT-5.