flowchart LR
M09["Módulo 9<br/>Autômatos de pilha<br/>o modelo que adivinha"]
M10["Módulo 10<br/>Análise sintática descendente<br/>SEGUNDO MARCO"]
M11["Módulo 11<br/>Análise sintática<br/>ascendente"]
M12["Módulos 12 a 14<br/>Semântica, execução<br/>e geração de código"]
M09 --> M10 --> M11
M10 --> M12
subgraph ENTREGA["O que o módulo 10 deixa pronto"]
D1["Gramática preparada<br/>sem recursão à esquerda<br/>e fatorada"]
D2["Primeiros, seguidores<br/>e tabela sem conflito"]
D3["Analisador recursivo<br/>com recuperação de erros"]
D4["Árvore sintática abstrata<br/>com posição em todo nó"]
end
M10 --- ENTREGA
D2 -.->|"tabela como critério<br/>de comparação"| M11
D4 -.->|"entrada de todas<br/>as fases seguintes"| M12
Análise Sintática Descendente — Plano de Aula
Documento exclusivo do professor. Este é o guia operacional das seis aulas deste módulo: 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 em duplas e o catálogo de sintomas de erro perdem função assim que o estudante os lê antes da aula.
Visão Geral do Módulo
Onde este módulo fica — é o segundo marco, e o mais pesado do semestre.
O módulo anterior entregou uma máquina que adivinha, e este existe para tirar a adivinhação dela. Ao fim das seis aulas o texto deixou de ser sequência de caracteres e virou árvore, e todas as fases seguintes trabalham sobre a árvore. É o fecho da metade de análise do front-end.
A dificuldade não está onde a turma espera, e vale dizer isso em voz alta na primeira aula. O algoritmo de análise é simples ao ponto de decepcionar — uma função por variável da gramática, e nada mais. O difícil vem antes dele: perceber que nem toda gramática serve, transformar a que não serve sem alterar a linguagem, e calcular sobre a transformada dois conjuntos que quase todo mundo erra na primeira tentativa. Se a turma sair daqui calculando primeiros e seguidores com segurança, o módulo cumpriu o que tinha de cumprir.
Há também um deslocamento de atitude a provocar, e ele é o que o módulo tem de mais transferível. Até aqui a gramática foi um dado que se estuda; a partir daqui ela é objeto de engenharia que se modifica para atender às restrições de um método, e cujos defeitos o método denuncia. O nome dessa denúncia é conflito, e lê-lo como informação sobre a gramática é o que permite depois operar geradores automáticos de analisadores.
Objetivos, Competências e Habilidades
Objetivos de aprendizagem. Converter o modelo abstrato do módulo anterior em um analisador real e completar o front-end. Estabelecer a leitura de conflitos como instrumento de diagnóstico de gramáticas. Introduzir a recuperação de erros e o critério de qualidade que a orienta.
Competências a desenvolver. Capacidade de preparar uma especificação para atender às restrições de um método, preservando o que ela especifica. Capacidade de ler um conflito de análise como informação sobre a gramática, e não como falha da ferramenta. Capacidade de projetar comportamento diante de entrada malformada, tratando a qualidade do diagnóstico como requisito.
Habilidades a adquirir. Eliminar recursão à esquerda nos casos imediato e indireto, e aplicar fatoração. Calcular os conjuntos de primeiros e de seguidores, incluindo o tratamento das variáveis que derivam a cadeia vazia. Construir a tabela de análise e interpretar seus conflitos. Implementar um analisador por descida recursiva. Construir a árvore sintática abstrata, distinguindo-a da árvore de derivação concreta. Implementar recuperação de erros.
Estrutura das Aulas
Aulas 1 e 2 — Aula Teórica
Roteiro por blocos — a ordem é a mesma ordem das operações no projeto, e ela não é negociável nem aqui nem na tutoria.
Bloco de abertura — o programa que não termina
Escreva no quadro, sem anúncio nenhum, a gramática canônica das expressões:
E \to E + T \mid T \qquad T \to T * F \mid F \qquad F \to (E) \mid \mathbf{id}
Elogie-a de propósito, porque tudo o que você vai dizer é verdade: ela é não ambígua, exibe a precedência da multiplicação sobre a soma na estrutura das árvores, e agrupa à esquerda. Peça então que as duplas escrevam, no caderno, o começo da função que reconhece E pela primeira produção. Circule enquanto escrevem; alguém chega antes dos outros ao ponto de a função chamar a si mesma sem ter consumido símbolo algum.
Pare a sala nesse ponto e formule a pergunta que abre o módulo: por que a gramática mais bem escrita do capítulo anterior produz um programa que estoura a pilha? Ouça as hipóteses sem julgar. A que sempre aparece é “porque falta um caso base”, e ela é o gancho: responda que caso base não resolve, porque não há problema menor — há recursão sobre o mesmo problema, com a mesma entrada. Escreva no canto do quadro as três palavras que vão organizar as duas aulas: preparar, decidir, recuperar. Não as apague, e volte a elas no fechamento.
Bloco seguinte — por que descendente é derivação mais à esquerda
Este bloco é curto e não pode ser pulado, porque é ele que justifica tudo o que vem depois. Mostre que, numa derivação mais à esquerda, toda forma sentencial tem o formato x A \gamma com x \in \Sigma^* — isto é, o prefixo de terminais só cresce. Nenhum terminal produzido num passo será alterado por passo posterior, porque todos os passos posteriores agem à direita dele. É exatamente o que se precisa para ler a entrada da esquerda para a direita, uma vez, sem voltar.
Feche condenando o retrocesso, com as três razões nesta ordem de peso, porque a terceira é a que a turma nunca antecipa: custo exponencial; necessidade de tornar reversível o compilador inteiro, incluindo nós de árvore já criados e entradas já inseridas em tabelas; e, a mais consequente, os diagnósticos ficam inúteis, porque quando o analisador com retrocesso desiste a posição em que ele está é a da última tentativa, sem relação com o ponto onde quem escreveu o programa errou.
Bloco seguinte — preparar a gramática
Volte à gramática da abertura e faça a transformação no quadro, derivando-a em vez de a apresentar pronta. Pergunte que cadeias A deriva quando as produções são A \to A\alpha_1 \mid \cdots \mid A\alpha_m \mid \beta_1 \mid \cdots \mid \beta_n. Conduza até a resposta: toda derivação precisa sair da recursão por algum \beta_j, que por ser recursão à esquerda acaba no início, e depois dele vêm os \alpha_i em ordem. Escrever isso como gramática é imediato, e a forma nova sai sozinha:
A \to \beta_1 A' \mid \cdots \mid \beta_n A' \qquad A' \to \alpha_1 A' \mid \cdots \mid \alpha_m A' \mid \varepsilon
Aplicada às expressões, produz a gramática que você vai usar no resto das duas aulas — escreva-a num canto limpo do quadro e proteja esse canto:
E \to T E' \qquad E' \to +\,T\,E' \mid \varepsilon \qquad T \to F T' \qquad T' \to *\,F\,T' \mid \varepsilon \qquad F \to (E) \mid \mathbf{id}
Antecipe aqui o erro sistemático de implementação: esquecer de acrescentar a variável nova ao final das produções não recursivas, escrevendo A \to \beta_1 em vez de A \to \beta_1 A'. O resultado compila, roda e reconhece expressões com uma ocorrência do operador, falhando a partir da segunda. Dê a consequência como regra de teste: toda expressão de teste precisa ter pelo menos três operandos encadeados.
Sobre o caso indireto, seja econômico. Mostre S \to Aa \mid b e A \to Ac \mid Sd \mid \varepsilon, exiba a derivação A \Rightarrow Sd \Rightarrow Aad e diga que o ciclo passa por S, de modo que um algoritmo que só procure produções A \to A\alpha não o encontra. Cite o algoritmo geral por ordenação e substituição e pare aí; o que interessa didaticamente é a decisão de engenharia, que fica para a tutoria: verificar a ausência com uma detecção de ciclo no grafo das variáveis é preferível a escrever a eliminação geral, que viraria código morto.
A fatoração vem depois, e diga por quê antes de fazer: a eliminação reescreve os lados direitos e pode dissolver prefixos comuns que existiam antes, de modo que fatorar primeiro é trabalho jogado fora. Use o condicional com parte alternativa opcional, porque ele volta na segunda aula:
S \to \mathbf{if}\;E\;\mathbf{then}\;S \mid \mathbf{if}\;E\;\mathbf{then}\;S\;\mathbf{else}\;S \mid \mathbf{outro}
Quatro símbolos de prefixo comum, divergência no quinto. Fatorado, vira S \to \mathbf{if}\,E\,\mathbf{then}\,S\,S' \mid \mathbf{outro} com S' \to \mathbf{else}\,S \mid \varepsilon. Anuncie que essa gramática vai exibir, na segunda aula, um conflito que a fatoração não resolve, e não explique mais nada — a pendência declarada trabalha a favor.
Feche o bloco cobrando os três preços, porque a turma sai daqui achando que transformar gramática é de graça. Legibilidade: a gramática deixou de descrever a linguagem e passou a descrever o procedimento de análise, e é por isso que muitos projetos mantêm duas — a de referência publicada e a preparada que alimenta o analisador. Associatividade: a - b - c vira a - (b - c), mesma linguagem, resultado diferente. E produções vazias, que a gramática ganha várias de uma vez. Diga a frase que amarra os dois blocos: a preparação da gramática cria o problema que os conjuntos têm de resolver.
Primeira questão de discussão em duplas. “A gramática A \to A\alpha \mid \beta foi transformada em A \to \beta A' com A' \to \alpha A' \mid \varepsilon. Essa transformação: (a) preserva a linguagem e a árvore de derivação; (b) preserva a linguagem e altera o agrupamento natural da árvore; (c) altera a linguagem e preserva a árvore; (d) preserva as duas, e o problema de associatividade só existe para quem implementa mal.”
Aplique o procedimento inteiro: voto individual sem comentário seu, discussão em duplas, segundo voto. A resposta é (b). A alternativa (a) costuma vencer o primeiro voto, e o erro tem nome: confundir igualdade de linguagem com igualdade de árvore. Quem vota (d) parou perto — o agrupamento à direita é o comportamento natural da gramática transformada, não defeito de programação, e corrigi-lo exige decisão explícita na montagem da árvore.
Bloco seguinte — o cálculo conduzido dos dois conjuntos
Este é o bloco mais valioso do módulo e o que mais se ganha fazendo coletivamente no quadro. Não projete os conjuntos prontos. Calcule-os com a sala, sobre a gramática preparada que está protegida no canto do quadro, e escreva a tabela linha a linha.
Comece pela anulabilidade, e faça a turma verificar que as anuláveis são exatamente E' e T', cada uma pela sua produção vazia direta. Depois enuncie a regra do avanço nos primeiros e sublinhe a condição, porque é a linha que separa o cálculo certo do errado: acrescentam-se os elementos não vazios de \mathrm{PRIM}(X_1) e prossegue-se para X_2 se e somente se X_1 for anulável. Dê os dois sintomas opostos, que é o que torna a regra memorável: quem percorre o lado direito inteiro obtém conjuntos grandes demais e a tabela ganha conflitos que não existem; quem para sempre no primeiro símbolo obtém conjuntos pequenos demais e a tabela ganha células vazias onde deveria haver produção. Os dois erros rejeitam programas válidos, e o primeiro é muito mais difícil de diagnosticar porque a rejeição ocorre longe da causa.
Conduza então o cálculo dos seguidores em voz alta, passo a passo, na ordem em que a dependência aparece. Comece com \mathrm{SEG}(E) = \{\$\} por E ser o símbolo inicial. A produção F \to (E) coloca ), e \mathrm{SEG}(E) = \{\,)\,,\ \$\,\}. Em E \to TE' a variável E' está no fim, logo herda \mathrm{SEG}(E). Para T, o que segue é E', cujos primeiros não vazios são \{+\}, e como E' é anulável acrescenta-se também \mathrm{SEG}(E) — este é o passo que a turma erra, e vale marcá-lo no quadro. Consolide na tabela e deixe-a visível até o fim da segunda aula:
| Variável | Anulável | Primeiros | Seguidores |
|---|---|---|---|
| E | não | (, \mathbf{id} | ), \$ |
| E' | sim | +, \varepsilon | ), \$ |
| T | não | (, \mathbf{id} | +, ), \$ |
| T' | sim | *, \varepsilon | +, ), \$ |
| F | não | (, \mathbf{id} | *, +, ), \$ |
Duas observações fecham o bloco. A primeira, que alguém sempre levanta: E, T e F têm o mesmo conjunto de primeiros, e isso não é problema — o conflito só apareceria entre duas produções da mesma variável. A segunda é o marcador de fim de entrada, cujo esquecimento em \mathrm{SEG} do símbolo inicial tem sintoma característico: a produção vazia da variável mais externa não entra na tabela e o analisador rejeita o programa exatamente no último símbolo, de modo que todo teste com um trecho passa e só o arquivo completo falha.
Encerre nomeando o mecanismo: os dois cálculos são pontos fixos sobre conjuntos que só crescem, o mesmo que já apareceu nos símbolos anuláveis e que reaparecerá na análise de fluxo. Quem reconhece o padrão uma vez paga muito menos pela terceira aparição.
Segunda questão de discussão em duplas. “Ao calcular os seguidores da gramática preparada, alguém esqueceu de propagar \mathrm{SEG}(T) e registrou \mathrm{SEG}(T') = \emptyset. Qual é o sintoma? (a) o analisador passa a aceitar programas inválidos; (b) expressões com multiplicação falham e expressões com soma funcionam; (c) expressões com soma falham no operador de soma e expressões com multiplicação funcionam; (d) nada acontece, porque os seguidores só são consultados para variáveis anuláveis.”
A resposta é (c): sem seguidores, a produção T' \to \varepsilon não entra em célula nenhuma, e o analisador que chega em T' com um + na entrada reporta erro. A alternativa (d) é o distrator que ensina — a afirmação é verdadeira, e é por isso que o erro análogo em \mathrm{SEG}(F) seria inofensivo; só que T' é anulável, e a exceção não se aplica. Mostre no quadro os dois erros lado a lado, um benigno e outro fatal. Quem vota (a) não percebeu que conjunto pequeno demais só produz rejeição, nunca aceitação indevida.
Bloco de abertura da segunda aula — retomada pelo sintoma
Não recapitule em forma de resumo. Retome pelas três palavras do canto do quadro e pergunte qual delas já está paga — preparar está, as outras duas não. Então dê um sintoma e peça a causa, invertendo o sentido do raciocínio: “o analisador funciona em todos os testes de trecho e falha no último símbolo do arquivo completo — o que está errado?”. A turma que acompanhou o bloco dos seguidores responde de imediato, e essa resposta vale mais que qualquer revisão que você fizesse.
Bloco seguinte — a tabela e a condição de decisão
A tabela sai de uma regra só, e recomendo que você escreva no quadro a leitura em português em vez da fórmula: a produção A \to \alpha vai para a célula do terminal a quando a pode ser o primeiro símbolo do que \alpha produz, e vai para a célula de b quando \alpha pode não produzir nada e b pode vir logo depois de A. A primeira parte diz onde a produção começa; a segunda, onde ela desaparece.
Preencha a tabela das expressões com a sala, célula a célula, e faça a conferência numérica em voz alta: são treze células preenchidas — duas para E, três para E', duas para T, quatro para T' e duas para F — e nenhuma com duas produções.
| \mathbf{id} | + | * | ( | ) | \$ | |
|---|---|---|---|---|---|---|
| E | E \to TE' | E \to TE' | ||||
| E' | E' \to +TE' | E' \to \varepsilon | E' \to \varepsilon | |||
| T | T \to FT' | T \to FT' | ||||
| T' | T' \to \varepsilon | T' \to *FT' | T' \to \varepsilon | T' \to \varepsilon | ||
| F | F \to \mathbf{id} | F \to (E) |
Chame a atenção para as células vazias, porque a turma as lê como desperdício. Cada uma é um erro detectável com informação anexa: o analisador que chega em F com um + na entrada sabe, olhando a linha, que os terminais aceitáveis ali são ( e \mathbf{id}, e pode dizer isso na mensagem. É a ponte para o bloco de recuperação.
Agora o deslocamento de atitude, que é o ponto alto da segunda aula. Quando uma célula recebe duas produções, a reação instintiva é tratar o fato como falha do algoritmo. Diga com todas as letras que a leitura é invertida: a tabela está certa, e o que ela afirma é que naquela situação um símbolo de antecipação não basta. Dê o catálogo curto de causas: produções em conflito que começam pela mesma variável do lado esquerdo indicam recursão à esquerda remanescente; prefixo de símbolos compartilhado indica falta de fatoração; e, se nenhuma das duas se aplica numa gramática já preparada, a causa provável é ambiguidade real, que nenhuma transformação mecânica resolve.
Volte então ao condicional prometido na primeira aula. Sobre a gramática já fatorada, \mathrm{PRIM}(\mathbf{else}\,S) = \{\mathbf{else}\} e \mathrm{SEG}(S') contém \mathbf{else}, porque S' está no fim de S \to \mathbf{if}\,E\,\mathbf{then}\,S\,S' e herda \mathrm{SEG}(S). A célula M[S', \mathbf{else}] recebe as duas produções: a fatoração não resolveu porque o problema não era prefixo comum, era ambiguidade. Registre a solução como decisão consciente — resolve-se por convenção, escolhendo a produção não vazia, o que associa a parte alternativa ao condicional mais próximo. Essa regra não sai da gramática, e por isso precisa ficar escrita em vez de implícita na ordem em que o código testa alternativas.
Terceira questão de discussão em duplas. “A célula M[S', \mathbf{else}] recebeu duas produções numa gramática já fatorada. A causa mais provável é: (a) recursão à esquerda que sobrou; (b) falta de fatoração adicional; (c) ambiguidade genuína da gramática; (d) erro no cálculo dos seguidores.”
A resposta é (c). Quem vota (b) aplica o remédio anterior por reflexo, e é o erro majoritário no primeiro voto — peça a essa dupla que tente fatorar no quadro e mostre onde trava, porque não há prefixo comum a extrair. Quem vota (d) tem hipótese verificável, e é a melhor oportunidade do bloco: mande conferir \mathrm{SEG}(S') na frente da turma. A conferência termina sem achar erro, e é esse resultado que é o conteúdo.
Antes de sair do bloco, delimite honestamente o poder do método com um exemplo só. A linguagem L = \{a^n b^n \mid n \ge 1\} \cup \{a^n c^n \mid n \ge 1\} é determinística e não admite gramática tratável por antecipação finita alguma: o analisador descendente teria de decidir, no primeiro passo, se está no ramo dos b ou no dos c, e essa informação só aparece depois de n símbolos. É o argumento honesto a favor dos métodos ascendentes, e anunciá-lo aqui prepara o módulo seguinte. Complete com a alavanca de projeto: um prefixo comum que atrapalha pode ser eliminado mudando a linguagem, não a gramática.
Bloco de construção ao vivo — a gramática de um lado, o código do outro
Este é o bloco de code-along e o ativo didático central do módulo. Divida o quadro ao meio: gramática preparada à esquerda, código à direita, produção a produção. Avise a sala para abrir o editor e digitar junto, e circule para conferir — quem só assiste não aprende este bloco.
Escreva uma função por variável, na mesma ordem em que elas aparecem, e verbalize a correspondência a cada linha: para cada terminal do lado direito, verificar e avançar; para cada variável, chamar a função correspondente; produção vazia, não fazer nada e retornar. Quando a terceira função estiver pronta, pare e cobre a observação que fecha o módulo anterior: a pilha de chamadas do programa é a pilha do autômato, e nenhuma linha de código de pilha foi escrita. Peça a quem fez o traçado manual de configurações que diga em voz alta o que está reconhecendo ali.
O ponto delicado vem na variável auxiliar, e ele não sai da transcrição mecânica. Transcrever A' \to \alpha A' \mid \varepsilon literalmente produz função recursiva que funciona e monta a árvore com agrupamento à direita. Escreva as duas versões lado a lado e faça o traçado sobre três operandos com subtração: a recursiva devolve a - (b - c), o laço com árvore acumulada devolve (a - b) - c. Diga em voz alta o que torna esse defeito o mais caro do módulo — ele não impede o programa de funcionar, passa em qualquer teste de aceitação e rejeição, e só se manifesta quando alguém avaliar a árvore, módulos adiante, para operadores não associativos. Turma que testa só com somas entrega analisador defeituoso convencida de que está correta.
Aproveite a diferença de uma palavra que carrega decisão de projeto: onde a gramática permite encadeamento, a função tem um laço; onde ela recusa a < b < c, a função tem um teste condicional simples. Não é detalhe de implementação, é a sintaxe da linguagem decidindo.
Termine o bloco projetando a implementação de referência sobre um programa de exemplo e exibindo os números do relatório, que tornam concreta a redução: centenas de caracteres entram, algumas dezenas de símbolos saem do analisador léxico e pouco mais de uma dezena de nós sobra na árvore. A diferença não é perda — o que sumiu foi pontuação, parênteses, palavras reservadas e as variáveis auxiliares que as transformações criaram.
Bloco seguinte — recuperar-se sem inventar erros
Abra pelo critério, escrito no quadro, porque a métrica errada é sedutora: a qualidade de uma estratégia de recuperação não se mede pelo número de erros reportados, e sim pela correspondência entre eles e os defeitos reais da entrada. Uma mensagem correta vale mais que dez, e um erro real seguido de vinte inventados é pior do que reportar só o primeiro e parar. Dê o teste honesto como rotina de trabalho: preparar um arquivo com número conhecido de defeitos em posições conhecidas e conferir se há uma mensagem para cada, no lugar de cada.
Apresente o modo pânico e concentre o bloco no que de fato decide a qualidade, que é a escolha dos pontos de sincronização. Delimitadores de fim de construção são a escolha óbvia e insuficiente — se o próximo ponto e vírgula está dentro da construção seguinte, o descarte apaga um trecho correto e a mensagem seguinte aponta um lugar sem defeito. A correção são as palavras que iniciam construção, que param o descarte sem serem consumidas. E há a distinção que o descuido apaga: o ponto e vírgula encerra a construção em que o erro ocorreu e é consumido junto, ao passo que a chave de fechamento pertence ao bloco de fora e precisa ser vista por quem chamou; consumi-la gera erro derivado imediato.
Feche com as duas salvaguardas, apresentadas como consequência e não como paranoia. A garantia de progresso torna-se necessária justamente quando a recuperação melhora: pontos que param sem consumir são a fonte natural do laço que não avança, e o sintoma é o compilador travar sem mensagem nenhuma. A supressão durante a recuperação silencia os diagnósticos enquanto o analisador se reorganiza e é o que elimina a cascata.
Conte aqui, com nome e sintoma, os dois defeitos que a implementação de referência teve: o uso após movimento, que fazia toda declaração bem-sucedida disparar um erro falso apontando justamente a palavra que o analisador esperava; e o laço que não progride, criado pela própria melhoria dos pontos de sincronização. Os dois apareceram rodando, e nenhum apareceria em revisão de código.
Bloco de fechamento — a árvore projetada, e volta ao gancho
Feche pelo que sai da fase. A árvore sintática abstrata não é derivada da gramática, é projetada: sem delimitadores, sem palavras reservadas redundantes e sem as variáveis auxiliares que as transformações criaram — expor essas variáveis seria expor às fases seguintes uma decisão de implementação do analisador, e elas passariam a depender dela.
Trate como obrigatórios os dois campos que a turma subestima. Posição no texto-fonte em todo nó, sem exceção, porque as fases seguintes precisarão reportar erros e a posição só existe naturalmente aqui; um verificador de tipos que diz “operação inválida” sem dizer onde é praticamente inútil, e a diferença é um campo por nó. E tipo do nó em forma sobre a qual as fases seguintes possam despachar. Sobre a representação, apresente as duas soluções defensáveis — hierarquia de tipos e nó uniforme com marcador — e recuse dar resposta universal; o que você exige é que a troca aceita fique registrada por escrito.
Volte ao gancho. Apague a versão ingênua da função que reconhece E e rode, na frente da turma, o analisador construído sobre a gramática preparada, sobre a mesma expressão com três operandos. Termine pelas três palavras do canto do quadro: a primeira transformou uma gramática que descreve bem a linguagem em outra que um programa consegue seguir; a segunda substituiu a adivinhação do módulo anterior por consulta a dois conjuntos; a terceira separou um analisador utilizável de um exercício. E anuncie o corte que vem: tudo o que o compilador verificou até aqui foi forma, e a árvore que acabou de sair pode representar um programa que usa um nome nunca declarado.
Aulas 3 a 6 — Tutoria do Projeto Integrador
Quatro aulas de tutoria — preparação da gramática com verificação, conjuntos e tabela, analisador recursivo com árvore, e recuperação de erros. Segundo marco de consolidação.
O andaime aqui já é bem menor que o dos módulos iniciais, e isso precisa ser dito: você fornece o critério de verificação e a ordem das operações, não a solução. O que substitui o andaime é o projeto de referência aberto e projetado durante as duas sessões — os grupos veem a gramática preparada, o relatório de transformações, a tabela e a árvore da linguagem de reconhecimento de padrões, e produzem o equivalente para a linguagem que escolheram.
Tenha à mão, além do código, os três defeitos documentados na referência. Eles valem mais em tutoria do que na aula teórica, porque aqui o grupo os está cometendo enquanto você conta.
Primeira sessão de tutoria — preparar e verificar, antes de escrever qualquer função
Institua uma trava explícita na abertura: nenhum grupo escreve linha de analisador nesta sessão. A regra causa desconforto e é o item de maior retorno do módulo inteiro — o grupo que programa sobre gramática com recursão à esquerda gasta a sessão seguinte inteira depurando uma recursão infinita cuja causa estava na gramática desde o módulo 8.
Comece pedindo que cada grupo aponte, na própria gramática, toda produção que começa pela variável do lado esquerdo. Circule conferindo, porque metade dos grupos vai afirmar que não tem nenhuma e vai estar errada — a recursão costuma estar na produção de expressão ou de lista, escrita justamente para dar associatividade à esquerda. Feita a eliminação, exija o registro: uma linha por transformação, com a variável, o tipo da transformação e a causa. Projete o relatório da referência para mostrar o formato, com as seis transformações registradas e as duas variáveis auxiliares criadas na eliminação.
Sobre a recursão indireta, conduza a decisão de engenharia em vez de dar a resposta. Pergunte a cada grupo se a gramática dele tem ciclo, e depois pergunte como ele sabe. Quem responde “não tem” sem verificação recebe a contraproposta: implementar a detecção, que é um percurso em profundidade sobre o grafo das variáveis, e deixar a eliminação geral de fora. Diga por que, com o argumento que eles vão reusar a vida inteira: algoritmo escrito sem caso de uso é código morto, que ninguém exercita e que apodrece; verificar a ausência custa poucas linhas e protege contra a gramática mudar depois.
A fatoração vem em seguida e é onde aparece a decisão mais interessante da sessão. Peça que procurem o prefixo comum mais longo entre quaisquer duas produções da mesma variável, não o primeiro símbolo comum — extrair um símbolo por vez obriga a refatorar a variável recém-criada e produz uma cascata de auxiliares que torna a gramática ilegível. Mostre a fatoração de quatro símbolos da referência, em que as duas produções de ação compartilham o prefixo inteiro e só divergem no quinto símbolo, e comente que foi o desenho da linguagem que a tornou inevitável.
A segunda metade da sessão é o cálculo dos conjuntos, e ele começa à mão. Antes de qualquer código, cada grupo calcula anuláveis, primeiros e seguidores da própria gramática no papel, e apresenta a tabela a você. Confira duas coisas em cada tabela, sempre as mesmas: se as variáveis auxiliares recém-criadas aparecem entre as anuláveis, e se o marcador de fim de entrada está nos seguidores do símbolo inicial. O primeiro item denuncia quem não percebeu que a preparação introduziu produções vazias; o segundo é o esquecimento clássico, cujo sintoma — falha exatamente no último símbolo do arquivo, com todo teste de trecho passando — vale repetir em voz alta.
Feche a sessão com a construção da tabela e a leitura dos conflitos. Peça que cada grupo construa a tabela duas vezes: sobre a gramática original e sobre a preparada. É essa comparação que transforma o preparo de burocracia em resultado — na referência, a gramática original produz dezenas de conflitos agrupáveis por causa, e a preparada produz zero. Para cada conflito remanescente, exija a causa nomeada segundo o catálogo da aula teórica, e não a correção imediata. Diga explicitamente que, na avaliação, a interpretação do conflito vale mais que o seu desaparecimento.
Segunda sessão de tutoria — o analisador, a árvore e a recuperação
Abra pela disposição física do trabalho, porque ela é o método: gramática preparada de um lado da tela, código do outro, uma função por variável, na mesma ordem. Circule cobrando essa disposição — o grupo que escreve o analisador sem a gramática visível perde a única propriedade que torna o método barato, que é poder ler um no outro.
Institua o revezamento de papéis com intervalo curto, porque esta é a sessão em que ele mais se paga e a que mais resiste. O piloto digita a função da vez; o navegador lê em voz alta a produção correspondente e confere símbolo a símbolo. Trocam a cada função concluída. Grupos em que só um integrante digita o módulo inteiro chegam à análise semântica com um integrante que não sabe onde a árvore é construída.
Dois pontos exigem intervenção sua, e nenhum dos dois aparece sozinho. O primeiro é a variável auxiliar: quando o grupo chegar nela, pare o trabalho e peça o traçado no papel, sobre três operandos, com um operador não associativo da linguagem dele. Deixe que descubram o agrupamento à direita antes de você dizer qual é a correção. Quem descobre sozinho escreve o laço com árvore acumulada e não esquece mais; quem recebe a instrução pronta transcreve e reintroduz o defeito na primeira refatoração. Sublinhe que o analisador com associatividade errada passa em todo teste de aceitação e rejeição — é o motivo de o teste ter de olhar a árvore desenhada, e não a saída do reconhecimento.
O segundo é a decisão sobre o que a árvore carrega, e ela merece discussão explícita com o grupo parado. Faça sempre as mesmas três perguntas: que nós desta árvore serão procurados na tabela de símbolos no próximo módulo; que nós carregam operador sobre o qual a verificação de tipos vai decidir; e que nós carregam o rótulo que a geração de código vai colocar no objeto produzido. O que não responder a nenhuma das três não entra. Exija posição em todo nó, sem exceção, e recuse a economia de guardá-la só onde parece necessária — recuperá-la depois é caro e impreciso, e a mensagem de erro semântica sem posição é praticamente inútil.
A última parte da sessão é a recuperação de erros, e é onde o cronograma dos grupos costuma quebrar. Não deixe que ela seja tratada como refinamento: peça a política por escrito — quais são os símbolos de sincronização, quais param sem serem consumidos, e quando o sinalizador de supressão liga e desliga — antes que o grupo escreva a segunda função. Conte a sequência de erros da referência na ordem em que ela aconteceu, porque é uma sequência que os grupos vão repetir: parar só em ponto e vírgula e apagar um bloco correto; acrescentar as palavras que iniciam construção e criar o laço que não progride; e, por fim, descobrir que ponto e vírgula se consome e chave de fechamento não.
Feche o módulo exigindo a demonstração ponta a ponta com um arquivo de defeitos deliberados, preparado pelo próprio grupo, com o número e as posições dos defeitos anotados antes de rodar. Confira mensagem a mensagem contra a anotação. Grupo que reporta o número certo de mensagens nos lugares errados não passou no critério, e é essa distinção que fecha a ideia central da parte de recuperação.
O que registrar no seu diário ao fim da segunda sessão
Anote três coisas por grupo. Quantos conflitos a gramática original produziu e se o grupo soube nomear a causa de cada família. Se a árvore agrupa à esquerda no teste com operador não associativo, verificada por você e não relatada pelo grupo. E quem, no grupo, conseguiu justificar uma linha da tabela de conjuntos quando você escolheu a pessoa em vez de deixar o grupo escolher. A terceira anotação é a que se paga no marco final: compreensão concentrada num integrante só aparece aqui com clareza suficiente para ser corrigida a tempo.
Entregáveis e Avaliação
A entrega é consolidada e tem cinco partes, na ordem em que foram construídas: a gramática transformada com registro de cada transformação e verificação de que a linguagem não mudou; os conjuntos calculados, em tabela; o analisador funcionando e produzindo a árvore; a recuperação de erros com exemplos de programas malformados e as mensagens efetivamente produzidas; e o front-end demonstrado ponta a ponta.
Confira cada entrega contra a mesma sequência de itens, para todos os grupos. Nenhuma produção começa pela própria variável do lado esquerdo. A ausência de recursão indireta foi verificada, e não suposta. Nenhum par de produções da mesma variável compartilha prefixo. Há uma linha de registro por transformação, com a causa. Os conjuntos tratam explicitamente as variáveis anuláveis. A tabela não tem célula com duas produções — ou, se tem, o conflito está interpretado e a resolução está escrita. A árvore agrupa à esquerda no teste com três operandos e operador não associativo. E há uma mensagem para cada defeito real do arquivo de teste, no lugar de cada.
Duas orientações de peso na correção. A primeira: na parte de conflitos, a interpretação vale mais do que a solução. Grupo que identifica a causa e explica a resolução escolhida entendeu o módulo; grupo que fez o conflito desaparecer sem saber como não entendeu, mesmo com a tabela limpa. A segunda: recuse entrega sem recuperação de erros justificada por falta de tempo. Ela é escopo mínimo — a decisão de como reportar e onde sincronizar atravessa o analisador inteiro, e acrescentá-la depois exige alterar todas as funções que já funcionavam.
Registre no componente contínuo a pontualidade da entrega, a contribuição nas discussões em duplas e o engajamento na tutoria. Por ser marco de consolidação, cobre também que qualquer integrante saiba justificar uma linha da tabela de conjuntos do próprio projeto, escolhendo você a pessoa em vez de deixar o grupo escolher.
Orientações Sobre o Aplicativo
Use o aplicativo para as três votações das aulas teóricas, com a projeção anônima. O dado que mais interessa é o da segunda questão, a dos seguidores esquecidos, cujo distrator (d) afirma algo verdadeiro em outro caso: a dispersão do primeiro voto entre ele e a alternativa correta mede exatamente o que o módulo quer instalar. Se a turma convergir para o distrator, refaça a definição de anulabilidade antes da discussão em duplas — a técnica só corrige quando há quem tenha entendido.
Guarde os histogramas das três questões e compare a distância entre o primeiro e o segundo voto com a que você registrou no módulo de análise léxica. É a melhor estimativa disponível de quanto o eixo sintático custou a esta turma, e é ela que orienta o tamanho da revisão de conjuntos na abertura do módulo seguinte, que vai comparar as duas famílias de analisadores sobre a mesma gramática.
Acompanhe também o engajamento no estudo do material, que responde por metade do componente contínuo. Este é o módulo de maior queda esperada, e a causa é identificável: a seção de conjuntos exige leitura com papel ao lado. Grupo cujo engajamento cai aqui e cuja entrega traz conjuntos calculados por tentativa chega à análise semântica com árvores erradas sem saber — aborde-o antes de a entrega vencer.
Pontos de Atenção Específicos
A ordem das operações não é negociável, e a turma vai querer inverter. Eliminar recursão à esquerda, verificar a ausência de recursão indireta, fatorar, e só então calcular os conjuntos. Calcular antes de terminar as transformações produz números que estarão errados assim que a gramática mudar, e ninguém os recalcula — apenas passa a desconfiar da tabela.
O grupo ansioso começa a programar sobre gramática com recursão à esquerda. É o risco número um do módulo e custa uma sessão inteira de depuração de uma recursão infinita cuja causa estava escrita na gramática desde o começo. Trate a verificação da forma da gramática como condição para começar a codificar, e verifique-a grupo a grupo antes de liberar.
O defeito de associatividade não impede o programa de funcionar. Repita isso nas duas aulas e na tutoria, porque é o único defeito do módulo que sobrevive a todos os testes que um grupo escreveria espontaneamente. Exija o teste com três operandos e operador não associativo desde a primeira versão do analisador, e confira o desenho da árvore, não a saída do reconhecimento.
A recuperação de erros é o que fica por fazer. Grupos a deixam por último e, deixada por último, não é feita. Anuncie desde a primeira sessão de tutoria que ela é escopo mínimo, e peça a política de recuperação por escrito antes da segunda função do analisador estar pronta.
Cuidado com a digressão sobre geradores de analisadores. Alguém vai perguntar por que não se usa uma ferramenta que gera o analisador a partir da gramática. A resposta é curta: geradores produzem tabelas, porque gerar tabela é mais fácil que gerar código, e quem os opera se comunica com eles quase só por relatórios de conflito — que é o que este módulo ensina a ler. Não vá além disso; o ferramental à mão é decisão travada do projeto.
Não antecipe a comparação com os métodos ascendentes. A pergunta “então existe método melhor?” aparece no bloco dos conflitos. Responda que sim, para uma classe estritamente maior de gramáticas e ao preço de construção mais complicada, diga que a comparação fundamentada é o assunto do módulo seguinte, e siga.