flowchart LR
N["nivelamento<br/>conjuntos, cadeias<br/>e recursão"] --> B
subgraph B["este módulo"]
direction TB
B1["alfabeto, cadeia e<br/>linguagem como conjunto"] --> B2["hierarquia de Chomsky<br/>lida pela memória"]
B2 --> B3["anatomia do tradutor:<br/>análise e síntese"]
B3 --> B4["primeira especificação<br/>formal da linguagem"]
end
B --> P["módulo seguinte:<br/>expressões regulares como<br/>descrição finita do infinito"]
P --> Q["arco de autômatos:<br/>construção, determinização<br/>e minimização"]
B4 -. "insumo direto" .-> P
1 Linguagens formais e a arquitetura de um compilador — Plano de Aula
Documento exclusivo do professor. Guia de condução deste módulo: os blocos na ordem de execução, duas questões conceituais prontas com a leitura de cada erro, o comando que sobe o marco em aula, o plano das sessões de tutoria e os tropeços previsíveis da turma. Não é material do estudante e não se distribui.
1.1 Visão Geral do Módulo
Este é o módulo em que a turma menos percebe estar aprendendo alguma coisa, e é o que decide o preço de todos os outros. Não há código do estudante para escrever, o vocabulário cabe em meia página, e as definições parecem óbvias na primeira leitura. Um estudante sai daqui com a impressão de que a semana foi introdução. Três módulos adiante, quando a construção do autômato falhar por causa de uma potência zero inicializada errado, a impressão terá custado uma tarde de depuração no lugar errado do código.
A decisão que organiza o roteiro é enunciar cada conceito com a consequência colada nele. Nunca diga que a potência zero vale o conjunto que contém a cadeia vazia sem mostrar, na mesma respiração, o que um acumulador inicializado com o conjunto vazio devolve. Nunca apresente a hierarquia sem perguntar de que memória a máquina precisaria. A turma que ouve definição sem consequência guarda a definição como formalidade de abertura e a esquece antes do fim da semana; a que ouve as duas juntas guarda a consequência e reconstrói a definição a partir dela, que é a ordem certa de esquecer as coisas.
O módulo ocupa as quatro aulas teóricas e as duas sessões de tutoria que a mecânica declarada nesta oferta reserva à semana. Do nivelamento o estudante traz conjunto, sequência e recursão; daqui ele leva o vocabulário formal inteiro, o critério que separa os degraus da hierarquia, o mapa das fases de um tradutor e — o que mais importa para a semana seguinte — a especificação escrita da linguagem que o próprio grupo vai tratar até o fim do percurso. Sem essa especificação, o módulo das expressões regulares chega sem objeto sobre o qual aplicar-se.
1.2 Objetivos, Competências e Habilidades
Objetivos de Aprendizagem. Estabelecer o vocabulário formal do percurso e o mapa do sistema que será construído, de modo que cada módulo seguinte possa ser localizado dentro de um todo. Ao final, o estudante deve descrever, sem consulta, o caminho completo que um trecho de texto percorre da primeira letra lida até o resultado executável, e situar cada fase quanto ao que consome e ao que produz.
Competências a desenvolver. Formalizar em notação de gramática uma linguagem antes descrita de modo intuitivo. Situar uma classe de linguagem na hierarquia que relaciona gramáticas e máquinas. Ler a arquitetura de um sistema de tradução como sequência de artefatos, e não de rótulos.
Habilidades a adquirir. Operar com alfabeto, cadeia e linguagem como conjunto, e com união, concatenação e fecho. Distinguir a metade que analisa da metade que sintetiza, e nomear o artefato de fronteira entre elas. Escrever, em notação formal, um exemplo válido da linguagem que o próprio grupo vai tratar.
Cada lista se verifica por um instrumento diferente, e trocar um pelo outro rende falso positivo com uma facilidade incômoda. Operar com as quatro operações e situar uma linguagem no degrau certo se medem por resposta, na hora, e é por isso que as duas questões conceituais do roteiro vêm escritas por extenso: item improvisado em sala rende distrator cuja única propriedade é estar errado, a turma vota, todo mundo acerta e você fica sabendo exatamente nada. Descrever o caminho do texto ao resultado não cabe em voto — cobra-se pedindo o artefato de fronteira entre duas fases nomeadas, e quem responde “aí ele compila” ainda não tem o mapa. Já a especificação escrita produz artefato, e se cobra na tutoria contra o documento do grupo, com a alternativa descartada ao lado de cada escolha.
1.3 Estrutura das Aulas
1.3.1 Aula Teórica — Do vocabulário formal ao mapa do sistema
Os blocos abaixo estão na ordem de execução e se distribuem pelas quatro aulas teóricas que a mecânica desta oferta reserva à semana. A dependência entre eles é estrita nos cinco primeiros — as operações precisam do alfabeto fechado, a descrição finita precisa das operações, a hierarquia precisa da descrição finita — e afrouxa nos últimos, de modo que, precisando comprimir, comprima da anatomia para trás. Anote em que bloco parou: retomar no meio exige recolocar o problema, e não apenas o resultado.
Bloco de abertura — o leitor mais literal que existe. Comece sem vocabulário nenhum. Escreva no quadro x = = 3 e pergunte à turma o que está errado ali. Todo mundo responde em meio segundo, e é essa velocidade que interessa: diga em voz alta que eles corrigiram de cabeça, seguiram adiante e provavelmente nem registraram que houve engano. O tradutor não tem essa boa vontade — percorre a mesma linha procurando uma sequência que case com alguma regra escrita, não acha nenhuma, e para. Nada mudou no arquivo. Mudou o leitor.
Ponha então o caso que a turma acha que quer resolver, e que ela vai defender com convicção. Escreva 3 x, sem o asterisco, e pergunte por que o compilador não adivinha. Alguém dirá que é óbvio o que a pessoa queria. Responda com o segundo palpite, e não com autoridade: um tradutor generoso poderia apostar em 3 * x, e outro poderia apostar que a pessoa quis escrever x3, um nome de variável que por acaso existe no programa e guarda o total de itens processados. A segunda aposta compila, roda e devolve um número errado, em silêncio, e tudo o que vem depois se apoia nele. Deixe a frase escrita no quadro sem apagá-la até o fim da semana, porque ela é a que o bloco de fechamento retoma: o tradutor sabe que aquele texto não pertence à linguagem, e nunca sabe o que você queria escrever.
Feche o bloco com a pergunta que abre o módulo inteiro. Toda essa recusa pressupõe um conjunto de textos admitidos contra o qual o arquivo é comparado. Esse conjunto quase sempre é infinito, nenhuma estrutura de dados guarda um conjunto infinito, e mesmo assim o programa responde milhares de vezes por segundo sem jamais ter visto a lista inteira. Escreva a pergunta e não a responda: como?
Bloco dos três degraus — o primeiro deles é uma decisão. Fixe símbolo, cadeia e alfabeto, e trate a definição de símbolo pelo lado que incomoda: nada num objeto o torna indivisível por natureza, e o que fixa o degrau é a escolha de quem descreve. Uma letra é símbolo quando o alfabeto é o dos caracteres; uma palavra classificada inteira é símbolo quando o alfabeto é o das unidades já reconhecidas. Diga que essa troca de altura acontece dentro do mesmo sistema, entre uma fase e a seguinte, e que ninguém avisa a troca — é a origem de metade da confusão deste ponto do percurso.
Enuncie a definição formal de alfabeto e cadeia e cobre as duas exigências uma por uma. Finito paga uma conta concreta: com uma lista fechada se monta uma tabela de uma linha por símbolo, consultável em tempo previsível, e alfabeto infinito nunca termina de ser montado. Não vazio parece arbitrário, então desfaça a exigência ao vivo: sobre um alfabeto sem símbolo algum existe exatamente uma cadeia, a de comprimento zero, logo o universo tem um elemento e há duas linguagens possíveis. Um alfabeto sem símbolos admite uma entrada, e essa entrada é a que ninguém consegue enxergar. Registre no quadro que grande e infinito são coisas distintas: o Unicode passa de cem mil símbolos, inclui hieróglifos egípcios e emojis, e continua sendo lista fechada.
Resolva \Sigma^3 sobre \Sigma = \{a, b\} escrevendo as oito cadeias uma por uma, sem pular nenhuma: aaa, aab, aba, abb, baa, bab, bba, bbb. São 2^3, e a conta é a de qualquer escolha independente posição a posição. Estenda para comprimento 10, que dá 1024, e para comprimento 20, que dá 2^{20} = 1.048.576. Feche com a comparação que a turma leva para fora da aula: um PIN de quatro dígitos tem 10.000 combinações, e vinte escolhas entre dois símbolos rendem cem vezes mais, com um alfabeto cinco vezes menor. O comprimento rende mais que a variedade, e a aritmética disso está inteira em |\Sigma|^n.
Trate por último o objeto que dá mais trabalho, que é perfeitamente definido e completamente invisível. Escreva no quadro o conjunto \{\varepsilon, a, aa\} e depois escreva como ele sai impresso sem tratamento: { , a, aa }. Pergunte quantos elementos a turma conta. Quem lê conta dois e uma vírgula sobrando, conclui que o programa tem defeito de formatação, e não desconfia de que o defeito está na leitura. O elemento foi impresso, com o número exato de caracteres que tem. Diga por que isso não é cosmético: enquanto não existe bateria de testes, a verificação disponível é comparar saídas a olho e contar elementos, e um formatador que apaga um elemento faz errar justamente a contagem que se usa para julgar se a operação anterior está correta.
Questão conceitual — a potência zero, e o que ela faz quando vira código. Aplique antes do bloco das operações, no formato completo: voto individual, discussão em duplas, segundo voto, e só então o seu fechamento.
Sobre \Sigma = \{a, b\} e a linguagem L = \{a, b\}, quanto vale L^0?
\emptyset, porque zero cópias de coisa nenhuma dá coisa nenhuma. — Vence o primeiro voto com folga, e o argumento é razoável, o que a torna a alternativa mais útil do item. Confunde a linguagem sem cadeia alguma com a linguagem cuja única cadeia é a vazia: uma tem cardinalidade zero, a outra tem cardinalidade um.
\{\varepsilon\}. — Correta. É o elemento neutro da concatenação, pelo mesmo motivo pelo qual o produto vazio de números vale um: concatenar essa linguagem com qualquer outra devolve a outra intacta.
L, porque elevar a zero não altera o conjunto. — Aplica ao conjunto a regra que vale para o expoente um. Quem marca isto leu a potência como operação sobre o rótulo, e não sobre o conteúdo.
\{\varepsilon, a, b\}. — Junta o nível zero com o nível um do fecho. É o erro de quem já viu a definição do fecho de Kleene e a colapsou com a da potência.
Feche pedindo a definição de potência e escrevendo-a no quadro, e depois desça ao código, porque é ali que o item paga. Um acumulador de fecho inicializado com o conjunto vazio não tem com o que colar: ele aniquila tudo o que multiplica, e a função devolve conjunto vazio para toda entrada, inclusive para uma linguagem de duas cadeias que se confere a olho. Siga o sintoma até o fim em voz alta, porque ele ensina mais que o conserto: quem depura vai olhar a função do fecho, que está somando corretamente uma sequência de conjuntos vazios. A linha que falha não costuma ser a linha errada, e nesse caso o defeito mora três funções acima, numa inicialização de uma palavra. Se (C) e (D) juntas passarem de um terço, refaça a definição antes de seguir.
Bloco das operações — a que escolhe, a que multiplica, a que não termina. Enuncie linguagem como subconjunto de \Sigma^* e detenha-se no que a definição não exige: nem regra, nem padrão, nem descrição finita, nem que alguém saiba decidir a pertinência. Diga por que a generosidade é rigor, e não frouxidão — quanto menos a definição exige, mais objetos ela alcança, e mais valem os teoremas que a usam. Diga também que a conta chega depois, porque alcançar tudo significa alcançar coisas com que nenhuma máquina lida. Esse é o fio que o bloco seguinte puxa.
Trate a união pela confusão que ela produz, e não pela facilidade que aparenta. Escreva a definição com o conectivo ou em destaque e diga o que acontece com quem lê depressa: escrever “as cadeias que estão nas duas” descreve a interseção, que é outra operação e produz outro conjunto. União é escolha, e é generosa. Passe à concatenação sobre L_1 = \{a, ab\} e L_2 = \{b\}, resolvendo no quadro: o resultado é \{ab, abb\}. Chame a atenção para o fato de que a definição fala de pares e o resultado é conjunto de cadeias — as duas metades se fundem numa só e a fronteira entre elas some. Quem devolve o par implementou outra operação com o nome certo.
Ponha os dois números lado a lado, porque a diferença de escala é o que fica. Duas linguagens de mil cadeias cada se unem em duas mil linhas; concatenadas, pedem um milhão. E acrescente o detalhe que contraria a aritmética à primeira vista: concatenar uma linguagem de 40 cadeias com outra de 25 produz no máximo mil cadeias, e quase sempre menos, porque ab com c e a com bc produzem a mesma cadeia abc, e num conjunto ela conta uma vez só. Mil é teto, e é teto porque o resultado é conjunto.
Feche pelo fecho de Kleene, que é a operação que produz infinito a partir de finito: se a linguagem contém uma cadeia não vazia, o fecho dela é infinito, sem exceção. Uma linguagem de duas cadeias de um símbolo cada já gera um conjunto que não termina. Aqui a turma percebe sozinha o problema que o bloco seguinte trata, e vale colher a percepção antes de anunciá-la — pergunte como se guardaria esse resultado em memória e espere alguém dizer que não se guarda.
Bloco da descrição finita — duas famílias, e a prova de que juntas elas não alcançam quase nada. Abra pela pergunta da abertura, agora com o vocabulário na mão: se a linguagem é infinita e a memória não é, o que se guarda? Guarda-se uma descrição em vez das cadeias. Mostre a ideia funcionando antes de formalizar: a linguagem dos identificadores válidos é infinita, a lista dela não termina de ser escrita, e a descrição cabe em três linhas e decide qualquer cadeia que alguém apresente, inclusive uma que ninguém jamais escreveu.
Separe as duas famílias pelo verbo. Uma gera: dá regras que produzem cadeias, e a linguagem é tudo o que se consegue produzir. A outra reconhece: descreve uma máquina que lê e responde sim ou não, e a linguagem é tudo o que recebe sim. Diga de onde vem a repartição de trabalho — regras que geram são confortáveis para pessoas, porque descrevem a forma da coisa como alguém a explicaria em voz alta; máquinas que reconhecem são o que um processador executa. Ninguém desenha estados à mão por prazer, e nenhum processador executa regra de produção diretamente. A ponte entre as duas é mecânica, existe algoritmo dentro de cada degrau, e o programa que faz a travessia é o compilador. Diga essa última frase devagar: ela é quase a definição do ofício, e a turma costuma ouvi-la aqui pela primeira vez.
Enuncie a gramática como quádrupla e derive aaabbb no quadro com as duas regras S \to aSb e S \to \varepsilon, escrevendo cada linha: de S vem aSb; depois aaSbb; depois aaaSbbb; a segunda regra apaga o S e sobra a cadeia. Quatro aplicações, seis símbolos, nenhum limite superior para quantas vezes o passo se repete. Aponte o lugar exato de onde o infinito sai: a primeira regra tem S dos dois lados da seta, e uma produção em que o não terminal reaparece à direita pode ser aplicada de novo sobre o próprio resultado. Retire a recursão e a gramática passa a gerar conjunto finito, sempre.
Trate ambiguidade na sequência, e trate-a com números, porque em prosa ela soa como preciosismo de notação. A definição não exige que cada cadeia tenha uma única derivação. Escreva 2 + 3 * 4 e derive de dois modos numa gramática mal escrita: um põe a multiplicação mais fundo, o outro põe a soma. Os resultados são 14 e 20. Duas árvores para a mesma cadeia, e nada na definição proibindo. Diga que desfazer ambiguidade é trabalho do arco da análise sintática e que por ora basta reconhecer o sintoma.
Feche a notação com data e com a advertência que ela exige. Em 1959, John Backus propôs uma forma de descrever a sintaxe da linguagem que viria a ser o ALGOL 60, e Peter Naur a adaptou ao editar o relatório oficial. Ela continua sendo o modo padrão de escrever gramática em manual, norma e artigo. O que ela acrescenta é abreviação: a barra vertical junta numa linha duas produções com o mesmo lado esquerdo, o colchete marca o opcional, o par de chaves marca a repetição. Escrever A \to [\,b\,] é escrever A \to b e A \to \varepsilon. O documento encurta; a linguagem gerada permanece a mesma. Guarde a distinção na forma que a turma consegue repetir: o que decide o alcance de uma gramática é a forma das produções permitidas, e açúcar de escrita não muda forma de produção nenhuma.
Reserve o fim do bloco para o argumento de contagem, que é o momento mais alto da semana e cabe em três movimentos. Conte as descrições: uma descrição finita é um texto finito sobre um alfabeto finito, seja gramática, máquina ou programa; enfileire as de comprimento 1, depois as de comprimento 2, e assim por diante. Cada bloco é finito, os blocos vêm em ordem, e toda descrição tem posição marcada. Conte as linguagens: uma linguagem é um subconjunto do universo de cadeias, e o argumento diagonal de Cantor mostra que os subconjuntos de um conjunto infinito enumerável não se enfileiram — dada qualquer fila proposta, constrói-se um subconjunto que difere do primeiro item no primeiro elemento, do segundo no segundo, e fica de fora da fila inteira. Compare: de um lado uma coleção que se enfileira, do outro uma que não. Para quase toda linguagem não existe gramática, não existe máquina e não existe programa. Insista na palavra existe, porque é a parte que passa batida: a descrição não está por descobrir esperando alguém mais esperto, e a diferença entre resultado de impossibilidade e problema em aberto é de espécie. Daí sai o recorte que organiza a área inteira, e vale dito com todas as letras — não se estudam as linguagens, estudam-se as que têm descrição finita.
Bloco da hierarquia — a pergunta certa é de que memória a máquina precisa. Abra pelo episódio e pela inversão que ele carrega. Em 1956, Noam Chomsky publicou nas IRE Transactions on Information Theory o artigo Three Models for the Description of Language. Ele era linguista, o alvo declarado era a linguagem humana, e computadores não entravam na conversa. Diga o caminho que ele percorreu, porque o senso comum o inverte: Chomsky partiu das regras e foi restringindo a forma delas — primeiro sem restrição, depois exigindo que o lado direito nunca encurte, depois que o lado esquerdo tenha um único não terminal, por fim apertando a forma do lado direito até quase nada caber. A correspondência com máquinas veio depois, de outra direção. A computação herdou o resultado.
Antes de descer aos degraus, derrube os três palpites comuns de uma vez: o que separa um degrau do seguinte não é o tamanho do alfabeto, nem o número de regras da gramática, nem a velocidade de coisa alguma. Uma gramática de degrau baixo pode ter centenas de regras. O critério é quanta memória a máquina precisa ter, e de que tipo é o acesso a ela.
Este é o único ponto do módulo em que se interrompe a aula para copiar uma frase. Mande a turma escrever: quem só sabe em que estado está não sabe quantas vezes já entrou nele. Converta na hora, em três movimentos no quadro. Fixe uma máquina com k estados, escolhidos antes de ela rodar. Alimente-a com uma abertura de parêntese, depois duas, depois três; as profundidades são infinitas e os estados são k, logo apresentadas k+1 profundidades, duas terminam no mesmo estado. Chame-as de i e j: dali em diante a máquina não as distingue, e o que vier a seguir será tratado de modo idêntico. Apresente i fechamentos. Para quem abriu i vezes a resposta certa é aceitar; para quem abriu j vezes, recusar. A máquina responde a mesma coisa às duas. O caso extremo vale dito em voz alta, porque a turma ri e depois lembra: existe entrada com mil aberturas e um único fechamento que essa máquina aceita, chegando ao fim perfeitamente confiante.
Questão conceitual — acrescentar estados não resolve. Aplique logo depois do argumento acima, no mesmo formato de voto, discussão e revoto. Ela existe porque a saída que a turma inventa sozinha é sempre a mesma.
Uma máquina finita de 101 estados é apresentada à linguagem dos parênteses balanceados. Que afirmação está correta?
Ela reconhece a linguagem, porque nenhum programa real aninha mais de cem níveis. — Troca a pergunta formal pela estatística de uso. Quem marca isto respondeu sobre o que costuma aparecer, e a definição não fala de frequência.
Ela reconhece outra linguagem — a dos balanceados até profundidade 100 —, que é regular. — Correta. Restringir a profundidade por escrito produz uma linguagem finita nessa dimensão, e o argumento das casas de pombo se refaz para qualquer k finito.
Ela não reconhece porque tem poucos estados; com estados suficientes reconheceria. — O obstáculo é a finitude do conjunto de estados, e não o tamanho dele. É a alternativa que mais aparece e a que mais rende no fechamento.
Ela não reconhece porque o alfabeto de dois símbolos é pequeno demais para distinguir profundidades. — Aplica o critério errado, e é o mesmo critério que você acabou de derrubar no quadro. Peso aqui significa que o bloco anterior não pegou.
Não apresse o fechamento. Peça a alguém que marcou (C) que diga qual número de estados bastaria, e deixe a sala perceber que a pergunta não tem resposta. Generalize em regra de trabalho para o resto do semestre: diante de qualquer linguagem nova, pergunte o que a máquina precisaria lembrar para decidir, e não quantos estados ela teria.
Bloco da pilha — a peça pobre que tem a forma do problema. Apresente o degrau seguinte pela restrição, e não pela capacidade. É uma pilha: lê-se e escreve-se apenas no topo, não se consulta o meio, não se conta sem desempilhar, não se troca a ordem. Uma estrutura com menos operações do que qualquer curso introdutório costuma apresentar, e é a pobreza que a torna útil — em troca do que recusa, ela lembra uma quantidade sem teto, na ordem inversa em que os itens chegaram, que é exatamente a ordem em que fechamentos casam com aberturas.
Dê a data, porque ela mostra que a peça entrou na engenharia antes de virar exemplo de aula. Em agosto de 1960, no Mathematisch Centrum de Amsterdã, Edsger W. Dijkstra e Jaap A. Zonneveld concluíram o primeiro compilador de ALGOL 60; a implementação de procedimentos recursivos por pilha de registros de ativação vem dessa linhagem, e Dijkstra a expôs em Recursive Programming, publicado na Numerische Mathematik em 1960. O problema na mesa era concreto: com o mesmo procedimento ativo várias vezes ao mesmo tempo, ninguém sabia dizer qual endereço de retorno era o certo. Guardar cada retorno numa pilha resolveu.
Anuncie as três alturas do mesmo objeto e diga que reconhecê-las como a mesma coisa é metade do ganho do percurso: aqui a pilha é a memória do autômato do segundo degrau; adiante é a cadeia de chamadas de um analisador escrito por procedimentos recursivos; no fim é o registro de ativação na memória da máquina que executa o traduzido. Trate os dois degraus de cima em poucas frases, porque nenhum aparece na construção de um compilador comum, e reserve o cuidado para a distinção que confunde: a máquina de Turing é o poder do compilador, e não o da linguagem compilada. O programa que traduz é um programa comum, com memória e laços; a gramática que ele reconhece fica dois ou três degraus abaixo, e fica ali por escolha.
Bloco da anatomia — cada fase entrega um artefato, e a seguinte só sabe ler aquilo. Funde o bloco com o episódio de 1952, e faça a lista sair dele. Num encontro da ACM, Grace Hopper apresentou um trabalho de título modesto, The Education of a Computer. O programa descrito chamava-se A-0, rodava num UNIVAC I, lia uma lista de chamadas escrita à mão, procurava cada rotina numa fita magnética e montava o programa final juntando os pedaços na ordem pedida. Hopper batizou aquilo de compilador no sentido de quem compila uma antologia. Desmonte a cena na sequência, sem deixar a turma sair com a versão heroica: o A-0 colava trechos prontos e não analisava coisa alguma, e nenhum compilador de hoje trabalha sem antes desmontar o texto que recebeu. O que sobreviveu foi a ideia por baixo do nome — o texto que uma pessoa escreve pode ser tratado como dado por outro programa.
Puxe dali a lista do que precisa acontecer entre o texto e o resultado, e deixe a turma ditar a ordem, porque ela se impõe sozinha. Onde termina cada unidade com significado próprio dentro da fila de caracteres? Como essas unidades se encaixam? O que se encaixou faz sentido segundo as regras da linguagem? Perguntar se uma soma é válida exige saber que ali há uma soma. Percorra então as fases sobre uma linguagem pequena e inventada, que o material chama de Régua, dizendo o que cada uma consome e o que entrega: de medida > 70 a primeira fase produz quatro itens classificados, com a posição de cada um preservada; a segunda produz uma árvore em que a comparação vira nó com dois filhos; a terceira devolve a mesma árvore verificada mais a tabela do que cada nome significa; a quarta produz o objeto executável; a quinta o executa. Nomeie o artefato de fronteira, porque a pergunta costuma ficar vaga até tarde: é a árvore verificada com a tabela de nomes, a análise entrega isso, a síntese consome isso, e nada atravessa em outro formato.
Ancore a arquitetura na exigência que a produziu. Em 1957, a equipe de John Backus, na IBM, entregou o compilador de FORTRAN sob a suspeita então generalizada de que código produzido por máquina seria lento demais para ser levado a sério. Explicite a inversão na condução, porque ela é o ponto do bloco: a separação em passagens sucessivas respondeu a uma exigência de desempenho, e a elegância de projeto veio depois, como leitura retrospectiva. Backus publicou o relato em 1978, no The History of FORTRAN I, II, and III, pela ACM SIGPLAN. Some a herança de método, que vale mais que a de forma: julgamento de otimização se faz com número, e uma implementação que se anuncia rápida sem apresentar a medida está pedindo crédito.
Trate as formas intermediárias pela pergunta que cada uma responde e pelo que se perde ao pular. Tome a + b * c e a pergunta “essa multiplicação já foi calculada acima?”. Sobre o texto, responder exige achar todas as ocorrências de b * c, descontar as que estão em comentário e conferir se b ou c mudaram entre uma e outra. Decomposto em t1 = b * c e t2 = a + t1, a mesma pergunta vira busca nas linhas anteriores por atribuição com o mesmo lado direito. O que separa as duas versões é a quantidade de casos que cada uma obriga a tratar. Diga também o que declarar uma forma exige, porque os grupos esquecem o terceiro item: o formato e o que ele garante, as duas conversões testadas separadamente, e a decisão sobre o que não entra ali — a sequência de unidades é útil porque jogou fora espaço e comentário, e a árvore é útil porque jogou fora os parênteses.
Desfaça em seguida a pergunta mal formulada, que alguém vai fazer de qualquer jeito: linguagem não é compilada nem interpretada, porque compilar e interpretar são propriedades de implementações, e a metade que analisa é idêntica nas três estratégias. Na compilação a tradução acontece antes da execução, uma vez, e quem publica arca com o tempo; na interpretação a estrutura é percorrida a cada execução, e as decisões que a compilação tomaria uma vez são retomadas toda vez; a terceira parte a diferença ao meio, traduzindo para um formato próprio executado por um programa que se comporta como máquina. Acrescente a consequência que decide projetos e raramente entra na comparação: sob interpretação o programa continua disponível como texto na máquina de quem o executa, o que permite corrigir um sistema em produção abrindo um arquivo e impede distribuir o programa sem distribuir tudo o que ele diz.
Feche o bloco anunciando a conta que este percurso cobra até o fim. Nenhuma máquina real oferece exatamente as operações que a linguagem oferece: uma operação ausente do repertório não some do programa, ela vira uma sequência de operações que existem, mais longa e mais lenta. Diga a frase em voz alta e sem número — o que a máquina não faz, o tradutor faz por ela, e cobra em instruções — e diga também que a última fase é quem paga, e que a conta volta com valor medido no fim do percurso. Não abra em aula a discussão de como se responde a ela: as respostas possíveis são conteúdo do módulo de geração de código, e antecipá-las aqui gasta o efeito da promessa sem que a turma tenha como avaliar nenhuma delas.
Bloco de construção ao vivo — o vocabulário e a arquitetura, em código. Ninguém apenas assiste: todos digitam junto, no próprio ambiente, enquanto você escreve. Declare o ponto de partida em voz alta antes da primeira linha — repositório vazio, arquivo de build declarando o padrão da linguagem uma vez e as flags de rigor conforme o compilador —, porque conferir de onde se parte é hábito de todo módulo daqui em diante, e este é o módulo em que o hábito se instala.
Construa na ordem: o tipo que representa uma linguagem como conjunto de cadeias, as quatro operações, e depois a tabela que declara a arquitetura. Verbalize as decisões enquanto digita, porque são elas o conteúdo, e o código é o veículo. A primeira é o conjunto ordenado, e diga a razão sem eufemismo: é decisão daquele projeto, tomada por reprodutibilidade da saída, porque ordem que muda a cada execução tira de quem lê a chance de comparar duas saídas lado a lado. Uma tabela de dispersão seria igualmente correta e mais rápida. Separe as duas coisas ali mesmo — o que o conceito exige, e o que um projeto decidiu com o motivo escrito ao lado —, porque confundi-las é o caminho mais curto para decorar como lei o que era preferência de quem implementou.
Ao escrever o fecho, pare na inicialização do acumulador e retome a questão conceitual. Digite primeiro a versão errada, com o conjunto vazio, rode sobre uma linguagem de duas cadeias e mostre a saída vazia; depois corrija para a cadeia vazia e rode de novo. A demonstração custa dois minutos e desfaz um erro que reaparece na determinização. Trate na sequência o parâmetro de comprimento máximo, que a teoria não pediu e a memória exigiu: diga que é bom que ele incomode, porque ele muda a resposta — perguntada sobre uma cadeia longa, a função responde “não está” quando a verdade é “está, e ficou fora do recorte materializado”. Uma implementação que não distingue as duas respostas ensina a quem lê a saída o oposto do verdadeiro. Depois de o fecho compilar, pare e espere a sala alcançar; pergunte quem ainda não compilou e não siga com mais de dois ou três pendentes.
Termine pela tabela da arquitetura, escrita como dado que o programa imprime, e diga por que não como comentário no alto de um arquivo: comentário não executa, não se compara com nada e envelhece em silêncio, enquanto tabela impressa é conferida junto com o resto da saída. Mostre as duas colunas do meio, que declaram o que cada fase consome e o que produz, e faça a conferência ao vivo — o produzido por uma linha tem de ser exatamente o consumido pela seguinte, e onde houver salto falta uma linha na arquitetura. Diga que nenhuma dessas fases existe ainda, e que a tabela é a promessa em formato executável: cada módulo seguinte substitui uma linha dela por implementação real.
Bloco de fechamento — especificar é recusar. Volte ao quadro da abertura, onde 3 x continua escrito. Agora a turma tem o vocabulário para dizer por que o tradutor não adivinha: ao especificar que um nome válido começa por letra, alguém já disse que 3x não vale, e a recusa é o que torna a tradução reprodutível. Enuncie o que cai junto se o conjunto de textos admitidos não for escrito: a gramática, a máquina reconhecedora, a mensagem de erro com posição e a própria noção de programa inválido. Uma fronteira que ninguém escreveu não existe.
Apresente então o documento que o grupo vai escrever na tutoria, e apresente-o como conjunto de quatro perguntas sem uma linha de código dentro: sobre que domínio a linguagem fala, que classe de construções ela aceita, que forma tem o texto que alguém escreve nela, e o que o sistema produz ao processá-lo. Pese a segunda, porque é a que os grupos respondem sem perceber o que estão decidindo — escolher a classe de construções é escolher em que degrau da hierarquia o sistema opera e, portanto, que tipo de máquina será preciso construir. Fixe o formato: cada decisão vem acompanhada da alternativa descartada, com a razão técnica ao lado, porque quem encontrar a decisão adiante sem o registro não distingue uma escolha de um esquecimento. E dê a pergunta de controle, que vale por linha do documento: se uma decisão não restringe nada, ela era descrição fantasiada de decisão, e sai sem perda.
Mande registrar a gramática como ela sair, feia, com recursão à esquerda e alternativas de prefixo comum. Diga que a feiura é de propósito e explique a razão, senão o grupo caprichado devolve o arquivo já arrumado: a comparação entre a forma de partida e a forma corrigida é a explicação mais eficiente que existe sobre por que cada transformação é necessária, e a forma final é sempre recuperável a partir das regras enquanto a de partida, apagada, não volta.
Fecho opcional, se houver fôlego. Havendo tempo depois de a especificação ser apresentada, feche com o experimento de agosto de 1984: ao receber o Prêmio Turing, Ken Thompson descreveu nas Communications of the ACM como um compilador pode ser modificado para inserir uma porta dos fundos em todo programa que compila, e como essa modificação pode ser feita desaparecer do código-fonte do próprio compilador. Conduza em três passos — o fonte modificado gera binário modificado; o binário modificado compila o fonte limpo e produz binário ainda modificado; ler o binário exigiria um desmontador que também foi compilado por alguém. O ganho é o deslocamento da pergunta, de “o que este programa faz?” para “quem traduziu este programa, e o que aquele tradutor sabia?”. Thompson comparece aqui como pessoa, e não como o conceito. Suprima este fecho sem culpa se a semana apertar: ele é o único movimento dispensável do roteiro, e volta com juros no módulo em que a geração de código existir.
Se você quiser inverter a sala. O roteiro acima não pressupõe leitura prévia e funciona com a turma chegando sem ter lido nada; conduza-o assim por padrão, porque roteiro que exige leitura pune quem não a fez. Querendo inverter, peça de antecipação o capítulo do módulo até a seção das operações sobre linguagens e ponha o tempo liberado no bloco da descrição finita e na construção ao vivo, que são os dois que mais sofrem com pressa. O plano B é obrigatório: se menos da metade tiver lido, conduza os dois primeiros blocos como estão escritos e trate a leitura como revisão de quem a fez.
1.3.2 O Marco Deste Módulo, Para Rodar em Aula
O que se projeta no bloco de construção ao vivo é o estado do projeto ao fim deste módulo, com dois pares de arquivos e um ponto de entrada próprio. Ele é imutável: nenhum módulo adiante o edita, de modo que rodá-lo em qualquer ponto do semestre mostra exatamente o que a turma viu no dia. Este é o primeiro marco do percurso, e não há anterior para projetar ao lado — a comparação começa na semana que vem, e vale avisar a turma de que ela vai existir.
O executável imprime três demonstrações, na ordem em que os conceitos se apoiam: as operações sobre cadeias fechando com \Sigma^3 e as oito cadeias uma por uma; as operações sobre linguagens, com o fecho truncado em comprimento 3 saindo com 15 elementos; e a anatomia como tabela construída pelo programa. Confira o 15 antes de rodar diante da turma, porque ele fecha à mão em dez segundos e localiza o defeito sozinho: uma cadeia vazia, duas de comprimento 1, quatro de comprimento 2 e oito de comprimento 3. Outro número aponta erro na potência zero ou na condição de parada, e em nenhum outro lugar.
O comando abaixo está declarado em projeto_professor/.claude/marcos.json, e tools/gerar_marcos.exe listar, com o seu modo, o reimprime a qualquer momento. Rode-o a partir da raiz da variante em uso — a pasta cpp/ do seu modo, dentro de projeto_professor/ —, depois que tools/gerar_marcos.exe check tiver acusado o marco em dia.
1.3.3 Tutoria do Projeto Integrador — a linguagem que cada grupo vai tratar
As duas sessões desta semana fecham três tarefas em que não se escreve uma linha do sistema: fixar o recorte da linguagem, escrever à mão um exemplo válido e montar o repositório. Este é o ponto de apoio máximo do percurso, e é do teto que a redução começa. Aqui você projeta o documento pronto, oferece a estrutura e confere entrada por entrada; no arco intermediário a estrutura sai e o grupo defende as próprias decisões; no arco final ele responde por consequências de escolhas feitas módulos antes. Anuncie a curva agora, numa frase, porque sem o anúncio a redução adiante é lida como descaso.
Primeira sessão — decidir é recusar. Abra projetando o documento de decisão do projeto de referência, a Peneira, com as entradas do recorte à vista: que classe de padrões a linguagem aceita, que forma tem a descrição que o usuário escreve, que objeto o compilador produz. O que interessa é a coluna ao lado, com a alternativa descartada e a razão técnica do descarte. Leia em voz alta a recusa dos retrovisores no dialeto de padrões — aceitá-los tiraria os padrões da classe regular e derrubaria o objeto a emitir, que é um vetor de autômatos finitos. Mostrar esse raciocínio custa menos do que descrevê-lo, e a turma sai sabendo como se escreve uma recusa.
Cobre em seguida a linha que quase todo grupo esquece, e que é a mais cara de todas: o pedido do domínio que a máquina finita não atende. Na Peneira é um padrão de parênteses balanceados, escrevível na linguagem e impossível para qualquer autômato finito — o mesmo caso que a aula teórica conduziu no quadro, com duas profundidades caindo no mesmo estado. Sem essa linha escrita agora, a subida do reconhecimento regular para o reconhecimento com pilha, seis módulos adiante, chega ao grupo como mudança de assunto em vez de resposta a um limite que ele próprio registrou. Peça o análogo no domínio de cada grupo e aceite qualquer um, desde que venha com a razão junto.
Diga então a frase que evita metade dos problemas da semana: a Peneira é exemplo resolvido, e serve de referência de acabamento. Cada grupo escolhe o próprio domínio e responde pelas próprias entradas. Circule com uma pergunta só, repetida grupo a grupo: que decisão futura esta escolha impede? Escolha que não impede nada era descrição disfarçada de decisão, e o grupo precisa ouvir isso enquanto reescrever um parágrafo ainda é barato. Ninguém sai da primeira sessão sem as entradas do recorte escritas, cada uma com a alternativa recusada ao lado.
A pergunta que desmonta o recorte em segundos, e que você faz em todos, inclusive nos impecáveis: mostre onde está escrito o que fica gravado quando o tradutor termina, e quem lê aquilo depois. Um recorte que descreve um sistema executando direto, sem gravar objeto algum, passa numa leitura apressada porque cobre domínio, forma da descrição e classe de padrões com competência. A lacuna só aparece no arco de geração de código, quando não há mais o que consertar sem jogar fora o que foi construído.
Segunda sessão — o exemplo, e o lugar onde ele vai morar. Comece pelo exemplo escrito à mão e cobre a metade que sempre falta: o resultado esperado, registrado antes de existir código que o produza. Peça que o exemplo exercite cada construção do recorte ao menos uma vez e, sobretudo, que inclua um caso que casa o padrão e não produz saída. Vale mostrar como a referência resolveu isso, porque o detalhe é o que ensina: na entrada de teste da Peneira, dois números casam o padrão numérico e nenhum dos dois produz linha, cada um por um motivo diferente — um reprova na condição por magnitude, que é o caso negativo que todo mundo pensa em escrever, e o outro reprova por sinal, porque o sinal entra no casamento e o número comparado é negativo. O segundo é o que ninguém escreve de propósito. Um sistema que ignorasse por inteiro a condição associada à regra emitiria linhas demais e passaria em dois terços da bateria — proporção que, num relatório de progresso, passa tranquilamente por sucesso.
Cobre também a gramática em rascunho, e cobre-a feia. O grupo escreve as produções da própria linguagem na forma de partida, com recursão à esquerda, alternativas de prefixo comum e o que mais sair, e preserva esse texto. Diga a razão em voz alta, senão o grupo caprichado devolve o arquivo já arrumado e perde a comparação: no arco das gramáticas livres de contexto a forma anterior aparece ao lado da corrigida, e essa comparação é a explicação mais eficiente que existe sobre por que cada transformação é necessária. Aproveite para cobrar uma cadeia derivada à mão a partir dessas produções, do símbolo inicial até o texto — é o exercício da aula teórica aplicado ao domínio do grupo, e é onde se descobre que a gramática escrita não gera o exemplo que o grupo acabou de registrar.
A segunda metade da sessão é o repositório e o comando único que reconstrói tudo e roda os casos existentes. Os grupos vão querer adiar a configuração de compilação com o argumento de que ainda não há o que compilar; não deixe. Montada agora, sobre nada, é trivial; montada adiante, sobre uma dúzia de arquivos, consome uma sessão inteira, e o hábito de rodar a bateria a cada mudança não se instala retroativamente. Encerre com revisão entre pares: cada grupo clona o repositório de outro e tenta reconstruir do zero, sem falar com o autor. Se exigir qualquer passo manual não documentado, não está pronto — e quem descobre isso é o grupo vizinho, não você.
Programação em pares vale também quando não há código. Um integrante redige a entrada do documento enquanto o outro lê em voz alta caçando ambiguidade, e os papéis giram a cada entrada concluída. Grupos maiores se dividem em pares simultâneos sobre entradas distintas; o integrante ímpar entra no rodízio de um par existente e nunca abre frente própria, porque frente própria vira trabalho paralelo sem revisão. Anuncie o revezamento você mesmo, duas ou três vezes por sessão: nenhum grupo troca de piloto sozinho na primeira semana. O sintoma a caçar é o teclado que não muda de dono. Ao notar, deixe a repreensão de lado e pergunte ao integrante que está de fora qual foi a alternativa descartada na última decisão. A resposta separa, na hora, quem participa de quem assiste.
O que vai aparecer, e o que fazer com cada caso. O primeiro e mais comum é o recorte largo: o grupo escolhe um domínio ambicioso prometendo restringir depois. Não discuta a ambição; peça o exemplo válido agora, nesse domínio. O exemplo denuncia o tamanho sozinho, e restrição que o grupo se impõe dura mais do que a imposta por você.
O segundo é o grupo que decalca a Peneira trocando os nomes. Identifica-se sem esforço: o documento não terá alternativas descartadas, porque quem copia não sabe o que o autor recusou. Devolva pedindo uma decisão que a Peneira não tomou, qualquer uma, com a razão técnica junto.
O terceiro escreve a gramática já arrumada, e responde que a versão anterior “não estava boa”. Peça a versão anterior; ela costuma existir num rascunho. Não existindo, aceite a corrigida e registre a perda no diário, para que o grupo saiba o que deixou de ter quando a comparação for pedida.
O quarto é o grupo que promete um objeto de saída sem dizer quem o lê. Devolva com a pergunta do quadro vermelho acima, e exija a resposta por escrito no documento, não em conversa.
O quinto é o silencioso, que garante estar tudo entendido e não produz artefato. É o mais perigoso da semana, porque não gera atrito nenhum na hora, e o remédio é material: ninguém sai da segunda sessão sem os três artefatos existindo, ainda que curtos. Quem sai devendo aqui chega ao módulo dos padrões sem ter sobre o que aplicá-los.
Fechamento das duas sessões. Cada grupo atualiza o diário registrando o que foi feito, por quem, que decisão foi tomada e qual alternativa ficou de fora. Nesta semana o diário é quase só decisão, o que o torna a evidência mais forte de contribuição individual que você terá no período: as perguntas da arguição final saem dele. O recorte, por sua vez, compõe a entrega parcial do Projeto Integrador com devolutiva e sem nota própria, e o que você devolve é a conferência do recorte contra a cobertura da ementa, tópico a tópico — a conferência mais barata do semestre, e a que evita o prejuízo mais caro.
1.4 Entregáveis e Avaliação
O que acompanha e não gera nota. As duas questões conceituais das aulas teóricas, a revisão entre pares no fim da tutoria, os exercícios do módulo e o diário de atividades do grupo. Todos produzem devolutiva imediata e nenhum produz nota. Diga isso à turma antes do primeiro voto, porque a sala silencia quando suspeita que está sendo medida: o valor de votar está em errar cedo, e um erro sobre a potência zero corrigido nesta semana é o que evita uma tarde de depuração no lugar errado, três módulos adiante.
O que compõe nota. Ao fim do módulo o grupo entrega o estado corrente do trabalho, e são três peças, nenhuma delas com código: o recorte da linguagem escrito por extenso, com a alternativa descartada ao lado de cada decisão; um exemplo válido escrito à mão, com o resultado pretendido registrado ao lado; e o repositório montado, com o comando único que reconstrói tudo e roda os casos existentes. A entrega alimenta a parcela de entregas parciais do Projeto Integrador, que vale quinze por cento da nota do período, e a pontualidade compõe parcela própria, de dez por cento. O módulo abre ainda o primeiro dos blocos de verificação individual definidos no conteúdo programático, aplicado ao término do bloco e não a cada módulo: dois itens decidindo um componente de nota seria sorteio, e é por isso que a verificação consolida por bloco.
Não crie instrumento com nota para este módulo. A tentação aqui é específica e nasce da ausência de código: como não há o que rodar, parece que só uma prova escrita provaria que a semana rendeu. Ela provaria, e a que prova já existe — a verificação individual do bloco mede exatamente a teoria desta semana, sem consulta e sem ferramenta de geração automática de texto. Multiplicar entregas avaliadas é a sobrecarga que esta disciplina evita de propósito, e a rubrica do projeto foi publicada junto com a proposta, sem ajuste módulo a módulo.
1.5 Orientações Sobre o Aplicativo
O banco de questões teóricas deste módulo vai ao aplicativo do estudante pelo seu próprio sistema, e o engajamento no estudo por ele compõe vinte por cento da nota do período. Libere o banco ao final da segunda aula teórica, depois de as operações sobre linguagens terem sido tratadas. Liberado antes, o estudante responde os itens de alfabeto e cadeia por reconhecimento de palavra, acerta, e conclui que o módulo é fácil — que é precisamente a conclusão que esta semana existe para impedir.
O mesmo banco rende mais em sala do que fora dela. Se a turma votar pelo aplicativo nas duas questões conceituais, você vê a distribuição do primeiro voto na hora e decide com dado se manda discutir ou se refaz a explicação antes da discussão. Registre qual alternativa errada concentrou o voto, porque as concentrações pedem intervenções distintas: peso em (A) na primeira questão é a confusão entre a linguagem vazia e a linguagem da cadeia vazia, e se resolve pela cardinalidade, escrita no quadro; peso em (C) ou (D) na primeira é a definição de potência que ainda não fechou, e se resolve refazendo-a antes de seguir; peso em (C) na segunda é o palpite de que basta acrescentar estados, e essa não cede a explicação — cede à pergunta sobre qual número bastaria, feita a quem a marcou.
Deixe explícito à turma que responder no aplicativo é estudo, e não avaliação: o instrumento que compõe a parcela individual é aplicado em aula, sem consulta e sem uso de ferramenta de geração automática de texto.
1.6 Pontos de Atenção Específicos
O erro estrutural do módulo. O estudante que conclui que a semana é dispensável porque não há código a escrever. O sintoma aparece na tutoria como grupo que garante estar tudo entendido e não produz artefato, e é o mais perigoso porque não gera atrito nenhum na hora. Quem sai sem recorte escrito e sem repositório montado começa o módulo seguinte devendo, e a dívida só aparece três ou quatro módulos adiante, quando já existe código apoiado sobre a decisão que faltou. O remédio é material, nunca retórico: ninguém sai da segunda sessão sem os três artefatos existindo, ainda que curtos.
A confusão que atravessa o período. A linguagem sem cadeia alguma e a linguagem cuja única cadeia é a vazia. O estudante escreve, com convicção e argumento coerente, que L^0 = \emptyset porque zero cópias de coisa nenhuma dá coisa nenhuma. Ela reaparece na construção do autômato, na determinização e na verificação de significado, e cada retorno sai mais caro. Não conte com uma explicação bem-feita: ataque-a três vezes nesta semana, em formatos diferentes — pela cardinalidade no bloco das operações, pelo voto na primeira questão conceitual, e pelo código na construção ao vivo, rodando a versão errada antes da certa.
O erro de classificação. O estudante olha a complexidade visual da cadeia e responde por aparência: texto que parece complicado vai para um degrau alto, texto curto vai para o de baixo. A devolutiva é sempre a mesma pergunta, e nunca a resposta — o que essa máquina precisaria lembrar para decidir? Repita a pergunta na mesma forma todas as vezes, inclusive quando a resposta do estudante estiver certa, porque é a forma da pergunta que ele precisa levar embora.
O erro que a definição autoriza e a intuição recusa. Alguém vai afirmar que uma linguagem precisa ter regra, padrão ou descrição para existir, e vai afirmar isso depois de você ter enunciado o contrário. A definição não faz exigência alguma, e o argumento de contagem mostra que quase nenhuma linguagem tem descrição finita. Quando a afirmação voltar sob a forma “ainda não descobriram descrição para essas linguagens”, corrija de imediato e com todas as letras: a descrição não existe, e isso é demonstrado, não conjecturado.
A digressão previsível. Alguém perguntará por que não se usa um gerador de analisadores, já que existem e são gratuitos. Responda inteiro, uma vez só, e não volte ao assunto: o arco de autômatos é o conteúdo da disciplina, e não o meio de produzir o artefato — com gerador, os seis primeiros módulos viram pré-requisito de uma caixa fechada. Diga também que geradores voltam como objeto de estudo comparativo no módulo de análise sintática ascendente, porque a promessa de retorno é o que encerra a pergunta.
O que tenta executar enquanto lê. Nas primeiras aulas o estudante processa o texto na cabeça, símbolo a símbolo, decidindo o significado de cada caractere no momento em que o lê. Funciona nos casos pequenos e desmorona no primeiro exemplo que exige olhar adiante antes de decidir — que é exatamente o argumento do retrocesso, no bloco de abertura. Quando notar, devolva o próprio 3x: pergunte que decisão ele tomou ao ver o 3, e o que aconteceu quando o x chegou.
Se o tempo apertar. Aceita compressão o bloco da pilha, retomado por inteiro no módulo dos autômatos de pilha — preserve dele a data de Amsterdã e as três alturas, que são o que impede a pilha de parecer artifício da teoria quando o autômato de pilha chegar. Aceita supressão o fecho de 1984. Não aceita compressão o bloco da descrição finita: sem gramática, derivação e o argumento de contagem, o módulo seguinte trata expressão regular como notação de conveniência, e a turma perde a única razão pela qual descrição finita é assunto e não detalhe de implementação.