Gramáticas Independentes de Contexto

Uma especificação formal de linguagens mais capaz do que as expressões regulares.

• Gramáticas Independentes de Contexto
  • Introdução
  • Gramáticas e Linguagens Independentes de Contexto
    • Recursividade
    • Derivação Esquerda/Direita
    • Árvore de Derivação
    • Ambiguidade
    • Gramáticas Regulares e Simulação de AFND
  • Conclusão

Introdução

Nos capítulos anteriores desenvolveu-se, para as ER, AFD e AFND, um conjunto de técnicas computacionais eficientes, com vista a resolver o Problema Principal de ALP. Porém, com o Pumping Lemma, conclui-se que é necessária uma forma mais geral de definir linguagens.

As linguagens naturais têm uma certa estrutura que resulta de regras gramaticais. Por exemplo, "O gato bebe leite." é válida em português mas "bebe. gato leite O" não. (N.B: neste exemplo os símbolos do alfabeto são as palavras da língua portuguesa — por exemplo, de um dicionário — e as palavras são sequências desses símbolos.)

Como descrever essas regras gramaticais? Por exemplo:

Frase       : Sujeito Predicado
Sujeito     : Artigo Substantivo
Predicado   : Verbo Advérbio
Artigo      : "o"
            | "as"
Substantivo : "gato"
            | "galinhas"
Verbo       : "bebe"
            | "voam"
Advérbio    : "devagar"
            | "baixinho"

Os termos Assim são variáveis e "entre aspas" são terminais.

Aplicando estas regras, obtém-se, por exemplo:

Frase   : Sujeito Predicado
        : Artigo Substantivo Predicado
        : o Substantivo Predicado
        : o gato Predicado
        : o gato Verbo Advérbio
        : o gato bebe Advérbio
        : o gato bebe devagar

Também se obtêm frases com pouco sentido, como as gato voam devagar. Esses problemas, em princípio, podem ser tratados com regras mais sofisticadas. No entanto, também este exemplo sem sentido mantém a estrutura entre as diferentes partes da palavra: o Artigo está no início, etc. Isto é, usando aquelas regras nunca se obtém, por exemplo, devagar bebe o gato.

Gramáticas e Linguagens Independentes de Contexto

As Gramáticas Independentes do Contexto são uma forma simples de representar rigorosamente regras gramaticais como as ilustradas acima.

Gramática Independente do Contexto (GIC). Uma Gramática Independente do Contexto é um tuplo $G=\left(V,\Sigma ,P,S\right)$ em que:

• Variáveis (ou Não Terminais): $V$ é um conjunto de símbolos, designados variáveis ou não terminais.
• Terminais: $\Sigma$ é um conjunto de símbolos, disjunto de $V$ (isto é, $V\cap \Sigma =\varnothing$), designados terminais.
• Produções (ou Regras): $P\subset V\times {\left(V\cup \Sigma \right)}^{\ast }$ é um conjunto finito. Os seus elementos são pares da forma $(A,p)$ com $A\in V$ e $p\in {\left(V\cup \Sigma \right)}^{\ast }$, designados produções ou regras e denotados $A\to p$.
• Símbolo Inicial: $S\in V$.

Numa GIC há dois tipos de símbolos: Os terminais, sem produções associadas e as variáveis, com produções associadas. Intuitivamente, as variáveis vão ser sucessivamente transformadas, até restarem apenas símbolos terminais.

É importante notar que o alfabeto das palavras é ${\left(V\cup \Sigma \right)}^{\ast }$ isto é, as palavras têm terminais e variáveis.

Esta mistura justifica a definição seguinte:

Prefixo (resp. Sufixo) Terminal. Seja $p\in {\left(V\cup \Sigma \right)}^{\ast }$ uma palavra formada por (zero ou mais) terminais e (zero ou mais) variáveis. Então, escrevendo $p=uqv$ em que $u,v\in {\Sigma }^{\ast }$ e $q$ começa e termina por variáveis.

• O prefixo terminal de $p$ é $u$.
• O sufixo terminal de $p$ é $v$.

Isto é, $u$ é o maior prefixo só de terminais de $p$ e $v$ é o maior sufixo só de terminais.

