flowchart LR
M06["Módulo 6<br/>Limites das linguagens<br/>regulares<br/>a falha demonstrada"]
M08["Módulo 8<br/>Gramáticas livres<br/>de contexto<br/>o lado gerativo"]
M09["Módulo 9<br/>Autômatos de pilha<br/>o lado reconhecedor<br/>SEM IMPLEMENTAÇÃO"]
M10["Módulo 10<br/>Análise sintática<br/>descendente<br/>o modelo vira código"]
M06 --> M08 --> M09 --> M10
subgraph ENTREGA["O que o módulo 9 deixa pronto"]
D1["Modelo formal do<br/>reconhecedor e traçado<br/>com pilha explícita"]
D2["Autômato de um estado<br/>construído da gramática<br/>expande e casa"]
D3["Não equivalência entre<br/>determinismo e não<br/>determinismo"]
D4["Pendências dos módulos<br/>anteriores saldadas"]
end
M09 --- ENTREGA
D2 -.->|"vira analisador recursivo"| M10
D3 -.->|"justifica a restrição LL(1)"| M10
Autômatos de Pilha — Plano de Aula
Documento exclusivo do professor. Este é o guia operacional das seis aulas do 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 a leitura pedagógica dos erros de traçado perdem função assim que o estudante as lê antes da aula.
Visão Geral do Módulo
Onde este módulo fica — é a ponte entre a gramática escrita no módulo 8 e o analisador escrito no módulo 10.
Este módulo tem uma característica que nenhum outro dos anteriores tem, e convém encarar isso de frente antes de planejar a semana: ele é o mais teórico do semestre e é o único até aqui que não deixa uma peça nova de compilador funcionando. O que ele deixa é o modelo abstrato do analisador sintático — e a experiência de quem já deu o módulo 10 é que a diferença entre uma turma que traçou o autômato à mão e uma turma que não traçou aparece já na primeira aula do módulo seguinte, na forma de estudantes que acham que as funções mutuamente recursivas funcionam por sorte.
A condução tem, portanto, um objetivo prioritário e explícito: a construção que parte da gramática, com o traçado passo a passo, merece tempo desproporcional à sua dificuldade técnica. Ela é curta — um estado, duas famílias de transição — e é o ponto do semestre com maior retorno pelo esforço investido. Tudo o mais deste módulo pode ser tratado com economia; essa construção, não.
O segundo eixo é o resultado que contraria a intuição formada no módulo 5, onde determinismo e não determinismo eram equivalentes e a construção de subconjuntos fazia a conversão pagando em tamanho. Aqui isso é falso, e a falsidade tem consequência de engenharia direta — é a razão de existir uma família de métodos de análise em vez de um método único. Retomar o contraste com o quadro dos dois níveis lado a lado é o que fixa os dois resultados em vez de deixar o segundo apagar o primeiro.
O terceiro eixo é de gestão. Sem tarefa de implementação, os grupos leem o módulo como folga. Chegue à primeira sessão de tutoria com o levantamento das pendências de cada grupo já feito, por escrito, a partir das entregas anteriores.
Objetivos, Competências e Habilidades
Objetivos de aprendizagem. Apresentar o modelo de máquina correspondente às gramáticas livres de contexto e estabelecer a equivalência entre os dois formalismos. Introduzir o resultado que distingue este nível do anterior — a não equivalência entre determinismo e não determinismo — e suas consequências para a prática da análise sintática.
Competências a desenvolver. Capacidade de reconhecer que uma propriedade válida num nível de abstração não se transfere automaticamente para outro. Capacidade de compreender por que uma restrição teórica se traduz em uma escolha de engenharia, e de aceitar limitações de método com base em razão e não em convenção.
Habilidades a adquirir. Definir formalmente o autômato de pilha e suas duas convenções de aceitação. Traduzir uma gramática para o autômato de pilha correspondente. Traçar manualmente o reconhecimento de uma cadeia, acompanhando a evolução da pilha. Explicar por que o determinismo restringe a classe reconhecida neste nível e o que isso implica para a análise sintática prática.
Estrutura das Aulas
Aulas 1 e 2 — Aula Teórica
Roteiro por blocos — a ordem importa, porque cada bloco responde a uma insuficiência deixada pelo anterior.
Bloco de abertura — a pergunta ingênua sobre memória
Comece sem definição alguma, com uma pergunta escrita no quadro: se o problema do autômato finito é ter pouca memória, por que não damos a ele mais memória e encerramos o assunto? Deixe a sala responder e anote as sugestões. Elas quase sempre vêm na forma “põe um contador” ou “põe uma lista”.
Aproveite a primeira sugestão, porque ela está certa pela metade e o modo de mostrar isso é concreto. Escreva no quadro as cadeias ((())) e ([)]. Um contador reconhece parênteses de um só tipo — incrementa na abertura, decrementa no fechamento, testa zero no fim. Diante da segunda cadeia ele falha, e a razão merece ser dita na frase mais curta possível: o contador guarda uma quantidade e não uma sequência, sabe que há duas aberturas pendentes e não sabe quais.
Feche o bloco com o abismo, porque é ele que vai segurar a atenção até o fim da segunda aula. Anuncie que uma máquina finita com duas pilhas independentes é equivalente em poder a uma máquina de Turing, e que sobre uma máquina dessas quase nada é decidível. Não demonstre agora: escreva no canto do quadro “por que não duas pilhas?” e deixe a pergunta ali durante as duas aulas.
Bloco seguinte — a definição, e a única coisa que se pode errar nela
Escreva a sétupla e, sobretudo, a assinatura da função de transição:
\delta : Q \times (\Sigma \cup \{\varepsilon\}) \times \Gamma \longrightarrow \mathcal{P}_{\text{fin}}(Q \times \Gamma^{*}).
Conduza a leitura por três perguntas. Por que \varepsilon no domínio? Porque a máquina precisa mexer na pilha sem consumir entrada, e a construção que parte da gramática é feita quase inteiramente dessas transições. Por que o domínio exige um símbolo de pilha? Porque toda transição consulta o topo, e portanto uma máquina com a pilha vazia está travada — detalhe burocrático que dá sentido à aceitação por pilha vazia, dois blocos adiante. Por que o contradomínio é um conjunto de pares? Porque é aí, e só aí, que mora o não determinismo.
Pare no ponto que produz o erro mais comum do módulo e trate-o com ostentação. A cadeia \gamma substitui o topo, e o símbolo mais à esquerda de \gamma fica no topo. Demonstre a armadilha em vez de anunciá-la: peça que a turma empilhe o corpo E + T “um símbolo por vez, na ordem em que está escrito” e escreva o resultado no quadro, T + E. Diga que o autômato assim obtido reconhece as cadeias espelhadas e que o defeito é invisível enquanto o corpo tiver um símbolo só — o caso dos primeiros exemplos que qualquer um testa.
Bloco seguinte — descrição instantânea e o primeiro traçado resolvido
Introduza a tripla (q, w, \alpha) e fixe a convenção da pilha escrita do topo para a base, justificando-a pela legibilidade: o símbolo consultado é sempre o primeiro caractere de \alpha. Exija a mesma convenção nos traçados da turma e não negocie — traçados que trocam a orientação no meio do caminho são fonte inesgotável de confusão.
Construa no quadro, com a sala, o autômato para L = \{a^{n}b^{n} : n \ge 1\}, com Q = \{q_0, q_1, q_2\}, \Gamma = \{A, Z_0\}, F = \{q_2\} e
\delta(q_0, a, Z_0) = \{(q_0, A Z_0)\}, \quad \delta(q_0, a, A) = \{(q_0, AA)\}, \quad \delta(q_0, b, A) = \{(q_1, \varepsilon)\}, \delta(q_1, b, A) = \{(q_1, \varepsilon)\}, \quad \delta(q_1, \varepsilon, Z_0) = \{(q_2, Z_0)\}.
Trace aabb na frente deles, uma linha por passo: parte de (q_0, aabb, Z_0); lê a e empilha marca, ficando (q_0, abb, A Z_0); lê o segundo a, ficando (q_0, bb, A A Z_0); lê b e desempilha, indo a (q_1, b, A Z_0); lê o segundo b e desempilha, chegando a (q_1, \varepsilon, Z_0); e a transição vazia leva a (q_2, \varepsilon, Z_0), com q_2 \in F. Aceita em cinco passos.
O que a turma não faz sozinha, e vale mais do que o traçado que aceita, são as rejeições. Faça as três, curtas: sobre aab, chega-se a (q_1, \varepsilon, A Z_0), não há transição vazia para topo A, a máquina trava e q_1 \notin F; sobre abb, chega-se a q_2 com um b por ler e sem transição a partir de q_2; sobre ba, não há transição para (q_0, b, Z_0). Feche com a comparação que dá a medida do ganho: três estados e uma pilha resolvem um problema que nenhum autômato finito resolve com nenhuma quantidade de estados.
Primeira questão de discussão em duplas. “No autômato acima, a transição \delta(q_1, \varepsilon, Z_0) = \{(q_2, Z_0)\} existe para: (a) esvaziar a pilha; (b) permitir aceitar a cadeia vazia; (c) tornar observável o fato de que todas as marcas foram consumidas; (d) evitar que a máquina trave ao ler o último b.”
Voto individual, discussão em duplas, segundo voto — sem revelar a resposta antes. A resposta é (c). Quem vota (a) não percebeu que a transição repõe Z_0 e não remove nada. Quem vota (b) comete o erro mais frequente e mais interessante: confunde a transição vazia do autômato com a cadeia vazia da entrada, e desfazer isso agora poupa metade dos enganos do traçado da segunda aula. Quem vota (d) raciocina na direção certa e trocou o instante.
Bloco seguinte — o não determinismo que não é adorno
O exemplo anterior é determinístico, e isso dá à turma a impressão errada de que o conjunto no contradomínio era generosidade da definição. Desfaça a impressão com os palíndromos de comprimento par, L_{pp} = \{ww^{R}\}.
Conduza pela dificuldade, não pela solução. A estratégia é evidente — empilhar a primeira metade, casar a segunda desempilhando — e exige uma informação que a máquina não tem: onde termina a primeira metade. Escreva abba no quadro e pergunte como a máquina descobre que o meio é depois de ab. A resposta é que ela não descobre: ela adivinha, porque a definição de aceitação é existencial e basta que algum ramo funcione.
Registre as transições, com o palpite isolado e nomeado:
\delta(q_0, c, X) = \{(q_0, cX),\ (q_1, X)\}, \qquad \delta(q_1, c, c) = \{(q_1, \varepsilon)\}, \qquad \delta(q_1, \varepsilon, Z_0) = \{(q_2, Z_0)\}.
Aponte o segundo par de \delta(q_0, c, X) e leia-o como uma frase: “o meio é aqui, e o símbolo que acabei de ler já pertence à segunda metade”. Avise que esta máquina volta na segunda aula como contraexemplo de um teorema — é bom que a turma veja a máquina antes do resultado.
Bloco de fechamento da primeira aula — as duas convenções e o marcador de fundo
Escreva as duas definições de aceitação lado a lado e conduza pelas assimetrias, que é o que se retém: por estado final, o conteúdo da pilha ao terminar é irrelevante; por pilha vazia, o estado é irrelevante, e por isso F costuma ser tomado vazio nessa convenção.
Enuncie a equivalência entre as duas para autômatos não determinísticos e esboce apenas o mecanismo comum às duas construções: um símbolo novo X_0, fora de \Gamma, instalado no fundo por uma transição vazia inicial. Explique o papel dele nas duas direções, porque são papéis diferentes e a turma tende a achar que é o mesmo truque repetido. Ao converter pilha vazia em estado final, X_0 transforma um evento invisível — a pilha ficar vazia, situação em que a máquina trava — em um evento observável, que é ter um símbolo específico no topo. Ao converter estado final em pilha vazia, o papel é defensivo: sem ele, a pilha poderia esvaziar no meio da simulação por transições legítimas do autômato original e a máquina aceitaria por acidente.
Feche com a consequência que a turma vai encontrar no projeto, e diga que ela é teórica e não de codificação: um autômato determinístico que aceita por pilha vazia só reconhece linguagens livres de prefixos, porque a computação que esvazia a pilha sobre um prefixo é a única que existe. É essa a razão pela qual analisadores reais exigem um marcador explícito de fim de entrada — sem ele, um analisador que esvazia a pilha ao completar a primeira declaração de um programa reporta “programa válido” e ignora o resto do arquivo.
Bloco de abertura da segunda aula — retomada pela dívida, não por resumo
Não recapitule. Aponte a pergunta que ficou no canto do quadro — “por que não duas pilhas?” — e diga que a resposta vem no fim desta aula. Em seguida faça a única retomada que interessa: peça que alguém diga, sem consultar, o que a pilha guarda no autômato de a^n b^n. A resposta esperada é “uma marca por a ainda não casado”. Guarde essa formulação, porque o bloco seguinte a generaliza e a generalização é o coração do módulo.
Bloco seguinte — a construção de um estado só
Este é o bloco que justifica o módulo; reserve-lhe folga. Escreva a construção inteira, que cabe em quatro linhas. Dada G = (V, \Sigma, P, S), tome o autômato com um único estado q, alfabeto de pilha V \cup \Sigma, símbolo inicial de pilha S, aceitação por pilha vazia, e
\delta(q, \varepsilon, A) = \{(q, \beta) : A \to \beta \in P\}, \qquad \delta(q, a, a) = \{(q, \varepsilon)\}.
Nomeie as duas famílias com as palavras que a turma vai usar o resto do semestre: expandir e casar. Expandir troca uma variável do topo pelo corpo de alguma produção, sem consumir entrada — e é aqui que vive todo o não determinismo. Casar remove um terminal do topo exigindo o mesmo terminal na entrada, consumindo-o.
Pare para o resultado que merece pausa e que a turma passa batido se você não o disser: o autômato tem um estado só. Todo o poder do modelo está na pilha e nenhum no controle finito. Os estados, que eram tudo no autômato finito, aqui existem apenas para dar conformidade formal à definição.
Enuncie então o invariante, que é o que se leva para o módulo 10. Se u é o prefixo já consumido e \alpha é a pilha do topo para a base, então S \Rightarrow^{*} u\alpha por derivação mais à esquerda. Traduza para a frase operacional e escreva-a no quadro: a pilha é uma lista de obrigações pendentes. Expandir troca uma obrigação por obrigações menores; casar cumpre uma obrigação elementar gastando um símbolo da entrada; e aceitar é não sobrar obrigação nem entrada.
Bloco seguinte — o traçado completo, feito no quadro
Tome a gramática de expressões na forma estratificada, E \to E + T \mid T, T \to T * F \mid F, F \to (\,E\,) \mid \text{id}, e trace \text{id} + \text{id} com a sala. Escreva uma linha por passo, pilha à esquerda com o topo primeiro.
Parte de pilha E com a entrada inteira. Expande E \to E + T e a pilha fica E + T. Expande E \to T, ficando T + T. Expande T \to F, ficando F + T. Expande F \to \text{id}, ficando \text{id} + T. Casa \text{id}, consumindo o primeiro símbolo e deixando +\,T. Casa +, deixando T. Expande T \to F e depois F \to \text{id}, deixando \text{id}. Casa \text{id}: pilha vazia, entrada vazia, aceita. São nove passos — seis expansões e três casamentos.
Dê imediatamente a conferência aritmética, a ferramenta mais útil que a turma leva deste módulo para a tutoria: o número de casamentos tem de ser exatamente o número de terminais da entrada, e o de expansões, o número de nós internos da árvore de derivação. Aqui, três e seis. Traçado cujas contas não fecham tem erro, e a verificação o localiza de imediato.
Feche o bloco com a identidade, e trate-a como identidade e não como analogia. Escreva a sequência de expansões usadas e, ao lado, a derivação
E \Rightarrow E + T \Rightarrow T + T \Rightarrow F + T \Rightarrow \text{id} + T \Rightarrow \text{id} + F \Rightarrow \text{id} + \text{id}.
É a mesma sequência de produções, na mesma ordem, expandindo sempre a variável mais à esquerda. Diga em voz alta: o autômato de pilha, executando, é a derivação mais à esquerda sendo construída passo a passo. Quem entende esta frase entende o analisador descendente antes de vê-lo.
Bloco seguinte — onde estão as adivinhações
O traçado anterior parece determinístico e não é. Volte a ele e marque as escolhas, uma a uma, porque é dessa marcação que nasce o módulo 10.
No primeiro passo havia E no topo e duas produções disponíveis. E — este é o detalhe que a turma não vê — a transição de expansão é vazia, de modo que a máquina não olhou a entrada ao escolher. Ela adivinhou. Faça a mesma marcação nos passos seguintes, onde houve escolha entre E \to T e nova aplicação de E \to E + T, entre T \to T * F e T \to F, e entre F \to (\,E\,) e F \to \text{id}.
Agora separe as duas naturezas de adivinhação, porque é a separação que desenha o módulo seguinte. A escolha de F é fácil: bastaria olhar um símbolo à frente, já que um parêntese de abertura e um \text{id} distinguem os dois corpos completamente. A escolha de E é impossível com qualquer janela fixa, porque a informação que a resolveria — quantas somas existem no resto da entrada — é global.
Trate a recursão à esquerda como caso destacado, com o traçado na mão. Com E no topo, expandir E \to E + T recoloca E no topo sem consumir nada, e nada impede repetir indefinidamente. No modelo não determinístico isso não é problema, e a razão merece precisão: o modelo não executa os ramos, ele os quantifica, e o ramo infinito não é considerado. Uma implementação determinística não tem esse luxo — uma função que chama a si mesma antes de consumir símbolo algum não retorna nunca. Registre também a dívida que a transformação do módulo 10 vai cobrar: a recursão à esquerda estava ali dando associatividade à esquerda, a transformação preserva a linguagem e muda as árvores, e a associatividade terá de ser reconstruída no código.
Segunda questão de discussão em duplas. “No traçado de \text{id} + \text{id}, as quatro primeiras transições aplicadas não consumiram nenhum símbolo da entrada. Isso acontece porque: (a) o traçado foi mal conduzido; (b) transições de expansão são vazias por definição, e a estratégia decide qual produção aplicar antes de ver a evidência; (c) a gramática é ambígua; (d) a entrada é curta demais.”
A resposta é (b). Quem vota (a) supõe que existe uma ordem melhor de aplicar as transições, e vale corrigir na hora: com terminal no topo só cabe casar, com variável no topo só cabe expandir. Quem vota (c) confunde escolha com ambiguidade — meia frase basta, porque o ponto volta no módulo 11. Aproveite a alternativa correta para anunciar a assimetria que organiza os dois módulos seguintes: a estratégia descendente decide antes de ver a evidência, e a ascendente acumula evidência antes de decidir.
Bloco seguinte — determinismo, e o que ele custa
Defina o autômato de pilha determinístico com as duas cláusulas, e insista na segunda, que é a que passa despercebida: se há transição vazia definida para uma configuração, então nenhuma transição que lê símbolo pode existir ali. Sem essa cláusula a máquina escolheria entre agir por conta própria e ler a entrada, o que é não determinismo disfarçado. Avise que definir determinismo só pela primeira cláusula é erro comum e leva a classificar como determinísticos autômatos que não são.
Enuncie a não equivalência com os palíndromos como contraexemplo — a mesma máquina da primeira aula — e dê a intuição em uma frase: uma máquina sem escolhas tem de decidir cedo, símbolo a símbolo, o que só se sabe tarde, quando a leitura termina.
O que precisa caber é por que a construção de subconjuntos não sobe de andar, e este é o ponto de maior valor conceitual do bloco. No nível regular, simular todos os ramos ao mesmo tempo funcionava porque um ramo era caracterizado por um estado, e o conjunto dos subconjuntos de um conjunto finito é finito. Aqui um ramo é caracterizado por um estado e uma pilha; simular todos exigiria guardar um conjunto de pilhas, que são objetos de tamanho ilimitado e divergem entre ramos. Escreva a lição transferível no quadro: o não determinismo é eliminável quando o estado da computação é finito.
Feche com a consequência de engenharia, com número. O algoritmo geral que trata qualquer gramática livre de contexto reconhece uma cadeia de comprimento n em tempo proporcional a n^{3}, por programação dinâmica. Faça a conta na frente deles com um arquivo de dez mil símbolos e compare com o analisador léxico, que é linear: a desproporção fala sozinha. Daí a decisão que a prática tomou — a análise sintática real se restringe a subclasses determinísticas, o que significa aceitar que existem gramáticas legítimas que nenhum analisador prático vai tratar, e que a escolha da gramática passa a ser parte do projeto do compilador.
Terceira questão de discussão em duplas. “No módulo 5 convertemos todo autômato finito não determinístico em determinístico. Aqui isso não se pode fazer porque: (a) a construção de subconjuntos ainda não foi generalizada; (b) o número de estados explodiria exponencialmente; (c) um ramo de computação inclui uma pilha, e conjuntos de pilhas não cabem em estrutura finita; (d) autômatos de pilha não têm estados suficientes.”
A resposta é (c). A alternativa (a) é a que mais aparece no primeiro voto e vale expor: sugere lacuna da nossa técnica, quando é impossibilidade. A alternativa (b) é atraente porque descreve corretamente o que acontece no nível regular — quem a escolhe está transportando um resultado de andar sem verificar a hipótese, que é exatamente a competência central deste módulo.
Bloco de fechamento — os limites da classe e a volta ao gancho
Enuncie o lema do bombeamento neste nível e conduza pela comparação, que é o que carrega o significado: no nível regular a decomposição era em três partes com uma bombeada; aqui é em cinco, z = uvwxy, com duas bombeadas simultaneamente e na mesma quantidade, sob as condições |vwx| \le p e |vx| \ge 1.
Faça a aplicação resolvida, curta, que fecha o argumento aberto na primeira aula. Tome L_3 = \{a^{n}b^{n}c^{n} : n \ge 1\} e a cadeia z = a^{p}b^{p}c^{p}, de comprimento 3p. A condição |vwx| \le p faz todo o trabalho: como há p símbolos b entre o bloco dos a e o dos c, a janela não alcança os dois extremos, e portanto vx é composto de símbolos de no máximo dois dos três blocos. Bombeie com i = 2: a cadeia cresce em pelo menos um símbolo, o crescimento se distribui em no máximo dois blocos, o terceiro permanece com exatamente p símbolos, e as três contagens deixam de ser iguais. Contradição.
Amarre à frase que a turma já ouviu na abertura e que agora está demonstrada: uma pilha conta uma coisa de cada vez. E repita a advertência de sempre — o lema é condição necessária e não suficiente; falhar no teste prova que a linguagem está fora da classe, passar não prova nada.
Sobre fechamento, vá direto às duas perdas. União, concatenação e fecho continuam valendo. Interseção e complemento não valem, e o contraexemplo é resolvido em duas linhas no quadro: L_a = \{a^{n}b^{n}c^{m}\} e L_b = \{a^{m}b^{n}c^{n}\} são livres de contexto, cada uma exigindo uma única correspondência de contagem, e a interseção delas é exatamente a linguagem que você acabou de excluir da classe. Registre que a interseção com linguagem regular continua fechada, e dê a razão, porque é ela que paga a dívida da abertura: o produto de um autômato de pilha com um autômato finito continua tendo uma pilha, ao passo que o produto de dois autômatos de pilha precisaria de duas.
Aponte então a pergunta no canto do quadro e responda-a. Duas pilhas simulam a fita da máquina de Turing, uma guardando o conteúdo à esquerda da cabeça e outra o da direita, com o movimento da cabeça correspondendo a transferir um símbolo de uma para a outra. O passo da segunda pilha não é conveniência: é a passagem do domínio decidível para o indecidível de uma vez só. É por isso que a restrição a uma pilha é decisão de projeto, e não limitação herdada — ela compra as garantias de que um compilador precisa.
Termine com o lugar do compilador na hierarquia, dito de forma que a turma possa repetir sem consultar: a análise léxica vive no tipo 3, onde um único algoritmo resolve o problema inteiro; a análise sintática vive no tipo 2, e não no tipo 2 inteiro, mas nas subclasses determinísticas; e a análise semântica seria naturalmente do tipo 1 e não é feita com o formalismo do tipo 1, por custo e ilegibilidade. Feche dizendo que a arquitetura do compilador é, em boa medida, um retrato dessa hierarquia — e que o módulo seguinte converte tudo isto em código.
Aulas 3 a 6 — Tutoria do Projeto Integrador
Quatro aulas de tutoria — auditoria de pendências, tradução da gramática do grupo para o modelo de pilha, traçado manual anotado e preparação do módulo 10.
Este é o primeiro dos dois módulos sem tarefa de implementação, e o risco de gestão é único no semestre: os grupos leem a ausência de código como folga. Corte essa leitura na primeira frase da primeira sessão, dizendo o que as sessões são: o abate das dívidas acumuladas até aqui e a preparação do módulo mais denso do curso. O andaime já está bem menor do que era nos módulos iniciais — você fornece o objetivo e o critério, não o caminho —, mas neste módulo específico convém retomar o controle sobre a agenda, porque grupos sem entrega de código tendem a dispersar.
Chegue à primeira sessão com o levantamento por escrito das pendências de cada grupo, feito antes da aula a partir das entregas dos módulos anteriores. Não improvise esse levantamento na sala: o grupo que é perguntado “o que está faltando em vocês?” responde “nada”, e o grupo que recebe uma lista com três itens nomeados começa a trabalhar de imediato.
Tenha o seu próprio projeto aberto e projetado nas duas sessões. A Peneira já tem, a esta altura, o analisador léxico apoiado no autômato finito determinístico e a gramática livre de contexto da linguagem — lista de declarações, declarações de padrão, blocos de regra e expressões de condição. O que ela não tem é o programa que decide se uma sequência de símbolos obedece a essa gramática, e é exatamente essa ausência que este módulo prepara. Diga isso em voz alta: o professor está na mesma posição que os grupos, com a gramática pronta e o analisador por escrever.
Primeira sessão de tutoria — saldar dívidas e traduzir a gramática
Abra pela lista de pendências, grupo a grupo, e classifique cada item na frente deles em uma de três categorias: caso de erro sem tratamento, documentação atrasada, teste nunca escrito. Essas são as três dívidas que aparecem de fato. Peça que o grupo ordene a própria lista por custo de pagar depois — e corrija a ordem quando ela vier errada, porque a tendência é começar pela documentação, que é a mais confortável e a menos urgente. O que se paga caro no módulo 10 é o caso de erro sem tratamento no analisador léxico, porque o analisador sintático vai consumir a saída dele.
Grupos sem pendências existem e são poucos. Para eles, antecipe o trabalho da segunda sessão: comece já a tradução da gramática, e depois use o tempo excedente para conferir se a gramática do módulo 8 continua não ambígua depois das últimas mudanças — costuma não continuar.
A segunda metade da sessão é a tradução da gramática do grupo para o modelo de pilha. É mecânica e os grupos a fazem rápido; o seu trabalho é circular verificando duas coisas específicas. A primeira é se escreveram as transições de expansão para todas as produções, incluindo as que quase ninguém lembra — as que derivam a cadeia vazia nas partes opcionais da gramática. A segunda é a ordem de empilhamento nos corpos com mais de um símbolo. Peça para ver um corpo de três símbolos de cada grupo e confira o topo. É onde o erro mora, e ele não se manifesta enquanto ninguém traçar.
Segunda sessão de tutoria — o traçado anotado e a ponte para o módulo 10
Abra fixando o formato do traçado, porque é a única exigência formal da entrega e é onde os documentos divergem: tabela com uma linha por passo, colunas de pilha, entrada restante e transição aplicada, pilha escrita do topo para a base do começo ao fim. Projete o traçado da Peneira que você fez sobre um programa de duas linhas — uma declaração de padrão e uma regra com emissão — e mostre onde as expansões se acumulam antes de o primeiro terminal ser casado.
Escolha do programa a traçar: exija que seja curto e que contenha uma construção aninhada. O grupo que traça uma sequência de declarações simples produz um traçado sem profundidade, em que a pilha nunca passa de dois símbolos, e não aprende nada — o modelo inteiro existe por causa do aninhamento. Recuse esses e peça outro programa; é uma correção imediata que salva a entrega.
Cobre a anotação das escolhas enquanto eles traçam, e não depois. Circule pedindo, em uma linha qualquer da tabela: “aqui você tinha quantas produções disponíveis para essa variável?”. Se a resposta for mais de uma e não houver anotação, o traçado é desonesto — o autor olhou a entrada para decidir. Mostre no traçado da Peneira como você anotou as suas próprias escolhas e qual informação teria dispensado cada uma, distinguindo as que um símbolo de antecipação resolve das que nenhuma janela finita resolve. Essa distinção é a espinha da discussão sobre determinismo que a entrega exige, e grupos que a fazem aqui escrevem o parágrafo sozinhos.
Feche com a conferência aritmética, aplicada por eles e não por você: contem os terminais do programa traçado e comparem com o número de casamentos; contem os nós internos da árvore e comparem com o número de expansões. Grupos cujas contas não fecham localizam o erro de imediato, e ver isso funcionar uma vez faz com que usem a conferência sem que você peça.
Reserve o final da sessão para a ponte com o módulo seguinte. Peça que cada grupo aponte, na própria gramática, uma produção recursiva à esquerda e diga o que aconteceria com ela no traçado — a variável volta ao topo sem consumir entrada, indefinidamente. Não ensine a transformação; ela é do módulo 10. O que se quer é que o grupo chegue lá sabendo que existe um problema concreto na gramática dele, com nome e localização. Registre no seu diário, por grupo, quais produções foram apontadas: é a lista de trabalho da primeira tutoria do módulo 10.
Cobre o revezamento de papéis também aqui, ainda que o trabalho seja de papel e quadro. Quem escreve a tabela é o piloto, quem confere passo a passo e questiona as escolhas é o navegador, e a troca acontece a cada bloco de linhas. Sem código, a tentação de um integrante fazer tudo enquanto os outros observam é maior do que nos módulos de implementação — e é justamente neste módulo que a observação direta da distribuição de trabalho é mais fácil de fazer.
Entregáveis e Avaliação
A entrega deste módulo é teórica, e isso não a torna menor. Cada grupo entrega um documento de fundamentação que conecta a gramática escrita no módulo anterior ao modelo de máquina estudado aqui: a tradução da gramática para o autômato de pilha seguindo a construção vista em aula, o traçado manual do reconhecimento de um programa curto da própria linguagem com o conteúdo da pilha a cada passo, a discussão sobre a restrição da análise prática às subclasses determinísticas, e o registro das pendências saldadas.
Confira cada documento contra cinco itens, na mesma ordem para todos os grupos: a construção foi aplicada à gramática do grupo, e não copiada do exemplo de expressões da aula; o traçado mantém a mesma orientação de pilha do começo ao fim; as contas fecham, com casamentos igual ao número de terminais e expansões igual ao número de nós internos da árvore; as escolhas não determinísticas estão anotadas, com a informação que as teria dispensado — um traçado sem nenhuma anotação de escolha é, quase sempre, um traçado em que o autor olhou a entrada para decidir, e deve ser devolvido; e a discussão sobre determinismo é específica da linguagem do grupo, e não um parágrafo genérico sobre teoria.
Registre no componente contínuo a pontualidade da entrega, a contribuição nas discussões em duplas e o engajamento nas sessões de tutoria. Diga à turma, no início do módulo, que a ausência de implementação não reduz o peso da entrega: o documento deste módulo é o rascunho intelectual do analisador do módulo seguinte, e grupos que o entregam de qualquer jeito pagam a diferença na semana mais densa do semestre.
Orientações Sobre o Aplicativo
Use o aplicativo da disciplina para as três votações, com histograma anônimo na projeção. A que mais informa é a terceira, sobre a construção de subconjuntos: ela mede diretamente a competência central do módulo, que é não transportar resultado de um nível para outro sem verificar a hipótese. Se o primeiro voto concentrar-se na alternativa que fala em explosão exponencial, não corrija de imediato — é o erro produtivo, e a discussão em duplas costuma resolvê-lo sozinha. Se concentrar-se na alternativa que sugere lacuna de técnica, refaça a definição de ramo de computação antes de mandar discutir, porque a discussão em duplas só corrige quando há quem tenha entendido.
Acompanhe também o engajamento no estudo do material, comparando com o módulo anterior em vez de olhar o número isolado. Este é um módulo sem código, e a queda de engajamento aqui é o sinal antecipado do grupo que vai chegar despreparado ao módulo 10 — informação acionável ainda dentro da semana: leve o nome do grupo para a segunda sessão de tutoria.
Guarde os dois histogramas de cada questão. A distância entre o primeiro e o segundo voto na questão sobre as transições vazias do traçado é o que melhor orienta o peso a dar, na abertura do módulo 10, à revisão da correspondência entre expansão e derivação mais à esquerda.
Pontos de Atenção Específicos
O módulo teórico vira leitura em voz alta se você deixar. Sem código, a tentação é enunciar definições em sequência. O antídoto é que todo bloco tenha algo escrito no quadro com a participação da sala. Se ao fim da segunda aula você não tiver preenchido duas tabelas de traçado com a turma, o módulo não cumpriu a função e o módulo 10 vai custar caro.
Não comprima a construção de um estado. É o bloco de maior retorno do semestre e o primeiro candidato a ser espremido quando o roteiro atrasa. Se precisar cortar, corte a direção inversa — do autômato para a gramática —, tecnicamente mais trabalhosa, praticamente não usada e cuja lição essencial cabe em uma frase: estado e pilha são recursos intercambiáveis.
A armadilha do traçado desonesto apanha quase todo mundo. Ao traçar à mão, é irresistível olhar a entrada para decidir qual produção expandir, porque você, humano, vê a cadeia inteira. O traçado sai certo e esconde exatamente o que deveria mostrar. Institua a regra na aula e cobre na entrega: em toda expansão com mais de uma produção possível, anote que houve escolha e que informação a teria dispensado.
A inversão da ordem de empilhamento é o erro que não se anuncia. Invisível enquanto os corpos tiverem um símbolo só, aparece no primeiro corpo com três. Circule durante o traçado da segunda aula olhando especificamente para isso — não pergunte se entenderam, olhe o caderno.
Duas digressões previsíveis, e o corte de cada uma. Alguém vai pedir a demonstração rigorosa da não equivalência: responda que ela combina propriedades de fechamento com um argumento sobre configurações alcançáveis, fora do escopo, dê a intuição, ofereça a referência bibliográfica e siga — ceder aqui consome o bloco do bombeamento. E assim que a turma ouve “existe uma família de métodos”, alguém pergunta qual ferramenta se usa na prática: responda em duas frases, registre que o projeto do semestre é feito à mão por decisão de escopo, e reconduza, porque a comparação entre famílias é o módulo 11 e sem o vocabulário de conflitos ela vira opinião.
Este módulo prepara o mais denso do semestre. Diga isso à turma explicitamente, e não como ameaça: o traçado manual feito aqui é o que separa reconhecer a estrutura do analisador de tentar decorá-la. É o argumento que sustenta a exigência da entrega teórica.