flowchart LR
M06["Módulo 6<br/>Limites do regular<br/>o aninhamento derruba<br/>o autômato finito"]
M07["Módulo 7<br/>Análise léxica<br/>marco de consolidação<br/>símbolos prontos"]
M08["Módulo 8<br/>Gramáticas livres<br/>de contexto<br/>A ESPECIFICAÇÃO NASCE"]
M09["Módulo 9<br/>Autômatos de pilha<br/>o reconhecedor<br/>correspondente"]
M10["Módulo 10<br/>Análise descendente<br/>a gramática vira<br/>programa"]
M06 --> M07 --> M08 --> M09 --> M10
subgraph ENTREGA["O que o módulo 8 deixa pronto"]
D1["Gramática completa<br/>da linguagem do grupo"]
D2["Argumento escrito de<br/>não ambiguidade"]
D3["Precedência e associatividade<br/>decididas na forma<br/>das produções"]
D4["Escopo revisto e<br/>redução registrada"]
end
M08 --- ENTREGA
D3 -.->|"cobra ou poupa trabalho"| M10
D1 -.->|"vira código"| M10
Gramáticas Livres de Contexto — Plano de Aula
Documento exclusivo do professor. Guia operacional das seis aulas do módulo 8: roteiro por blocos das duas aulas teóricas, plano das quatro aulas de tutoria, entregáveis e riscos antecipados. Não distribua à turma — as questões de discussão perdem função assim que o estudante lê a resposta antes de votar.
Visão Geral do Módulo
Onde este módulo fica — a virada de “que palavras existem” para “como elas se combinam”.
Sete módulos descreveram palavras. Este é o primeiro que descreve estrutura, e a mudança de objeto muda o critério de qualidade da aula. Até aqui, o que se produzia era código, e código se avalia executando: passou nos testes, serve. Aqui o que se produz é uma especificação, e especificação se avalia lendo. A turma não tem hábito disso, e instalar esse hábito é o principal trabalho de condução do módulo.
O módulo também é a ponte entre duas dívidas. Uma vem de trás: o lema do bombeamento demonstrou que nenhum autômato finito reconhece aninhamento, e ficou pendente qual formalismo o reconhece. A outra vai para a frente: cada decisão tomada aqui — lado da recursão, presença ou ausência de produção vazia, hierarquia de precedência — reaparece no módulo 10 cobrando ou poupando trabalho de forma visível. Diga isso no primeiro bloco e repita no fechamento, porque é o que impede que o módulo seja lido como interlúdio teórico entre dois módulos de programação.
Calibre o esforço para o risco central: você vai passar boa parte das duas aulas diante de pares de gramáticas que geram exatamente o mesmo conjunto de cadeias, argumentando que uma presta e a outra não. Se a turma sair achando que “as duas dão certo”, o módulo falhou.
Objetivos, Competências e Habilidades
Objetivos de aprendizagem. Introduzir o formalismo que descreve estruturas aninhadas e estabelecer a ambiguidade como problema central do projeto de linguagens. Desenvolver a capacidade de escrever e transformar gramáticas.
Competências a desenvolver. Capacidade de especificar formalmente a estrutura de uma linguagem e de avaliar criticamente uma especificação quanto a ambiguidade. Capacidade de reconhecer, num formalismo, a origem de propriedades desejáveis do artefato que dele decorre.
Habilidades a adquirir. Definir formalmente uma gramática livre de contexto. Distinguir derivações mais à esquerda e mais à direita e relacioná-las à árvore de derivação. Identificar ambiguidade e eliminá-la por estratificação de precedência e escolha do lado da recursão. Simplificar gramáticas removendo símbolos inúteis e produções vazias e unitárias.
Estrutura das Aulas
Aulas 1 e 2 — Aula Teórica
Roteiro por blocos — cada bloco existe porque o anterior deixou uma pergunta sem resposta.
Bloco de abertura — duas árvores, dois números
Não anuncie o assunto da aula. Escreva no quadro a gramática
E \to E + E \mid E \times E \mid \texttt{num}
e a cadeia \texttt{num} + \texttt{num} \times \texttt{num}, com os valores 2, 3 e 4 escritos por baixo dos três números. Depois desenhe as duas árvores, lado a lado, você mesmo, em silêncio. Numa delas o nó raiz é a soma e o produto está no filho direito; na outra o nó raiz é o produto e a soma está no filho esquerdo. Avalie as duas na frente da turma: a primeira dá 2 + (3 \times 4) = 14; a segunda dá (2 + 3) \times 4 = 20.
Então faça a pergunta única do bloco: qual das duas está certa segundo a gramática. Insista no complemento quando alguém responder 14, porque a resposta que a sala dá é a da escola, não a do formalismo. A resposta correta é que a gramática não decide, e que portanto a pergunta “o que este programa faz” não tem resposta. Deixe as duas árvores no quadro pelas duas aulas inteiras — elas são o fio do módulo.
Feche com a pergunta que organiza tudo o que vem: se a precedência não está no texto, que tem cinco símbolos e nenhum deles diz “multiplicação primeiro”, e não pode estar no processador, que nunca viu esta expressão, em que lugar ela está. Anuncie que a resposta é “na forma das regras” e não explique mais nada agora.
Bloco seguinte — pagar a dívida do bombeamento e definir
Retome L = \{a^n b^n \mid n \ge 0\} e a impossibilidade demonstrada no módulo 6, em três frases, sem refazê-la. O que interessa é o deslocamento: a dificuldade não é contar, é contar duas coisas em correspondência, uma de cada lado de um ponto central. Peça à sala que descreva a linguagem em português e conduza até a frase recursiva — uma cadeia de L é vazia, ou é um a seguido de uma cadeia de L seguida de um b. Escreva-a em símbolos na frente deles:
S \to a\,S\,b \mid \varepsilon.
Derive aaabbb passo a passo: S \Rightarrow aSb \Rightarrow aaSbb \Rightarrow aaaSbbb \Rightarrow aaabbb — três aplicações da primeira produção, uma da segunda, seis terminais. Ao lado, derive A \to a\,A \mid b: A \Rightarrow aA \Rightarrow aaA \Rightarrow aab. Pergunte o que mudou e force a resposta posicional até sair: no segundo caso o símbolo recursivo está na ponta; no primeiro, no meio, com terminal de cada lado. Escreva “aninhamento é símbolo recursivo no meio” e não apague — é a imagem que a turma leva do módulo.
Só então dê a quádrupla G = (V, \Sigma, P, S) e a forma A \to \alpha, e insista na observação que organiza o semestre e quase sempre passa despercebida: os terminais desta gramática não são caracteres, são as categorias de símbolo léxico que o analisador do módulo 7 produz. O módulo anterior operava sobre caracteres porque descrevia o interior das palavras; este opera sobre símbolos porque descreve como as palavras se combinam. Mesmo vocabulário matemático, alfabetos diferentes.
Bloco seguinte — o nome é uma afirmação técnica
Explique “livre de contexto” pela produção proibida, não pela definição positiva. Escreva x\,A\,y \to x\,\alpha\,y e leia em voz alta: substitua A por \alpha, mas apenas quando estiver entre x e y. A definição da quádrupla proíbe isso pela forma — do lado esquerdo cabe um símbolo só, e não sobra espaço para escrever contexto nenhum. O que a turma precisa levar não é a proibição, é a contrapartida: essa perda de poder é a fonte de tudo que torna o formalismo utilizável. Diga concretamente — quando você escreve a produção da expressão condicional, ela vale igualmente dentro de um laço, dentro de uma função e dentro de outra condicional, e você não escreve uma versão para cada situação. Feche ligando à fase que a turma já conhece pelo nome: “todo nome usado precisa ter sido declarado” é sensível ao contexto por natureza, e nenhuma gramática livre de contexto captura isso de forma praticável. É por isso que existe uma análise semântica separada — a escolha de um formalismo mais fraco na análise sintática é deliberada, e o preço é uma fase a mais. Costuma ser o momento em que a arquitetura de fases do módulo 1 deixa de parecer arbitrária.
Bloco seguinte — a notação que eles já leram sem saber
Bloco curto e de alto retorno. Conte que Backus propôs a notação no contexto do projeto de ALGOL e que Naur a adaptou ao editar o relatório sobre ALGOL 60 — a primeira vez que a sintaxe de uma linguagem de programação foi publicada como objeto matemático em vez de exemplos com prosa em volta. Peça então que alguém abra a página de gramática do manual da linguagem que mais usa. O reconhecimento — “eu já li isso e pulei” — é o gancho do bloco e vale provocá-lo em voz alta.
Trate a notação estendida com rigor, porque é aqui que nasce um erro que reaparece na tutoria. Chaves de repetição e colchetes de opcional não existem no formalismo. A repetição vira recursão: A \to \beta\,\{\gamma\} reescreve-se com uma auxiliar, A \to \beta\,R e R \to \gamma\,R \mid \varepsilon. O opcional vira duas produções: A \to \beta\,[\gamma]\,\delta vira A \to \beta\,\gamma\,\delta e A \to \beta\,\delta.
Antecipe a armadilha aqui, porque na tutoria já é tarde. Alguém vai propor traduzir o opcional criando uma auxiliar anulável, O \to \gamma \mid \varepsilon, e escrever A \to \beta\,O\,\delta. Funciona, e é pior. Diga por quê com data: acabou de entrar uma produção vazia numa gramática que talvez não precisasse de nenhuma, e produções vazias são a principal fonte de erro no cálculo dos conjuntos do módulo 10. Escreva “duplicar a produção, não criar anulável” no quadro. Metade dos grupos vai tentar o contrário na tutoria mesmo assim, e você vai apontar para o quadro.
Bloco seguinte — árvore não é derivação
Defina derivação em um passo, derivação mais à esquerda e mais à direita, e a árvore. Enuncie a correspondência: cada árvore corresponde a exatamente uma derivação mais à esquerda e a exatamente uma mais à direita. Esboce o argumento pelo percurso em profundidade da esquerda para a direita e pare — a indução completa não paga o que custa aqui.
O exemplo deste bloco é minúsculo e obrigatório, porque é o ponto em que mais gente escorrega. Tome S \to A\,B, A \to a, B \to b e a cadeia ab. Escreva as duas derivações no quadro: S \Rightarrow AB \Rightarrow aB \Rightarrow ab e S \Rightarrow AB \Rightarrow Ab \Rightarrow ab. Pergunte se a gramática é ambígua. A sala tende a dizer que sim, porque contou duas derivações. Desenhe então a árvore: raiz S, filhos A e B, cada um com o seu terminal — uma só. As duas derivações são a mesma árvore lida em ordens diferentes, uma mais à esquerda e outra mais à direita, exatamente como o teorema previu. Registre a consequência, que sustenta toda a segunda aula: contar derivações não serve como teste; contar árvores serve.
Primeira questão de discussão em duplas. “Uma gramática admite, para certa cadeia, exatamente três derivações distintas. Sobre a ambiguidade dessa gramática, pode-se concluir que: (a) ela é ambígua, pois há mais de uma derivação; (b) ela não é ambígua, pois derivações distintas podem ser a mesma árvore; (c) nada se conclui sem examinar as árvores correspondentes; (d) ela é ambígua apenas se as três forem mais à esquerda.”
Aplique o procedimento inteiro: voto individual sem comentário seu, discussão em duplas, segundo voto. A resposta é (c). Quem vota (a) é maioria no primeiro voto, e é exatamente o erro que o bloco atacou. Quem vota (b) acertou o argumento e errou a conclusão, generalizando o exemplo do ab. A alternativa (d) é a mais instrutiva de comentar: três derivações mais à esquerda de fato implicam três árvores, mas o enunciado não diz que são, e é isso que torna (c) a única resposta sustentável. Não revele nada antes da discussão em duplas.
Bloco de abertura da segunda aula — a pendência no quadro
Não recapitule. Aponte para as duas árvores que ficaram no quadro desde a abertura e pergunte o que ainda não foi respondido — qual delas está certa, e a resposta honesta continua sendo “nenhuma”. Anuncie o programa em uma frase: hoje conserta-se a gramática, e o conserto é de forma, não de anotação lateral.
Bloco seguinte — estratificação
Diagnóstico antes da solução: pergunte o que a gramática ambígua permite e não deveria, e conduza até a formulação exata — ela permite que uma soma apareça como operando direto de uma multiplicação e, ao mesmo tempo, que uma multiplicação apareça como operando direto de uma soma, porque há uma variável só, e com uma variável só qualquer coisa cabe dentro de qualquer coisa. Escreva a correção:
\begin{aligned} E &\to E + T \mid T \\ T &\to T \times F \mid F \\ F &\to (\,E\,) \mid \texttt{num} \end{aligned}
Leia as produções como afirmações sobre continência, não como regras a decorar: 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.
Derive \texttt{num} + \texttt{num} \times \texttt{num} na frente deles e mostre que só há um caminho: E \Rightarrow E + T \Rightarrow T + T \Rightarrow F + T \Rightarrow \texttt{num} + T \Rightarrow \texttt{num} + T \times F \Rightarrow \texttt{num} + F \times F \Rightarrow \texttt{num} + \texttt{num} \times \texttt{num}. Sete formas sentenciais, uma árvore. Depois dê o argumento estrutural, que é o que fica: T é alcançável a partir de E, e E não é alcançável a partir de T senão por parênteses explícitos. A precedência deixou de ser convenção anotada ao lado da gramática e virou hierarquia de variáveis, legível na especificação.
Alguém vai objetar que a gramática ficou maior e as árvores mais altas. A objeção é boa: responda que a alternativa não é uma gramática menor e correta, é uma menor e ambígua, que só funciona porque existe, fora dela, uma tabela de precedência que o analisador consulta. O tamanho que a estratificação acrescenta é exatamente a informação que a outra abordagem esconde em outro lugar.
Bloco seguinte — associatividade é o lado da recursão
Faça a conta antes da teoria. Escreva \texttt{num} - \texttt{num} - \texttt{num} com os valores 10, 4 e 3: agrupando à esquerda, (10 - 4) - 3 = 3; à direita, 10 - (4 - 3) = 9. Dois números, um texto, e a precedência não tem nada a ver com isso — o operador é o mesmo. Só então escreva o par
E \to E - T \mid T \qquad\text{contra}\qquad E \to T - E \mid T
e conclua: recursão à esquerda produz associatividade à esquerda; recursão à direita, à direita. As duas geram o mesmo conjunto de cadeias, as duas são não ambíguas, e apenas uma dá o resultado que a aritmética exige.
Acrescente os dois complementos que a turma não deduz sozinha. O primeiro: nem todo operador binário deve associar — a < b < c não tem significado natural, e a decisão correta é a gramática recusar a cadeia, o que se escreve tornando a produção da comparação não recursiva. Recusar cedo é mais barato que explicar tarde: o erro sai como erro de sintaxe apontando o segundo operador, em vez de mensagem obscura sobre tipos duas fases adiante. O segundo, e diga-o mesmo sabendo que causa desconforto: a recursão à esquerda que a associatividade aritmética exige é incompatível com a análise descendente do módulo 10, e a transformação padrão que a elimina destrói a associatividade legível na gramática, que precisa ser reconstruída no código. É melhor que a turma saiba disso agora do que descubra como surpresa.
Segunda questão de discussão em duplas. “As gramáticas E \to E - T \mid T e E \to T - E \mid T, com T \to \texttt{num}, diferem em: (a) conjunto de cadeias geradas; (b) ambiguidade — a primeira é ambígua e a segunda não; (c) estrutura das árvores, e portanto no valor calculado; (d) nada, são notações equivalentes.”
A resposta é (c). Quem vota (a) não percebeu que ambas geram exatamente as mesmas cadeias e é a confusão mais comum do módulo entre linguagem gerada e estrutura gerada. Quem vota (d) fez a mesma confusão com mais confiança. A alternativa (b) é o distrator que vale explorar: nenhuma das duas é ambígua, e é precisamente por isso que o exemplo é bom — mostra que “não ambígua” está longe de ser o mesmo que “correta”.
Bloco seguinte — o condicional pendurado
Mude de natureza de problema e diga que está mudando. Escreva
S \to \texttt{se}\ c\ \texttt{entao}\ S \mid \texttt{se}\ c\ \texttt{entao}\ S\ \texttt{senao}\ S \mid \texttt{cmd}
e a cadeia \texttt{se}\ c\ \texttt{entao}\ \texttt{se}\ c\ \texttt{entao}\ \texttt{cmd}\ \texttt{senao}\ \texttt{cmd}. Dois condicionais, uma alternativa. Pergunte a quem ela pertence e desenhe as duas árvores: numa leitura a alternativa executa quando a condição externa é falsa; na outra, quando a externa é verdadeira e a interna é falsa. Comportamentos diferentes, mesmo texto.
Aponte o que separa este exemplo do anterior: a estratificação não ajuda aqui, porque não há precedência entre operadores a estabelecer, e sim uma decisão sobre a qual de duas construções aninhadas um sufixo pertence. Escreva a reescrita em casados e abertos e explique a chave em uma frase: o ramo verdadeiro de um condicional que tem alternativa só pode conter comandos casados, o que proíbe um condicional sem alternativa de ficar pendurado ali dentro.
O ponto do bloco é o método, não a solução, e merece ser dito devagar: a desambiguação não foi feita acrescentando uma regra externa dizendo “ligue ao mais próximo”, e sim reescrevendo a gramática até que só a leitura desejada fosse derivável. A regra externa também funciona — é o que os geradores oferecem por declarações de precedência — e resolve o conflito no analisador, deixando a especificação ambígua para quem a lê. As duas produzem o mesmo compilador e não produzem o mesmo manual.
Termine com a saída de projeto, a que mais serve aos grupos nesta semana: linguagens que exigem delimitador de fim para o condicional não têm o problema, e essa escolha é feita antes da primeira produção.
Bloco seguinte — o que não se pode decidir, e o que se pode refutar
Aqui a turma precisa de honestidade explícita, e ela prepara o critério de correção da entrega. Diga que a ambiguidade de uma gramática arbitrária é indecidível — não existe algoritmo que decida o caso geral, e portanto nenhuma ferramenta dirá que a gramática do grupo é boa — e que existem linguagens inerentemente ambíguas, artificiais, entre as quais nenhuma linguagem de programação real se encontra.
Escreva no quadro as duas formas de sustentar a afirmação de não ambiguidade, que têm forças diferentes. A primeira é o argumento estrutural: para expressões, a hierarquia de estratificação; fora delas, mostrar que as produções de cada variável começam por terminais distintos, ou que divergem em ponto posterior detectável. 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. O algoritmo clássico preenche uma tabela indexada por variável e por intervalo da entrada, e é devido de forma independente a Cocke, a Kasami, em relatório técnico de 1965, e a Younger, em publicação de 1967. É exponencial no número de árvores produzidas: não serve como analisador de compilador e serve muito bem como instrumento de estudo.
Este é o bloco de demonstração ao vivo do módulo. Projete a ferramenta de contagem de árvores da implementação de referência e rode-a sobre as duas gramáticas de expressão que estão no quadro desde a aula anterior. A saída é o argumento inteiro: duas árvores na gramática de uma variável só, uma na estratificada, com as leituras exibidas lado a lado. A partir daí, “esta gramática é ambígua” vira contagem, e é essa mudança de regime que a turma leva para a tutoria.
Diga em voz alta o limite da ferramenta, porque a turma vai querer usá-la como certificado: ela refuta — encontrou duas árvores, a gramática é ambígua e acabou —, e nunca confirma. Essa assimetria é a forma prática da indecidibilidade que você acabou de enunciar.
Terceira questão de discussão em duplas. “Um grupo enumerou todas as árvores de derivação de trinta programas de exemplo e encontrou exatamente uma para cada. Isso demonstra que a gramática do grupo é não ambígua? (a) sim, trinta casos são amostra suficiente; (b) sim, desde que os trinta cubram todas as produções; (c) não, mas seria demonstração se o conjunto de teste fosse infinito; (d) não, e nenhum conjunto de teste demonstraria.”
A resposta é (d). A alternativa (b) é a que mais atrai, porque parece critério de cobertura respeitável — e cobrir todas as produções é ótimo critério de teste e não é demonstração de coisa alguma. Emende com a consequência prática: por isso a entrega deste módulo exige o argumento escrito, e não a gramática mais um relatório de testes.
Bloco seguinte — simplificações, e uma que não se aplica
Trate as quatro simplificações como três cálculos de ponto fixo e uma operação de fechamento, sobre uma única gramática pequena e deliberadamente defeituosa:
S \to A\,B \mid a, \qquad A \to a\,A \mid \varepsilon, \qquad B \to b, \qquad C \to c\,C, \qquad D \to d.
Calcule com a sala, um conjunto por vez. Anuláveis: começa com quem tem produção vazia, e é \{A\}; nenhuma outra variável tem corpo inteiramente formado por anuláveis. Produtivos: terminais o são por definição, B e D produzem terminal direto, A produz \varepsilon, e S tem corpo AB com ambos marcados — resulta \{A, B, D, S\}, sem C. Alcançáveis, descendo de S: \{A, B, S, a, b\}, sem D.
Nomeie os defeitos pelo que costumam ser na origem. C é improdutiva: toda derivação a partir dela produz outro C e nunca chega a cadeia só de terminais — quase sempre uma produção esquecida. D é inalcançável: nenhuma derivação a partir do símbolo inicial chega até ela — quase sempre resto de reescrita anterior. Numa gramática saudável os dois conjuntos saem vazios, e por isso essas checagens valem rodar antes de tudo. Sobre a ordem: improdutivos primeiro, porque remover uma variável improdutiva pode tornar outras inalcançáveis.
Guarde o melhor para o fim do bloco. Volte à gramática estratificada e conte as unitárias: E \to T e T \to F, duas — e essas duas produções são a estratificação, os elos que ligam um nível de precedência ao imediatamente mais forte. Faça a remoção no quadro com a sala. Por fechamento de renomeação, E alcança T e F, e T alcança F; herdando as produções não unitárias, E \to E + T \mid T \times F \mid (\,E\,) \mid \texttt{num}, T \to T \times F \mid (\,E\,) \mid \texttt{num} e F \to (\,E\,) \mid \texttt{num}. De seis produções para nove.
Deixe o número no quadro. A gramática cresceu ao ser “simplificada” e perdeu a propriedade pela qual havia sido escrita assim: já não se lê nela qual operador tem precedência sobre qual. O critério geral, que é o que deve ser copiado, é que transformação canônica não é automaticamente melhoria — aplique-a se um algoritmo posterior exigir, sobre uma cópia.
Bloco seguinte — formas normais pelo que garantem
Este bloco é curto de propósito e não deve consumir o fechamento. Apresente cada forma normal pela garantia. Chomsky: todo corpo é duas variáveis ou um terminal, logo toda árvore é binária e o número de passos da derivação é função previsível do comprimento da cadeia. Greibach: todo corpo começa por terminal, logo cada passo consome um símbolo da entrada e a recursão à esquerda desaparece por construção.
Diga, como decisão fundamentada e não como omissão, que este curso não converte gramática nenhuma para forma normal — a técnica de análise adotada não exige, e a conversão produz uma gramática ilegível para servir a um analisador que não vamos escrever. Se alguém perguntar por que estudá-las: são pré-condição de resultados e algoritmos que a turma encontrará em qualquer texto da área.
Bloco de fechamento — volta às duas árvores
Aponte de novo para o quadro da abertura. As duas árvores continuam lá, com 14 e 20 escritos por baixo. Refaça a pergunta original e deixe a sala responder: na gramática de uma variável só, ela não tem resposta; na estratificada, o produto só cabe dentro da soma, a árvore é única e o valor é 14. Nada foi acrescentado ao texto, nada foi anotado ao lado da gramática — mudou a forma das regras.
Feche com a dívida para a frente, em duas frases. O módulo seguinte apresenta o reconhecedor correspondente a este gerador, o autômato de pilha, e traz o resultado mais contraintuitivo do curso: neste andar, ao contrário do que valeu para autômatos finitos, o não determinismo aumenta o poder de reconhecimento. E o módulo 10 toma o objeto escrito nesta semana e o converte em código, com uma função por variável — escrever bem a gramática agora é o investimento mais rentável desta parte do curso, e o retorno chega datado.
Aulas 3 a 6 — Tutoria do Projeto Integrador
Quatro aulas de tutoria — a gramática completa da linguagem do grupo, o argumento escrito de não ambiguidade, três árvores de derivação e a revisão honesta do escopo.
O andaime já é intermediário: você dá o objetivo e os critérios, e o caminho é do grupo. Mas há um ponto em que ele volta a ser máximo, e é o argumento de não ambiguidade — nenhum grupo sabe como um argumento desses se parece antes de ver um. Tenha a gramática da Peneira projetada e o argumento escrito ao lado, em onze linhas, desde a primeira sessão. Grupos que veem o formato entendem de imediato; grupos que só ouvem a descrição da tarefa escrevem “testamos e não deu problema”.
Primeira sessão de tutoria — traduzir o design para o formalismo puro
Abra recolhendo o que já existe: os programas de exemplo escritos no módulo 1 e a especificação léxica do módulo 2. A gramática desta semana descreve como aquelas palavras se combinam para produzir aqueles programas, e o critério de completude é exatamente esse — toda construção que aparece nos exemplos precisa ter produção.
Projete a gramática da Peneira impressa, as onze linhas, e conte o que ela custou: onze variáveis, vinte e um terminais, vinte e duas produções, e quatro decisões de tradução que precisaram de defesa. Percorra as quatro em voz alta, porque cada uma é uma armadilha que algum grupo da sala vai cair nesta sessão. A repetição virou recursão, e o lado importou nas expressões e não nas listas. O opcional — a ação com e sem condição — virou duas produções, e não uma variável anulável. A comparação não é recursiva, porque encadear comparação não faz sentido na linguagem e a gramática recusa em vez de aceitar e reclamar depois. E não há produção vazia alguma, de propósito: as listas exigem pelo menos um elemento, porque programa vazio e bloco sem ação não são úteis e proibi-los na gramática evita tratar o caso em todas as fases seguintes.
Circule cobrando o formalismo puro. O erro mais frequente da sessão é o grupo entregar a notação estendida com asterisco e interrogação, achando que traduziu. Peça que leiam a própria gramática procurando qualquer símbolo que não seja variável, terminal, seta ou barra vertical; se encontrarem, não terminaram.
O segundo erro é o da variável anulável para expressar opcional, que você já anunciou na aula teórica e que aparecerá do mesmo jeito. Não aceite a negociação de “depois eu arrumo”: mostre no seu próprio projeto que o conjunto de anuláveis saiu vazio e que isso não é acaso, é consequência de ter escrito a gramática sem produções vazias e de ter verificado antes de seguir.
Feche a sessão exigindo de cada grupo a contagem — quantas variáveis, quantos terminais, quantas produções. É o número que abre a conversa de escopo da segunda sessão, e é melhor que ele venha do grupo.
Segunda sessão de tutoria — precedência, associatividade e a conversa de escopo
Comece pelas expressões, que é onde a ambiguidade mora em quase toda linguagem de grupo. Peça que listem os operadores da própria linguagem em ordem de precedência e que confiram se há exatamente um nível de variável por nível. Na Peneira são três — or, and, comparação —, cada nível referenciando apenas o imediatamente mais forte, com o ciclo fechado só por parênteses explícitos em primaria. É a mesma estrutura da gramática estratificada da aula teórica, com três níveis em vez de dois.
Depois passe ao lado da recursão, operador por operador, e exija justificativa semântica e não estética. Nas listas de declaração e de ação da Peneira a recursão é à direita, porque não há operador entre os elementos e a associatividade não significa nada ali; nos binários or e and é à esquerda, e aí a escolha é semântica, porque agrupa da forma que o módulo 12 vai ler. Grupos que responderem “escolhemos porque ficou mais bonito” ainda não fizeram a tarefa.
A segunda metade da sessão é a conversa de escopo, e ela é a razão de este módulo existir no meio do semestre. Faça a pergunta a todos os grupos, com o número deles na mão: com esta quantidade de produções, você escreve um analisador para cada uma nas quatro sessões do módulo 10. Deixe o silêncio trabalhar. Quando um grupo decidir cortar, registre no seu diário o que foi cortado e por quê, e repita à sala que redução registrada não é penalizada — o que é penalizado é chegar ao módulo 13 com uma linguagem que não cabe.
Aproveite para mostrar o contraexemplo do seu lado: a linguagem da Peneira coube inteira, sem redução, e coube porque foi decidida pequena lá no módulo 1. Não é mérito da gramática; é consequência de uma decisão de projeto tomada meses antes.
Terceira sessão de tutoria — as árvores e a ferramenta de contagem
Esta é a sessão em que as ambiguidades escondidas aparecem, e o instrumento é o desenho. Exija que cada grupo escolha três programas que exercitem caminhos distintos da gramática — na Peneira foram a declaração de padrão, a ação sem condição e a ação com condição —, e não três variações do mesmo caminho. Grupos que testam apenas o que escreveram para funcionar não descobrem nada.
Deixe que desenhem à mão primeiro. Depois disponibilize o enumerador exaustivo do meu projeto e mostre o que ele faz: sobre a gramática de expressão sem estratificação, a cadeia com soma e produto devolve duas árvores; sobre a estratificada, uma. Exiba as duas leituras lado a lado e diga de novo o limite — o enumerador refuta, não confirma. Sobre os programas reais da Peneira ele devolveu uma árvore para cada um dos três, e isso é evidência que acompanha o argumento estrutural, não substituto dele.
Vale mostrar também a distinção que o módulo insistiu, porque na mão ela fica óbvia. O primeiro programa, pattern email = /[a-z]+/;, tem cinco terminais, uma árvore e cinco formas sentenciais na derivação mais à esquerda. A derivação é uma sequência; a árvore é uma estrutura. Grupos que ainda contam derivações vão descobrir aqui, e é o lugar barato de descobrir.
Reforce o revezamento de papéis. Nesta semana o trabalho é de escrita, e por isso o revezamento é mais fácil de abandonar — quem escreve melhor assume o teclado e o resto assiste. Cobre a troca a cada árvore concluída, e circule verificando, porque o módulo 10 exige que qualquer integrante saiba explicar a gramática, e quem não a escreveu não a explica.
Quarta sessão de tutoria — argumento escrito, higiene e fechamento
A última sessão é a do argumento por escrito, e ela costuma ser subestimada. Projete o argumento da Peneira e mostre que ele tem duas partes, ambas obrigatórias. A primeira é sobre as expressões: três níveis estratificados na ordem de precedência, cada um referenciando apenas o imediatamente mais forte, ciclo fechado só por parênteses. A segunda é sobre o resto da gramática: cada produção começa por um terminal distinto — pattern, rule, on — e as duas formas da ação divergem no símbolo que segue o parêntese de fechamento, where ou a seta. Não há ponto em que duas produções da mesma variável comecem igual e sigam diferente.
Peça que cada grupo escreva o argumento nessa forma e leia em voz alta para outro grupo, que faz o papel de revisor procurando um ponto de escolha não coberto. Instrução por pares fora da aula teórica funciona bem aqui, e é mais eficiente do que você revisar quinze argumentos sozinho.
Feche cobrando a higiene, que é a parte mecânica e a que ninguém lembra: conjunto de anuláveis, símbolos improdutivos e símbolos inalcançáveis. Na referência os três saíram vazios, e o esperado é o mesmo em qualquer gramática saudável. Um conjunto não vazio quase sempre aponta produção esquecida ou resto de reescrita anterior, e é bom que apareça agora.
Registre no seu diário, por grupo, três coisas: o número de produções final, a redução de escopo imposta ou aceita, e se o argumento de não ambiguidade foi estrutural ou apenas empírico. A terceira anotação é a que se paga no módulo 10, quando os conflitos aparecerem e você precisar saber quais grupos nunca sustentaram uma afirmação sobre a própria especificação.
Entregáveis e Avaliação
Ao fim do módulo, cada grupo entrega a gramática completa da própria linguagem no formalismo puro; o argumento de não ambiguidade por escrito, com a justificativa das escolhas de precedência e associatividade; as árvores de derivação de pelo menos três programas de exemplo; e, havendo redução de escopo, o registro da mudança e do motivo.
Confira cada entrega contra sete itens, na mesma ordem para todos os grupos: toda construção usada nos programas de exemplo do módulo 1 está coberta por alguma produção; a gramática não usa chaves, colchetes nem qualquer marca de notação estendida; o argumento é estrutural e não uma lista de testes que passaram; há um nível de variável por nível de precedência; o lado da recursão de cada operador binário está justificado pela semântica pretendida; as três árvores vêm de programas que exercitam caminhos distintos, e não três variações do mesmo caminho; e os conjuntos de símbolos improdutivos e inalcançáveis são vazios.
Explicite antes de recolher o que separa entregas boas de medianas: a gramática é o primeiro artefato do semestre que não é código executável, e o valor dela está em estar correta, não em rodar. Um grupo que entrega gramática certa com um argumento de três linhas do tipo “testamos e não deu problema” não cumpriu a tarefa.
Registre no componente contínuo a pontualidade da entrega, a contribuição nas três discussões em duplas e o engajamento nas atividades colaborativas da tutoria. Redução de escopo decidida e registrada nesta semana não é penalizada — diga isso em voz alta na primeira sessão, porque grupos que temem perder nota escondem o problema e chegam ao módulo 13 com uma linguagem que não conseguem implementar.
Orientações Sobre o Aplicativo
Use o aplicativo da disciplina para as três votações, com a distribuição projetada de forma anônima. Na primeira, sobre contar derivações, espere maioria na alternativa errada no primeiro voto e forte migração no segundo — se a migração não acontecer, a distinção entre árvore e derivação não pegou, e seguir sem voltar atrás é desperdício, porque toda a segunda aula depende dela.
A segunda questão é o termômetro do módulo. Se a turma se dividir entre a alternativa correta e a que afirma diferença no conjunto de cadeias geradas, há um problema de fundo — confusão entre linguagem gerada e estrutura gerada — que reaparecerá na tutoria como grupos que trocam o lado da recursão sem perceber que mudaram o significado. Nesse caso, gaste uma passagem extra no par de gramáticas antes de seguir.
A terceira, sobre o valor demonstrativo dos testes, costuma convergir bem e serve mais como preparação da entrega: guarde a distribuição e projete-a de novo na primeira sessão de tutoria, ao cobrar o argumento escrito.
Acompanhe também o engajamento no estudo do material, que responde por metade do componente contínuo. Este módulo tem prosa longa e pouco código, e é comum o indicador cair em relação ao módulo 7. A queda costuma vir de quem confundiu “menos código” com “menos importante”, e uma frase na abertura da tutoria — a gramática desta semana vira o analisador do módulo 10 — corrige mais que qualquer cobrança.
Pontos de Atenção Específicos
“Mas as duas dão certo.” É o risco central do módulo, e aparece toda vez que você exibe duas gramáticas que geram o mesmo conjunto de cadeias. Não responda com autoridade: volte à conta. Dois números diferentes para o mesmo texto encerram a discussão de um jeito que nenhum argumento sobre elegância encerra, e é por isso que os exemplos numéricos do roteiro — 14 contra 20, 3 contra 9 — estão posicionados antes da teoria correspondente e não depois.
Não deixe o módulo virar taxonomia de simplificações. A tentação é enunciar quatro definições e quatro algoritmos, que a turma copia e não usa. O antídoto é a gramática defeituosa única no quadro, com os conjuntos calculados com a sala, e o fechamento pela remoção de unitárias que piora a gramática. Se tiver de cortar algo do bloco, corte a ordem de remoção — nunca o exemplo das unitárias.
Duas digressões previsíveis, e o corte de cada uma. Ao mencionar que declarações de precedência resolvem o conflito no analisador, alguém perguntará por que não usar uma ferramenta dessas em vez de escrever à mão: responda que ela resolve o conflito e deixa a especificação ambígua para quem a lê, e prometa o assunto para o módulo 11. Depois do bloco de indecidibilidade, alguém pedirá um exemplo de linguagem inerentemente ambígua: dê a existência do resultado, diga que os exemplos conhecidos são construções artificiais, e siga — perseguir a construção consome o bloco de simplificações.
O desenho das árvores é tratado como burocracia e não é. Grupos consideram a exigência das três árvores requisito de documentação e a delegam ao integrante menos ativo. Corte isso na tutoria mostrando o que ela faz: é ao tentar desenhar a segunda árvore de um mesmo programa que ambiguidades escondidas aparecem. A árvore não é registro do que se sabe; é o instrumento que descobre o que não se sabia.
O momento de reduzir escopo é este e não outro. Quem perceber agora que a linguagem é grande demais reduz ao custo de uma sessão de tutoria; quem perceber no módulo 13 paga com o semestre. A pergunta que provoca a descoberta na hora certa deve ser feita a todos os grupos, inclusive aos que parecem bem: quantas produções tem a sua gramática, e você escreve um analisador para cada uma delas nas quatro sessões do módulo 10.