Por exemplo, em $p=abSaB$ o prefixo terminal é $ab$ e o sufixo terminal é $\lambda$.

A aplicação de regras de uma GIC transforma palavras. Formalmente:

Derivação. Sejam $G=\left(V,\Sigma ,P,S\right)$ uma GIC, $u,v\in {\left(V\cup \Sigma \right)}^{\ast }$.

• Se $A\to p\in P$, então $uAv$ deriva diretamente $uwv$ e escreve-se $uAv\Rightarrow upv$.
• Se existem $p_0,p_1,\dots ,p_n\in {\left(V\cup \Sigma \right)}^{\ast }$ tais que $$p=p_0\Rightarrow p_1\Rightarrow \cdots \Rightarrow p_n=q$$ então $p$ deriva $q$ em $n$ passos e escreve-se $p\stackrel{n}{\Rightarrow }q$.
• Se existe $n$ tal que $p\stackrel{n}{\Rightarrow }q$ então $p$ deriva $q$ e escreve-se $p\stackrel{\ast }{\Rightarrow }q$.

As regras de uma gramática são aplicadas às variáveis de uma palavra e o resultado é uma nova palavra. A esse processo chama-se "derivação direta". Se forem aplicadas $n$ derivações diretas obtém-se uma "derivação em $n$ passos". Por fim, se o número exato de passos não for importante, tem-se uma "derivação".

Por exemplo, dada a gramática $G=\left(\left\{S,A\right\},\left\{a,b\right\},\left\{S\to bAb,S\to b,A\to AAa,A\to \lambda \right\},S\right)$:

• $abSbAb\Rightarrow abSbb$ pela regra $A\to \lambda$.
• Também $abSbAb\Rightarrow abbbAb$ pela regra $S\to b$.
• $abSbAb\Rightarrow abbAbbAb$ pela regra $S\to bAb$.

Em certas circunstâncias é necessário especificar a GIC de onde estão a ser usadas as derivações. Nesse caso acrescenta-se o índice ${}_G$ e a notação das derivações fica $p{\Rightarrow }_{G}q,p{\stackrel{n}{\Rightarrow }}_{G}q,p{\stackrel{\ast }{\Rightarrow }}_{G}q$ para indicar que são usadas apenas produções de $G$.

Para escrever uma GIC é comum usarem-se as seguintes regras para simplificar a notação:

• Os terminais são representados por minúsculas e as variáveis por maiúsculas.
• Se nada for dito, $S$ é o símbolo inicial.
• As produções de cada variável ficam agrupadas e, entre si, separadas por "$|$".

Por exemplo, a gramática acima fica completamente definida por $$\begin{array}{rl}S& \to bAb|b\\ A& \to AAa|\lambda \end{array}$$

As produções de uma gramática transformam palavras noutras palavras. Essa transformação tem a designação técnica de derivação e é a base para associar uma linguagem a uma GIC.

Linguagem Gerada. Seja $C=\left(V,\Sigma ,P,S\right)$ uma GIC.

• O conjunto das palavras deriváveis a partir de $p\in {\left(V\cup \Sigma \right)}^{\ast }$ é $D\left(p\right)=\left\{q:p{\Rightarrow }^{\ast }q\right\}$.
• A linguagem gerada por $G$ é $L\left(G\right)=\left\{t\in {\Sigma }^{\ast }:S\stackrel{\ast }{\Rightarrow }t\right\}$.
  • Neste caso diz-se que $L\left(G\right)$ é uma Linguagem Independente do Contexto.
• Duas gramáticas são equivalentes se geram a mesma linguagem.

Observação. As palavras da linguagem gerada são só de terminais. Isto é: $L(G)\subseteq {\Sigma }^{\ast }$.

Tal como foi feito para as ER, os AFD e AFND, a equivalência entre GIC assenta na linguagem associada.

Por exemplo, qual é a linguagem gerada por $G=S\to aSb|\lambda$?

