Gramáticas independientes del contexto Unidad 2

Conceptos generales 

Chomsky: G3⊂G2⊂G1⊂G

Definición

ΣN - un conjunto de símbolos no terminales (variables)

ΣT - un conjunto de símbolos terminales

P - un conjunto de reglas de producción

S∈ΣN un símbolo no terminal de ΣN

La cuaterna (ΣT, ΣN , S, P) se llama gramática independiente del contexto (Gramáticas de tipo 2, según la clasificación de Chomsky) si todas las reglas de producción de P tienen la forma:

A::= β, siendo A∈ΣN y β∈ Σ

Todo lenguaje generado por una GIC G (se denota por L(G)) se llama Lenguaje independiente del contexto.

Ejemplos:

G1={{a,b},{S},S,{S::=aSb | ab}}

G2={{a,b},{S},S,{S::=aSbb | abb}}

G3={{a,b},{S},S,{S::=a | bS }}

G4={{a,b},{S},S,{S::=aSb | SS | λ}}

G5={{a,b},{S},S,{S::=aS | Sb | a | b}}

 Motivación

Representación de la sintaxis de lenguajes de programación; descripción de la estructura de lenguajes de marcado (DTD en XML, …); generadores de compiladores (Yacc, …), etc.

Justificación

Sea la siguiente GIC G definida por sus reglas:

S::= Aa | B | D

B ::= b

A ::= A | Aa | bA | B | cE

C ::= abd

E ::= λ

D::=Db

En G se pueden observar las siguientes redundancias:

1. La regla A::=A es innecesaria.
2. Del símbolo D no se pueden derivar sentencias (símbolo superfluo).
3. Del símbolo C se puede derivar la sentencia abd, pero no es accesible desde S (símbolo inaccesible).
4. Las reglas E ::= λ y A ::= cE podrían ser reemplazadas por la regla A ::= c (regla no generadora).
5. El símbolo B podría ser eliminado, y la regla B::= b podría ser reemplazada por las reglas S ::= b y A ::= b (regla de redenominación).

Si eliminamos estas redundancias en la gramática G, obtendremos una GIC G’ tal que L(G) = L(G’):

S::= Aa | b

A ::= Aa | bA | b | c

Reglas innecesarias

Una regla de la forma A::=A es innecesaria y puede ser eliminada.

Ejemplo A::=A

Símbolos superfluos (o no generadores)

Un símbolo superfluo es un símbolo no terminal A tal que no existe una derivación A → * w, donde w∈ΣT * .

Ejemplo D (D::=Db)

Algoritmo de eliminación de símbolos superfluos

Sea la GIC G = (ΣT , ΣN , S, P). Transformaremos G en G′ = (ΣT , Σ’ N , S, P’) de forma que L(G) = L(G’). Construimos iterativamente el nuevo Σ’ N como sigue:

Inicializar Σ’ N a ∅

 Repetir

Añadir a Σ’ N todo no terminal A para el cual existe

A ::= w ∈ P y w∈(ΣT ∪ Σ’ N)*.

Hasta que no se puedan añadir más símbolos a Σ’ N.

1. Asignar a P’ todas las reglas p∈P cuyos símbolos pertenezcan a ΣT ∪ Σ’ N
2. Si S∉Σ’ N, añadir S a Σ’ N

Símbolos inaccesibles

Un símbolo X (terminal o no terminal) será inaccesible si no existe ninguna derivación S →* αXβ tal que α, β ∈(ΣT ∪ ΣN)*.

 

Ejemplo: C (C::=abd)

Algoritmo de eliminación de símbolos inaccesibles

Sea la GIC G = (ΣT , ΣN , S, P). Transformaremos G en G′ = (Σ‘ T , Σ’ N , S, P’) de forma que L(G) = L(G’). Construimos iterativamente los nuevos Σ‘ T, Σ’ N y P’ como sigue :

1.  Inicializar Σ’ N de forma que contenga el axioma S, e inicializar P’ y Σ‘ T a ∅.
2. Repetir