Gramáticas livres de contexto

A análise léxica nos deu tokens. Mas como descrever que "( ( ) )" é válido e "( ) )" não é? Aninhamento arbitrário foge das expressões regulares — precisamos de uma ferramenta mais forte.

As gramáticas livres de contexto (tipo 2 de Chomsky) são essa ferramenta. Elas descrevem a estrutura sintática das linguagens de programação.

• A definição formal de uma GLC.
• Como gerar cadeias e registrar sua estrutura.
• O problema da ambiguidade e como resolvê-lo.
• As notações padrão de gramáticas.

Os não-terminais são variáveis sintáticas (como E para "expressão"); os terminais são os tokens; as produções dizem como reescrever cada não-terminal; S é o ponto de partida.

Guarde os quatro nomes. A bancada que transforma essa definição em quatro botões vem duas seções adiante: ela trabalha sobre a gramática de expressões e sobre a árvore sintática, que você ainda vai ver.

O exemplo clássico, que usaremos o curso inteiro, é o das expressões aritméticas:

Há três níveis: E (expressão, soma), T (termo, produto) e F (fator). Essa estratificação não é casual — ela codifica a precedência dos operadores, como veremos.

Para "id + id", uma derivação é: E ⇒ E + T ⇒ T + T ⇒ F + T ⇒ id + T ⇒ id + F ⇒ id + id.

Agora que N, T, P e S têm um exemplo concreto e você já sabe o que é uma árvore, a bancada abaixo vira a definição do avesso. Tire um símbolo de T, desligue uma produção de P, mova o S de lugar — e a linguagem gerada e a árvore se refazem na hora. Depois renomeie os elementos de N e confira: não muda absolutamente nada. Três dos quatro componentes decidem a linguagem; o quarto é só o nome que você escolheu para as variáveis.

A bancada logo abaixo faz esse mesmo movimento com as suas mãos: clique num não-terminal, escolha a produção, e veja a forma sentencial e a árvore crescerem juntas. Experimente também os modos mais à esquerda e mais à direita — e repare no número que a bancada mostra no fim: são muitas ordens diferentes de derivação para uma única árvore. A ordem é escolha do analisador; a árvore é o que fica.

Ambiguidade é um defeito: o compilador não saberia qual interpretação adotar.

A gramática estratificada (E, T, F) elimina esse problema: ela só produz uma árvore para cada cadeia, com o agrupamento correto id+(id*id).

A EBNF acrescenta açúcares sintáticos à BNF, deixando as gramáticas mais compactas:

Em EBNF: chaves { } repetem (zero ou mais), colchetes [ ] tornam opcional, parênteses ( ) agrupam.

Açúcar não é poder novo. Na bancada abaixo, escreva a gramática em EBNF e veja a tradução mecânica para BNF pura: cada { } vira um não-terminal recursivo, cada [ ] vira uma alternativa com ε. Em seguida a bancada enumera as duas — a sua EBNF e a BNF gerada — e confere que produzem exatamente as mesmas cadeias.

A gramática gera; a árvore registra. O parser, que veremos na próxima aula, faz o caminho inverso: recebe a cadeia e reconstrói a árvore.

A estrutura da gramática codifica dois conceitos:

• Precedência: operadores que ligam mais forte ficam em níveis mais profundos. Como * está abaixo de + (no nível T), ele agrupa primeiro.
• Associatividade: a recursão à esquerda (E → E + T) torna o operador associativo à esquerda, então a - b - c é lido como (a - b) - c.

Na mesa abaixo, precedência e associatividade deixam de ser explicação e viram controle: mude o nível de um operador ou o lado da recursão e a bancada reescreve a gramática, refaz a árvore e recalcula o valor. Vale testar 8 - 3 - 2 (3 ou 7?) e 2 ^ 3 ^ 2 (512 ou 64?) — expressões que separam os dois casos.

Ambiguidade é um conceito que só convence quando você vê. No simulador abaixo, a cadeia 2+3*4 é derivada por uma gramática ambígua de duas maneiras — e cada árvore avalia para um número diferente: 20 e 14.

Depois troque para a gramática corrigida e observe que sobra uma única árvore. A precedência deixou de ser combinação e passou a ser estrutura: os níveis E, T e F obrigam o * a ser reduzido antes do +.

E há um segundo botão que vale a aula inteira: a varredura. Ela enumera a linguagem da gramática, analisa cada cadeia e devolve a menor que admite duas árvores — a testemunha. Guarde o que acontece quando a varredura não acha nada: isso não é prova de que a gramática é inambígua (voltamos a esse ponto na seção 18).

O clássico "dangling else": em if E then if E then S else S, a quem pertence o else? Ao if interno ou ao externo?

A bancada abaixo não para nas duas árvores: ela mostra o que cada leitura faz quando a condição externa é falsa — numa, nada acontece; na outra, o else executa. Depois compare as duas saídas reais: a gramática estratificada em comando casado e não-casado, que resolve o problema na raiz, e o delimitador (as chaves), que resolve apenas aquele texto.

É exatamente essa fronteira que a varredura do simulador da seção 13 torna palpável: achar uma testemunha é sempre possível quando ela existe — basta procurar o suficiente; concluir que não existe nenhuma, para uma gramática qualquer, é que não tem algoritmo. Por isso a engenharia real é a da seção 17: projetar para que a ambiguidade não possa nascer.

Esta é a aula-base da análise sintática:

• Vem da aula 2: GLC é o tipo 2 (livre de contexto) de Chomsky.
• Continua na aula 6: o parser descendente percorre a gramática para reconstruir a árvore.
• Prepara a aula 7: FIRST/FOLLOW e LL(1) dependem de a gramática estar bem formada (sem ambiguidade).