Formas Normais

Gramáticas Adaptadas para Análise Sintática por Pesquisa Geral.

Introdução

A análise sintática é representada como um problema de pesquisa em grafos orientados que, em geral, pode ser resolvido por quatro estratégias diferentes: (ascendente ou descendente) x (largura ou profundidade). Nenhuma destas estratégias gerais é eficiente.

Nesta secção é apresentado um processo (a normalização de uma gramática) que, numa sequência de passos, transforma numa gramática noutra, equivalente, e adaptada (tanto quanto possível) aos algoritmos de pesquisa: uma forma normal.

Conteúdo

O bom funcionamento (mínimo número de passos) da pesquisa no grafo de uma GIC depende da própria gramática.

Problemas como:

• Pesquisas infinitas quando a palavra não é derivada pela gramática.
• Exploração repetida de ramos quando a gramática é ambígua.

reduzem significativamente o desempenho da pesquisa.

Em certos caso é possível transformar a gramática dada noutra equivalente mas que “favorece” a pesquisa, reduzindo o número de ramificações, desambiguando, e/ou detetando “cedo” se a palavra não é gerada pela gramática.

Esta secção descreve um processo algorítmico de transformação de gramáticas. No fim a gramática que se obtém proporciona pesquisas gerais mais eficientes.

Todo este processo vai ser ilustrado com um exemplo de uma GIC (especialmente desenhada) para ilustrar a aplicação de cada passo:

$$ \begin{aligned} G^0 =& \del{\set{L, M, N, O}, \set{a, b, c, d}, \ldots, L} \cr &\begin{aligned} L &\to Mb \alt aLb \alt \nil \cr M &\to Lb \alt MLN \alt \nil \cr N &\to NaN \alt NbO \cr O &\to cO \alt \nil \end{aligned} \end{aligned} $$

1. Símbolo Inicial Não Recursivo

A recursividade é a “vantagem” das GIC sobre as ER, mas é também, uma fonte de dificuldades. Embora não seja desejável, nem sequer possível, remover completamente a recursividade das produções de uma GIC esta pode ser, em certos casos, controlada.

Símbolo Inicial Não Recursivo. Seja $G = \del{V, \Sigma, P, S}$ uma GIC. Existe uma GIC $G’ = \del{V’, \Sigma, P’, S’}$ equivalente a $G$ e onde o símbolo inicial não é recursivo.

Porque:

• Se o símbolo inicial de $G$ não for recursivo então $G’ = G$.
• Se o símbolo inicial de $G$ for recursivo então, fazendo $S’$ uma variável nova:

$$ G’ = \del{V \cup \set{S’}, \Sigma, P \cup \set{S’ \to S}, S’}. $$

Exemplo. Em $G^0$ o símbolo inicial é recursivo porque $L \to aLb$ é uma produção de $G^0$. Portanto esta gramática é transformada em

$$ \begin{aligned} G^1 =& \del{\set{\alert{L’}, L, M, N, O}, \set{a, b, c, d}, \ldots, \alert{L’}} \cr & \begin{aligned} \alert{L’} &\alert{\to L} \cr L &\to Mb \alt aLb \alt \nil \cr M &\to Lb \alt MLN \alt \nil \cr N &\to NaN \alt NbO \cr O &\to cO \alt \nil \end{aligned} \end{aligned} $$

Em $G^1$ o símbolo inicial já não é recursivo. Além disso, $L\at{G^0} = L\at{G^1}$.

2. Eliminação de Produções Vazias

Antes de tratar do segundo passo na normalização de uma gramática é necessário definir alguns conceitos e técnicas.

Quase todas as produções “aumentam” o tamanho da palavra. Por exemplo $A \to bB$ faz com que $aAa$ passe para $abBa$, isto é de comprimento três para quatro. E esta é uma propriedade desejável pois permite cortar “filhos demasiado grandes” durante a pesquisa.

Há duas exceções de nota: as produções vazias $A \to \nil$ e as produções unitárias $A \to B$. Formalmente:

Produções Vazias. Produções Unitárias. Gramática Contraível. Seja $G = \del{V, \Sigma, P, S}$ uma GIC.

