Gramáticas Libres de Contexto

Sea $G$ una GLC con las siguientes definiciones:

• Regla $A$ de $G$: $A\to \alpha$.
• Handle: $x$ en $A\to x\beta$.
• Producción útil: $A\to \alpha$ es útil $⟺\Sigma \stackrel{\ast }{⟹}\phi A\psi ⟹\phi \alpha \psi \stackrel{\ast }{⟹}\omega$ con $\omega \in T^{\ast }$.
• No terminal útil: $A$ es útil $⟺$ es parte izquierda de una producción útil.
• Producción no generativa: $A\to B$.
• No terminal recursivo por izquierda: $A$ en $A\stackrel{\ast }{⟹}A\psi$.
• No terminal recursivo por derecha: $A$ en $A\stackrel{\ast }{⟹}\psi A$.
• No terminal cíclico: $A\stackrel{\ast }{⟹}A$. Es causado por producciones no generativas.

Transformaciones Gramaticales

Dos GLC $G_1$ y $G_2$ son débilmente equivalentes si $L(G_1)=L(G_2)$. $G_1$ y $G_2$ son fuertemente equivalentes si son débilmente equivalentes y para cada string terminal $\omega$ las derivaciones por izquierda mínimas de $\omega$ en $G_1$ tienen una correspondencia uno a uno con las de $G_2$. Una derivación es mínima si ninguna forma sentencial se repite en la derivación.

Sustitución

Sea $A\to \phi B\psi$ y $B\to {\beta }_1,{\beta }_2,{\beta }_3,\dots ,{\beta }_n$, la $G^{\prime }$ es obtenida por sustitución de acuerdo a:

1. $A\to \phi B\psi$ no está en $G^{\prime }$.
2. Todas las otras producciones están en $G^{\prime }$.
3. Cada $A\to \phi {\beta }_i\psi$ está en $G^{\prime }$ con $i=1,2,3,\dots ,n$.

Si ninguna producción de $G^{\prime }$ introducida por la regla 3 ha sido previamente introducida por la regla 3, $G$ y $G^{\prime }$ son fuertemente equivalentes. Se puede perder la equivalencia fuerte si se introduce por sustitución una producción duplicada.

Expansión

Sea $A\to \phi \psi$ con $\phi ,\psi \in (N\cup T{)}^{\ast }-\lambda$, se la reemplaza por una de dos opciones:

• $A\to X\psi ,X\to \phi$, o
• $A\to \phi X,X\to \psi$.

Siendo $X$ un nuevo no terminal. Se dice que se expandió la regla $A\to \phi \psi$. Siempre se mantiene la equivalencia fuerte entre $G$ y $G^{\prime }$.

Se observa que sustitución y expansión son transformaciones inversas.

Eliminación de Producciones Inútiles

Sea una producción inútil $A\to \alpha /\cancel{\exists }\Sigma \stackrel{\ast }{⟹}\phi A\psi ⟹\phi \alpha \psi \stackrel{\ast }{⟹}\omega$ con $\omega \in T^{\ast }$.

Para eliminar producciones inútiles, se puede utilizar el marcado $T$, que marca cada regla de $G$ si hay una derivación de un string terminal. Las producciones no marcadas nunca terminan, por lo que se eliminan. Pasos:

1. Sean $P_0=N_0=\varphi$ con $(i=0)$.
2. Sea $P_{i+1}=\{A\to \alpha \in P/\alpha \in (Ni\cup T{)}^{\ast }\}$ y $N_{i+1}=\{A\in N/A\to \alpha \in P_{i+1}\}$ el marcado de producciones terminables.
3. Repetir hasta que $P_i=P_{i+1}⟹P_{i+1}=P_T$ y $N_{i+1}=N_T$.

Luego se utiliza el marcado $\Sigma$, que marca cada regla ya marcada por $T$ si es alcanzable desde $\Sigma$. Si no es alcanzable, se elimina. Pasos:

1. Sea $P_T$ del marcado $T$ y $Q_1=\{\Sigma \to \alpha \in P_T\}$ con $(i=1)$.
2. Sea $Q_{i+1}=Q_i\cup \{A\to \alpha \in P_T/B\to \phi A\psi \in Q_i\}$ el marcado de producciones alcanzables.
3. Repetir hasta que $Q_i=Q_{i+1}⟹Q_{i+1}=P_{\Sigma }$.

Aseguramos que cada producción de $P$ como $A\to \alpha$ es terminable de la forma $\Sigma \stackrel{\ast }{⟹}\phi A\psi ⟹\phi \alpha \psi \stackrel{\ast }{⟹}\omega$. Así, por cada producción de $P$ de $G$ se puede decidir si es o no útil en $G$.

El test de vacío dice que para cualquier GLC $G$ es posible decidir si $L(G,A)=\varphi \forall A\in N$. En particular, si la gramática genera o no strings, $L(G)=L(G,\Sigma )=\varphi$.

Eliminación de Producciones No Generativas

Sea la producción no generativa $A\to B$, se desea eliminarla porque puede causar no terminales cíclicos. Las secuencias de pasos de derivación no generativos consecutivos de $G$ pueden ser representadas por un AEF $M(G)$ con solo transiciones lambda.

Sean $G=(N,P,T,\Sigma )$ y $M(G)=(Q,\varphi ,P^{\prime },I,F)$ con:

