1 Linguagens formais e a arquitetura de um compilador — resolução comentada
Documento exclusivo do professor, e gabarito de instrumento que compõe nota. Não o publique em perfil de estudante nem o distribua antes da aplicação.
As duas questões da verificação individual do módulo 01 medem coisas que costumam ser confundidas com uma só. A objetiva pede uma contagem de seis elementos, pequena o bastante para caber num canto do quadro, e ela separa quem sabe recitar a definição de fecho de quem sabe usá-la contra um caso concreto com recorte de comprimento. A dissertativa sai da teoria dos conjuntos e vai para a arquitetura: alguém propõe apagar uma fase do tradutor, com três argumentos que soam bem numa reunião, e o estudante precisa dizer por escrito o que acontece com o trabalho que aquela fase fazia.
O par cobre os dois riscos de aprendizagem do módulo, e nenhum dos dois revela o outro. Um estudante pode escrever uma página correta sobre a anatomia em fases e ainda começar o acumulador do fecho no conjunto vazio. O contrário também acontece, e é mais comum do que parece: quem acerta a contagem de cabeça pode nunca ter percebido que uma forma intermediária vale pelo que ela joga fora.
Conduza a devolutiva na ordem do arquivo. A objetiva se corrige sozinha no ambiente, e o que interessa dela chega pelo relatório de distribuição das respostas — cada um dos quatro números errados tem dono conceitual registrado no contrato do módulo, e a proporção que caiu em cada um aponta a seção que precisa voltar ao quadro. A dissertativa fica aguardando avaliação até a correção manual, contra a rubrica da Seção 1.2.3, e a nota do bloco A só fecha depois dela. São seis módulos no bloco, portanto seis respostas escritas por estudante: a régua tem de ser a mesma na primeira e na trigésima, e é por isso que ela está escrita aqui em vez de estar na sua memória.
1.1 Questão 1: ::M01E01:: — objetiva
1.1.1 O que o item pede
O cenário é a conferência à mão de uma função de fecho que a turma acabou de escrever em C++, antes de rodá-la. A linguagem de entrada tem duas cadeias sobre um alfabeto de um símbolo só, aa e aaa, e a função recebe um comprimento máximo valendo seis, porque nenhuma memória materializa um conjunto infinito. A pergunta é quantas cadeias distintas a função devolve, se estiver correta.
O comando tem três passos encadeados: recuperar o caso de baixo da potência, recuperar a definição de fecho, e compor as duas com o recorte, absorvendo as cadeias que dois caminhos diferentes produzem. A alternativa marcada com = é, ao pé da letra:
“Seis — a cadeia vazia e as cadeias de comprimento dois, três, quatro, cinco e seis.”
1.1.2 O caminho até a resposta
Com um alfabeto de um símbolo, uma cadeia é inteiramente descrita pelo seu comprimento. aaaa é a cadeia de quatro, e não existe outra de quatro. Essa simplificação torna o item resolvível no papel, e transforma uma pergunta sobre cadeias numa pergunta sobre números.
O primeiro passo é a potência zero. L^0 = \{\varepsilon\}, o conjunto que contém a cadeia vazia, e não o conjunto vazio. A cardinalidade aqui é um, não zero, e essa distinção decide a questão inteira antes que qualquer conta comece. Comprimento disponível no nível zero: o zero.
O segundo passo é a potência um, que é a própria linguagem dada: aa e aaa, comprimentos dois e três. Até aqui nada foi construído; foram apenas os dois níveis que já vieram prontos.
O terceiro passo é a potência dois, e é ele que exige atenção. A concatenação toma uma cadeia de cada lado e as cola, o que dá quatro pares: 2+2, 2+3, 3+2 e 3+3. As somas são quatro, cinco, cinco e seis. Dois pares distintos produziram a mesma cadeia de cinco símbolos, e num conjunto ela conta uma vez só. O nível dois entrega três cadeias, e a distância entre esse três e o quatro dos pares é o pedaço do item que separa a turma.
O quarto passo é a potência três. As somas menores começam em 2+2+2 = 6, que cabe no recorte e repete uma cadeia que o nível dois já tinha entregue. As outras sete combinações passam de seis e ficam de fora. O nível três, portanto, não acrescenta elemento algum ao conjunto. A partir da potência quatro o mínimo é oito, e o laço não tem mais o que fazer.
A união dos níveis, já filtrada pelo recorte, dá os comprimentos \{0, 2, 3, 4, 5, 6\}. São seis cadeias.
Existe uma conferência independente, e ela vale ir ao quadro. Como cada cadeia é uma soma de parcelas dois e três, a pergunta “que comprimentos o fecho alcança?” vira “que números se escrevem somando dois e três?”. O zero se escreve com nenhuma parcela; o um não se escreve de jeito nenhum, e é exatamente o comprimento um que falta na resposta; do dois em diante, todos se escrevem. Contando de zero a seis e removendo o um, restam seis valores. A segunda conta não usou nada da primeira e chegou ao mesmo lugar, que é o padrão de conferência que este item quer instalar.
1.1.3 Por que cada distrator atrai
Cinco — escreveu a potência zero como o conjunto vazio. É o erro E-1 do contrato do módulo, e chega com uma frase que os estudantes escrevem quase literalmente assim: “L^0 = \emptyset porque zero cópias de coisa nenhuma dá coisa nenhuma”. O argumento é razoável, e a razoabilidade dele é o que torna o engano difícil de enxergar — ninguém desconfia de uma frase que parece aritmética elementar. A consequência no papel é modesta: some um elemento da lista. A consequência no código é outra. Um acumulador iniciado no conjunto vazio aniquila tudo o que multiplica, e a função passa a devolver conjunto vazio para qualquer entrada, inclusive esta, de duas cadeias, que se confere a olho. A linha que falha não é a linha errada: o defeito mora numa inicialização de uma palavra, algumas funções acima do ponto em que o sintoma aparece.
Sete — trocou o fecho da linguagem pelo universo truncado. Sobre um alfabeto de um símbolo, as cadeias de comprimento até seis são exatamente sete: a vazia e as de um a seis. Quem responde assim leu “todas as cadeias até o comprimento seis” onde o enunciado dizia “o fecho desta linguagem”, e a troca é fácil porque o material apresenta as duas construções em seções vizinhas, ambas produzindo conjuntos infinitos que o recorte torna finitos. O fecho reúne as potências da linguagem dada, e nunca tudo o que o alfabeto permite escrever. O teste rápido para devolver em aula é a cadeia a: ela está no universo e não está no fecho, porque nenhuma soma de dois e três dá um.
Oito — contou concatenações em vez de cadeias. Este distrator faz a conta certa e para uma linha antes do fim: um do nível zero, dois do nível um, quatro pares do nível dois e um do nível três. O que ele ignora é que o resultado da concatenação é um conjunto de cadeias, e que as duas metades se fundem numa só, sem fronteira visível entre elas. Quem conta pares está tratando o resultado como se cada caminho carimbasse a própria origem no produto. É o mesmo teto que faz uma linguagem de quarenta cadeias concatenada com outra de vinte e cinco render no máximo mil, e quase sempre menos — no papel, um par que colide com outro; no código, uma inserção no conjunto que não aumenta o tamanho dele e ninguém percebe.
Nove — usou o recorte só para parar o laço. Este é o distrator de quem programou de verdade, e por isso o mais instrutivo dos quatro. O estudante escreveu a condição de parada corretamente — encerra quando o comprimento mínimo do nível ultrapassa o recorte — e esqueceu de filtrar o que cada nível produz antes de acumular. A potência três entra inteira, com quatro cadeias distintas, três delas mais longas que o limite declarado. O resultado tem os comprimentos zero, dois, três, quatro, cinco, seis, sete, oito e nove, e a função passa a devolver cadeias que ela mesma anunciou estarem fora. A confusão de fundo é entre uma cadeia que não pertence ao fecho e uma que pertence mas ficou fora do recorte materializado, e as duas exigem tratamento diferente de quem consome a saída.
1.1.4 O que o erro revela sobre o ensino
Concentração em “Cinco” é o sinal de que E-1 não foi vencido, e ele não cede a uma explicação bem-feita: retome a potência zero em três formatos na mesma semana — cardinalidade no bloco das operações, voto na primeira questão conceitual, e a inicialização do acumulador lida em voz alta no código. Concentração em “Oito” ou “Nove” pede o oposto, e pede o computador ligado: rode a função com o recorte em seis, imprima o tamanho do conjunto a cada nível e mostre o nível três somando zero elementos novos.
1.2 Questão 2: ::M01E02:: — dissertativa
1.2.1 O que o item pede
O cenário é o tradutor de uma pequena linguagem de regras em que técnicos de laboratório declaram as faixas de referência usadas na leitura dos exames. Numa revisão de arquitetura, alguém propõe suprimir a primeira fase — a que devolve a sequência de unidades classificadas — e fazer a fase que descobre a estrutura ler o texto do arquivo diretamente. A justificativa tem três partes, e todas as três são verdadeiras: há menos código para manter, há um artefato a menos atravessando fronteira, e o texto já está na memória de qualquer modo. Proposta errada defendida com três fatos corretos é o tipo de item que a reunião real produz.
O comando pede crítica com posição tomada, em oito a doze linhas, cobrindo o destino do trabalho da fase suprimida, a informação que deixa de existir, quem paga por essa perda no serviço descrito, e um fecho dizendo o que se exigiria por escrito de quem insistisse em declarar uma forma intermediária a menos.
O espelho #### do item, transcrito ao pé da letra, é o esqueleto da correção:
“A resposta esperada percorre quatro pontos, nesta ordem. Primeiro, o destino do trabalho — suprimir a forma intermediária não faz o trabalho dela desaparecer, faz o trabalho migrar. O descarte de espaços e comentários continua sendo necessário, e passa a ser responsabilidade de quem descobre a estrutura, que agora recebe texto cru e precisa tratar lixo tipográfico em cada regra que aplica, em vez de uma vez só. A resposta forte observa que a utilidade daquela forma vinha justamente do que ela jogava fora, do mesmo modo que a árvore é útil por ter jogado fora os parênteses. Segundo, a informação perdida — cada unidade classificada carrega a posição em que estava no texto, e sem ela nenhuma mensagem de erro adiante consegue dizer onde o problema mora. Terceiro, quem paga — o técnico de laboratório recebe uma recusa correta e sem lugar, e passa a procurar o defeito relendo o arquivo inteiro; num serviço em que a faixa de referência decide a leitura de um exame, o custo de uma correção adiada não recai sobre quem escreveu o tradutor, e sim sobre quem espera o resultado. A posição aceitável é a recusa da proposta, e ela precisa ser sustentada pelo mecanismo, não pela autoridade da arquitetura clássica. Quarto, o fecho — declarar uma forma intermediária a menos exige as mesmas três coisas que declarar uma a mais, e nenhuma delas é código. A definição do formato e do que ele garante a quem consome, as duas conversões escritas e testadas separadamente, e a decisão sobre o que não entra ali. Vale ainda exigir a conferência de fronteira, em que o produzido por uma fase tem de ser exatamente o consumido pela seguinte — onde houver salto, falta uma linha na arquitetura, e a lacuna reaparece muitos capítulos adiante como peça esquecida. Resposta que se limite a comparar linhas de código ou a prometer medir o desempenho antes de decidir não cumpre o comando, porque nenhuma das duas medidas alcança o argumento. O equívoco mais provável é tratar a proposta como questão de eficiência, argumentando que uma passagem a menos sobre o texto deixa o sistema mais rápido; quem tropeçar aí precisa rever, no capítulo sobre a anatomia do tradutor, a seção que lê a arquitetura como sequência de artefatos e não de rótulos, porque é ela que explica por que cada fase é testável isoladamente.”
O item admite uma posição só, a recusa da proposta, e isso é escolha declarada de projeto. A liberdade do estudante está no mecanismo com que ele sustenta a recusa e nas exigências que redige no fecho, e é ali que a rubrica mede.
1.2.2 Resposta de referência
Segue o texto esperado de uma resposta de nota máxima, na extensão declarada pelo enunciado. Ele ocupa onze linhas.
Recuso a proposta. Suprimir a primeira fase não faz o trabalho dela desaparecer; faz o trabalho migrar para quem descobre a estrutura. Descartar espaço, comentário e quebra de linha continua sendo necessário, e passa a ser condição repetida dentro de cada produção da gramática, em vez de resolvida uma vez só antes de tudo. A utilidade daquela forma vinha exatamente do que ela jogava fora, do mesmo modo que a árvore é útil por ter jogado fora os parênteses. Junto com o trabalho, some uma informação: cada unidade classificada carrega a posição em que estava no texto, e sem ela nenhuma mensagem de erro adiante consegue dizer onde o problema mora. Quem paga é o técnico de laboratório, que declara a faixa de referência e recebe de volta uma recusa correta e sem lugar; ele passa a procurar o defeito relendo o arquivo inteiro, e num serviço em que a faixa decide a leitura de um exame o custo da correção adiada não recai sobre quem escreveu o tradutor, e sim sobre quem espera o resultado. A proposta também apaga a fronteira que tornava as duas fases testáveis em separado. De quem insistisse em declarar uma forma intermediária a menos eu exigiria por escrito as mesmas três coisas que declarar uma a mais exige, e nenhuma delas é código: a definição do formato e do que ele garante a quem o consome, as duas conversões escritas e testadas separadamente, e a decisão sobre o que não entra ali. Exigiria ainda a conferência de fronteira — o produzido por uma fase tem de ser exatamente o consumido pela seguinte —, porque uma fronteira que ninguém escreveu não existe.
1.2.3 Rubrica de correção
As faixas cobram os quatro pontos na ordem do espelho, mais a posição que o comando exigiu. A evidência é sempre algo que se lê no texto do estudante, e adjetivo de impressão não decide faixa aqui. Os pesos moram na especificação de avaliação.
| Faixa | Evidência observável no texto do estudante | O que devolver |
|---|---|---|
| Satisfaz | Escreve a recusa da proposta; afirma que o trabalho da fase suprimida migra para a fase da estrutura, nomeando o descarte de espaço, comentário ou quebra de linha e observando que ele passa a ser tratado em cada produção em vez de uma vez só; nomeia a posição no texto como a informação que deixa de existir e liga essa perda à mensagem de erro que não consegue mais dizer onde o problema mora; nomeia o técnico de laboratório como quem paga, com a consequência escrita — recusa sem lugar, releitura do arquivo inteiro, resultado de exame que espera; e fecha exigindo por escrito ao menos duas das três exigências de uma forma intermediária (definição do formato e do que ele garante, as duas conversões testadas separadamente, a decisão sobre o que não entra) ou a conferência de fronteira entre o produzido e o consumido. | Apontar em qual dos quatro pontos a redação está mais firme e pedir a mesma frase, com sujeito e verbo, aplicada à fronteira que o próprio projeto do estudante ainda não escreveu. |
| Satisfaz em parte, com a lacuna nomeada | Cumpre de um a três dos pontos. Lacunas típicas, cada uma nomeada na devolutiva: recusa e sustenta a recusa só pelo descarte de espaços, sem chegar à posição perdida; nomeia a posição e não diz quem paga, deixando o cenário humano de fora; percorre os três primeiros pontos e fecha sem exigência nenhuma, ou exigindo apenas “documentação”; afirma que o trabalho desaparece em vez de migrar, e ainda assim recusa a proposta por outra razão correta; ou nomeia como pagante apenas a equipe de manutenção, sem alcançar o técnico do serviço descrito. | Nomear a lacuna com a palavra que faltou e devolver a pergunta correspondente por escrito: quem passa a descartar os espaços, e quantas vezes; que campo cada unidade carregava além do texto dela; quem, no serviço descrito, fica sem saber onde está o defeito; e o que você exigiria assinado antes de aprovar a mudança. |
| Não satisfaz | Aceita a proposta, com ou sem salvaguarda; ou trata a decisão como questão de eficiência, argumentando que uma passagem a menos sobre o texto deixa o sistema mais rápido, e para aí; ou compara linhas de código entre as duas arquiteturas como se isso decidisse; ou promete medir o desempenho antes de decidir; ou recusa a proposta apenas invocando que a arquitetura clássica tem cinco fases, sem mecanismo algum; ou descreve as fases corretamente e não toma posição sobre a proposta; ou escreve tão abaixo da extensão pedida que não há texto em que verificar ponto algum. | Devolver a seção do capítulo sobre a anatomia do tradutor que lê a arquitetura como sequência de artefatos, e pedir a reescrita respondendo a uma pergunta única: depois da supressão, quem faz o que a primeira fase fazia, e com que informação. |
1.2.4 Erros recorrentes e o que devolver
Tratar a proposta como questão de eficiência. É o equívoco que o próprio espelho antecipa, e chega bem escrito: uma passagem a menos sobre o texto, menos alocação, menos cópia. A quantidade de trabalho não caiu, porque o descarte de lixo tipográfico continua acontecendo — mudou de dono e passou a ser repetido em cada produção que se aplica. Faixa inferior quando é a espinha da resposta, faixa intermediária quando aparece como observação lateral ao lado de um argumento correto sobre a posição perdida. Devolva a pergunta que fecha o assunto: qual medição de tempo faria a posição no texto voltar a existir.
Afirmar que o trabalho desaparece. Variante mais crua da anterior, e mais fácil de diagnosticar. O estudante lê “menos código para manter” como “menos coisa a fazer”. Faixa intermediária quando o resto está lá. Devolva pedindo o desenho das três condições — espaço, comentário, quebra de linha — multiplicadas pelo número de produções da gramática, escrito no papel dele.
Descrever sem decidir. A resposta explica corretamente o que a primeira fase faz, lista as cinco fases em ordem e nunca diz o que fazer com a proposta. Faixa intermediária, com a lacuna na posição. Devolva pedindo a primeira frase do texto reescrita como decisão assinada.
Decidir sem justificar, por autoridade. Recusa em uma linha porque “todo compilador tem análise léxica”. O espelho recusa essa defesa com todas as letras: a posição precisa ser sustentada pelo mecanismo. Faixa inferior, porque uma recusa por tradição não sobrevive a quem tem uma reunião para vencer. Devolva a pergunta operacional: o que essa fase produz que a seguinte não consegue produzir sozinha.
Trocar a informação perdida por outra. O estudante diz que se perde a árvore, a tabela de nomes ou a classificação das unidades. A classificação, de fato, migra junto com o resto; o que não migra é a posição, porque ninguém a recalcula depois que o texto foi consumido. Faixa intermediária, lacuna no segundo ponto. Devolva a mensagem de erro mais honesta que um tradutor consegue dar, que nomeia a posição e diz o que era esperado ali.
Pagar a conta com o bolso errado. A resposta nomeia como pagante a equipe que mantém o tradutor, ou o próprio programador. O enunciado descreveu um serviço com gente esperando resultado de exame, e o item existe para que essa gente apareça no texto. Faixa intermediária, lacuna no terceiro ponto. Devolva o cenário: quem lê a faixa de referência, e o que acontece com o exame enquanto o arquivo é relido linha a linha.
Fechar com “mais documentação”. O fecho pedia exigências nomeadas, e recebe uma palavra guarda-chuva. Faixa intermediária. Devolva as três exigências pelo nome e peça que ele escreva a terceira aplicada ao caso: o que não entra na forma intermediária daquela linguagem de regras.
1.2.5 O que o erro revela sobre o ensino
Turma que recusa a proposta pelo argumento do desempenho leu a anatomia como sequência de rótulos, e não de artefatos com formato declarado — retome a fronteira entre a primeira e a segunda fase com medida > 70 no quadro, exibindo os quatro itens com o campo de posição preenchido ao lado de cada um, e pergunte, antes de qualquer conclusão, quem recalcularia aquele campo depois que o texto tivesse sido lido.