• Uma produção vazia tem a forma $A \to \nil$.
• Uma produção unitária tem a forma $A \to B$.
• O conjunto dos geradores da palavra vazia é $$\Lambda = \set{A \in V \st A \ider \nil}.$$
• Numa gramática não contraível não existem geradores da palavra vazia. Isto é $\Lambda = \empty$.
• Numa gramática essencialmente não contraível o único gerador de vazio é o símbolo inicial. Isto é $\Lambda = \set{S}$.

O interesse das gramáticas essencialmente não contraíveis é que:

Numa gramática essencialmente não contraível os passos intermédios de uma derivação só podem diminuir de tamanho por aplicação de $S \to \nil$.

Não é possível, nem desejável, descartar completamente os geradores de vazio. Por exemplo, se $\nil \in L\at{G}$ então em qualquer gramática equivalente a $G$ tem de existir pelo menos uma produção vazia. Neste caso, o melhor que se pode fazer é “concentrar” todas as produções vazias em $S \to \nil$.

A transformação de uma gramática noutra equivalente envolve a introdução de novas produções e a substituição de uma produção por outras, de forma a manter a linguagem gerada.

Introdução de Produções. Substituição de Produções. Seja $G = \del{V, \Sigma, P, S}$ uma CIG.

• Se $A \ider u$ então $G’ = \del{V, \Sigma, P \cup \set{A \to u}, S}$ é equivalente a $G$.
• Se $A \to uBv \in P$ e $B \to w_1 \alt w_2 \alt \cdots \alt w_n$ são todas as produções de $B$ então a gramática $G’ = \del{V, \Sigma, P’, S}$ em que $$P’ = P \setminus \set{A \to uBv} \cup \set {A \to uw_1v \alt uw_2v \alt \cdots \alt uw_n v}$$ é equivalente a $G$.

Intuitivamente, estas duas regras permitem “saltar” passos intermédios numa derivação.

O primeiro passo para retirar as produções que reduzem o comprimento das palavras trata das produções vazias.

Eliminação de Produções Vazias. Sejam $G = \del{V, \Sigma, P, S}$ uma GIC em que o símbolo inicial não é recursivo. e $G’ = \del{V, \Sigma, P’, S}$ em que as produções são, em conjunto:

• As produções de $P$ que não são produções da palavra vazia.
• A produção $S \to \nil$ se $\nil \in L\at{G}$.
• Todas as produções que se obtêm eliminando um ou mais símbolos de $\Lambda$ do corpo $w$ de cada produção $A \to w$, desde que o resultado, $w’$, tenha pelo menos um símbolo.

Então $G’$ é equivalente a $G$ e essencialmente não contraível.

Exemplo. Na gramática $G^1$ o símbolo inicial não é recursivo. Além disso, os seus geradores da palavra vazia são $$ \Lambda = \set{L’, L, M, O}. $$

A gramática $G^2$, que resulta de $G^1$ por eliminação das produções vazias é:

$$ \begin{aligned} G^2 =& \del{\set{L’, L, M, N, O}, \set{a, b, c, d}, \ldots, L’} \cr & \begin{aligned} L’ & \to L \alt \alert{\nil} \cr L &\to Mb \alt \alert{b} \alt aLb \alt \alert{ab} \alt \xcancel{\nil} \cr M &\to Lb \alt \alert{b} \alt MLN \alt \alert{LN} \alt \alert{MN} \alt \alert{N} \alt \xcancel{\nil} \cr N &\to NaN \alt NbO \alt \alert{Nb}\cr O &\to cO \alt \alert{c} \alt \xcancel{\nil} \end{aligned} \end{aligned} $$

Note-se que:

1. Foram retiradas as produções $L \to \nil$ e $M \to \nil$.
2. Como $\nil \in L\at{G^1}$, foi acrescentada $L’ \to \nil$.
3. De cada produção em cujo corpo ocorrem geradores da palavra vazia foram acrescentadas variantes sem esses símbolos. Por exemplo:
   1. Em $L \to Mb$ no corpo, $Mb$, ocorre $M \in \Lambda$. Portanto é acrescentada a produção $L \to b$, que resulta de $Mb$ removendo $M$.
   2. Mais interessante, no corpo da produção $M \to MLN$ tanto $M$ como $L$ são geradores da palavra vazia. As combinações possíveis sem algum desses elementos são $LN, MN, N$.

Sem os cálculos auxiliares:

