flowchart TB
subgraph A20["árvore A — a soma fecha primeiro:<br/>(2 + 3) * 4, e a conta dá 20"]
direction TB
A0["E"] --> A1["E"]
A0 --> A2["op = *"]
A0 --> A3["E = num 4"]
A1 --> A4["E = num 2"]
A1 --> A5["op = +"]
A1 --> A6["E = num 3"]
end
subgraph B14["árvore B — o produto fecha primeiro:<br/>2 + (3 * 4), e a conta dá 14"]
direction TB
B0["E"] --> B1["E = num 2"]
B0 --> B2["op = +"]
B0 --> B3["E"]
B3 --> B4["E = num 3"]
B3 --> B5["op = *"]
B3 --> B6["E = num 4"]
end
A20 -.->|"mesma cadeia, mesma gramática,<br/>duas árvores admitidas"| B14
1 Linguagens formais e a arquitetura de um compilador — Resolução dos Exercícios
Documento exclusivo do professor. Não o entregue à turma nem o registre em perfil de estudante. Os três problemas foram armados para que o erro apareça antes da correção, e quem lê o gabarito antes de tentar sai sem errar nada — prejuízo disfarçado de economia. Em cada exercício as orientações vêm antes do gabarito, na ordem da condução em sala e não na da conferência.
Esta é a primeira vez no semestre em que a turma escreve vocabulário formal por conta própria, e o resultado costuma ser desigual de um jeito que engana. Boa parte da folha sai correta porque as contas são pequenas; o que discrimina são três ou quatro linhas em que o estudante precisa dizer qual espécie de objeto tem na mão — elemento ou conjunto, cadeia ou linguagem, texto ou árvore. Corrija olhando para essas linhas primeiro.
Dois dos três problemas giram em torno de um número, e é por isso que eles funcionam. Número errado se discute; impressão errada, não. O primeiro pede quinze cadeias e uma fórmula, e derruba quem esquece o andar de comprimento zero. O segundo põe um arquivo de dezenas de gigabytes ao lado de duas linhas de gramática, e é o único momento do módulo em que a economia da descrição finita aparece como grandeza medida, e não como tese. O terceiro não tem conta nenhuma até a última letra, e é ali que reaparece o erro que atravessa o período inteiro: classificar uma exigência pela aparência do texto que a expressa.
Reserve para o terceiro problema mais tempo do que para os dois primeiros somados, e conduza-o com a turma inteira falando. Ele é o único ponto do módulo em que a teoria arbitra uma decisão de engenharia cuja conta é paga por quem está fora do sistema — a pessoa na fila do terminal, a quem uma regra mal lida nega a isenção a que tem direito.
Uma advertência de método, e vale para os três. Vários caminhos errados descritos abaixo chegam ao número certo pelo motivo errado, e nenhum deles aparece na folha. Só aparecem quando você pergunta por quê em voz alta. Pergunte sempre, inclusive a quem acertou — sobretudo a quem acertou depressa.
1.1 Resolução do Exercício 1: contar antes de listar
Nível básico
1.1.1 Orientações Pedagógicas para o Professor
Comece pedindo a soma da letra (a) de cabeça, antes de qualquer conta escrita, e anote no quadro os números que a turma gritar. Vai aparecer 14, e vai aparecer com convicção. Quem responde 14 somou os andares de comprimento 1, 2 e 3 e não contou o topo do diagrama, que tem exatamente um habitante e nenhum símbolo dentro. A diferença entre 14 e 15 é a cadeia vazia, e ter os dois números lado a lado no quadro rende mais que qualquer explicação sobre ela. O diagrama tem o andar zero desenhado à vista, com rótulo e tudo. Ele some assim mesmo.
O tropeço seguinte em (a) é a fórmula. A resposta errada frequente é 2^n, e a concepção por baixo dela é razoável: o estudante leu “até n” e escreveu a expressão do andar n, que era a única que ele tinha na mão. A soma dos andares de 0 a n vale 2^{n+1} - 1, e a maneira de fazer isso pegar não passa por demonstrar a progressão geométrica no quadro. Peça que ele confira a própria fórmula contra o 15 que acabou de contar à mão. Fórmula que não reproduz o caso pequeno já conferido está errada, e o estudante descobre isso sozinho.
A letra (b) é o coração do exercício e é o primeiro encontro escrito com a confusão que reaparece na construção do autômato, na determinização e na verificação semântica, cada vez mais cara. Três respostas erradas circulam para A^0, e vêm de concepções diferentes. Distinga-as pela fala, porque a intervenção muda em cada caso.
A primeira aparece quase literalmente assim: “A^0 = \emptyset porque zero cópias de coisa nenhuma dá coisa nenhuma”. Ela vence o primeiro voto com folga em qualquer turma, e o argumento é bom — o que torna o item útil. Quem raciocina desse jeito aplica à potência a intuição correta sobre a concatenação, onde o conjunto vazio de fato aniquila. A segunda forma é “A^0 = A, porque elevar a zero não altera o conjunto”: aqui o estudante aplicou a regra do expoente um e leu a potência como operação sobre o rótulo, e não sobre o conteúdo. A terceira é “A^0 = \{\varepsilon, 0, 01\}”, que junta o nível zero com o nível um e denuncia alguém que já viu o fecho de Kleene e o colapsou com a potência. Se a segunda e a terceira somadas passarem de um terço da turma, pare e refaça a definição de potência antes de seguir para a letra (c); o resto do módulo se apoia nela.
A devolutiva que funciona em (b) é a cardinalidade, e não a explicação. Peça os três resultados escritos por extenso, com o número de elementos ao lado de cada um: \emptyset tem zero, \{\varepsilon\} tem um, e a distância entre zero e um é a resposta inteira. Enquanto o estudante falar em “vazio” para os dois, ele tem uma palavra só para duas coisas e vai continuar errando — em fevereiro, e de novo no módulo da determinização.
Na letra (c), o erro previsível é listar dois prefixos — 0 e 01 — e parar. Faltam os dois casos de borda, que são justamente os que o programa vai encontrar: a cadeia inteira e a cadeia vazia. A pergunta de devolutiva é curta: no instante em que o programa ainda não leu nada, que prefixo ele já tem na mão? A segunda parte da letra é onde aparece a tentativa de executar o texto enquanto se lê. O estudante descreve o que o programa “conclui” ao ver 01, e o que ele escreve é o que ele próprio concluiu olhando a cadeia inteira impressa no enunciado. Devolva pelo recorte físico: tape com o dedo o que vem depois do 01 na folha dele e refaça a pergunta.
Circule pelas carteiras ouvindo duas palavras. Quem diz que a cadeia vazia “não existe” está prestes a errar (b) na primeira forma; quem diz que ela “é o espaço” está prestes a errar a contagem de (a) e a lista de (c). As duas falas anunciam o erro antes de a folha registrá-lo, e conserta-se mais barato em voz alta.
Sobre a devolutiva escrita. Uma boa resposta escreve os quatro andares por extenso mesmo achando o pedido bobo, confere a fórmula contra o caso pequeno e dá a cardinalidade dos três resultados de (b) com uma frase de razão em cada. Uma resposta parcial típica acerta a contagem, acerta A\emptyset e A\{\varepsilon\} e erra A^0: ela mostra alguém que entendeu a concatenação e ainda não separou potência de concatenação. A orientação para essa pessoa é uma tarefa de três linhas, e não uma explicação — escreva A^0, A^1 e A^2 por extenso e diga, em cada passagem, qual conjunto foi multiplicado por qual. Quem errou (c) por listar dois prefixos tem outra fragilidade: peça a definição de prefixo por escrito antes de qualquer correção da lista.
1.1.2 Resolução Modelo
(a) Os quatro andares, lidos do diagrama e escritos por extenso.
\Sigma^0 = \{\varepsilon\} \qquad \Sigma^1 = \{0,\ 1\} \qquad \Sigma^2 = \{00,\ 01,\ 10,\ 11\}
\Sigma^3 = \{000,\ 001,\ 010,\ 011,\ 100,\ 101,\ 110,\ 111\}
A cardinalidade de \Sigma^3 confere com a fórmula: |\Sigma|^n = 2^3 = 8, e são oito cadeias listadas. Somando os quatro andares, chega-se às janelas de comprimento até 3: 1 + 2 + 4 + 8 = 15.
A fórmula geral da soma é a progressão geométrica de razão 2, truncada em n:
\sum_{i=0}^{n} |\Sigma|^i = \sum_{i=0}^{n} 2^i = 2^{n+1} - 1 .
Ela reproduz o caso já contado: para n = 3, 2^4 - 1 = 15. Avaliada em n = 20, dá 2^{21} - 1 = 2.097.151 janelas, das quais 2^{20} = 1.048.576 têm o comprimento máximo. Cada minuto acrescentado à janela dobra o total, e é essa taxa que decide a pergunta, não o valor em si. Tome uma referência explícita, hipotética e generosa: um verificador capaz de submeter um milhão de janelas por segundo. Em n = 20 ele termina em cerca de dois segundos; em n = 30, em cerca de trinta e sete minutos; em n = 40, em cerca de vinte e cinco dias. A estratégia exaustiva deixa de caber em algum ponto entre a terceira e a quarta dezena de minutos de janela, e nenhuma melhoria de constante move essa fronteira mais que alguns minutos para a direita: dobrar a velocidade da máquina compra exatamente um minuto a mais de janela.
(b) Os três resultados, com a cardinalidade e a razão de cada um.
A\emptyset = \emptyset, com zero elementos. A concatenação forma o par uv para cada u \in A e cada v \in \emptyset, e não existe v a escolher: nenhum par se forma. É o papel do zero na multiplicação — qualquer que seja o outro fator, o produto morre.
A\{\varepsilon\} = \{0,\ 01\} = A, com dois elementos. Aqui existe exatamente um v possível, e ele é a cadeia de comprimento zero: cada u produz u\varepsilon = u. É o papel do um na multiplicação — o fator neutro devolve o conjunto intacto.
A^0 = \{\varepsilon\}, com um elemento. A potência zero de uma linguagem qualquer é o conjunto que contém apenas a cadeia vazia, e ela é a base da definição recursiva de potência: L^{n+1} = L^n L precisa de um ponto de partida que se comporte como neutro, e \{\varepsilon\} é esse ponto. Os dois primeiros resultados diferem entre si sem que nenhum seja contradição porque leem “zero” em sentidos distintos: A\emptyset multiplica por um conjunto sem elementos e aniquila; A\{\varepsilon\} multiplica pelo neutro e preserva.
Um programa que escrevesse A^0 como \emptyset produziria saída vazia para qualquer entrada, se o fecho for construído acumulando potências por multiplicação sucessiva a partir da potência zero: o acumulador começa aniquilado e permanece aniquilado em toda iteração, de modo que A^* sai vazio mesmo para uma linguagem de duas cadeias que se confere a olho. A linha que falha não coincide com a linha errada — a inicialização defeituosa mora várias funções acima do ponto em que a saída aparece.
(c) Os prefixos de 011 são quatro: \varepsilon, 0, 01 e 011. Toda cadeia é prefixo de si mesma e a cadeia vazia é prefixo de qualquer cadeia, de modo que os dois casos de borda entram na lista pela definição, e não por concessão.
No instante em que acabou de ler 01, um programa que lê da esquerda para a direita sem voltar atrás sabe três coisas: que os dois primeiros minutos observados foram livre e ocupado, nessa ordem; que a janela completa, qualquer que venha a ser, tem 01 como prefixo; e que tudo o que começa por 00, 10 ou 11 já está descartado. Ele não sabe se a janela termina ali ou continua, não sabe o comprimento total e, portanto, não sabe se ela dispara alarme — a menos que a linguagem de alarme já esteja decidida por esse prefixo, o que exigiria que toda cadeia começada por 01 tivesse o mesmo destino. Enquanto essa condição não valer, decidir naquele instante é apostar, e o preço de errar a aposta é voltar atrás — que é exatamente o que a leitura sem retrocesso proíbe.
1.2 Resolução do Exercício 2: o que cabe na memória, o conjunto ou o critério
Nível intermediário
1.2.1 Orientações Pedagógicas para o Professor
Peça um palpite antes de qualquer conta e escreva-o no quadro: quanto cresce o arquivo da lista quando a especificação passa de seis rumos para vinte? A turma chuta “umas dez vezes”, “cem vezes”, e alguém arrisca “mil”. A resposta é 14.348.907 vezes, que por acaso é 3^{15} redondo. Ter o palpite ao lado do resultado é o que faz a lição pegar, porque a distância entre os dois números é o assunto do exercício inteiro. O robô do armazém precisaria de um armazém.
Em (a) o erro de conta mais comum é 6^3 em vez de 3^6. A concepção é de leitura: o estudante lê “seis rumos, três símbolos” e escreve os dois números na ordem em que apareceram na frase. A devolutiva é o caso pequeno — quantos trajetos de dois rumos existem? —, que ele consegue listar à mão e conferir contra as duas fórmulas. Nove contra oito resolve a discussão em quinze segundos. Vale insistir: a base é o número de escolhas por posição e o expoente é o número de posições, e essa ordem volta em todo o módulo de autômatos.
O item (b) tem um resultado que confere contra o diagrama, e por isso é autoverificável: são quatro produções, e o diagrama já declara quatro. Quem responde duas contou linhas de texto; quem responde três esqueceu a produção do símbolo inicial. Nenhum dos dois é descuido puro — os dois revelam alguém que está lendo a gramática como documento em vez de como conjunto de regras, que é a mesma leitura que produz a resposta errada da segunda metade do item.
Essa segunda metade merece atenção redobrada porque a afirmação errada é sedutora e circula em livros mal escritos: a de que a barra vertical, ou a notação abreviada em geral, acrescenta poder de expressão. Ela não acrescenta nada; encurta o documento e se desfaz mecanicamente antes de qualquer analisador rodar. Se alguém defender o contrário, não discuta em abstrato — peça a reescrita completa e pergunte qual cadeia a gramática abreviada gera que a expandida não gera. A busca fracassa, e o fracasso é o argumento. O fecho do item pede o que decide o alcance, e a resposta correta é a forma permitida às produções, que é o critério de onde saem as classes da hierarquia; o tamanho do documento decide o custo de digitar, e mais nada.
No item (c) o tropeço é de método, e é caro deixar passar. Pedida a derivação de EDF, muita gente escreve duas linhas e um “e assim por diante”. A derivação completa tem sete linhas, uma produção por linha, e escrevê-las é o treino que o módulo do analisador descendente vai cobrar com juros. Exija as sete. O segundo erro do item aponta o infinito no lugar errado: o estudante diz que ele vem “das chaves”. As chaves são notação, e some na reescrita; o infinito vem da produção recursiva, aquela em que o não terminal auxiliar reaparece do lado direito. Peça que ele circule na folha a produção exata e diga quantas vezes ela pode ser aplicada.
O item (d) traz o erro que o escopo ampliado deste módulo tornou previsível, e ele tem uma forma verbal fixa que você precisa reconhecer de imediato: “ainda não descobriram descrição para essas linguagens”. Quem diz isso trocou uma demonstração por uma ignorância provisória, e imagina que o argumento de contagem descreve o estado atual da pesquisa. Corrija na hora e com todas as letras: a descrição não existe, e isso está demonstrado. A pergunta que desmonta a concepção é sobre a espécie do argumento — o que teria de acontecer para essa afirmação ser derrubada amanhã? Não há resposta, porque não é uma conjectura à espera de alguém mais esperto.
Ainda em (d), a assimetria entre pertencer e não pertencer costuma ser respondida com “basta testar todas as derivações”. Devolva a pergunta pelo número: quantas derivações a gramática de (c) admite? Ele acabou de mostrar que são infinitas, três linhas acima, e a contradição entre as duas respostas é dele para resolver, não sua para explicar. A resposta boa percebe que a não pertinência exige um argumento sobre as produções, e não uma varredura.
Uma nota de condução. Este exercício rende em duplas e rende pouco em silêncio, porque as contas de (a) são conferíveis entre duas pessoas em um minuto e a discordância aparece na hora. Reserve os últimos dez minutos para o item (d) com a turma inteira: ele é conceitual, não tem número, e é o único ponto do módulo em que a turma encosta num resultado de teoria dos conjuntos. Deixá-lo para leitura em casa é perdê-lo.
Sobre a devolutiva. Uma boa resposta traz as duas medidas de (a) com o multiplicador exato, as quatro produções de (b) conferidas contra o diagrama, as sete linhas da derivação de (c) com a produção recursiva apontada, e em (d) separa com clareza o que se demonstra exibindo um objeto do que se demonstra argumentando sobre todos. Uma resposta parcial típica acerta todas as contas e, em (d), conclui que “quase toda linguagem é difícil de descrever”: ela trocou impossibilidade por dificuldade, que é a mesma fragilidade da forma verbal citada acima, em roupa mais discreta. A orientação para essa pessoa é escrever, em duas linhas, por que as descrições se enfileiram e as linguagens não. Quem entregou a derivação incompleta precisa de outra tarefa: refazer EDDF com uma produção por linha, sem pular nada, e contar os passos.
1.2.2 Resolução Modelo
(a) As duas medidas, e o que cada uma faz sob a mesma alteração.
Com seis rumos e três símbolos por posição, existem 3^6 = 729 trajetos. A 7 bytes por linha, a lista ocupa 729 \times 7 = 5.103 bytes — cinco quilobytes, um arquivo que se abre em qualquer editor sem pensar duas vezes.
Com vinte rumos, existem 3^{20} = 3.486.784.401 trajetos. A 21 bytes por linha, o arquivo ocupa 3^{20} \times 21 = 73.222.472.421 bytes, algo em torno de setenta e três gigabytes. O multiplicador é exato:
\frac{3^{20} \times 21}{3^{6} \times 7} = 3^{14} \times 3 = 3^{15} = 14.348.907 .
A segunda descrição, sob a mesma alteração, passa de seis para vinte ocorrências de R na primeira linha: catorze símbolos a mais, vinte e oito caracteres contando os espaços que os separam. A segunda linha não muda em nada, porque o alfabeto de rumos continua o mesmo. Trinta e poucos caracteres digitados contra setenta e três gigabytes gravados, para o mesmo conjunto de trajetos.
(b) A gramática sem a barra vertical tem quatro produções:
T ::= R\,R\,R\,R\,R\,R \qquad R ::= E \qquad R ::= D \qquad R ::= F
O total confere com o número que o diagrama declara para a segunda descrição. Duas linhas de texto e quatro produções descrevem a mesma coisa porque a barra vertical junta numa linha as produções que compartilham o lado esquerdo: a linha R ::= E \mid D \mid F é uma abreviação tipográfica de três produções, e a expansão é mecânica e sem escolhas.
A linguagem gerada é idêntica antes e depois porque o conjunto de produções, uma vez expandido, é o mesmo, e a linguagem gerada depende apenas de quais produções existem — não da forma como elas foram impressas. Toda derivação disponível na versão abreviada usa uma das três alternativas de R a cada passo, e é exatamente essa a escolha que a versão expandida oferece. Uma notação de abreviação não pode ampliar o alcance de uma gramática justamente por essa razão: ela se desfaz em produções comuns antes de o analisador rodar, e o que roda é sempre a versão expandida.
O que decide o alcance é a forma permitida às produções — que espécie de sequência pode aparecer de cada lado da seta. É daí que saem as classes da hierarquia, e é por isso que a classificação de uma gramática não muda quando alguém reescreve o documento de maneira mais econômica. O tamanho do documento decide quanto se digita.
(c) A abreviação T ::= R\ \{\,R\,\} pede um não terminal auxiliar, que aqui se chama C, para carregar a repetição:
T ::= R\,C \qquad C ::= R\,C \qquad C ::= \varepsilon
A derivação de EDF a partir do símbolo inicial, uma produção por linha, substituindo sempre o não terminal mais à esquerda:
T \Rightarrow R\,C \Rightarrow E\,C \Rightarrow E\,R\,C \Rightarrow E\,D\,C \Rightarrow E\,D\,R\,C \Rightarrow E\,D\,F\,C \Rightarrow E\,D\,F
São sete formas sentenciais e seis passos. O infinito vem da produção C ::= R\,C, e a razão está na reaparição de C do lado direito: aplicá-la produz uma forma sentencial que admite aplicá-la de novo, sem que nada no conjunto de produções limite o número de repetições. A produção C ::= \varepsilon é o que permite parar; sem ela, nenhuma derivação terminaria e a linguagem gerada seria vazia.
A primeira descrição, sob essa alteração, deixa de existir como arquivo. O conjunto de trajetos passa a ser infinito, a lista nunca termina de ser escrita, e nenhuma quantidade de disco muda isso — o obstáculo é de espécie, não de tamanho. Truncar a lista em algum comprimento máximo produz outro conjunto, o dos trajetos até aquele comprimento, e descrever esse outro conjunto não responde à especificação que foi entregue.
(d) Para demonstrar que uma cadeia pertence ao conjunto gerado, basta exibir uma derivação: o objeto tem tamanho finito, é escrito numa folha e conferido por outra pessoa em minutos, como as sete linhas acima. Para demonstrar que ela não pertence, essa saída não existe: seria preciso examinar todas as derivações possíveis a partir do símbolo inicial e verificar que nenhuma produz a cadeia, e o conjunto das derivações é infinito para qualquer gramática com produção recursiva. A tarefa não é simétrica porque uma testemunha positiva é um objeto e uma testemunha negativa seria uma varredura. O que se faz, na prática, é argumentar sobre as produções em vez de enumerar derivações: para a gramática de (c), toda derivação a partir de T produz uma sequência de um ou mais símbolos de \{E, D, F\}, logo EDX está fora sem que nenhuma derivação precise ser tentada.
Feita a amarração das três letras anteriores, chega-se ao argumento de contagem. As descrições finitas são textos finitos sobre um alfabeto finito, e por isso se enfileiram por comprimento — primeiro as de comprimento 1, depois as de 2, e assim adiante —, de modo que toda gramática que alguém venha a escrever tem posição marcada nessa fila. As linguagens sobre \Sigma são os subconjuntos de \Sigma^*, e o argumento diagonal de Cantor mostra que os subconjuntos de um conjunto infinito enumerável não se enfileiram. Uma coleção cabe na fila; a outra não. A conclusão obrigatória é que a fatia de linguagens que um sistema de tradução consegue tratar — as que têm alguma descrição finita — é uma parte desprezível do total, e que quase toda linguagem não tem descrição nenhuma.
Esse resultado é demonstrado, e não uma dificuldade à espera de alguém mais esperto. A demonstração não fala de esforço, de estado da técnica nem de quanto se pesquisou: ela compara duas coleções e mostra que uma é maior que a outra em espécie. Não há descoberta futura que faça caber na fila o que provadamente não cabe.
Falta o passo que fecha o problema. A informação que precisa ser conhecida antes de escolher entre as duas descrições é se o conjunto é finito e, sendo finito, qual é o teto do comprimento e quão estável ele é. Guardar o conjunto sobrevive a especificações finitas, pequenas e congeladas. Guardar o critério sobrevive à alteração de (c), que aniquila a lista e cobra vinte e oito caracteres da gramática.
1.3 Resolução do Exercício 3: quatro relatos, e nenhuma gramática
Nível desafiador
1.3.1 Orientações Pedagógicas para o Professor
Este é o problema que separa a turma, e a separação não acontece por dificuldade de conta — não há conta até a última letra. Ela acontece porque as quatro respostas precisam ser lidas como um argumento único, e o estudante que tratou cada letra como uma pergunta independente entrega quatro parágrafos corretos que não se sustentam juntos. Corrija na ordem inversa: leia primeiro o fecho, depois as letras.
Em (a) o caminho errado fino não está nas árvores, que quase todo mundo desenha certo. Está na pergunta sobre onde mora o defeito. Aparecem duas respostas erradas, com concepções distintas. A primeira culpa as implementações: “uma das duas equipes leu errado”. A segunda culpa a cadeia: “2 + 3 * 4 é ambíguo”. Nenhuma das duas se sustenta, e a réplica é a mesma para as duas — as duas árvores são derivações legítimas da gramática que foi escrita, de modo que nenhuma equipe violou a especificação e nenhuma cadeia carrega ambiguidade sozinha. Ambiguidade é propriedade da gramática, e o defeito mora nela. Quem culpa a implementação está buscando um culpado onde falta um árbitro, e é essa a lição do problema.
O segundo tropeço de (a) é a correção proposta. Parte da turma “resolve” a ambiguidade escrevendo em prosa que a multiplicação vem primeiro, o que apenas devolve o problema ao manual em português de onde ele veio. Outra parte propõe estratificar a gramática e depois não consegue argumentar que o conjunto de cadeias permanece o mesmo. Peça o argumento nas duas direções: nenhuma cadeia nova entra e nenhuma sai. Quem entender que a estratificação remove árvores e não remove cadeias entendeu o item.
O item (b) é onde o erro estrutural do módulo aparece com fantasia nova, e é o item que exige a sua presença. O estudante classifica os parênteses encaixados pela aparência do texto: acha o trecho visualmente complicado e sobe um degrau, ou acha que “parênteses são só dois símbolos” e desce um. Diga a réplica exatamente assim, sem parafrasear: quem só sabe em que estado está não sabe quantas vezes já entrou nele. E emende com a pergunta de intervenção, que é a mesma o período inteiro — o que essa máquina precisaria lembrar para decidir?
Há um caminho errado mais fino em (b), e é o mais frequente de todos. O estudante aceita que a máquina de estados fixa falha e conclui que basta acrescentar estados. A concepção é de custo: ele leu um limite de princípio como um limite de orçamento. Não corrija pela afirmação; peça a ele que diga qual número de estados bastaria, e deixe a sala perceber que a pergunta não tem resposta. Depois conduza o argumento no quadro em três movimentos, nessa ordem: fixe k antes de qualquer coisa, ponha k+1 profundidades de abertura na frente da máquina, mostre que duas caem no mesmo estado. Feche com o complemento que costuma faltar: a máquina de 101 estados reconhece corretamente uma linguagem, só que outra — a dos aninhamentos até profundidade 100, que é finita no aninhamento e cai no degrau regular. Nenhuma peça dela está defeituosa; a pergunta é que era outra.
Em (c) o erro previsível é apontar a fase da árvore. A concepção é de expectativa: se a exigência é sobre o texto, a gramática deveria pegá-la. Devolva pela distância — a que distância, no arquivo, pode estar a declaração do uso? — e depois pergunte quantas produções seriam necessárias para uma gramática que só aceitasse os nomes efetivamente declarados naquele arquivo. A conta não fecha porque o conjunto de nomes muda a cada texto, e o conjunto de produções é fixo e escrito antes. Aproveite para cobrar o nome do artefato de fronteira: a árvore verificada acompanhada da tabela de nomes. Muita gente sabe descrever a coisa e não sabe nomeá-la, e nomeá-la agora economiza uma aula inteira no módulo da análise semântica.
O item (d) é o momento de instalar um hábito que vale o semestre. Quando o estudante escrever que um dos sistemas “é mais rápido”, pergunte de onde saiu o número. Não vai haver número. Use o precedente: em 1957, a equipe de John Backus, na IBM, teve de demonstrar com medida que o código produzido por máquina aguentava comparação com o escrito à mão, e o próprio Backus relatou isso em 1978, em The History of FORTRAN I, II, and III, na ACM SIGPLAN. Aquela equipe não teve o crédito de graça; o consórcio da Régua também não deveria ter.
O segundo cuidado em (d) é com uma resposta correta pela metade. Quem diz que o quarto relato veio do sistema que percorre a árvore a cada pedido está certo, e a maioria para aí. Falta a condição: a tradução antecipada só ganha vantagem sobre os defeitos que a análise consegue detectar examinando o texto parado. Um defeito que só se manifesta com certos dados de entrada escapa das duas estratégias, e quem percebe isso sozinho merece ser lido em voz alta para a turma.
Sobre a devolutiva. Uma boa resposta aqui nomeia a propriedade que falha em (a) e localiza o defeito na gramática; classifica (b) e (c) pela memória exigida, e não pelo aspecto do texto; nomeia o artefato de fronteira em (c) dizendo o que ele carrega; e fecha (d) com duas medidas concretas em vez de um adjetivo. Uma resposta parcial típica acerta a classificação de (b) pela razão certa e responde (c) com “é semântico” sem dizer o que a fase precisa ter guardado para decidir: a fragilidade é a fase confundida com a estrutura de dados que a torna possível. Devolva a essa pessoa uma tarefa de uma linha — escreva o que a tabela de nomes precisa conter para que a verificação do campo não declarado seja possível. Quem respondeu (b) na direção de acrescentar estados precisa de outra tarefa, e ela é escrita: refaça o argumento dos k estados para k = 4, com as cinco profundidades desenhadas, e diga qual par colidiu.
1.3.2 Resolução Modelo
(a) A gramática E \rightarrow E\ \text{op}\ E \mid num, com \text{op} \rightarrow +\ \mid\ *, admite duas árvores de derivação para 2 + 3 * 4.
Na primeira, o nó de raiz aplica o operador * e tem à esquerda uma subárvore que aplica o +: a soma é avaliada antes, e a cadeia é lida como (2 + 3) * 4, que dá 20. Na segunda, a raiz aplica o + e a subárvore da direita aplica o *: a cadeia é lida como 2 + (3 * 4), que dá 14. As duas árvores usam apenas produções que a gramática oferece, e por isso as duas são derivações legítimas.
A propriedade que falha é a não ambiguidade: uma gramática é ambígua quando existe ao menos uma cadeia de sua linguagem com duas ou mais árvores de derivação. O defeito mora na gramática. A cadeia é a mesma nos dois sistemas, caractere por caractere, e nenhuma das duas equipes violou a especificação que recebeu — cada uma escolheu uma das leituras que a gramática autoriza, e a especificação não continha nada que arbitrasse a escolha. Culpar uma das implementações é procurar culpado onde falta árbitro.
A alteração que admite uma só árvore por cadeia estratifica a gramática em níveis de precedência, com recursão à esquerda para fixar a associatividade:
E \rightarrow E + T \mid T \qquad T \rightarrow T * F \mid F \qquad F \rightarrow num
O conjunto de cadeias geradas permanece o mesmo, e o argumento vai nas duas direções. Nenhuma cadeia nova entra: toda cadeia derivável na gramática estratificada é uma sequência de números separados por + e *, e qualquer sequência dessas também é derivável na gramática original, que permite combinar dois E com qualquer operador. Nenhuma cadeia sai: dada uma sequência de n operadores, ela se deriva na gramática estratificada tomando o último + de cima como raiz e, na ausência de +, o último *. O que a estratificação faz é retirar árvores, deixando exatamente uma por cadeia; o conjunto de cadeias é indiferente a isso.
(b) A exigência de parênteses encaixados sem profundidade fixada de antemão é livre de contexto, e está fora do degrau regular.
A justificativa é a memória que a máquina reconhecedora precisaria ter. Para decidir se os parênteses fecham corretamente, ela precisa saber quantas aberturas continuam pendentes, e essa quantidade não tem teto: como a profundidade não é fixada, não existe número máximo de aberturas simultâneas. A memória necessária cresce com a entrada, e o acesso a ela é na ordem inversa da chegada, porque o fechamento que vem primeiro casa com a abertura mais recente. Memória de tamanho ilimitado, consultada na ordem inversa, é uma pilha, e é ela que separa o degrau livre de contexto do regular.
A máquina de estados fixa do terceiro relato funciona até certa profundidade porque, com um número fixo de estados, ela consegue distinguir uma quantidade fixa de situações. Enquanto os textos submetidos aninham menos parênteses do que o número de situações que ela distingue, cada profundidade tem seu estado próprio e as respostas saem corretas. Além desse ponto, duas profundidades diferentes passam a compartilhar o mesmo estado, e a partir daí a máquina não as separa mais.
O argumento fecha assim, e vale para qualquer máquina de estados finita. Fixe k, o número de estados, antes de qualquer coisa — ele é parte da máquina, escolhido na construção. Apresente a ela as k+1 cadeias formadas por 1, 2, …, k+1 aberturas consecutivas. São k+1 entradas e apenas k estados, de modo que duas delas, digamos com i e j aberturas, i \neq j, terminam no mesmo estado. Dali em diante a máquina responde igual às duas, porque tudo o que ela sabe é o estado em que está. Apresente então o fechamento correto para i: ela aceita, corretamente, a cadeia de i aberturas e i fechamentos, e aceita também, incorretamente, a cadeia de j aberturas e i fechamentos, que está desbalanceada.
Acrescentar estados não resolve o problema em princípio porque o argumento acima se refaz para qualquer k: escolhido um número de estados, existem k+1 profundidades que o esgotam, e a colisão volta. A ordem dos quantificadores é o ponto — para toda máquina finita existe um contraexemplo, e não o contrário. Uma máquina de 101 estados reconhece corretamente uma linguagem, só que outra: a dos aninhamentos até profundidade 100, que tem profundidade limitada e por isso é regular. Comprar mais memória troca a linguagem reconhecida; não alcança a que foi pedida.
(c) A exigência de que todo campo usado tenha sido declarado antes cai fora dos dois degraus baixos da hierarquia: ela não é regular, e também não se escreve como gramática livre de contexto do texto da Régua. Na prática, todo sistema de tradução a verifica fora da gramática, na terceira fase do diagrama — a que recebe a árvore e devolve a árvore verificada acompanhada da tabela de nomes.
O artefato que atravessa a fronteira entre a metade que analisa e a metade que sintetiza é exatamente esse par: a árvore verificada mais a tabela de nomes. Ele carrega, para cada nome que aparece no texto, o que se sabe a respeito dele — que foi declarado, em que ponto, e de que natureza é o valor que ele guarda. É esse registro que torna a verificação possível: ao encontrar o uso de um campo, a fase consulta a tabela em vez de reler o arquivo, e a ausência de entrada é a resposta. Sem a tabela, cada uso obrigaria a percorrer o texto de novo desde o começo.
A exigência não foi posta dentro da gramática porque ela liga dois pontos do texto arbitrariamente distantes, e a coincidência que precisa ser verificada é entre dois nomes que podem ser quaisquer. Uma gramática decide pela forma das produções, que são fixas e escritas antes de qualquer texto existir; para capturar a declaração prévia, ela precisaria de produções que dependessem do conjunto de nomes declarados naquele arquivo específico, e esse conjunto muda a cada texto submetido. É por isso que a condição sobre o texto que parece mais banal das quatro é a que a estrutura não alcança — a verificação sobe para uma fase que dispõe de memória associativa, e não apenas da forma.
(d) O quarto relato veio do aplicativo dos terminais de rua, que percorre a árvore a cada pedido sem produzir objeto nenhum. Cada estratégia descobre um defeito num momento diferente. O serviço central traduz o texto uma vez, e nessa passagem examina o texto inteiro, inclusive as regras que nenhum pedido alcançou ainda; um defeito detectável pela análise aparece antes de o sistema entrar em serviço. O aplicativo dos terminais só olha o trecho que a execução alcança, de modo que uma regra raramente atingida fica sem exame até que um pedido a atinja — o que aconteceu na validação de número quarenta mil, meses depois. Vale a condição, e ela é parte da resposta: a vantagem da tradução antecipada existe apenas para os defeitos que a análise consegue detectar examinando o texto parado. Um defeito que só se manifesta diante de certos dados escapa às duas estratégias com a mesma facilidade.
Quem paga essa diferença é a pessoa na fila do terminal. Ela não trabalha em nenhuma das duas equipes, não sabe que a Régua existe, e o que lhe chega é a negação de uma isenção a que tem direito, meses depois de a regra defeituosa entrar em serviço. A distância entre o erro e a consequência é o que torna o caso grave: quem decidiu a estratégia de execução não é quem sofre o efeito dela.
A especificação da Régua deveria ter registrado, ao lado da gramática, os requisitos operacionais que arbitram a escolha entre as duas estratégias: quantos pedidos são decididos por cada texto — isto é, quantas execuções por tradução —, qual o tempo aceitável para a primeira resposta depois de uma alteração de regra, e em que momento os defeitos precisam ser detectados, se antes de o texto entrar em serviço ou durante o atendimento. Com esses três registros, a escolha é uma decisão de engenharia; sem eles, é preferência de equipe.
Sobre evidência, e é onde o item fecha. Nenhuma afirmação de que um dos dois sistemas é melhor que o outro se sustenta sem medida. O consórcio precisaria medir, no mínimo, duas grandezas: o tempo de decisão por pedido nos dois sistemas, sobre o mesmo conjunto de pedidos e o mesmo texto em Régua; e a quantidade de pedidos em que os dois sistemas chegam a decisões divergentes. A primeira responde à pergunta de desempenho; a segunda responde à pergunta que importa mais, que é a de correção — dois sistemas que discordam sobre quem tem direito à isenção não se comparam por velocidade. O precedente está registrado: em 1957 a equipe de John Backus, na IBM, entregou o compilador de FORTRAN sob a suspeita generalizada de que código produzido por máquina seria lento demais para ser levado a sério, e teve de demonstrar com número que ele aguentava comparação com o escrito à mão — episódio que o próprio Backus relatou em 1978, em The History of FORTRAN I, II, and III, na ACM SIGPLAN. Implementação que se anuncia melhor sem apresentar a medida está pedindo crédito.