1. Da produção $S\to \lambda$ resulta a derivação $S\stackrel{\ast }{\Rightarrow }\lambda$. Portanto $\lambda \in L\left(G\right)$.
2. Da derivação $S\stackrel{S\to aSb}{\Rightarrow }aSb\stackrel{S\to \lambda }{\Rightarrow }ab$ resulta que $ab\in L\left(G\right)$.
3. Igualmente, de $S\stackrel{S\to aSb}{\Rightarrow }aSb\stackrel{S\to aSb}{\Rightarrow }aaSbb\stackrel{S\to \lambda }{\Rightarrow }aabb$ conclui-se que $aabb\in L\left(G\right)$.
4. Sucessivamente, $aaabbb,a^4{b}^4,\dots ,a^m{b}^m,\dots \in L\left(G\right)$.

Portanto, $G=S\to aSb|\lambda$ gera a linguagem simplificada dos parêntesis equilibrados, $E=\left\{a^m{b}^m:m\ge 0\right\}$.

A linguagem $E$, usada para mostrar que as linguagens recursivas não são adequadas para definir linguagens de programação é a linguagem gerada por uma GIC com apenas duas produções.

Este exemplo é um sinal positivo para resolução do Problema Principal de ALP, pelo menos em termos da adequação. Falta ainda aprofundar casos mais complexos de adequação e tratar dos aspetos da computação e da eficiência.

Recursividade

Donde vem a capacidade das GIC para gerar tão facilmente $E$, quando as ER falharam?

Olhando de novo para a GIC em questão, $G=S\to aSb|\lambda$, destaca-se a regra $S\to aSb$. O "$S$" em "$aSb$" permite "repetir indefinidamente" o $S$, como um ciclo.

Esta possibilidade de "repetições indefinidamente" está além da capacidade expressiva das ER. Porém, é uma espada de dois gumes, que levanta problemas novos. Por exemplo, que palavras são geradas pela GIC $S\to Sa$?

Formalmente, a produção $S\to aSb$ é "diretamente recursiva" e a recursão pode surgir de várias formas:

Produção Recursiva. Não Terminal Recursivo, Derivação Recursiva. Sejam $G=\left(V,\Sigma ,P,S\right)$ uma GIC, $A\in V$ e $p,u,v\in {\left(V\cup \Sigma \right)}^{\ast }$.

1. Uma produção da forma $A\to uAv$ é diretamente recursiva.
2. Uma variável $A$ é recursiva se $A\to p\stackrel{\ast }{\Rightarrow }uAv$ (isto é, $A\stackrel{\ast }{\Rightarrow }uAv$ em um ou mais passos).
3. Uma derivação da forma $A\stackrel{\ast }{\Rightarrow }p\stackrel{\ast }{\Rightarrow }uAv$ onde $A$ não ocorre em $p$ é indiretamente recursiva.

Por exemplo,

• $S\to aSb$ é uma produção diretamente recursiva.
• No exemplo anterior, $S$ é uma variável recursiva.
• Na gramática $S\to aAb,A\to cSc|\lambda$, a derivação $S\Rightarrow aAb\Rightarrow acScb$ é indiretamente recursiva.

Mais tarde serão tratadas várias situações relacionadas com a recursividade mas por enquanto importa aprofundar mais aspetos das derivações.

Em primeiro lugar importa assegurar que, numa derivação $p\stackrel{n}{\Rightarrow }q$, as sub-derivações de uma variável em $p$ não são afetadas pelas sub-derivações de outras variáveis também em $p$.

Por exemplo, supondo que numa certa CIG $aXbYc\stackrel{7}{\Rightarrow }acccbaaac$, é intuitivamente evidente que os $ccc$ resultam de $X$ e apenas de $X$ e que os $aaa$ resultam apenas do $Y$ e que, no total, fizeram-se $7$ derivações.

Mas a evidência intuitiva precisa de um apoio rigoroso:

Independência das Sub-Derivações. Seja $G={\left(V,\Sigma ,P,S\right)}^{\ast }$ uma GIC e $p\stackrel{n}{\Rightarrow }q$ uma derivação em $G$ onde

$$p=p_1{A}_1{p}_2{A}_2\cdots p_k{A}_k{p}_{k+1}$$

com os $p_i\in {\Sigma }^{\ast }$ (portanto, palavras só de terminais) e os $A_i\in V$.

Então existem palavras $q_i\in {\left(V\cup \Sigma \right)}^{\ast }$ tais que:

• Para cada $i$, $A_i\stackrel{n_i}{\Rightarrow }{q}_i$.
• $q=p_1{q}_1{p}_2{q}_2\dots p_k{q}_k{p}_{k+1}$.
• ${\sum }_{i=1}^k{n}_i=n$.

A independência está na afirmação de que o resultado $q=p_1{q}_1{p}_2{q}_2\dots p_k{q}_k{p}_{k+1}$ é obtido isoladamente em cada variável, $A_i\stackrel{n_i}{\Rightarrow }{q}_i$.

Por exemplo, dada a gramática $S\to cAcBc,A\to aA|\lambda ,B\to Bb|\lambda$, a derivação em $5$ passos $$\underset{p}{\underbrace{cAcBc}}\Rightarrow c\underline{aA}cBc\Rightarrow c\underline{a}cBc\Rightarrow cac\underline{Bb}c\Rightarrow cac\underline{Bbb}c\Rightarrow \underset{q}{\underbrace{cac\underline{bb}c}}$$ tem sub-derivações:

• $A\Rightarrow aA\Rightarrow a$ com dois passos; $A=A_1\stackrel{2}{\Rightarrow }a=q_1$.
• $B\Rightarrow Bb\Rightarrow Bbb\Rightarrow bb$ com três passos; $B=A_2\stackrel{3}{\Rightarrow }bb=q_2$
• $q=c{q}_{1}c{q}_{2}c$.

Derivação Esquerda/Direita

Considerando a GIC $S\to SS|aSb|\lambda$, a partir do símbolo inicial, $S$, há três opções para "escolher a produção". Se a escolha for $S\to SS$, fica-se com a derivação $S\Rightarrow SS$, se for $S\to aSb$ a derivação é $S\Rightarrow aSb$ e também $S\Rightarrow \lambda$ é uma derivação possível.

Em $SS$ há duas opções para "escolher a variável". A primeira $S$ ou a segunda? Se for a primeira, obtém-se $aSbS$, $SSS$ e $S$ mas se for a segunda os resultados possíveis são $SSS$, $SaSb$ e $S$.

As regras das derivações permitem duas escolhas:

1. Que variável substituir?
2. Com que produção dessa variável?

Se por um lado estas escolhas permitem "capacidade expressiva" (o que é bom: as ER não são suficientemente expressivas) por outro lado as escolhas têm um custo elevado (exponencial) na eficiência computacional de futuros algoritmos sobre CIG e LIC.

Uma boa solução para este dilema restringe as escolhas sem sacrificar a "capacidade expressiva".

Derivação Esquerda. Derivação Direita.

• Numa derivação esquerda é escolhida a variável mais à esquerda em todos os passos. Nas derivações esquerdas o símbolo $\Rightarrow$ é substituído por ${\Rightarrow }_L$.

• Numa derivação direita é escolhida a variável mais à direita em todos os passos. Nas derivações direitas o símbolo $\Rightarrow$ é substituído por ${\Rightarrow }_R$.

Seja $G=\left(V,\Sigma ,P,S\right)$ uma GIC. Para cada $p\in {\Sigma }^{\ast }$, $$p\in L\left(G\right)⟺S\stackrel{\ast }{\Rightarrow }p⟺S\stackrel{\ast }{{\Rightarrow }_L}p⟺S\stackrel{\ast }{{\Rightarrow }_R}p.$$

Isto é, numa derivação esquerda escolhe-se sempre a primeira variável e numa derivação direita escolhe-se sempre a última. A "capacidade expressiva" não fica prejudicada porque qualquer palavra só de terminais que seja gerada pela GIC também é gerada por uma derivação esquerda e também é gerada por uma derivação direita.

Por exemplo, continuando com a gramática $S\to SS|aSb|\lambda$, como derivar $abaabb$?