$$ \begin{aligned} G^2 =& \del{\set{L’, L, M, N, O}, \set{a, b, c, d}, \ldots, L’} \cr & \begin{aligned} L’ & \to L \alt \nil \cr L &\to Mb \alt b \alt aLb \alt ab \cr M &\to Lb \alt b \alt MLN \alt LN \alt MN \alt N \cr N &\to NaN \alt NbO \alt Nb\cr O &\to cO \alt c \end{aligned} \end{aligned} $$

3. Eliminação de Produções Unitárias

As produções unitárias substituem uma variável por outra variável e podem ser eliminadas usando cadeias.

Cadeia. Seja $G = \del{V, \Sigma, P, S}$ uma GIC essencialmente não contraível.

Para cada $A \in V$, a cadeia de $A$ é o conjunto $\cadeia\at{A} = \set{B \in V \st A \ider B}$.

Qualquer gramática $G’ = \del{V, \Sigma, \ldots, S}$ cujas produções $A \to w$ são tais que:

1. $w \not\in V$.
2. Existe $B \in \cadeia\at{A}$ tal que $B \to w \in P$.

é equivalente a $G$.

Este enunciado pode ser difícil de interpretar. O primeiro ponto afirma que na gramática $G’$ não existem produções unitárias. O segundo ponto permite substituir a produção unitária $A \to B$ por $A \to w$ para cada $B \to w$.

Exemplo. As cadeias de $G^2$ são

$$ \begin{array}{l|l} A \in V & \cadeia\at{A} \cr \hline L’ & L’, L\cr L & L \cr M & M, N\cr N & N \cr O & O \end{array} $$

e as produções unitária são $L’ \to L$ e $M \to N$. As respetivas substituições são:

• de $L’ \to \alert{L}$, dado que $L \to Mb \alt b \alt aLb \alt ab$: $L’ \to \alert{Mb \alt b \alt aLb \alt ab}$.
• de $M \to \alert{N}$, dado que $N \to NaN \alt NbO \alt Nb$: $M \to \alert{NaN \alt NbO \alt Nb}$.

A gramática que se obtém, equivalente a $G^2$, é:

$$ \begin{aligned} G^3 =& \del{\set{L’, L, M, N, O}, \set{a, b, c, d}, \ldots, L’} \cr & \begin{aligned} L’ & \to Mb \alt b \alt aLb \alt ab \alt \nil \cr L &\to Mb \alt b \alt aLb \alt ab \cr M &\to Lb \alt b \alt MLN \alt LN \alt MN \alt NaN \alt NbO \alt Nb \cr N &\to NaN \alt NbO \alt Nb\cr O &\to cO \alt c \end{aligned} \end{aligned} $$

4. Eliminação de Símbolos Inúteis

A definição de linguagem gerada pela GIC $G = \del{V, \Sigma, P, S}$ é $$ L\at{G} = \set{p \in \cl{\Sigma} \st S \ider p} $$

Uma inspeção rápida a $N \to NaN \alt NbO \alt Nb$ mostra que a recursividade desta variável impede-a de gerar palavras só de terminais. Portanto, em termos de linguagem gerada, este é um símbolo que pode ser retirado da gramática. Também podem ser retirados os símbolos que não podem ser atingidos a partir do símbolo inicial.

Símbolo Útil. Símbolo Acessível. Gramática Limpa. Seja $G = \del{V, \Sigma, P, S}$ uma GIC.

Um símbolo $x \in V \cup \Sigma$ é:

• Útil se existe uma derivação $S \ider u\alert{x}v \ider p \in \cl{\Sigma}$.
• Inútil se não é útil.
• Acessível se existe uma derivação $S \ider u\alert{x}v$.
• Inacessível se não é acessível.

Uma variável $A \in V$ é:

• Produtiva se $A \ider p \in \cl{\Sigma}$.
• Improdutiva se não é produtiva.

Uma variável é útil se e só se for acessível e produtiva.

Uma gramática sem símbolos inúteis e inacessíveis diz-se limpa (ou reduzida).

Para limpar uma gramática de símbolos inúteis e inacessíveis:

1. Eliminar as variáveis improdutivas:
   1. Encontrar as variáveis produtivas (por exemplo, derivando delas uma palavra só de terminais).
   2. Remover as produções onde ocorrem as variáveis improdutivas.
