flowchart LR
G["Gramática livre<br/>de contexto"] --> V["Variáveis<br/>nomes de construções"]
G --> T["Terminais<br/>símbolos léxicos"]
G --> S["Variável inicial<br/>construção mais externa"]
G --> P["Produções"]
P --> F["Uma única variável<br/>do lado esquerdo"]
F --> C["A substituição não<br/>consulta a vizinhança"]
C --> R["Composicionalidade:<br/>a regra vale em todo lugar"]
C --> D["Dívida: condições de<br/>contexto vão para outra fase"]
1 Módulo 08: Gramáticas Livres de Contexto — Resumo
Esta é a versão de revisão. Recapitulo aqui, em ritmo de véspera, o que este módulo tem de guardado; nada é demonstrado por inteiro, e para isso existem a versão completa do material deste módulo e o livro. Use este texto para conferir se você consegue olhar para um punhado de produções e dizer, de cabeça, qual operador tem precedência sobre qual e se aquele texto admite duas leituras.
Escreva no papel 2 + 3 \times 4 e diga quanto vale. Você respondeu quatorze, rápido, porque a escola lhe ensinou a ordem. Agora inverta os papéis comigo: de onde o computador tira essa informação? Não é do texto, que são cinco símbolos e nenhum deles manda multiplicar primeiro; não é do processador, que só executa a ordem que alguém decidiu emitir. A resposta deste módulo é que a precedência mora na forma das regras.
1.1 O formalismo, e por que o nome é esse
O módulo dos limites das linguagens regulares fechou com uma impossibilidade demonstrada: nenhum autômato finito reconhece as cadeias com parênteses balanceados. Como toda linguagem que vale a pena tem aninhamento, aquilo foi a certidão de óbito de descrever a estrutura de um programa com expressões regulares.
Olhe para L = \{a^n b^n\}: a dificuldade não é contar, é contar duas coisas em correspondência, uma de cada lado de um centro. Dizer “uma cadeia de L é vazia, ou é um a seguido de outra cadeia de L seguida de um b” resolve, e escrever isso em símbolos já é a sua primeira gramática livre de contexto, S \to a\,S\,b \mid \varepsilon. Compare com A \to a\,A \mid b, que gera uma linguagem regular: a diferença é só a posição do símbolo recursivo. Se você guardar uma imagem só deste módulo, guarde esta — aninhamento é símbolo recursivo no meio.
Formalmente, uma gramática livre de contexto é a quádrupla G = (V, \Sigma, P, S), com V finito de variáveis, \Sigma finito de terminais disjunto de V, S a variável inicial e P finito de produções A \to \alpha, com A \in V e \alpha \in (V \cup \Sigma)^*.
O ponto em que mais se tropeça na primeira leitura: numa gramática que descreve a sintaxe de uma linguagem de programação, os terminais não são caracteres, são as categorias de símbolo léxico que a fase anterior entrega. As variáveis nomeiam construções — expressão, declaração, bloco — e existem só durante a geração, como andaimes que se desmontam. E a produção tem duas assimetrias: à esquerda, exatamente um símbolo, obrigatoriamente uma variável; à direita, qualquer sequência.
Dessa assimetria vem o nome. Não há como escrever “substitua A por \alpha, mas só quando A estiver entre um x e um y”: com um símbolo só à esquerda, não sobra espaço para o contexto. Toda ocorrência de A pode virar \alpha, sempre, sem consultar a vizinhança. Parece perda de poder, e é — deliberada. O formalismo fica composicional: escrevo a produção da condicional uma vez e ela vale dentro de um laço, de uma função, de outra condicional. O preço aparece depois, porque “todo nome usado precisa ter sido declarado” é sensível ao contexto, e é por isso que existe uma fase de análise semântica separada.
No fim dos anos 1950, John Backus propôs, no projeto de ALGOL, uma notação para descrever formalmente a sintaxe de uma linguagem, e Peter Naur, editando o relatório de ALGOL 60, adaptou-a e a empregou sistematicamente. Aquelas linhas com barras verticais que você pulou na documentação de alguma linguagem são gramáticas livres de contexto. A variante estendida dos manuais — asterisco, interrogação — não existe na definição e não aumenta o poder: repetição vira recursão, e o opcional vira duas produções.
A expansão do opcional é onde mais se erra. A tentação é criar uma variável auxiliar anulável e pô-la no meio da produção. Funciona, e é pior que duplicar: você introduziu produção vazia numa gramática que talvez não precisasse de nenhuma, e produção vazia é a principal fonte de erro nos conjuntos que orientam o analisador descendente.
1.2 Derivações e árvores: a relação exata
Escrevemos \gamma\,A\,\delta \Rightarrow \gamma\,\alpha\,\delta quando A \to \alpha está em P; o que se obtém de S em zero ou mais passos é forma sentencial, e se só tiver terminais é sentença. A linguagem gerada é L(G) = \{\, w \mid S \Rightarrow^* w \,\}.
Duas liberdades ficam em aberto, e elas são de naturezas diferentes: qual variável expandir é escolha de ordem; qual produção aplicar é escolha de estrutura. A primeira não altera o resultado, a segunda altera tudo. Confundir as duas é o erro clássico deste módulo. A de ordem se elimina por convenção — derivação mais à esquerda expande sempre a variável mais à esquerda, mais à direita faz o simétrico —, e as convenções nomeiam as duas famílias de analisadores: o descendente constrói uma derivação mais à esquerda; o ascendente reconstrói uma mais à direita, ao contrário.
A árvore de derivação descarta a ordem e guarda a estrutura, com a cláusula que impede desenhar qualquer árvore bonita: os filhos de cada nó interno correspondem a uma produção que existe na gramática. E vem o teorema que carrega o módulo — para toda cadeia da linguagem há bijeção entre as suas árvores e as suas derivações mais à esquerda, e outra entre as árvores e as mais à direita.
flowchart LR
A["Árvore de derivação<br/>estrutura"]
E["Derivação mais à esquerda<br/>sequência"]
D["Derivação mais à direita<br/>sequência"]
A -- "percurso em profundidade" --> E
E -- "pendura filhos passo a passo" --> A
A -- "percurso espelhado" --> D
D -- "pendura filhos passo a passo" --> A
A --> Q["Contar árvores decide ambiguidade"]
E --> N["Contar derivações não decide nada"]
Pare e pense. Se eu contar derivações de uma cadeia e encontrar duas, isso prova que a gramática é ambígua? Pense na gramática com as produções que levam S a A\,B, A a a e B a b, e na cadeia formada pelos dois terminais, antes de responder.
Não prova nada: ali eu expando A antes de B ou o contrário, duas derivações distintas, e há uma única árvore lida em duas ordens, exatamente como o teorema promete. Moral: contar derivações encontra multiplicidade em gramáticas bem comportadas; contar árvores é o teste correto.
1.3 Ambiguidade: o problema central do projeto de linguagens
Uma gramática é ambígua quando alguma cadeia da linguagem tem duas ou mais árvores distintas. Repare que é propriedade da gramática, não da linguagem — e é por isso que o conserto existe. Conviver com ela não dá: a árvore é o objeto sobre o qual todas as fases seguintes trabalham, e duas árvores para o mesmo texto significam dois programas com o mesmo fonte.
flowchart TB
subgraph L1["Leitura 1 (vale quatorze)"]
direction TB
A1["E"] --> B1["E (num)"]
A1 --> C1["mais"]
A1 --> D1["E"]
D1 --> E1["E (num)"]
D1 --> F1["vezes"]
D1 --> G1["E (num)"]
end
subgraph L2["Leitura 2 (vale vinte)"]
direction TB
A2["E"] --> B2["E"]
B2 --> C2["E (num)"]
B2 --> D2["mais"]
B2 --> E2["E (num)"]
A2 --> F2["vezes"]
A2 --> G2["E (num)"]
end
A gramática ingênua de uma variável só permite que uma soma seja operando direto de uma multiplicação. A correção é dar a cada nível de precedência a sua própria variável:
\begin{aligned} E &\to E + T \mid T \\ T &\to T \times F \mid F \\ F &\to (\,E\,) \mid \texttt{num} \end{aligned}
O nível do produto é alcançável a partir do da soma, e o caminho de volta só existe passando por parênteses explícitos. A precedência virou hierarquia de variáveis, e o padrão generaliza: com k níveis, k+1 variáveis.
Isso resolve operadores diferentes; falta o agrupamento entre ocorrências do mesmo operador, e ele está no lado em que a variável recursiva aparece. Recursão à esquerda, E \to E - T, agrupa à esquerda, que é o que a aritmética exige — e é incompatível com a análise descendente, incômodo que cobra dois módulos adiante. Recursão à direita agrupa à direita, certo para atribuição encadeada e exponenciação. E há o terceiro caso: nem todo operador binário deve associar, e para algo como uma comparação encadeada a decisão certa é a gramática recusar, em vez de aceitar com algum agrupamento e deixar a semântica reclamar depois.
O segundo caso clássico tem outra natureza: o condicional com parte alternativa opcional, aninhado, e uma alternativa só — a quem ela pertence? Essa ambiguidade esteve no relatório original de ALGOL 60. A estratificação não ajuda, porque não há precedência a estabelecer; a saída é separar os comandos em casados (todo condicional com a sua alternativa) e abertos, exigindo que o ramo verdadeiro de um condicional com alternativa contenha apenas comandos casados.
O que esse exemplo ensina é o método. A desambiguação não veio de uma regra externa do tipo “em caso de dúvida, ligue ao mais próximo”, e sim de reescrever a gramática até que ela só admitisse a leitura desejada. A regra externa também funciona, e deixa a especificação ambígua para quem a lê.
E como você sustenta que a sua gramática não é ambígua? Por duas vias de forças bem diferentes. O argumento estrutural examina as produções e mostra que, em cada ponto de escolha, ela está determinada — pela estratificação nas expressões e, fora delas, por as produções de cada variável começarem por terminais distintos. A verificação empírica enumera todas as árvores de cadeias de teste, algo mecanizável pelo algoritmo devido de forma independente a John Cocke, a Tadao Kasami, em relatório técnico de 1965, e a Daniel Younger, em publicação de 1967. A assimetria é o ponto: a enumeração refuta e não confirma, e esse limite é matemático — decidir se uma gramática arbitrária é ambígua é indecidível, resultado estabelecido por David Cantor e por Robert Floyd, ambos em 1962, e por Noam Chomsky e Marcel-Paul Schützenberger, em 1963, por redução ao problema de correspondência de Post. Existem ainda linguagens inerentemente ambíguas, mas o exemplo canônico é artificial de propósito: achando ambiguidade na sua gramática, o mais provável é que ela esteja mal escrita.
1.4 Simplificação, e o que não simplificar
Quatro operações, e marcar quais são higiene e quais são pré-processamento evita estrago.
flowchart LR
G["Gramática recém-escrita"] --> P["Improdutivos<br/>ponto fixo de baixo para cima"]
P --> A["Inalcançáveis<br/>ponto fixo a partir do início"]
A --> N["Anuláveis<br/>caso base por vacuidade"]
N --> U["Unitárias<br/>fechamento por renomeação"]
P -.- H1["higiene: espere conjunto vazio"]
A -.- H2["higiene: espere conjunto vazio"]
U -.- H3["exigida por algoritmos,<br/>não é melhoria"]
Um símbolo é produtivo quando alguma derivação a partir dele alcança cadeia só de terminais; alcançável quando alguma forma sentencial derivada de S o contém; e uma variável é anulável quando deriva a cadeia vazia. Os três são cálculos de ponto fixo, e a ordem importa: remova os improdutivos primeiro, porque isso pode tornar outras variáveis inalcançáveis, e o contrário não acontece. No cálculo de anuláveis mora o defeito recorrente: a condição “todos os símbolos do corpo são anuláveis” é satisfeita por vacuidade no corpo vazio, e é essa vacuidade que dá partida — quem exige ao menos um símbolo no laço obtém o resultado errado sem aviso.
A quarta é a lição que eu mais quero que fique. Produção unitária é a de corpo formado por uma única variável, e remove-se por fechamento de renomeação. Olhe de novo para a gramática estratificada: as suas unitárias são a estratificação, os elos entre níveis. Removê-las gera a mesma linguagem, continua não ambígua e destrói a propriedade que se pagou para obter, além de inflar a gramática. Transformação canônica não é automaticamente melhoria — aplique quando um algoritmo posterior exigir, sobre uma cópia.
flowchart TB
C["Forma normal de Chomsky"] --> C1["toda árvore é binária"]
C1 --> C2["derivação com número<br/>de passos previsível"]
R["Forma normal de Greibach"] --> R1["todo passo consome<br/>um terminal"]
R1 --> R2["sem recursão à esquerda<br/>por construção"]
C2 --> X["Preço comum: dezenas de<br/>variáveis auxiliares sem sentido"]
R2 --> X
X --> Y["Entrada de algoritmo,<br/>não especificação de linguagem"]
As formas normais fecham a teoria pelo que garantem. Na forma normal de Chomsky, todo corpo é ou duas variáveis, ou um terminal; a garantia é que toda árvore é binária, e daí toda derivação de cadeia de comprimento n tem exatamente 2n-1 passos — saber o número de passos de antemão é o que torna a busca exaustiva viável. Na forma normal de Greibach, todo corpo começa por terminal e segue só com variáveis, de modo que todo passo consome um terminal e a recursão à esquerda some por construção. O preço, nos dois casos, é a legibilidade, e por isso aqui não convertemos nada: a análise descendente com um símbolo de antecipação não exige forma normal alguma.
1.5 A gramática do artefato conduzido
Tudo isso desemboca numa única atividade: escrever a gramática da linguagem — a primeira vez que o projeto produz artefato que não é código executável. Código se avalia executando; gramática, por leitura. Na implementação de referência da Peneira, ela é dado, com uma decisão que contraria o que a definição sugere: variáveis e terminais não ficam em listas separadas.
// Símbolos que derivam a cadeia vazia, direta ou indiretamente. Calculado
// por ponto fixo: começa com quem tem produção vazia e cresce enquanto
// alguma variável tiver um corpo inteiro formado por anuláveis.
std::set<std::string> anulaveis() const;
// Símbolos produtivos: os que derivam alguma cadeia só de terminais.
// Variável improdutiva costuma ser esquecimento — uma produção que ficou
// faltando.
std::set<std::string> produtivos() const;Variável é todo símbolo que aparece do lado esquerdo de alguma produção; terminal é todo o resto. Derivar em vez de declarar elimina uma classe inteira de erro — a variável declarada que nunca recebe produção vira terminal, e a checagem de improdutivos a encontra sem verificação dedicada. A gramática resultante tem onze variáveis, vinte e um terminais e vinte e duas produções, sem produção vazia e sem símbolo inútil, com recursão à esquerda nos operadores lógicos e à direita nas listas. O enumerador de árvores mede o que a teoria afirma: duas árvores na gramática de expressões sem estratificação, uma na estratificada. E as oito produções unitárias, se removidas, levariam a gramática de vinte e duas para quarenta e uma — implementei a remoção para medir e não a apliquei, porque essas oito unitárias são o argumento de não ambiguidade escrito na própria gramática.
Pergunta para a sua entrega. A gramática do seu grupo tem produção vazia? Se tiver, ela está lá porque a linguagem precisa dela, ou porque ninguém perguntou se um programa vazio deveria ser aceito?
1.6 Síntese
Gramática livre de contexto é a quádrupla de variáveis, terminais, produções e símbolo inicial, com exatamente uma variável à esquerda de cada produção — restrição de forma que o nome anuncia e que é perda de poder deliberada, paga com uma fase semântica separada. Derivar é aplicar produções a partir do inicial, com uma liberdade de ordem que as convenções mais à esquerda e mais à direita eliminam, nomeando de passagem as duas famílias de analisadores; a árvore guarda a estrutura, e a correspondência com as derivações canônicas é exata, razão pela qual o teste de ambiguidade conta árvores e não derivações. As técnicas de desambiguação atacam problemas distintos: estratificação para precedência, lado da recursão para associatividade, reescrita em construções casadas e abertas para o condicional. As simplificações são três pontos fixos e um fechamento, duas delas higiene cujo resultado esperado é conjunto vazio, e a remoção de unitárias é o caso instrutivo em que a transformação canônica é a coisa errada a fazer. Voltando à expressão da abertura: agora você sabe onde mora o quatorze — não no texto, não no processador, e sim na hierarquia de variáveis que impede uma soma de caber dentro de um produto sem parênteses.