Encontrar la GIC a partir del AP

Vista previa del material en texto

f(q, b, b) ::= {(q, λ)}
(q, aab, S) ⊢ (q, ab, Ab) ⊢ (q, b, b) ⊢ (q, λ, λ)
3. Gramática en forma normal de Greibach con restricciones:
S ::= aB|aAB;A ::= a|aA;B ::= b|bB
S → aAB → aaB → aab
Se obtiene el siguiente AP:
f(q, a, S) ::= {(q, B), (q, AB)}
f(q, a, A) ::= {(q, λ), (q, A)}
f(q, b, B) ::= {(q, λ), (q, B)}
(q, aab, S) ⊢ (q, ab, AB) ⊢ (q, b, B) ⊢ (q, λ, λ)
11.3.2 Construcción una gramática a partir de un autómata de pila
Para completar la equivalencia de autómatas de pila y gramática indepen-
dientes de contexto.
Idea: Un autómate de pila trabaja de la siguiente manera: Extraer un
śımbolo de la pila mientras lee/consume un śımbolo de entrada.
El autómata también podŕıa cambiar de estado conforme extrae śımbolos
de pila, por tanto, también hay que registrar el estado al que pasa cuando
termina de extraer un nivel de la pila.
25
El autómata de pila se encuentra en el estado p0 y lee el śımbolo de
entrada x1 y elimina el śımbolo Y1 de la pila. Esta “extracción” es el
efecto de muchos movimientos. Al final el AP entra en el estado p1.
El AP se encuentra en el estado p1 y lee el śımbolo de entrada x2
y elimina el śımbolo Y2 de la pila. Después de haber procesado estos
elementos entra en el estado p2.
Al final, el AP se encuentra en el estado pk−1 y consume el śımbolo de
entrada xk y elimina el último śımbolo Yk de la pila. El AP termina en
el estado pk.
En nuestra construcción de una gramática equivalente a un autómata de pila
utilizaremos variables de la forma [pi−1Yipi], que representan los “resultados”
de estos movimientos.
La contrucción de una gramática equivalente usa variables, cada una de las
cuales representa un “evento”.
Estos “resultados” se componen de la siguiente manera:
1. Se extrae algún śımbolo Yi de la pila.
2. Una modificación del estado de pi−1 a pi, si se reemplaza el śımbolo de
pila Yi por λ (eliminación de Yi).
Estos cinco śımbolos son una única variable, no son cinco śımbolos de la
gramática.
26
Teorema: Sea el autómata de pila APV PV = (Σ,Γ, Q, q0, S, fV ) (que acep-
ta por vaciado de pila). Para todos qi ∈ Q, S ∈ Γ: A partir de este autómata,
y la definición anterior, construimos la siguente gramática independiente de
contexto G = (ΣN ,ΣT , S, P ), donde el conjunto de variable ΣN consta de
ΣN = {S ∪ {[pXq]}|p, q ∈ Q;X ∈ Γ}:
El śımbolo especial S, que es el śımbolo inicial.
Todos los śımbolos de la forma [pXq], donde p y q son estados de Q y
X es un śımbolo de pila perteneciente a Γ.
Las producciones P de G son como sigue:
1. Para todos los estados p ∈ Q, G contiene una producción S ::= [q0Sp].
Es decir, (q0, w, S) ⊢
∗ (p, λ, λ). Produccionen que generan todas las
secuencias de carácteres w a partir del śımbolo S, y que causan que P
vaćıe su pila, empezando con la configuración inicial.
2. Supongamos que fV (q, a, X) contiene la tupla (r, Y1Y2 . . . Yk), donde
a ∈ ΣT o a = λ;X, Y1, Y2, . . . , Yk ∈ Γ; q, r ∈ Q
k puede ser cualquier número, incluido 0, en cuyo caso la tupla
seŕıa (r, λ).
Entonces, para todas las listas de estados r1, r2, . . . , rk, G contiene
la producción
[qXrk] ::= a[rY1r1][r1Y2r2] . . . [rk−1Ykrk]
Esta producción dice que una forma de extraer X de la pila y
pasar desde el estado q al estado rk consiste en leer un śımbolo de
entrada a (que puede ser λ), leer una entrada para extraer Y1 de
la pila pasando del estado r al estado r1. Luego leer otra entrada
más, que extrae Y2 de la pila y cambiar del estado r1 al estado r2,
y aśı sucesivamente.
(sin demostración)
27
Ejemplo: Dado el autómata de pila que acepta por vaciado de pila:
Descripción formal de APV PV = ({a, b}, {A, S}, {q}, q, S, fV )
siendo fV :
fV (q, a, S) = {(q, SA), (q, A)}
fV (q, b, A) = {(q, λ)}
Ejemplo: (q, aabb, S) ⊢ (q, abb, SA) ⊢ (q, bb, AA) ⊢ (q, b, A) ⊢ (q, λ, λ)
Construir una gramática G a partir de APV PV :
⇒ G = ({a, b},ΣN , S, P ),ΣN = {S, [qSq], [qAq]}
(Regla 1: S ::= [q0Sp], ∀p ∈ Q))
S ::= [qSq]
(Regla 2:
fV (q, a, X) = {(r, Y1Y2 . . . Yk)} → [qXrk] ::= a[rY1r1][r1Y2r2] . . . [rk−1Ykrk])
1. fV (q, a, S) = {(q, A)} → [qSx] ::= a[qAx], con x ∈ Q
⇒ [qSq] ::= a[qAq]
2. fV (q, a, S) = {(q, SA)} → [qSx] ::= a[qSy][yAx], con x, y ∈ Q
⇒ [qSq] ::= a[qSq][qAq]
3. fV (q, b, A) = {(q, λ)} → [qAx] ::= b[qλx], con x ∈ Q
⇒ [qAq] ::= b[qλq] = b
S ⇒ [qSq]⇒ a[qSq][qAq]⇒ aa[qAq][qAq] ⇒ aab[qAq] ⇒ aabb
S ⇒ [qSq]⇒ a[qSq][qAq]⇒ a[qSq]b ⇒ aa[qAq]b ⇒ aabb
28
Usamos otros śımbolos y simplificamos:
[qSq]=̂S1, [qAq]=̂A
⇒ G = ({a, b}, {S, S1, A}, S, P )
P : (S ::= S1, S1 ::= aA, S1 ::= aS1A, A ::= b)
S ⇒ S1 ⇒ aS1A ⇒ aaAA ⇒ aabA ⇒ aabb
S ⇒ S1 ⇒ aS1A ⇒ aS1b ⇒ aaAb ⇒ aabb
Ejemplo: AP PV = ({0, 1}, {X, S}, {p, q}, q, S, fV )
siendo fV :
1. fV (q, 1, S) = {(q, XS)}
2. fV (q, 1, X) = {(q, XX)}
3. fV (q, 0, X) = {(p, X)}
4. fV (q, λ, X) = {(q, λ)}
5. fV (p, 1, X) = {(p, λ)}
6. fV (p, 0, S) = {(q, S)}
Construir una gramática G a partir de APV PV :
G = (ΣT ,ΣN , S, P ); ΣT = {0, 1};
ΣN = {S, [qXq], [qSq], [pXp], [pSp], [pXq], [pSq], [qXp], [qSp]}
siendo P :
(Regla 1: S → [q0Sp], ∀p ∈ Q))
S ::= [qSp]
S ::= [qSq]
(Regla 2:
fV (q, a, X) = {(r, Y1Y2 . . . Yk)} → [qXrk] ::= a[rY1r1][r1Y2r2] . . . [rk−1Ykrk])
29
1. fV (q, 1, S) = {(q, XS)} → [qSx] ::= 1[qXy][ySx], ∀x, y ∈ Q
[qSq] ::= 1[qXq][qSq]
[qSq] ::= 1[qXp][pSq]
[qSp] ::= 1[qXq][qSp]
[qSp] ::= 1[qXp][pSp]
2. fV (q, 1, X) = {(q, XX)} → [qXx] ::= 1[qXy][yXx], ∀x, y ∈ Q
[qXq] ::= 1[qXq][qXq]
[qXq] ::= 1[qXp][pXq]
[qXp] ::= 1[qXq][qXp]
[qXp] ::= 1[qXp][pXp]
3. fV (q, 0, X) = {(p, X)} → [qXx] ::= 0[qXx], ∀x ∈ Q
[qXq] ::= 0[qXq]
[qXp] ::= 0[qXp]
4. fV (q, λ, X) = {(q, λ)} → [qXx] ::= λ[qλx], ∀x ∈ Q
[qXq] ::= λ[qλq] = λ
[qXp] ::= λ[qλp] ⇐ No existe
5. fV (p, 1, X) = {(p, λ)} → [pXx] ::= 1[pλx], ∀x ∈ Q
[pXp] ::= 1[pλp] = λ
[pXq] ::= 1[pλq] ⇐ No existe
6. fV (p, 0, S) = {(q, S)} → [pSx] ::= 0[qSx], ∀x ∈ Q
[pSp] ::= 0[qSp]
[pSq] ::= 0[qSq]
11.4 Autómata de pila determinista
Importante para la práctica: Los analizadores sintácticos se comportan
como AP deterministas.
Define los tipos de construcciones, que se pueden utilizar en lenguajes
de programación.
30