2. Eliminar as variáveis inacessíveis:
   1. Encontrar os símbolos acessíveis (por exemplo, fazendo uma derivação a partir do símbolo inicial onde o símbolo ocorra).
   2. Remover as produções das variáveis inacessíveis.

Exemplo. Como foi observado acima, $N$ é inútil. Portanto as produções onde $N$ ocorre podem ser removidas. As novas produções são:

$$ \begin{aligned} L’ & \to Mb \alt b \alt aLb \alt ab \alt \nil \cr L &\to Mb \alt b \alt aLb \alt ab \cr M &\to Lb \alt b \alt \xcancel{MLN} \alt \xcancel{LN} \alt \xcancel{MN} \alt \xcancel{NaN} \alt \xcancel{NbO} \alt \xcancel{Nb} \cr \xcancel{N} &\xcancel{\to NaN \alt NbO \alt Nb}\cr O &\to cO \alt c \end{aligned} $$

Como resultado destas remoções $O$ deixou de ser acessível: Nenhuma derivação $L’ \ider \cdots$ “contém” $O$. Portanto, também as produções de $O$ podem ser removidas e o resultado é:

$$ \begin{aligned} G^4 =& \del{\set{L’, L, M}, \set{a, b}, \ldots, L’} \cr & \begin{aligned} L’ & \to Mb \alt b \alt aLb \alt ab \alt \nil \cr L &\to Mb \alt b \alt aLb \alt ab \cr M &\to Lb \alt b \end{aligned} \end{aligned} $$

Note-se que, removendo as produções de $O$, o terminal $c$ ficou inacessível, pelo que foi retirado de $\Sigma$, tal como $d$, que nunca constou nas produções.

Finalmente, é fácil de verificar que $L’, L$ e $M$ são produtivos e acessíveis. Também $a$ e $b$ são acessíveis.

Numa gramática limpa todos os símbolos “contam”. Além disso, e de se ter tratado das produções vazias e unitárias, pouco se fez para melhorar o processo de pesquisa no grafo da gramática. Para esse efeito é preciso “controlar a forma” das produções.

5. Forma Normal de Chomsky

O corpo das produções de uma CIG é uma palavra de $\clpar{V \cup \Sigma}$, pelo que pode ter vários terminais e variáveis misturados. Aqui pretende-se “arrumar” as formas possíveis que as produções podem ter.

Forma Normal de Chomsky (FNC). Uma GIC $G = \del{V, \Sigma, P, S}$ está na forma normal de Chomsky se cada uma das suas produções tem uma das formas seguintes:

1. $A \to BC$ com $B, C \in V \setminus \set{S}$.
2. $A \to a$ com $a \in \Sigma$.
3. $S \to \nil$.

A forma normal de Chomsky é bastante fácil de obter, substituindo terminais “inconvenientes” por variáveis e usando novas variáveis para “agrupar” cadeias três ou mais símbolos.

Exemplo. Na gramática

$$ \begin{aligned} G^4 =& \del{\set{L’, L, M}, \set{a, b}, \ldots, L’} \cr & \begin{aligned} L’ & \to Mb \alt b \alt aLb \alt ab \alt \nil \cr L &\to Mb \alt b \alt aLb \alt ab \cr M &\to Lb \alt b \end{aligned} \end{aligned} $$

acrescentam-se $A \to a$ e $B \to b$ para retirar estes terminais das outras produções: $$ \begin{aligned} L’ & \to M\alert{B} \alt b \alt \alert{A}L\alert{B} \alt \alert{AB} \alt \nil \cr L &\to M\alert{B} \alt b \alt \alert{A}L\alert{B} \alt \alert{AB} \cr M &\to L\alert{B} \alt b \cr \alert{A} &\alert{\to a} \cr \alert{B} &\alert{\to b} \end{aligned} $$

Para se obter a FNC ainda falta tratar das produções $L’ \to ALB$ e $L \to ALB$. Para tal acrescenta-se a produção $X \to LB$ e substitui-se $L’, L \to AX$. O resultado final é:

$$ \begin{aligned} G^5 =& \del{\set{L’, L, M, \alert{A, B, X}}, \set{a, b}, \ldots, L’} \cr & \begin{aligned} L’ & \to MB \alt b \alt A\alert{X} \alt AB \alt \nil \cr L &\to MB \alt b \alt A\alert{X} \alt AB \cr M &\to LB \alt b \cr A &\to a \cr B &\to b \cr \alert{X} &\alert{\to LB} \end{aligned} \end{aligned} $$

