Gramaticas

CIENCIAS DE LA COMPUTACION I

2008

GRAMATICAS LIBRES DEL CONTEXTO
Estas gramáticas, conocidas también como gramáticas de tipo 2 o gramáticas independientes del contexto, son las que generan los lenguajes libres o independientes del contexto. Los lenguajes libres del contexto son aquellos que pueden ser reconocidos por un autómata de pila determinístico o no determinístico. Como todagramática se definen mediante una cuadrupla G = (N, T, P, S), siendo - N es un conjunto finito de símbolos no terminales - T es un conjunto finito de símbolos terminales N∩T=∅ - P es un conjunto finito de producciones - S es el símbolo distinguido o axioma S ∉ (N ∪ T) En una gramática libre del contexto, cada producción de P tiene la forma A ∈ N ∪ {S} A→ω ω ∈ (N ∪ T)* - {ε} Es decir, que en el ladoizquierdo de una producción pueden aparecer el símbolo distinguido o un símbolo no terminal y en el lado derecho de una producción cualquier cadena de símbolos terminales y/o no terminales de longitud mayor o igual que 1. La gramática puede contener también la producción S → ε si el lenguaje que se quiere generar contiene la cadena vacía. Los ejemplos mostrados a continuación corresponden a loslenguajes libres del contexto que fueron introducidos en los ejemplos 1, 2 y 3 del apunte de autómatas de pila. Ejemplo 1: La siguiente gramática genera las cadenas del lenguaje L1 = {wcwR / w ∈ {a, b}* } G1 = ({A}, {a, b, c}, P1, S1), y P1 contiene las siguientes producciones S1 → A A → aAa A → bAb A →c Ejemplo 2: La siguiente gramática genera las cadenas del lenguaje L2 = {0i 1i+k 2k 3n+1 / i, k, n ≥ 0} Casos Cadenas de L2 si n, i, k > 0 0i 1i+k 2k 3n+1 si n=0 y i, k > 0 0i 1i+k 2k 3 si i=0 y n, k >0 1k 2k 3n+1 si k=0 y n, i >0 0i 1i 3n+1 si n, i=0 y k >0 1k 2 k 3 si n, k=0 y i >0 0i 1 i 3 si i, k =0 y n >0 3n+1 si n,i,k=0 3 G2 = ({A, B, C}, {0, 1, 2, 3}, P2, S2), y P2 contiene las producciones

CIENCIAS DE LA COMPUTACION I S2 → ABC S2 → AC S2 → BC S2 → C A → 0A1 A → 01 B → 1B2 B → 12 C → 3CC→ 3

2008

Ejemplo 3: La siguiente gramática genera las cadenas del lenguaje L3 = {hn gj e2n d3i / i, j, n ≥ 0 } Casos Cadenas de L3 si n, i, j > 0 hn gj e2n d3i si n=0 y i, j > 0 gj d3i si i=0 y n, j >0 hn gj e2n si j=0 y n, i >0 hn e2n d3i si n, i=0 y j >0 gj si n, j=0 y i >0 d3i si i, j =0 y n >0 hne2n si n,i,j=0 ε G3 = ({A, B, C}, {h, g, d, e}, P3, S3), y P3 contiene las producciones A→B S3 → ε S3 → AC B → gB B →g S3 → A S3 → C C → dddC C → ddd A → hAee A → hee

Ejemplo 4: La siguiente gramática genera las cadenas de L4 = {am bp cp+m / m, p ≥ 1} ∪ {ai b2i / i ≥ 1 } G4 = ({A, B, C}, {a, b, c}, P4, S4), y P4 contiene las producciones S4 → A S4 → C A → aAc A → aBc B → bBc B → bc C → aCbb C → abb BNF Las gramáticas libres del contexto se escriben, frecuentemente, utilizando unanotación conocida como BNF (Backus-Naur Form). BNF es la técnica más común para definir la sintaxis de los lenguajes de programación. En esta notación se deben seguir las siguientes convenciones: - los no terminales se escriben entre paréntesis angulares < > - los terminales se representan con cadenas de caracteres sin paréntesis angulares

CIENCIAS DE LA COMPUTACION I -

2008

el ladoizquierdo de cada regla debe tener únicamente un no terminal (ya que es una gramática libre del contexto) el símbolo ::=, que se lee “se define como” o “se reescribe como”, se utiliza en lugar de → varias producciones del tipo ::= ::= . . . ::= se pueden escribir como ::=   ... 

Ejemplo 5: La siguiente es una definición BNF del lenguaje que consiste de cadenas de paréntesis anidados: :: = ::= ( )  ( ) Por ejemplo las cadenas ( ) ( ( ) ) y ( ) ( ) ( ) son cadenas válidas. En cambio las cadenas ( ( ) y ( ) ) ) no pertenecen al lenguaje. Arbol de derivación Un árbol de derivación permite mostrar gráficamente cómo se puede derivar cualquier cadena de un lenguaje a partir del símbolo distinguido de una gramática que genera ese lenguaje. Un árbol es un conjunto de puntos,...