\begin{align} Q &= \left\{ A \,\middle/\, A \rightarrow B \text{ ó } B \rightarrow A \in P;\; A, B \in N \right\} \\ P' &= \left\{ A \xrightarrow{\lambda} B \,\middle/\, A \rightarrow B \in P \right\} \\ I &= \left\{ A \in Q \,\middle/\, \Sigma \rightarrow A \in P \ \lor \ B \rightarrow \varphi A \psi \in P \text{ con } \varphi \psi \neq \lambda \right\} \\ F &= \left\{ A \in Q \,\middle/\, A \rightarrow \beta \in P \text{ con } \beta \notin N \right\} \end{align}

$G^{\prime }=(N^{\prime },T,P^{\prime \prime },\Sigma )$ incluye un nuevo no terminal por cada secuencia de pasos no generativos en una derivación mínima. Eso en $M(G)$ es un camino sin ciclos.

$$\begin{array}{rl}{N}^{\prime }=N& \cup \left\{[X_1\dots X_n];X_1=X\in I,X_n=Y\in F,X_i\ne X_j\text{ para }i\ne j,X_1\stackrel{\lambda }{\to }\cdots \stackrel{\lambda }{\to }{X}_n\text{ en }M(G)\right\}\\ & \cup \left\{[XX]|X\in I\cap F\right\}\end{array}$$

Así:

1. Toda producción sin un símbolo de $Q$ es copiada.
2. Por cada producción generativa $A\to {\alpha }_0{B}_1\dots V_k{\alpha }_k$ con $B_i\in Q$ en $G$ surge en $G^{\prime }$ una producción $U\to {\alpha }_0{V}_1\dots V_k{\alpha }_k$ donde:

$$U\in \{\begin{array}{ll}\{A\}& \text{si }A\notin F\\ \{[X\dots Y]\mid Y=A\}& \text{si }A\in F\end{array}{V}_i\in \{\begin{array}{ll}\{B_i\}& \text{si }{B}_i\notin I\\ \{[X\dots Y]\mid X=B_i\}& \text{si }{B}_i\in I\end{array}$$

Se cumple que $G$ y $G^{\prime }$ son fuertemente equivalentes siempre.

Factorización por Izquierda

Sean $A\to \beta {\alpha }_1\wedge A\to \beta {\alpha }_k$ dos producciones con el mismo handle de una misma parte derecha. Esto provoca ambigüedad al diseñar un compilador por izquierda. Para evitarlo, se puede aplicar una factorización por izquierda:

$$\begin{array}{rl}\forall A\in N\text{ de }G:& \text{ si }A\to \beta {\alpha }_1,\dots ,A\to \beta {\alpha }_k\text{ con }k>1,\\ \text{ en }{G}^{\prime }\text{ se las cambia por}:& A\to \beta A^{\prime }\\ & A^{\prime }\to {\alpha }_1,\dots ,A^{\prime }\to {\alpha }_k\text{ con }k\ge 1\end{array}$$

Es un caso especial de expansión, por lo que $G$ y $G^{\prime }$ son fuertemente equivalentes.

Ejemplo:

$$\begin{array}{rl}G:\Sigma & \to \lambda |S\\ S& \to SS|(S)|()|[S]|[]\\ \text{ luego de la}& \text{ factorizacioˊn por izquierda resulta... }\\ G^{\prime }:\Sigma & \to \lambda |S\\ S& \to SS|(S^{\prime }|[S^{\prime \prime }\\ S^{\prime }& \to S)|)\\ S^{\prime \prime }& \to S]|]\end{array}$$

Eliminación de Producciones $\lambda$

Sea $A\to \lambda$ una producción lambda. $A$ es anulable $⟺A\stackrel{\ast }{⟹}\lambda$. Se acepta una definición no estricta de una GLC que tenga $A\to \lambda$ porque es salvable.

Identificación de no terminales anulables:

1. Sea ${\Delta }_1=\{A\in N/A\to \lambda \in P\};i=1$.
2. Sea ${\Delta }_{i+1}={\Delta }_i\cup \{A\in N/A\to \omega \in P\wedge \omega \in {\Delta }_i^{\ast }\}$.
3. Repetir hasta que ${\Delta }_i={\Delta }_{i+1}⟹{\Delta }_1=\Delta$.

Procedimiento:

$\forall A\to {\alpha }_1\dots {\alpha }_n$ de $G$ se agregan producciones $A\to {\beta }_1\dots {\beta }_n$ donde ${\beta }_i\in \{\begin{array}{ll}\{{\alpha }_i\}& \text{ si }{\alpha }_i\notin \Delta \\ \{{\alpha }_i,\lambda \}& \text{ si }{\alpha }_i\in \Delta \end{array}$. Luego, se eliminan todas las producciones $\lambda$. Si $\Sigma \in \Delta ⟹\Sigma \to \lambda \in P^{\prime }$.

$G$ y $G^{\prime }$ son fuertemente equivalentes, y toda producción $\lambda$ es salvable.

Formas Canónicas de Gramáticas

Se pueden definir formas restringidas de gramáticas libres de contexto, conocidas como formas canónicas:

• Gramáticas Bien Conformadas.
• Gramáticas en Forma Normal.
• Gramáticas en Forma Stándard.