6. Forma Normal de Greibach

Uma forma de reduzir o número de ramificações durante a pesquisa consiste em “olhar para o próximo símbolo” da palavra e escolher apenas produções que colocam esse símbolo no início.

Por exemplo, dadas a GIC $S \to aA \alt bB; A \to aA \alt \nil; B \to bB \alt \nil$ e a palavra $aa$, é simples de ver que a única derivação possível é $S \nder{S \to aA} aA \nder{A \to aA} aaA \nder{A \to \nil} aa$ porque em cada passo há só um candidato possível.

Neste caso, em cada passo da pesquisa é muito simples descartar todos os candidatos que não começam pelo terminal correto. Esta observação motiva a seguinte definição:

Forma Normal de Greibach (FNG). Uma GIC $G = \del{V, \Sigma, P, S}$ está na forma normal de Greibach se cada uma das suas produções tem uma das formas seguintes:

1. $A \to aB_1 B_2 \cdots B_n$ com $a \in \Sigma, B_i \in V \setminus \set{S}, i \in 1\ldots n$.
2. $A \to a$ com $a \in \Sigma$.
3. $S \to \nil$.

Note-se que, em relação à forma normal de Chomsky, a única diferença na primeira forma das produções: $A \to aB_1 B_2 \cdots B_n$ em vez de $A \to BC$.

As gramáticas na FNG são úteis para:

• evitar recursões infinitas nos algoritmos de pesquisa.
• guiar (com o primeiro símbolo) a escolha das regras a expandir.
• produzir AP equivalente à gramática dada.

Construção de uma GIC na FNG

Ao contrário da construção da FNC, que é simples de obter, a construção de uma GIC na FNG requer alguma orientação.

Construção da FNG. Dada uma GIC $G = \del{V, \Sigma, P, S}$ na FNC:

1. Ordenar as variáveis. Define-se uma ordem total nas variáveis de $G$ com uma única condição: $S$ é o primeiro elemento.
2. Passo Descendente. Segue-se essa ordem para transformar todas as produções de modo que, se $\alert{A \to Bp}, B\in V, p \in \clpar{V\cup \Sigma}$ então $\alert{A \lt B}$.
3. Passo Ascendente. Segue-se essa ordem invertida para substituir cada produção $\alert{A \to Bp}$ por $\alert{A \to qp}$ para cada produção $\alert{B \to q}, q \in \clpar{V\cup \Sigma}$.

Exemplo. Continuando com $G^5$, que está na FNC:

$$ \begin{aligned} L’ & \to MB \alt b \alt AX \alt AB \alt \nil \cr L &\to MB \alt b \alt AX \alt AB \cr M &\to LB \alt b \cr A &\to a \cr B &\to b \cr X &\to LB \end{aligned} $$

Ordenar as variáveis. A única condição é “$L’$ é o primeiro elemento”. Por exemplo $$L’ \lt X \lt B \lt A \lt L \lt M.$$

Passo Descendente. Ordenar as produções seguindo essa ordem.

$$ \begin{aligned} L’ & \to MB \alt b \alt AX \alt AB \alt \nil & L \lt M, A\cr X &\to LB & X < L\cr B &\to b \cr A &\to a \cr L &\to MB \alt b \alt \alert{A}X \alt \alert{A}B & L \lt M; \alert{L \not\lt A}\cr M &\to \alert{L}B \alt b & \alert{M \not\lt L} \end{aligned} $$

As produções de $L$ e de $M$ não verificam a condição do passo descendente. No caso de $L$ esse problema resolve-se facilmente substituindo o $A$ no início da produções de $L$ por $a$ (porque $A \to a$).

$$ \begin{aligned} L’ & \to MB \alt b \alt AX \alt AB \alt \nil & L \lt M, A\cr X &\to LB & X < L\cr B &\to b \cr A &\to a \cr L &\to MB \alt b \alt \underline{a}X \alt \underline{a}B & L \lt M\cr M &\to \alert{L}B \alt b & \alert{M \not\lt L} \end{aligned} $$

Resta o problema com a produção $ M \to \alert{L}B$. Segue-se também o método anterior:

$$ \begin{aligned} L’ & \to MB \alt b \alt AX \alt AB \alt \nil & L \lt M, A\cr X &\to LB & X < L\cr B &\to b \cr A &\to a \cr L &\to MB \alt b \alt aX \alt aB & L \lt M\cr M &\to \underline{\alert{M}B}B \alt \underline{b}B \alt \underline{aX}B \alt \underline{aB}B \alt b & \alert{M \not\lt M} \end{aligned} $$

Só que desta vez o problema não ficou resolvido e resultou numa Recursão Direta à Esquerda da variável $M$.

Eliminação da Recursividade Direta à Esquerda. Se

$$A \to A x_1 \alt \cdots \alt A x_n \alt y_1\alt \cdots \alt y_m$$

são as produções de $A$, organizadas de forma que:

• Cada $A x_1, \ldots, A x_n$ começa por $A$ e
• Nenhuma $y_1, \ldots, y_m$ começa por $A$.

Então obtém-se uma gramática equivalente:

1. Acrescentando uma nova variável, por exemplo $Z$.
2. Substituindo as produções de $A$ por

$$ \begin{aligned} A &\to y_1 Z \alt \cdots \alt y_m Z \alt y_1 \alt \cdots \alt y_m \cr Z &\to x_1 Z \alt \cdots \alt x_n Z \alt x_1 \alt \cdots \alt x_n \end{aligned} $$

Uma mnemónica para este processo é a seguinte:

Substituir $\alert{A \to A x \alt y}$ por $\alert{A \to yZ \alt y}$ e $\alert{Z \to xZ \alt x}$.

Intuitivamente percebe-se porque esta substituição é válida observando que a linguagem gerada por $A \to Ax \alt y$ é: $$ y, yx, yxx, yxxx, \ldots, yx^n, \ldots $$

Agora, outra forma de descrever esta linguagem é “Um $y$ seguido de zero ou mais $x$.” Neste caso:

• $Z \to xZ \alt x$ gera um ou mais $x$.
• $A \to yZ \alt y$ gera um $y$ seguido de zero ou um $Z$.

A eliminação da RDE de

$$ \overbrace{M}^{A} \to \overbrace{M}^{A}\ \overbrace{BB}^{x_1} \alt \overbrace{bB}^{y_1} \alt \overbrace{aXB}^{y_2} \alt \overbrace{aBB}^{y_3} \alt \overbrace{b}^{y_4} $$

define as produções

$$ \begin{aligned} M &\to bBZ \alt aXBZ \alt aBBZ \alt bZ &&\alt bB \alt aXB \alt aBB \alt b \cr Z &\to BBZ &&\alt BB \end{aligned} $$

pelo que a ordem inicialmente definida para as variáveis tem de ser estendida de forma que $Z < B$. Por exemplo:

$$L’ \lt X \lt \alert{Z} \lt B \lt A \lt L \lt M.$$

A nova gramática equivalente fica:

$$ \begin{aligned} L’ & \to MB \alt b \alt AX \alt AB \alt \nil & L \lt M, A\cr X &\to LB & X < L\cr \alert{Z} &\alert{\to BBZ \alt BB} & Z \lt B\cr B &\to b \cr A &\to a \cr L &\to MB \alt b \alt aX \alt aB & L \lt M\cr \alert{M} &\alert{\to bBZ \alt aXBZ \alt aBBZ \alt bZ \alt bB \alt aXB \alt aBB \alt b} \end{aligned} $$

No fim do passo descendente cada produção ou é vazia ou começa por um terminal ou começa por uma variável “mais abaixo”.

Passo Ascendente. Substituir, “de baixo para cima” a primeira variável de cada produção:

$$ \begin{aligned} L’ & \to \underbrace{bBZB \alt aXBZB \alt aBBZB \alt bZB \alt bBB \alt aXBB \alt aBBB \alt bB}{MB} \alt b \alt \underbrace{aX}{AX} \alt \underbrace{aB}{AB} \alt \nil \cr X &\to \underbrace{bBZBB \alt aXBZBB \alt aBBZBB \alt bZBB \alt bBBB \alt aXBBB \alt aBBBB \alt bBB \alt bB \alt aXB \alt aBB}{LB}\cr Z &\to \underbrace{bBZ}{BBZ} \alt \underbrace{bB}{BB}\cr B &\to b \cr A &\to a \cr L &\to \underbrace{bBZB \alt aXBZB \alt aBBZB \alt bZB \alt bBB \alt aXBB \alt aBBB \alt bB}_{MB} \alt b \alt aX \alt aB\cr M &\to bBZ \alt aXBZ \alt aBBZ \alt bZ \alt bB \alt aXB \alt aBB \alt b \end{aligned} $$

