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
1 Módulo 08: Gramáticas Livres de Contexto
Bem-vindo ao módulo em que a especificação vira projeto. Aqui você não vai aprender um algoritmo novo — vai aprender a julgar. Ao fim desta leitura, olhando para as regras que descrevem uma linguagem, você deve conseguir dizer qual operador tem precedência sobre qual, para que lado cada um agrupa e se aquele texto admite duas leituras.
1.1 O problema: duas árvores, dois resultados
Escreva no papel a expressão 2 + 3 \times 4 e diga quanto vale. Você respondeu quatorze e respondeu rápido, porque a escola lhe ensinou que multiplicação vem antes de soma. Agora inverta os papéis comigo: de onde o computador tira essa informação?
Não é do texto: são cinco símbolos e nenhum deles diz “multiplique primeiro”. Também não é do processador, que apenas executa instruções que alguém decidiu emitir em certa ordem. A precedência está em algum lugar, e a pergunta deste módulo é onde.
Vamos por partes, com uma gramática mínima para expressões: uma variável só, E, e quatro regras.
E \to E + E \mid E \times E \mid (\,E\,) \mid \texttt{num}.
Curta, legível — e profundamente defeituosa. Aplique essas regras à cadeia \texttt{num} + \texttt{num} \times \texttt{num} de dois jeitos: começando pela regra da soma, a multiplicação fica inteira dentro de um operando dela; começando pela regra do produto, é a soma que fica dentro.
Com os números 2, 3 e 4, a primeira vale quatorze e a segunda vale vinte. Repara: não é que o computador escolha mal — é que a especificação não diz o que ele deveria escolher, e qualquer escolha vira arbitrária. É esse buraco que o módulo serve para tapar, e adianto a resposta: a precedência mora na forma das regras, não numa tabela pendurada ao lado delas.
Uma palavra sobre o que este capítulo pressupõe, para que você possa decidir se precisa voltar antes de seguir.
Pressuponho as três coisas que os capítulos anteriores estabeleceram e nada além delas. A primeira é o vocabulário elementar de alfabetos, cadeias e linguagens, com \Sigma^* denotando o conjunto de todas as cadeias sobre um alfabeto e \varepsilon denotando a cadeia vazia. A segunda é a noção de reconhecimento como decisão de pertinência a um conjunto, e a familiaridade com os autômatos finitos como os reconhecedores do primeiro andar da hierarquia. A terceira, e a mais importante aqui, é o resultado negativo do capítulo sobre os limites das linguagens regulares: a demonstração, por bombeamento, de que nenhum autômato finito reconhece o conjunto das cadeias com parênteses balanceados. É desse resultado que este capítulo parte, e sem ele o formalismo apresentado aqui parece um enfeite em vez de uma necessidade.
Pressuponho também que você já viu um analisador léxico funcionando de ponta a ponta, produzindo símbolos léxicos a partir de um texto. Este capítulo trabalha um nível acima: os terminais das gramáticas que vou escrever não são caracteres, são as categorias de símbolo léxico que aquele analisador entrega. Se essa mudança de alfabeto ainda não estiver confortável, vale reler a seção sobre a interface entre as duas primeiras fases antes de continuar — é o ponto exato em que este capítulo se encaixa no anterior.
O que não pressuponho é qualquer contato prévio com gramáticas formais, com notação de produção ou com o problema da ambiguidade. Tudo isso é construído aqui, do início, e no ponto em que passa a ser necessário. Se você já leu a seção de sintaxe do manual de alguma linguagem e passou os olhos pelas regras sem entender o que elas eram, este capítulo é a explicação daquilo.
1.2 O formalismo, e por que ele tem esse nome
Antes de consertar, defina. O módulo anterior 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 em toda parte, aquilo foi a certidão de óbito de qualquer projeto que descreva a estrutura de um programa com expressões regulares.
Olhe de novo para L = \{a^n b^n\} e note onde mora a dificuldade. Não é contar; é contar duas coisas em correspondência, uma de cada lado de um centro. Se eu puder dizer “uma cadeia de L é vazia, ou é um a seguido de outra cadeia de L seguida de um b”, acabou: a descrição é finita e captura a correspondência. Escreva isso em símbolos e você escreveu 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: lá ele está na ponta, aqui está no meio, com terminal de cada lado. Se você guardar uma única imagem 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 da forma A \to \alpha, com A \in V e \alpha \in (V \cup \Sigma)^*.
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"]
Os terminais são os símbolos que aparecem nas cadeias geradas — e aqui é onde mais se confunde numa 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. A gramática do módulo passado operava sobre caracteres, porque descrevia o interior dos símbolos léxicos; esta opera sobre símbolos léxicos, porque descreve como eles se combinam.
As variáveis são os nomes das construções sintáticas: expressão, declaração, bloco, lista de argumentos. Não aparecem nas cadeias geradas; existem só durante a geração, como andaimes que se desmontam no fim. A variável inicial nomeia a construção mais externa, e trocá-la muda a linguagem gerada. E as produções têm duas assimetrias: do lado esquerdo, exatamente um símbolo, obrigatoriamente uma variável; do lado direito, uma sequência qualquer de variáveis e terminais.
Dessa assimetria vem o nome. Numa gramática mais geral, nada impediria uma produção que diga “substitua A por \alpha, mas só quando A estiver entre um x à esquerda e um y à direita” — a substituição dependeria do contexto. A definição acima proíbe isso pela forma: com um símbolo só à esquerda, não sobra espaço para escrever contexto nenhum. Logo, se A \to \alpha é produção, toda ocorrência de A, em qualquer derivação, pode virar \alpha. Sempre, sem consultar a vizinhança.
Pare e pense. Essa restrição parece uma perda de poder. Por que ela seria uma vantagem? Dica: pense em quantas versões da regra da condicional você precisaria escrever se a substituição dependesse de onde a condicional aparece.
A vantagem é essa. Escrevo a produção da expressão condicional uma vez e ela vale dentro de um laço, de uma função, de outra condicional. O formalismo fica composicional, e o reconhecimento trata cada variável uma vez, em vez de cada par variável-contexto. O preço vem depois: regras como “todo nome usado precisa ter sido declarado” são sensíveis ao contexto, e nenhuma gramática livre de contexto as captura de forma praticável. É por isso que existe uma fase de análise semântica separada.
Vale a conexão que costuma provocar reconhecimento em quem já programa. No fim dos anos 1950, John Backus propôs, no projeto da linguagem ALGOL, uma notação para descrever formalmente a sintaxe de uma linguagem, e Peter Naur, ao editar o relatório de ALGOL 60, adaptou-a e a empregou sistematicamente — a notação ficou conhecida pelas iniciais dos dois. Aquelas linhas com barras verticais que você pulou ao consultar a documentação de alguma linguagem são gramáticas livres de contexto.
O que muda o formalismo é a variante estendida dos manuais modernos: asterisco para “zero ou mais”, interrogação para “opcional”. Nada disso existe na definição — e nada disso aumenta o poder, porque a repetição vira recursão e o opcional vira duas produções. Uma regra A \to \beta\,\{\gamma\} reescreve-se com uma variável auxiliar, A \to \beta\,R e R \to \gamma\,R \mid \varepsilon; e uma regra com parte opcional vira duas produções, uma com e outra sem essa parte.
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 do que duplicar: você introduziu uma produção vazia numa gramática que talvez não precisasse de nenhuma, e produção vazia é a principal fonte de erro no cálculo dos conjuntos que orientam o analisador descendente.
1.3 Derivações e árvores: a relação exata
Gramática é sistema de reescrita, e reescrever precisa de definição precisa. Escrevemos \gamma\,A\,\delta \Rightarrow \gamma\,\alpha\,\delta quando A \to \alpha está em P. Uma cadeia obtida de S por zero ou mais passos é forma sentencial; se só tiver terminais, é sentença. E a linguagem gerada é L(G) = \{\, w \mid S \Rightarrow^* w \,\}.
Duas observações carregam o módulo inteiro. A definição não diz qual variável expandir quando há várias na forma sentencial, nem qual produção aplicar quando a variável escolhida tem várias. São liberdades de naturezas diferentes: qual variável é escolha de ordem; qual produção é escolha de estrutura. A primeira não altera o resultado; a segunda altera tudo. Distinguir as duas é o que separa quem entende ambiguidade de quem a confunde com outra coisa.
A liberdade de ordem se elimina por convenção: uma derivação é mais à esquerda quando expande sempre a variável mais à esquerda, e mais à direita no caso simétrico. Não é preciosismo — essas convenções nomeiam as duas grandes famílias de analisadores sintáticos. O descendente constrói uma derivação mais à esquerda, partindo da variável inicial; o ascendente reconstrói uma derivação mais à direita ao contrário, partindo da entrada.
A árvore de derivação descarta a ordem e guarda a estrutura. É uma árvore ordenada e rotulada com raiz S, nós internos rotulados por variáveis, folhas rotuladas por terminais, e — esta é a cláusula que impede desenhar qualquer árvore bonita e alegar que ela deriva a cadeia — filhos de cada nó interno correspondendo a uma produção que existe na gramática.
E aí vem o ponto técnico mais importante do módulo: para toda cadeia da linguagem, há uma bijeção entre as suas árvores de derivação e as suas derivações mais à esquerda, e outra entre as árvores e as derivações mais à direita. Cada árvore corresponde a exatamente uma derivação de cada tipo. A demonstração é uma indução curta: percorrer a árvore em profundidade, da esquerda para a direita, produz a derivação; e cada passo da derivação diz onde pendurar os próximos filhos na árvore parcial.
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"]
Pergunta que decide o resto do módulo. Se eu contar derivações de uma cadeia e encontrar duas, isso prova que a gramática é ambígua? Pense na gramática S \to A\,B, A \to a, B \to b e na cadeia ab antes de responder.
Não prova nada. Ali eu posso expandir A antes de B ou o contrário, o que dá duas derivações distintas — e há uma única árvore, lida em ordens diferentes, uma mais à esquerda e a outra mais à direita, como o teorema promete. Moral: contar derivações encontra multiplicidade em gramáticas bem comportadas; contar árvores é o teste correto.
Uma última distinção. A árvore que acabei de definir também se chama concreta: registra cada produção aplicada e toda a pontuação. A árvore sintática abstrata, derivada dela, guarda só qual operação e quais operandos. Falarei sempre de árvores concretas daqui em diante — e por isso a estratificação a seguir, embora infle a concreta, não custa nada depois.
1.4 Ambiguidade: o problema central do projeto de linguagens
Uma gramática é ambígua quando existe alguma cadeia da linguagem com duas ou mais árvores de derivação distintas — o que, pelo teorema da correspondência, equivale a existir cadeia com duas derivações mais à esquerda distintas. Repare na formulação: ambiguidade é propriedade da gramática, não da linguagem — a mesma linguagem pode ter uma gramática ambígua e outra que não é, e é isso que torna o conserto possível.
Por que não conviver com ela? Porque a árvore não é subproduto: é o objeto sobre o qual todas as fases seguintes trabalham, e duas árvores para o mesmo texto significam dois programas com o mesmo fonte — a pergunta “o que este programa faz?” deixa de ter resposta. Há o lado do processo: os analisadores eficientes deste curso são determinísticos, e a ambiguidade se manifesta na construção deles como conflito, duas entradas competindo pela mesma célula da tabela, descoberto tarde e com diagnóstico ruim. E há o lado de quem lê: especificação ambígua faz o manual mentir, porque a escolha real fica enterrada numa declaração de precedência dentro do código do analisador.
Agora as técnicas, que atacam problemas diferentes. Comece perguntando o que a gramática da abertura permite e não deveria. Ela permite que uma soma seja operando direto de uma multiplicação sem parênteses, e vice-versa, porque há uma variável só e ela gera tudo. 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}
flowchart TB
E["E — nível da soma"] --> T["T — nível do produto"]
T --> F["F — operandos atômicos"]
F -. "somente com parênteses explícitos" .-> E
T -.- N1["um produto cabe dentro de uma soma"]
E -.- N2["uma soma não cabe dentro de um produto"]
Leia as produções como afirmações sobre o que contém o quê: uma soma é uma soma mais um produto, ou um produto sozinho; um produto é um produto vezes um átomo, ou um átomo sozinho; um átomo é um número ou uma expressão inteira entre parênteses. A linguagem gerada é a mesma de antes; o que mudou foi a estrutura das árvores.
Por que a estratificação elimina a ambiguidade
O nível do produto é alcançável a partir do nível da soma, e o caminho de volta só existe passando pelos operandos atômicos e, portanto, por parênteses explícitos. A consequência é direta: um produto pode aparecer dentro de uma soma, e uma soma não pode aparecer dentro de um produto sem parênteses. A precedência virou propriedade da hierarquia de variáveis, legível na própria especificação.
O padrão generaliza: com k níveis de precedência, escrevem-se k+1 variáveis, cada nível combinando a si mesmo com o imediatamente mais forte, e no fundo a variável dos átomos com a produção de parênteses que reabre o ciclo. E a alternativa não é uma gramática menor e correta: é uma menor e ambígua.
Isso resolve a precedência entre operadores diferentes. Falta o agrupamento entre ocorrências do mesmo operador. Tome uma subtração encadeada com os valores 10, 4 e 3: agrupando à esquerda dá três, à direita dá nove. A escolha está no lado em que a variável recursiva aparece.
A produção E \to E - T põe a ocorrência recursiva antes do operador e força agrupamento à esquerda, porque a subexpressão com as subtrações anteriores fica no filho esquerdo. É o que a aritmética exige dos operadores binários usuais. O incômodo aparece dois módulos adiante: essa forma é incompatível com a análise descendente, porque o analisador que tentar expandi-la chamando a si mesmo entra em recursão infinita sem consumir símbolo algum.
A produção E \to T - E põe a ocorrência recursiva depois do operador e força agrupamento à direita. Gera as mesmas cadeias, é igualmente não ambígua, e dá o resultado errado para a subtração. É a escolha certa, porém, para atribuição encadeada, exponenciação e listas sem operador entre os elementos.
Nem todo operador binário deve associar. Uma cadeia como a < b < c não tem significado natural na maioria das linguagens, e a decisão certa é a gramática recusar, em vez de aceitar com algum agrupamento e deixar a semântica reclamar depois. Recusar cedo é mais barato que explicar tarde.
O segundo caso clássico tem outra natureza e exige uma terceira técnica. Aparece em toda linguagem cujo comando condicional tem parte alternativa opcional. Tome um texto com dois condicionais aninhados e uma única parte alternativa: a quem ela pertence? Uma árvore põe a alternativa no condicional externo; a outra, no interno. As duas são legítimas, e os comportamentos diferem. Essa ambiguidade esteve no relatório original de ALGOL 60 e foi apontada na literatura logo em seguida.
A estratificação não ajuda, porque não há precedência a estabelecer: há uma decisão sobre a qual de duas construções aninhadas um sufixo pertence. A saída é reescrever a gramática para que só a leitura desejada seja derivável, separando os comandos em duas categorias. Um comando casado é aquele em que todo condicional tem a sua alternativa; um comando aberto é o que termina com condicional sem alternativa. A chave está em exigir que o ramo verdadeiro de um condicional com alternativa contenha apenas comandos casados, o que força a ligação ao condicional mais próximo.
O que esse exemplo ensina é o método, não a solução. A desambiguação não foi feita acrescentando uma regra externa do tipo “em caso de dúvida, ligue ao mais próximo”, e sim reescrevendo a gramática até que ela só admitisse a leitura desejada. A regra externa também funciona, mas resolve o conflito no analisador e deixa a especificação ambígua para quem a lê.
E como você sustenta a afirmação de que a sua gramática não é ambígua? De duas maneiras, com forças bem diferentes. A primeira é o argumento estrutural: examinar as produções e mostrar que, em cada ponto onde poderia haver escolha, ela está determinada — pela hierarquia de estratificação nas expressões e, fora delas, pelo fato de as produções de cada variável começarem por terminais distintos. A segunda é a verificação empírica: enumerar todas as árvores de um conjunto de cadeias de teste e conferir que cada uma tem exatamente uma. Isso é mecanizável por um algoritmo clássico, 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 entre as duas é o ponto. A enumeração refuta: achou duas árvores, a gramática é ambígua. Ela não confirma: não achar segunda árvore em vinte cadeias de teste é evidência, não demonstração. E esse limite não é descuido de ferramenta — é matemático.
Duas notícias ruins fecham a seção. A primeira: existem linguagens inerentemente ambíguas, para as quais toda gramática que as gera é ambígua. O exemplo canônico é a união de \{a^n b^n c^m d^m\} com \{a^n b^m c^m d^n\}, cujo problema está nas cadeias que pertencem às duas partes ao mesmo tempo. É o único caso em que falar de “linguagem ambígua” é correto, e ele é artificial de propósito: ao achar ambiguidade na sua gramática, o mais provável de longe é que ela esteja mal escrita.
A segunda é mais séria: decidir se uma gramática livre de contexto arbitrária é ambígua é indecidível. O resultado foi estabelecido no início da década de 1960, em trabalhos independentes de David Cantor e de Robert Floyd, ambos de 1962, e de Noam Chomsky e Marcel-Paul Schützenberger, de 1963, por redução ao problema de correspondência de Post; também é indecidível saber se duas gramáticas geram a mesma linguagem. A consequência prática você vai sentir: nenhum gerador de analisadores dirá “sua gramática é ambígua”; ele dirá que o método escolhido não consegue construir um analisador determinístico para ela. Diante de um conflito, a pergunta certa não é “onde está a ambiguidade?”, e sim “por que esta gramática está fora do alcance deste método?”.
1.5 Simplificação: o que remover, e o que não
Mudo de assunto: até aqui, escrever gramáticas boas; agora, transformá-las removendo o que não serve. São quatro operações; marco quais são higiene e quais são pré-processamento, porque aplicá-las indiscriminadamente é erro.
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 uma cadeia só de terminais. O cálculo é um ponto fixo: comece pelos terminais, produtivos por definição, e repita — havendo produção cujo corpo tem todos os símbolos já marcados, marque a variável do lado esquerdo. Variável improdutiva é quase sempre defeito real: o caso típico é aquela cujas produções a referenciam de novo sem saída para terminais, e então ela não gera cadeia alguma.
Um símbolo é alcançável quando alguma forma sentencial derivada de S o contém. Outro ponto fixo, agora descendente: comece com a variável inicial e, para cada variável marcada, marque tudo o que aparece nos corpos das suas produções. Inalcançável costuma ser resto de reescrita.
A ordem das duas remoções importa, e a assimetria não é óbvia. Remova os improdutivos primeiro e os inalcançáveis depois. Remover uma variável improdutiva apaga as produções que a mencionam, e isso pode tornar outras variáveis inalcançáveis, dando trabalho novo à segunda passagem. O contrário não acontece, porque a produtividade depende do que o símbolo deriva, não de quem o alcança.
Uma variável é anulável quando deriva a cadeia vazia. Terceiro ponto fixo, e o mais sutil: comece marcando as variáveis com produção de corpo vazio e repita marcando toda variável cuja produção tenha corpo formado só de anuláveis. Aqui mora um erro de implementação recorrente: a condição “todos os símbolos do corpo são anuláveis” é satisfeita por vacuidade quando o corpo é vazio, e é essa vacuidade que dá partida ao processo — quem escreve o laço exigindo ao menos um símbolo obtém o resultado errado sem nenhum aviso. A remoção das vazias acrescenta a cada produção as variantes obtidas omitindo subconjuntos dos anuláveis, o que infla a gramática exponencialmente.
Escreva a gramática sem produções vazias desde o início. Lista com pelo menos um elemento se escreve L \to x\,L \mid x, e listas que admitem zero elementos geralmente admitem porque ninguém pensou se deveriam. Um programa vazio ou um bloco sem comandos custam tratamento explícito em todas as fases seguintes, e o cálculo de anuláveis serve de verificação: o conjunto deve sair vazio.
Falta a quarta, e é a lição que eu mais quero que fique. Uma produção é unitária quando o corpo é uma única variável. Remove-se por fechamento: para cada variável, calcule quem ela alcança só por produções unitárias e faça-a herdar as produções não unitárias desses alcançados. O algoritmo é fácil; o problema é outro. Olhe de novo para a gramática estratificada: ela tem exatamente duas produções unitárias, e elas são a estratificação, os elos que ligam um nível ao imediatamente mais forte.
A simplificação que mais frequentemente piora a gramática
Remover as unitárias de uma gramática estratificada gera a mesma linguagem, continua não ambígua, e destrói a propriedade que se pagou para obter: já não se lê nas produções qual operador tem precedência sobre qual, porque a hierarquia foi achatada. Ela existe porque certos algoritmos a exigem como pré-processamento, não porque a gramática fique melhor. E o efeito quantitativo surpreende: é comum a gramática quase dobrar de tamanho ao ser “simplificada”.
Registre o critério geral: transformação canônica não é automaticamente melhoria — aplique-a quando um algoritmo posterior exigir, sobre uma cópia.
1.6 Formas normais: apresentadas pelo que garantem
Fecho a teoria com as duas formas normais clássicas, em tratamento conceitual: o que cada uma garante, e por que este curso não converte nada.
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"]
Uma gramática está na forma normal de Chomsky quando toda produção tem por corpo ou duas variáveis, ou um único terminal. Toda linguagem livre de contexto tem uma gramática nessa forma, por construção: removem-se vazias, unitárias e símbolos inúteis, substitui-se cada terminal que apareça em corpo longo por uma variável nova, e quebram-se os corpos longos em produções binárias. A garantia é estrutural e forte: toda árvore é binária, exceto pelas folhas, e daí decorre que toda derivação de uma 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.
Uma gramática está na forma normal de Greibach quando o corpo de toda produção começa por um terminal e segue só com variáveis. A garantia é operacionalmente atraente: todo passo consome exatamente um terminal, de modo que o reconhecedor nunca gira sem progredir. Em particular, a recursão à esquerda desaparece por construção.
O preço, nos dois casos, é a legibilidade: a conversão de uma gramática real produz dezenas de variáveis auxiliares sem significado. São formas de entrada para algoritmos, não de especificação — e é por isso que aqui não convertemos nada. A técnica de análise deste curso é a descendente com um símbolo de antecipação, e o que ela exige não é forma normal alguma: é ausência de recursão à esquerda e ausência de produções da mesma variável começando pelos mesmos símbolos, duas transformações locais que preservam quase toda a legibilidade.
1.7 O caso conduzido
Tudo o que este módulo estabeleceu é matéria-prima para uma única atividade: escrever a gramática da linguagem que o curso constrói — a primeira vez que o projeto produz um artefato que não é código executável. Um trecho de código se avalia executando; uma gramática avalia-se por leitura. A precedência está legível na hierarquia de variáveis? A associatividade está no lado certo da recursão? Existe cadeia com duas árvores? Existe produção vazia dispensável?
1.7.1 6.1 Da notação estendida para o formalismo puro
A linguagem Peneira foi desenhada, lá no primeiro capítulo, escrevendo o programa pretendido e olhando para ele. Aquele desenho ficou anotado em notação estendida, com asterisco para repetição e interrogação para as partes opcionais. Agora preciso convertê-lo para o formalismo da Definição 1.1, e a conversão é o exercício em que este capítulo desemboca.
Antes das produções, a representação. Uma decisão de projeto vale ser explicada, porque ela contraria o que a Definição 1.1 sugere:
08_gramatica.h
#ifndef PENEIRA_08_GRAMATICA_H
#define PENEIRA_08_GRAMATICA_H
#include <set>
#include <string>
#include <vector>
namespace peneira {
// Uma produção: a variável do lado esquerdo e a sequência de símbolos do lado
// direito. Corpo vazio representa a produção vazia, que a teoria escreve com
// épsilon.
struct Producao {
std::string variavel;
std::vector<std::string> corpo;
bool ehVazia() const { return corpo.empty(); }
};
// Gramática livre de contexto: variáveis, terminais, produções e símbolo
// inicial.
//
// Não guardo variáveis e terminais em listas separadas. Variável é todo
// símbolo que aparece do lado esquerdo de alguma produção; terminal é todo o
// resto que aparece em algum corpo. Derivar em vez de declarar elimina a
// classe de erro em que um símbolo é declarado variável e nunca recebe
// produção — ele simplesmente vira terminal, e a checagem de símbolos
// improdutivos o encontra.
//
// O nome do formalismo se explica na estrutura: a substituição de uma
// variável depende apenas dela, nunca do que está em volta. Por isso o lado
// esquerdo de toda produção tem exatamente um símbolo.
class Gramatica {
public:
Gramatica(std::string nome, std::string inicial);
void adicionar(const std::string& variavel,
const std::vector<std::string>& corpo);
const std::string& nome() const noexcept;
const std::string& inicial() const noexcept;
const std::vector<Producao>& producoes() const noexcept;
std::set<std::string> variaveis() const;
std::set<std::string> terminais() const;
std::vector<Producao> producoesDe(const std::string& variavel) const;
bool ehVariavel(const std::string& simbolo) const;
std::string formatar() const;
// 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;
// Símbolos alcançáveis a partir do inicial. Variável inalcançável costuma
// ser resto de uma reescrita da gramática.
std::set<std::string> alcancaveis() const;
// Inúteis = improdutivos ou inalcançáveis. A ordem de remoção importa:
// tirar improdutivos primeiro pode tornar outras variáveis inalcançáveis,
// e o contrário não é verdade.
Gramatica semSimbolosInuteis(std::string novoNome) const;
// Produções unitárias: corpo formado por uma única variável, como
// `expr -> exprE`. Não produzem terminal algum; só renomeiam.
std::vector<Producao> producoesUnitarias() const;
// Remove as unitárias por fechamento: cada variável herda diretamente as
// produções não unitárias de tudo que ela alcança por renomeação.
//
// Cuidado ao aplicar: a estratificação por precedência PRODUZ unitárias de
// propósito — `expr -> exprE` é o elo entre dois níveis. Removê-las
// encurta a derivação e destrói a hierarquia que tornava a precedência
// legível na própria gramática. A transformação existe porque certos
// algoritmos a exigem, não porque a gramática fique melhor.
Gramatica semProducoesUnitarias(std::string novoNome) const;
std::size_t quantidadeDeProducoes() const noexcept;
private:
std::string nome_;
std::string inicial_;
std::vector<Producao> producoes_;
};
} // namespace peneira
#endif // PENEIRA_08_GRAMATICA_H
A definição formal enumera V e \Sigma como componentes independentes da quádrupla, e eu não os guardo em listas separadas. Variável é todo símbolo que aparece do lado esquerdo de alguma produção; terminal é todo o resto que aparece em algum corpo. Derivar em vez de declarar elimina uma classe inteira de erro — a variável declarada que nunca recebe produção. Nessa representação ela simplesmente vira terminal, e a checagem de símbolos improdutivos da subseção 4.1 a encontra sem que eu precise de uma verificação dedicada.
A gramática propriamente dita:
08_gramaticas.cpp
#include "08_gramaticas.h"
#include <set>
#include "01_diagnostico.h"
#include "01_source.h"
#include "07_lexer.h"
namespace peneira {
Gramatica gramaticaPeneira() {
Gramatica g("gramatica da Peneira", "programa");
// A repetição da notação estendida vira recursão. Escolhi recursão à
// DIREITA para as listas de declaração e de ação: elas não têm operador
// entre os elementos, então a associatividade não significa nada, e a
// recursão à direita produz árvores que se leem de cima para baixo na
// ordem do texto.
g.adicionar("programa", {"listaDecl"});
g.adicionar("listaDecl", {"decl", "listaDecl"});
g.adicionar("listaDecl", {"decl"});
g.adicionar("decl", {"declPadrao"});
g.adicionar("decl", {"blocoRegra"});
g.adicionar("declPadrao", {"pattern", "ID", "=", "PADRAO", ";"});
g.adicionar("blocoRegra", {"rule", "{", "listaAcao", "}"});
g.adicionar("listaAcao", {"acao", "listaAcao"});
g.adicionar("listaAcao", {"acao"});
// O opcional da notação estendida vira duas produções. Não há como
// representar "opcional" numa gramática livre de contexto senão assim, e é
// por isso que a versão em BNF é mais longa que o design.
g.adicionar("acao", {"on", "ID", "(", "ID", ")", "=>", "emit", "(", "TEXTO",
",", "expr", ")", ";"});
g.adicionar("acao", {"on", "ID", "(", "ID", ")", "where", "expr", "=>",
"emit", "(", "TEXTO", ",", "expr", ")", ";"});
// Aqui o lado da recursão IMPORTA. Recursão à esquerda dá associatividade
// à esquerda: "a or b or c" agrupa como "(a or b) or c", que é o que se
// espera de um operador binário. Trocar o lado mudaria o agrupamento sem
// mudar a linguagem reconhecida — mesmo conjunto de cadeias, árvores
// diferentes, semântica diferente no módulo 12.
g.adicionar("expr", {"expr", "or", "exprE"});
g.adicionar("expr", {"exprE"});
g.adicionar("exprE", {"exprE", "and", "comparacao"});
g.adicionar("exprE", {"comparacao"});
// A comparação NÃO é recursiva: "a > b > c" não faz sentido nesta
// linguagem, e a gramática recusa em vez de aceitar e deixar a semântica
// resolver. Recusar cedo é mais barato que explicar depois.
g.adicionar("comparacao", {"primaria", "OPREL", "primaria"});
g.adicionar("comparacao", {"primaria"});
g.adicionar("primaria", {"ID"});
g.adicionar("primaria", {"NUMERO"});
g.adicionar("primaria", {"TEXTO"});
g.adicionar("primaria", {"value", "(", "ID", ")"});
g.adicionar("primaria", {"(", "expr", ")"});
return g;
}
Gramatica gramaticaExpressaoAmbigua() {
Gramatica g("expressao sem estratificacao", "E");
g.adicionar("E", {"E", "+", "E"});
g.adicionar("E", {"E", "*", "E"});
g.adicionar("E", {"num"});
return g;
}
Gramatica gramaticaExpressaoEstratificada() {
Gramatica g("expressao estratificada", "E");
// Um nível por precedência, do operador que liga mais fraco para o que
// liga mais forte. A recursão à esquerda em cada nível dá a
// associatividade à esquerda.
g.adicionar("E", {"E", "+", "T"});
g.adicionar("E", {"T"});
g.adicionar("T", {"T", "*", "F"});
g.adicionar("T", {"F"});
g.adicionar("F", {"num"});
return g;
}
Gramatica gramaticaCondicionalAmbigua() {
Gramatica g("condicional ambiguo", "S");
g.adicionar("S", {"se", "c", "entao", "S"});
g.adicionar("S", {"se", "c", "entao", "S", "senao", "S"});
g.adicionar("S", {"cmd"});
return g;
}
Gramatica gramaticaCondicionalDesambiguada() {
Gramatica g("condicional desambiguado", "S");
// A separação em "casado" e "aberto" força o `senao` a se ligar ao `se`
// mais próximo: o ramo verdadeiro de um condicional com alternativa só
// aceita comandos que já tenham a sua própria alternativa.
g.adicionar("S", {"casado"});
g.adicionar("S", {"aberto"});
g.adicionar("casado", {"se", "c", "entao", "casado", "senao", "casado"});
g.adicionar("casado", {"cmd"});
g.adicionar("aberto", {"se", "c", "entao", "S"});
g.adicionar("aberto", {"se", "c", "entao", "casado", "senao", "aberto"});
return g;
}
Gramatica gramaticaComDefeitos() {
Gramatica g("gramatica com defeitos", "S");
g.adicionar("S", {"A", "B"});
g.adicionar("S", {"a"});
g.adicionar("A", {"a", "A"});
g.adicionar("A", {}); // produção vazia: A é anulável
g.adicionar("B", {"b"});
g.adicionar("C", {"c", "C"}); // improdutiva: nunca chega a terminais
g.adicionar("D", {"d"}); // inalcançável a partir de S
return g;
}
std::vector<std::string> terminaisDe(
const std::vector<SimboloLexico>& simbolos) {
static const std::set<std::string> comparadores{"<", ">", "==",
"!=", ">=", "<="};
std::vector<std::string> terminais;
for (const SimboloLexico& s : simbolos) {
switch (s.categoria) {
case Categoria::PalavraReservada:
terminais.push_back(s.lexema);
break;
case Categoria::Identificador:
terminais.push_back("ID");
break;
case Categoria::Numero:
terminais.push_back("NUMERO");
break;
case Categoria::Texto:
terminais.push_back("TEXTO");
break;
case Categoria::Padrao:
terminais.push_back("PADRAO");
break;
case Categoria::Pontuacao:
terminais.push_back(comparadores.count(s.lexema) > 0
? std::string("OPREL")
: s.lexema);
break;
case Categoria::FimDeArquivo:
case Categoria::Invalido:
break;
}
}
return terminais;
}
std::vector<std::string> terminaisDoPrograma(const std::string& fonte) {
const SourceFile arquivo = SourceFile::fromText("trecho.pen", fonte);
DiagnosticBag diagnosticos;
AnalisadorLexico lexer(arquivo, diagnosticos);
return terminaisDe(lexer.todos());
}
} // namespace peneira
Impressa, ela cabe em onze linhas:
programa -> listaDecl
listaDecl -> decl listaDecl | decl
decl -> declPadrao | blocoRegra
declPadrao -> pattern ID = PADRAO ;
blocoRegra -> rule { listaAcao }
listaAcao -> acao listaAcao | acao
acao -> on ID ( ID ) => emit ( TEXTO , expr ) ;
| on ID ( ID ) where expr => emit ( TEXTO , expr ) ;
expr -> expr or exprE | exprE
exprE -> exprE and comparacao | comparacao
comparacao -> primaria OPREL primaria | primaria
primaria -> ID | NUMERO | TEXTO | value ( ID ) | ( expr )Onze variáveis, vinte e um terminais, vinte e duas produções. Quatro decisões de tradução merecem defesa, e cada uma delas é uma aplicação direta de algo estabelecido nas seções anteriores.
A repetição virou recursão, e o lado importa em um caso e não no outro. Para as listas de declaração e de ação escolhi recursão à direita. Elas não têm operador entre os elementos, de modo que a discussão de associatividade da subseção 3.4 não se aplica — não há o que agrupar —, e a recursão à direita produz árvores que se leem de cima para baixo na ordem do texto. Para os operadores lógicos, escolhi recursão à esquerda, e aí a escolha é semântica: ela agrupa uma disjunção de três termos como a disjunção dos dois primeiros com o terceiro. Trocar o lado não mudaria a linguagem reconhecida e mudaria as árvores, e portanto o significado que a análise semântica vai extrair delas.
O opcional virou duas produções. A ação com condição e a ação sem condição são produções distintas, e não há alternativa: uma gramática livre de contexto não tem como dizer “opcional”. É a razão de a versão em formalismo puro ser mais longa que o desenho original, e é honesto reconhecer que a notação estendida existe justamente porque essa expansão é chata de escrever à mão. Note que não caí na armadilha que registrei ao final da subseção 1.4 — não criei uma variável anulável para a parte opcional.
A comparação não é recursiva. Encadear operadores relacionais não faz sentido nesta linguagem, e a gramática recusa em vez de aceitar com algum agrupamento e deixar a semântica reclamar depois. É exatamente a recomendação do fim da subseção 3.4, aplicada.
Não há produção vazia, de propósito. Escrevi as listas exigindo pelo menos um elemento. Um programa vazio ou um bloco de regra sem ação nenhuma não são úteis, e proibi-los na gramática evita tratar o caso em todas as fases seguintes. O cálculo de anuláveis da subseção 4.3 confirma: o conjunto sai vazio, como recomendei que saísse.
A checagem de higiene também passa limpa, com os dois conjuntos vazios:
11 variaveis, 21 terminais, 22 producoes
Simbolos improdutivos: {}
Simbolos inalcancaveis: {}1.7.2 6.2 O instrumento que transforma ambiguidade em contagem
O argumento de não ambiguidade da subseção 3.6 tem duas pernas, e a segunda — a verificação empírica — pede uma ferramenta. Construí uma: um enumerador exaustivo de árvores de derivação, no espírito do algoritmo de Cocke, Younger e Kasami, generalizado para corpos de qualquer tamanho como comentei na subseção 5.3.
08_derivacao.h
#ifndef PENEIRA_08_DERIVACAO_H
#define PENEIRA_08_DERIVACAO_H
#include <cstddef>
#include <memory>
#include <string>
#include <vector>
#include "08_gramatica.h"
namespace peneira {
// Nó de uma árvore de derivação. Folha é o nó sem filhos, e o rótulo dela é um
// terminal; nó interno é rotulado por uma variável, e seus filhos são o corpo
// da produção aplicada.
struct NoDerivacao;
using ArvorePtr = std::shared_ptr<const NoDerivacao>;
struct NoDerivacao {
std::string rotulo;
std::vector<ArvorePtr> filhos;
};
// Enumera TODAS as árvores de derivação de uma sequência de terminais.
//
// É um reconhecedor exaustivo, no espírito do algoritmo de Cocke, Younger e
// Kasami: preenche uma tabela indexada por (variável, início, fim) e combina
// os pedaços. Não é o analisador sintático do projeto — aquele chega no módulo
// 10, é linear e produz UMA árvore. Este é instrumento de estudo: serve para
// responder "quantas árvores existem?", e é assim que a ambiguidade deixa de
// ser afirmação e vira contagem.
//
// Exige gramática SEM produções vazias. Com elas, um span de tamanho zero
// admitiria infinitas derivações e a enumeração não terminaria. A restrição
// está aqui em vez de ser contornada porque as gramáticas que interessam a
// este módulo são todas livres de vazio.
//
// `limite` corta a coleta por célula, para que uma gramática muito ambígua não
// exploda a memória. Quando o corte age, o resultado é "pelo menos isto", e o
// chamador é avisado por `atingiuLimite`.
struct ResultadoDerivacao {
std::vector<ArvorePtr> arvores;
bool atingiuLimite = false;
};
ResultadoDerivacao derivacoes(const Gramatica& g,
const std::vector<std::string>& entrada,
std::size_t limite);
// Desenho da árvore em texto, por indentação.
std::string desenhar(const ArvorePtr& raiz);
// Sequência de formas sentenciais da derivação mais à esquerda que a árvore
// representa. É o que torna precisa a relação entre árvore e derivação: cada
// árvore corresponde a exatamente uma derivação mais à esquerda.
std::vector<std::string> derivacaoMaisAEsquerda(const Gramatica& g,
const ArvorePtr& raiz);
// Frontier da árvore: a cadeia de terminais que ela deriva.
std::vector<std::string> fronteira(const ArvorePtr& raiz);
} // namespace peneira
#endif // PENEIRA_08_DERIVACAO_H
Este enumerador não é o analisador sintático do projeto e não vai virar um. Ele é exponencial no pior caso e produz todas as árvores; o do capítulo sobre análise descendente é linear e produz uma. São instrumentos de propósitos opostos, e confundi-los seria erro de projeto. Aqui o objetivo é responder “quantas árvores existem?”, e é assim que a ambiguidade deixa de ser afirmação a ser acreditada e vira contagem.
Duas particularidades da implementação valem nota, porque as duas realizam decisões teóricas do capítulo.
A memoização é marcada antes da descida, com lista vazia. Isso faz a recursão à esquerda terminar: uma variável que precise de si mesma no mesmo intervalo da entrada encontra a lista vazia e desiste daquele caminho — comportamento correto, já que sem consumir entrada não há progresso. Sem essa marca prévia, a produção recursiva à esquerda dos operadores lógicos giraria para sempre. É a mesma dificuldade que, no capítulo sobre análise descendente, obriga a eliminar a recursão à esquerda antes de gerar o analisador; aqui ela é contornada pela estrutura da tabela em vez de por transformação da gramática.
E o enumerador exige gramática sem produção vazia. Com elas, um intervalo de tamanho zero admitiria infinitas derivações e a enumeração não terminaria. A restrição está declarada em vez de contornada, e ela é satisfeita por construção pelas gramáticas deste capítulo — o que é mais um dividendo da recomendação da subseção 4.3.
1.7.3 6.3 A contagem sobre os dois exemplos clássicos
Com o instrumento na mão, os dois exemplos das subseções 3.3 e 3.5 deixam de ser desenhos no papel. Sobre a gramática de expressões sem estratificação e sobre a estratificada, alimentando as duas com a mesma cadeia:
"num + num * num" -> 2 arvore(s) (sem estratificacao)
"num + num * num" -> 1 arvore(s) (estratificada)Duas contra uma. É a demonstração inteira da subseção 3.3, agora sem depender de eu ter desenhado corretamente as duas árvores. E as árvores saem exibidas lado a lado, uma agrupando como soma de um produto e a outra como produto de uma soma — dois valores numéricos diferentes para o mesmo texto, e a gramática ambígua sem meio de escolher.
Sobre o condicional, o mesmo instrumento encontra duas árvores para a cadeia com um único senao e dois se, e uma só depois da reescrita em comandos casados e abertos. Confirma, portanto, a subseção 3.5 pelo mesmo procedimento.
Vale insistir no que essa concordância significa e no que ela não significa. Ela confirma que eu não errei o desenho das árvores nem o raciocínio sobre elas. Ela não demonstra não ambiguidade em caso algum, pela razão do Teorema 3.1. Um instrumento que refuta é o máximo que se pode ter, e é bastante.
1.7.4 6.4 O argumento para a linguagem do livro
Agora o argumento estrutural, que é o que sustenta a afirmação positiva. Ele fica curto porque a gramática foi escrita para que ficasse.
As expressões da Peneira têm três níveis estratificados na ordem de precedência: a disjunção, a conjunção e a comparação. Cada nível referencia apenas o nível imediatamente mais forte, e o ciclo só se fecha por parênteses explícitos na variável dos operandos atômicos. É exatamente a estrutura da gramática estratificada da subseção 3.3, com três níveis em vez de dois, e o argumento de alcançabilidade que dei lá se transporta sem mudança: um termo de conjunção pode aparecer dentro de uma disjunção, e o contrário só com parênteses.
Fora das expressões, não há ambiguidade possível porque cada produção começa por um terminal distinto. A declaração de padrão começa pela palavra reservada de declaração, o bloco de regra pela palavra reservada de bloco, a ação pela palavra reservada de ação. As duas formas de ação — com e sem condição — começam igual, e é por isso que elas exigem verificação adicional: elas divergem no símbolo que segue o parêntese de fechamento, que é ou a palavra reservada da condição, ou a seta da ação. A divergência acontece em posição fixa e é decidível olhando um símbolo adiante. Não há ponto na gramática em que duas produções da mesma variável possam começar igual e seguir iguais por uma distância que dependa da entrada.
Sobre os programas reais, o enumerador confirma. Os três exemplos que exercitam caminhos distintos da gramática — uma declaração de padrão, uma regra simples e uma regra com condição — derivam de forma única. Os terminais não são escritos à mão: os programas passam pelo analisador léxico do capítulo anterior, e os símbolos léxicos que ele produz viram os terminais da gramática. A conversão colapsa os seis operadores de comparação num terminal único, porque a gramática não distingue entre eles e não deveria — quem distingue é a análise semântica, e carregar essa distinção na sintaxe multiplicaria produções sem ganho algum.
Para o primeiro dos três programas, a saída é esta:
terminais: pattern ID = PADRAO ;
arvores: 1
programa
listaDecl
decl
declPadrao
pattern
ID
=
PADRAO
;Cinco terminais, uma árvore. E a derivação mais à esquerda correspondente, que o Teorema 2.1 garante ser única, tem cinco formas sentenciais:
programa
listaDecl
decl
declPadrao
pattern ID = PADRAO ;Compare as duas exibições e a distinção da subseção 2.4 fica tangível: a derivação é uma sequência de cinco linhas que se substituem; a árvore é uma estrutura de nove nós que coexistem. E é a árvore, não a derivação, que se conta para decidir ambiguidade.
1.7.5 6.5 A simplificação que eu implementei e não apliquei
A gramática da Peneira tem oito produções unitárias, de vinte e duas. São elas que ligam os níveis de precedência entre si e as variáveis de lista aos seus elementos. Implementei a remoção por fechamento descrita na subseção 4.4 e rodei-a, sem aplicar o resultado, apenas para medir:
removendo-as: 22 -> 41 producoesA remoção quase dobra a gramática, exatamente pelo motivo estrutural que antecipei: cada variável herda as produções de tudo que alcança por renomeação, e a estratificação criou cadeias longas de renomeação de propósito. A variável do nível mais fraco passa a carregar diretamente tudo o que os três níveis abaixo dela produziam.
E o custo não é apenas de tamanho. Essas oito unitárias são o argumento de não ambiguidade da subseção 6.4 escrito na própria gramática. Removê-las encurta a derivação em alguns passos e destrói a hierarquia que tornava a precedência legível na especificação — o argumento estrutural deixaria de poder ser lido nas produções, e teria de ser mantido à parte, em prosa, com todo o risco de a prosa e a gramática divergirem na primeira alteração.
É um caso em que a simplificação canônica é a coisa errada a fazer, e saber disso vale mais que saber executá-la. Implementei porque quero a medição; não apliquei porque a gramática que fica é a especificação da linguagem, e especificação se escolhe por legibilidade.
Das outras simplificações, a gramática da Peneira não precisa de nenhuma: os conjuntos de improdutivos e de inalcançáveis saem vazios, e não há anuláveis. Isso não é sorte. É consequência de tê-la escrito sem produções vazias e de ter rodado as checagens de higiene antes de seguir adiante — que é precisamente o hábito que a seção 4 recomendou.
1.8 Síntese
Uma gramática livre de contexto é uma quádrupla de variáveis, terminais, produções e símbolo inicial, com exatamente uma variável do lado esquerdo de cada produção — restrição de forma que o nome anuncia e que é perda de poder deliberada: torna o formalismo composicional e analisável, ao preço de uma fase de análise semântica encarregada das condições que dependem de contexto. Derivar é aplicar produções a partir da variável 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 descarta a ordem e guarda a estrutura, e a correspondência entre árvores e derivações canônicas é exata — por isso o teste de ambiguidade conta árvores, não derivações.
Ambiguidade é a existência de duas árvores para a mesma cadeia, é propriedade da gramática e é inaceitável porque a árvore é o objeto sobre o qual todas as fases seguintes trabalham. As técnicas atacam problemas distintos: a estratificação transforma precedência em hierarquia de variáveis; o lado da recursão fixa a associatividade; o caso do condicional exige reescrever a gramática separando construções fechadas de abertas. E sobre o que se pode saber fui honesto: a ambiguidade é indecidível no caso geral, nenhuma ferramenta lhe dirá que a sua gramática é boa, e o que sustenta a afirmação positiva é o argumento estrutural sobre as produções.
As simplificações são três cálculos de ponto fixo e uma operação de fechamento, duas delas higiene cujo resultado esperado é conjunto vazio. A remoção de unitárias é o caso instrutivo, porque é a transformação canônica que, aplicada a uma gramática estratificada, destrói a propriedade que se pagou para obter. E as formas normais fecham a teoria pelo que garantem, sem que nenhuma seja usada aqui.
Volto, para terminar, à expressão da abertura. Agora você sabe onde mora o quatorze: não no texto, não no processador, e sim na forma das regras — na hierarquia de variáveis que impede uma soma de caber dentro de um produto sem parênteses. Escrever bem a gramática agora é o investimento mais rentável desta parte do curso, porque cada decisão tomada aqui vai cobrar ou poupar trabalho quando a gramática deixar de ser especificação e virar programa.