• Sem restrições, uma solução é $S\Rightarrow SS\Rightarrow aSbS\Rightarrow aSbaSb\Rightarrow abaSb\Rightarrow abaaSbb\Rightarrow abaabb$. Nuns passos foi escolhida a primeira variável, noutros a última.
• Derivação esquerda: $S{\Rightarrow }_{L}SS{\Rightarrow }_{L}aSbS{\Rightarrow }_{L}abS{\Rightarrow }_{L}abaSb{\Rightarrow }_{L}abaaSbb{\Rightarrow }_{L}abaabb$.
• Derivação direita: $S{\Rightarrow }_{R}SS{\Rightarrow }_{R}SaSb{\Rightarrow }_{R}SaaSbb{\Rightarrow }_{R}Saabb{\Rightarrow }_{R}aSbaabb{\Rightarrow }_{R}abaabb$.

Árvore de Derivação

As derivações podem ser representadas graficamente por diagramas em árvore.

Árvore de Derivação. Seja $G=\left(V,\Sigma ,P,S\right)$ uma GIC e $S\stackrel{\ast }{\Rightarrow }p$ uma derivação de $G$.

A árvore da derivação $S\stackrel{\ast }{\Rightarrow }p$ é formada por:

• Raiz: O símbolo inicial $S$.
• Filhos: Se a produção $A\to x_1{x}_2\cdots x_n$, com $x_i\in V\cup \Sigma$ for a produção usada para substituir a variável $A$ então o vértice $A$ tem filhos $x_1,x_2,\dots x_n$ por essa ordem.
• Folhas Vazias: Se $A\to \lambda$ for a produção usada para substituir a variável $A$ então o vértice $A$ tem $\lambda$ como único filho.

Uma palavra $p$ tem árvore de derivação $T$ se $p$ for a concatenação das folhas de $T$ lidas da esquerda para a direita.

Por exemplo, a derivação $S\stackrel{S\to aSb}{\Rightarrow }aSb\stackrel{S\to aSb}{\Rightarrow }aaSbb\stackrel{S\to \lambda }{\Rightarrow }aabb$ tem a seguinte árvore:

Exemplo de Árvore de Derivação

Lendo as folhas da esquerda para a direita obtém-se $aabb$, a palavra derivada.

Ambiguidade

Um problema (ver Dangling Else na wikipedia) que ocorre frequentemente em várias linguagens de programação, e que é responsável por erros difíceis de detetar e com consequências graves, pode ser ilustrado no seguinte exemplo:

if (a) if (b) s1; else s2;

Este fragmento tanto pode ser tratado como

if (a) {
    if (b) s1;
    else s2;
}

ou como

if (a) {
    if (b) s1;
}
else s2;

No primeiro caso, se a for falso não corre nem s1 nem s2. No segundo caso, se a for falso corre s2. O que acontece se a for "inimigo detetado", s2 "lançar mísseis" e b testa "cenário simulado"?

Este problema resulta diretamente da gramática porque a palavra if (a) if (b) s1; else s2; tem duas derivações diferentes, uma que associa o else ao primeiro if e outra que o associa ao segundo.

Formalmente,

Gramática Ambígua. Linguagem Inerentemente Ambígua.

• Uma gramática $G$ é ambígua se alguma palavra de $L\left(G\right)$ tem:
  • duas árvores de derivação distintas ou
  • duas derivações esquerdas distintas ou
  • duas derivações direitas distintas.
• Uma linguagem é inerentemente ambígua se não for gerada por uma gramática não ambígua.

Nesta definição é importante lembrar e distinguir o seguinte:

• Uma linguagem pode ser gerada por várias gramáticas equivalentes. Algumas dessas gramáticas podem ser ambíguas e outras não. Por isso, "ambígua" é uma propriedade que diz respeito às gramáticas.
• Também pode acontecer que todas as gramáticas que geram uma certa linguagem sejam ambíguas. Esta situação é uma caraterística da linguagem, não das gramáticas que a geram. Por isso "inerentemente ambígua" é uma propriedade que diz respeito às linguagens.

Um exemplo de uma linguagem inerentemente ambígua é:

$$\left\{a^i{b}^j{c}^k:i,j,k\ge 0\right\}$$

A gramática $S\to SS|\lambda$ é ambígua porque $S{\Rightarrow }_R\lambda$ e $S{\Rightarrow }_{R}SS{\Rightarrow }_{R}S{\Rightarrow }_R\lambda$ são duas derivações direitas de $\lambda$. Esta gramática é equivalente a $S\to \lambda$ que não é ambígua (exercício: porquê?).