Sem anotações, a GIC final, $$ \begin{aligned} G^6 =& \del{\set{L’, L, M, A, B, X, Z}, \set{a, b}, \ldots, L’} \cr & \begin{aligned} L’ & \to bBZB \alt aXBZB \alt aBBZB \alt bZB \alt bBB \alt aXBB \alt aBBB \alt bB \alt b \alt aX \alt aB \alt \nil \cr X &\to bBZBB \alt aXBZBB \alt aBBZBB \alt bZBB \alt bBBB \alt aXBBB \alt aBBBB \alt bBB \alt bB \alt aXB \alt aBB\cr Z &\to bBZ \alt bB\cr B &\to b \cr A &\to a \cr L &\to bBZB \alt aXBZB \alt aBBZB \alt bZB \alt bBB \alt aXBB \alt aBBB \alt bB \alt b \alt aX \alt aB\cr M &\to bBZ \alt aXBZ \alt aBBZ \alt bZ \alt bB \alt aXB \alt aBB \alt b \end{aligned} \end{aligned} $$ está na Forma Normal de Greibach e é equivalente à GIC inicial $$ \begin{aligned} G^0 =& \del{\set{L, M, N, O}, \set{a, b, c, d}, \ldots, L} \cr &\begin{aligned} L &\to Mb \alt aLb \alt \nil \cr M &\to Lb \alt MLN \alt \nil \cr N &\to NaN \alt NbO \cr O &\to cO \alt \nil \end{aligned} \end{aligned} $$

Embora $G^6$ tenha muito mais produções do que $G^0$ e ainda por cima aparentemente redundantes (mas não o são) o facto de $G^6$ estar na FNG torna-a mais adequada e eficiente do que $G^0$ em termos de pesquisa. Por exemplo:

• A derivação de uma palavra com $n$ símbolos tem, no máximo, $n$ passos porque cada produção “produz” um terminal.
• O primeiro símbolo “filtra” as possíveis produções aplicáveis.
• A pesquisa de uma palavra não gerada pela GIC, $p \not\in L$, “falha cedo”, no máximo em $\len{p}$ passos.

Ver o exemplo no código deste capítulo.

Processo de Normalização de uma Gramática

Resumindo todos os passos, a normalização de uma GIC consiste em:

1. Eliminar a recursividade do símbolo inicial.
2. Eliminar as produções vazias exceto, se necessário, do símbolo inicial.
3. Eliminar as produções unitárias.
4. Eliminar os símbolos inúteis.
5. Transformar na Forma Normal de Chomsky.
6. Transformar na Forma Normal de Greibach.

Conclusão

O problema da Análise Sintática, que se está a tentar resolver, é uma reformulação do Problema Principal de ALP para as GIC e pergunta “como determinar se $p \in L$” quando $p$ é uma palavra/programa e $L$ é uma linguagem gerada por uma gramática independente de contexto.

Inicialmente tentou-se formalizar as linguagens $L$ usando expressões regulares mas o Pumping Lemma mostrou a necessidade de uma abordagem mais geral — as gramáticas independentes de contexto.

Embora as GIC resolvam a adequação (com as expressões algébricas) e os autómatos de pilha proporcionem um modelo computacional, este não é eficiente.

A Normalização de uma GIC é um processo que começa com uma GIC e que, ao longo de vários passos, produz outras GIC equivalentes, de forma a obter-se uma gramática “adequada” aos algoritmos de pesquisa geral. A Forma Normal de Greibach impõe restrições fortes às produções, que podem ser bem aproveitadas para reduzir a complexidade/ramificação da pesquisa.

Mesmo com a FNG a ajudar na pesquisa, a resposta a “$p \in L$” ainda permite ramificações ao pesquisar a árvore das derivações. Portanto o problema do não determinismo persiste e, com ele, a eficiência fica por resolver.

Os algoritmos deterministas são o próximo assunto e assentam, tanto quanto possível, nas propriedades das gramáticas e das derivações.