Como é que as LIC se relacionam com as LR? O que foi feito nos capítulos anteriores está "perdido" ou as GIC estendem as ER?

Gramáticas Regulares e Simulação de AFND

Como definir linguagens regulares com GIC?

Gramática Regular. Uma gramática $G=\left(V,\Sigma ,P,S\right)$ é regular se todas as suas produções têm uma das formas seguintes: $$\begin{array}{rl}A& \to a\\ A& \to aB\\ A& \to \lambda \end{array}$$ com $A,B\in V$ e $a\in \Sigma$.

O interesse desta definição é que

Se $G$ é uma GIC regular então $L\left(G\right)$ é uma linguagem regular.

A demonstração desta afirmação está fora do âmbito de ALP. A consequência das gramáticas regulares é que as GIC podem gerar algumas linguagens regulares*. Será que podem gerar todas?

Simulação de AFND por GIC. Seja $A=\left(Q,\Sigma ,\delta ,q_I,F\right)$ um AFND. A GIC equivalente a $A$ é $G=\left(V,\Sigma ,P,S\right)$ em que:

• variáveis - estados. $V=\left\{X_q:q\in Q\right\}$.
• símbolo inicial - estado inicial. $S=X_{q_I}$.
• produções - estados finais. Se $q\in F$ então $X_q\to \lambda \in P$.
• produções - transições $q\stackrel{a}{⟶}p$. Para cada $a\in \Sigma$, se $p\in \delta \left(q,a\right)$ então $X_q\to a{X}_p\in P$.
• produções - transições $q\stackrel{\lambda }{⟶}p$. Se $p\in \delta \left(q,\lambda \right)$ então $X_q\to X_p\in P$.

Neste caso $L\left(A\right)=L\left(G\right)$.

Dado um AFND qualquer, aplicando este método, obtém-se uma GIC equivalente no sentido em que a linguagem aceite pelo AFND é gerada pela GIC. Portanto as LIC incluem todas as LR.

Por exemplo, dado o AFND antes usado para ilustrar o Algoritmo de Kleene:

AFND equivalente a $\left(\lambda \cup a\right){\left(b\cup b{\left(a\cup b\right)}^{\ast }a\right)}^{\ast }$

vai construir-se a GIC em que:

1. As variáveis são $X_0,X_1,X_2,X_3$.
2. O símbolo inicial é $S=X_0$.
3. As transições e os estados finais definem as seguintes produções: $$\begin{array}{rl}{X}_0& \to a{X}_1|b{X}_2|X_1\\ X_1& \to b{X}_1|b{X}_3|\lambda \\ X_2& \to X_3\\ X_3& \to a{X}_1|a{X}_3|b{X}_2\end{array}$$

A palavra abaabb é aceite pelo AFND, pela computação

$$0\stackrel{a}{⊢}1\stackrel{b}{⊢}3\stackrel{a}{⊢}3\stackrel{a}{⊢}1\stackrel{b}{⊢}1\stackrel{b}{⊢}1\in F.$$

Será gerada pela GIC? $$X_0\Rightarrow a{X}_1\Rightarrow ab{X}_3\Rightarrow aba{X}_3\Rightarrow abaa{X}_1\Rightarrow abaab{X}_1\Rightarrow abaabb{X}_1\Rightarrow abaabb.$$

Este exemplo também ilustra como a produção $X_q\to a{X}_p$ da GIC representa a transição $q\stackrel{a}{⊢}p$ do AFND.

Conclusão

As GIC foram introduzidas depois de se ter constatado, no capítulo anterior, que as linguagens regulares são insuficientes para definir as linguagens de programação.

• Logo um dos primeiros exemplos de GIC permitiu definir a linguagem simplificada dos parêntesis equilibrados, o que é um indicador positivo para as GIC.
• Outro exemplo, as expressões algébricas, permitiu ilustrar como tratar o problema da ambiguidade.
• A questão da relação entre as LR e as LIC ficou resolvida com a simulação de AFND por uma GIC regular.

Embora as GIC pareçam um candidato razoável para descrever as linguagens de programação, falta tratar as questões da computação: Como responder algoritmicamente, de forma eficiente, à questão $p\in L\left(G\right)$?