flowchart LR
R["ε<br/>comprimento 0"] --> Z["0"]
R --> U["1"]
Z --> Z0["00"]
Z --> Z1["01"]
U --> U0["10"]
U --> U1["11"]
Z0 --> A1["000"]
Z0 --> A2["001"]
Z1 --> A3["010"]
Z1 --> A4["011"]
U0 --> A5["100"]
U0 --> A6["101"]
U1 --> A7["110"]
U1 --> A8["111"]
1 Linguagens formais e a arquitetura de um compilador — Exercícios
Três pessoas leem o mesmo parágrafo de um manual e escrevem três programas que discordam sobre um texto de quatro caracteres. Nenhuma das três leu errado: o parágrafo admitia as três leituras, e ninguém percebeu porque o exemplo que acompanhava o manual passava em todas. Enquanto a descrição de uma linguagem for prosa, o desacordo entre implementações não tem árbitro, e a discussão termina em quem fala mais alto ou em quem escreveu primeiro.
Os três problemas a seguir atacam essa situação por caminhos que não se parecem. O primeiro é uma contagem que cresce mais depressa do que a intuição admite, e é ela que decide se uma estratégia de verificação cabe no mundo. O segundo põe duas descrições do mesmo conjunto lado a lado, mede as duas em bytes e depois muda uma vírgula da especificação para ver qual das duas sobrevive. O terceiro é um desacordo entre dois sistemas construídos a partir do mesmo manual em prosa, e nele o preço do desacordo recai sobre quem nem sabe que a notação existe.
Tenha papel ao lado. Dois dos três giram em torno de um número, e conta feita de cabeça neste terreno costuma sair com um caso de borda a menos — justamente aquele de que a resposta dependia. Escreva os conjuntos por extenso, mesmo quando parecerem óbvios demais para merecer a tinta.
Os três cobram duas coisas. A primeira é o vocabulário formal, que serve para dizer com exatidão o que uma coisa é, em vez de dizer com o que ela se parece. A segunda é o mapa do sistema: onde cada verificação cabe, e o que atravessa a fronteira entre uma fase e a seguinte. Nenhum deles pede código, e nenhum se resolve reconhecendo uma frase já lida. Sempre que se pegar classificando pela aparência do texto, pare e refaça a pergunta pela memória que a máquina precisaria ter.
Vale saber de onde veio o instrumento que você vai usar no terceiro problema. 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. As quatro classes saíram de restrições na forma das regras; a correspondência com máquinas veio depois, e a computação herdou o resultado sem ter encomendado.
1.1 Exercício 1: contar antes de listar
Nível básico
Um sensor de ocupação grava, a cada minuto, um único símbolo: 0 se o corredor estava livre, 1 se estava ocupado. Uma janela de observação é, portanto, uma sequência finita desses dois símbolos, e você foi encarregado de verificar o programa que decide quais janelas disparam alarme. Alguém sugeriu a estratégia mais confortável possível: submeter o programa a todas as janelas existentes, uma por uma, e conferir cada resposta. A sugestão é excelente enquanto a janela for curta, e morre pouco depois. Descobrir onde exatamente ela morre é uma conta, e a conta cabe nesta página.
O diagrama mostra os quatro primeiros andares do universo de janelas sobre esse alfabeto. Cada nó é uma cadeia, e cada seta acrescenta um símbolo à direita da cadeia de onde partiu. Leia-o antes de escrever qualquer coisa, e repare no andar de cima: ele existe, tem exatamente um habitante, e é o que quase todo mundo esquece de contar.
Antes de começar, fixe a distinção que derruba mais gente neste ponto do percurso. A cadeia vazia, escrita \varepsilon, é a sequência de comprimento zero — ela não é o espaço em branco e não ocupa posição alguma. A linguagem vazia, escrita \emptyset, é o conjunto que não contém cadeia nenhuma. Uma é elemento; a outra é conjunto. Trocar uma pela outra produz erro sem mensagem, e o erro aparece três funções acima do ponto em que foi cometido.
O que peço de você: três respostas curtas, cada uma acompanhada da razão que a sustenta. Em (a), escreva por extenso, lendo do diagrama, os conjuntos \Sigma^0, \Sigma^1, \Sigma^2 e \Sigma^3 para \Sigma = \{0, 1\}. Confirme a cardinalidade de \Sigma^3 pela fórmula |\Sigma|^n e calcule quantas janelas existem com comprimento até 3, somando os quatro andares. Escreva em seguida a fórmula geral dessa soma para comprimento até n, avalie-a em n = 20 e feche a letra dizendo em que ordem de grandeza a verificação exaustiva deixa de caber num tempo razoável.
Em (b), tome a linguagem A = \{0,\ 01\} e calcule três resultados: A\emptyset, A\{\varepsilon\} e A^0. A concatenação de linguagens toma todos os pares possíveis e justapõe cada um, isto é, LM = \{\, uv : u \in L,\ v \in M \,\}. Dê a cardinalidade de cada um dos três resultados. Justifique os dois primeiros pela correspondência com o zero e com o um da multiplicação, e explique, em uma frase, o que aconteceria com a saída de um programa que escrevesse A^0 como \emptyset.
Em (c), liste todos os prefixos da cadeia 011. São mais do que parece: a cadeia é prefixo de si mesma, e a cadeia vazia é prefixo de todas. Suponha agora que o programa leia da esquerda para a direita, um símbolo por vez, sem voltar atrás. Diga, em duas ou três frases, o que ele já sabe e o que ele ainda não sabe no instante em que acabou de ler 01.
Você terá terminado quando conseguir explicar, sem consultar o capítulo, por que os dois primeiros resultados de (b) diferem entre si sem que nenhum dos dois seja contradição. O segundo sinal é a fórmula de (a): ela precisa responder à pergunta do comprimento máximo por conta, e não por impressão.
1.2 Exercício 2: o que cabe na memória, o conjunto ou o critério
Nível intermediário
Um robô de armazém registra o trajeto que percorreu como uma sequência de rumos, sobre o alfabeto de três símbolos \Sigma = \{E, D, F\} — esquerda, direita e frente. A especificação atual admite exatamente seis rumos por trajeto, nem mais nem menos. Dois arquivos chegaram à sua mesa afirmando descrever o mesmo conjunto de trajetos válidos. O primeiro é uma lista, com um trajeto por linha. O segundo cabe em duas linhas, escritas na notação abreviada que os manuais usam:
T ::= R\ R\ R\ R\ R\ R \qquad\qquad R ::= E \mid D \mid F
A barra vertical é abreviação, e só. Ela junta numa linha as produções que têm o mesmo lado esquerdo, e se desfaz mecanicamente antes de qualquer analisador rodar. Guarde essa afirmação: uma das letras abaixo pede que você a defenda.
flowchart TB
subgraph I["Descrição I — o conjunto escrito por extenso"]
direction TB
LI["arquivo com uma cadeia por linha"] --> P1["pertence?<br/>procurar a cadeia na lista"]
LI --> N1["não pertence?<br/>chegar ao fim da lista sem achar"]
end
subgraph II["Descrição II — um critério de tamanho fixo"]
direction TB
GR["quatro produções e um símbolo inicial"] --> P2["pertence?<br/>exibir uma derivação"]
GR --> N2["não pertence?<br/>examinar quais derivações"]
end
I -.->|"mesmo conjunto de cadeias"| II
O diagrama separa, para cada descrição, a pergunta “esta cadeia pertence?” da pergunta “esta cadeia não pertence?”. A caixa do lado da gramática ficou pela metade de propósito. Completá-la é parte do que peço.
O que peço de você: quatro respostas, nesta ordem. Em (a), meça as duas descrições. Calcule quantos trajetos existem com comprimento exatamente 6 sobre um alfabeto de três símbolos e, supondo que cada linha do arquivo ocupe 7 bytes — seis rumos mais o fim de linha —, dê o tamanho da lista. Refaça a conta supondo que a especificação passe a exigir trajetos de exatamente 20 rumos, com 21 bytes por linha, e diga por quanto o arquivo foi multiplicado. Diga então quanto cresceu a segunda descrição sob a mesma alteração, contando os caracteres que precisariam ser digitados nela.
Em (b), desfaça a abreviação. Reescreva a gramática usando apenas produções com um lado esquerdo e um lado direito, sem barra vertical, e conte quantas produções restaram. Confira o total contra o número que o diagrama declara para a segunda descrição, e diga por que duas linhas de texto e esse total podem descrever a mesma coisa. Argumente em seguida por que a linguagem gerada é a mesma antes e depois dessa reescrita, e por que uma notação de abreviação não pode ampliar o alcance de uma gramática. Feche a letra dizendo o que decide esse alcance, já que o tamanho do documento não decide.
Em (c), mude a especificação. O armazém passa a admitir trajetos de um ou mais rumos, sem teto de comprimento, e a segunda descrição registra isso como T ::= R\ \{\,R\,\}, em que o par de chaves marca o que se repete zero ou mais vezes. Reescreva também essa abreviação em produções simples, introduzindo o não terminal auxiliar de que ela precisa, e exiba a derivação completa de EDF a partir do símbolo inicial, uma linha por passo. Aponte a produção exata de onde vem o infinito e explique por quê. Diga, por fim, o que acontece com a primeira descrição sob essa mesma alteração.
Em (d), volte ao diagrama e complete a caixa que ficou pela metade. Para demonstrar que uma cadeia pertence ao conjunto gerado por uma gramática, basta exibir uma derivação, como você fez em (c). Descreva o que seria preciso examinar para demonstrar que ela não pertence, e diga por que essa segunda tarefa não é simétrica da primeira. Amarre então as três letras anteriores. As descrições finitas se enfileiram por comprimento — primeiro as de comprimento 1, depois as de 2 —, e toda gramática que alguém venha a escrever tem posição marcada nessa fila. As linguagens, que são os subconjuntos de \Sigma^*, não se enfileiram. Diga o que essa comparação obriga a concluir sobre a fatia de linguagens que um sistema de tradução consegue tratar, e por que a conclusão é um resultado demonstrado, e não uma dificuldade à espera de alguém mais esperto.
Você terá terminado quando puder defender, com os números de (a) na mão, que guardar o critério sobrevive à alteração de (c) enquanto guardar o conjunto não sobrevive. Falta então um passo: diga, em uma frase, que informação sobre o conjunto precisa ser conhecida antes de escolher entre as duas descrições.
1.3 Exercício 3: quatro relatos, e nenhuma gramática
Nível desafiador
Este problema leva o capítulo inteiro para um cenário que ele não tratou, e o cenário está descrito por completo aqui: você não precisa de nada além deste enunciado e do conteúdo do capítulo. Um consórcio de transporte urbano mantém uma notação pequena chamada Régua, na qual se escrevem as regras que concedem isenção de tarifa. Um texto em Régua começa declarando os campos do pedido, um por linha — idade, renda mensal, tempo de residência —, e segue com as regras, cada uma comparando expressões numéricas e combinando comparações com parênteses, sem profundidade fixada de antemão.
A Régua nunca teve gramática escrita. O que existe é um manual em português, com a autoridade de qualquer texto em prosa: a de quem o leu por último. Duas equipes construíram, cada uma a partir dele, um sistema que lê a Régua. O serviço central traduz o texto uma vez e guarda o objeto produzido; o aplicativo dos terminais de rua percorre a árvore a cada pedido, sem produzir objeto nenhum. Quem paga a diferença entre os dois não trabalha em nenhuma das equipes: é a pessoa na fila do terminal, a quem uma regra mal lida nega a isenção a que tem direito.
Quatro relatos chegaram, e nenhum deles vem com a fase responsável identificada.
flowchart TB
T["texto escrito em Régua"] --> F1["fase 1<br/>caracteres → símbolos classificados"]
F1 --> F2["fase 2<br/>símbolos → árvore"]
F2 --> F3["fase 3<br/>árvore → árvore verificada<br/>e tabela de nomes"]
F3 --> F4["fase 4<br/>árvore verificada → objeto"]
F4 --> EX["execução sobre os dados de cada pedido"]
R1["relato 1<br/>20 contra 14"] -.-> Q["que fase responde<br/>por cada relato?"]
R2["relato 2<br/>campo nunca declarado"] -.-> Q
R3["relato 3<br/>trava além de certa profundidade"] -.-> Q
R4["relato 4<br/>defeito visto na validação 40.000"] -.-> Q
No primeiro relato, o trecho 2 + 3 * 4 — o mesmo trecho, caractere por caractere, nos dois sistemas — leva um deles a 20 e o outro a 14. No segundo, um texto usa um campo que não aparece na parte declarativa do arquivo; um sistema o admite e o outro o recusa. No terceiro, um texto com condições encaixadas passa por um sistema e trava no outro a partir de certa profundidade de parênteses, e a equipe responsável explica que o seu reconhecedor foi escrito como uma máquina de estados fixa. No quarto, um defeito numa regra raramente alcançada só apareceu na validação de número quarenta mil, meses depois de a regra entrar em serviço.
Para o primeiro relato, alguém finalmente escreveu no papel a gramática que o manual descrevia em prosa. Saiu E \rightarrow E\ \text{op}\ E \mid num, com \text{op} \rightarrow +\ \mid\ *. Guarde essa gramática: ela é o ponto de partida da primeira resposta.
O que peço de você: quatro respostas, cada uma com a justificativa explícita. Em (a), desenhe as duas árvores de derivação que essa gramática admite para 2 + 3 * 4, mostre qual delas conduz a 20 e qual conduz a 14, e nomeie a propriedade da gramática que falha. Diga onde mora o defeito: na cadeia, na gramática ou nas implementações. Proponha então uma alteração na gramática que admita uma só árvore por cadeia, e argumente por que o conjunto de cadeias gerado permanece o mesmo depois dela.
Em (b), classifique na hierarquia a exigência de parênteses encaixados sem profundidade fixada, justificando pela memória que a máquina reconhecedora precisaria ter. Explique por que a máquina de estados fixa do terceiro relato funciona até certa profundidade e falha além dela. Feche o item com o argumento dos k estados diante de infinitas profundidades de abertura, e diga por que acrescentar estados não resolve o problema em princípio, e não apenas por que ficaria caro. Se a sua resposta puder ser satisfeita comprando mais memória, ela ainda não é a resposta.
Em (c), classifique a exigência de que todo campo usado tenha sido declarado antes, e indique em qual das quatro fases do diagrama ela é verificada. Nomeie o artefato que atravessa a fronteira entre a metade que analisa e a metade que sintetiza, e diga o que ele carrega para tornar essa verificação possível. Explique também por que a exigência não foi posta dentro da gramática, já que ela é uma condição sobre o texto como qualquer outra.
Em (d), trate o quarto relato. Diga qual dos dois sistemas o produziu e por quê, ligando a resposta ao momento em que cada estratégia de execução descobre um defeito. Argumente em seguida quem paga essa diferença no cenário descrito, e o que a especificação da Régua deveria ter registrado para que a escolha entre as duas estratégias fosse decidida por critério. Conclua com uma frase sobre evidência: em 1957, a equipe de John Backus, na IBM, teve de demonstrar com número que o código produzido por máquina aguentava comparação com o escrito à mão, episódio que ele mesmo relatou em 1978. Nomeie o número que o consórcio precisaria medir para sustentar qualquer afirmação de que um dos dois sistemas é melhor que o outro.
Você terá terminado quando as quatro respostas puderem ser lidas como um argumento único. A classificação de (b) e de (c) determina em que fase cada exigência é verificada; o artefato de (c) é o que carrega a verificação adiante; a letra (a) explica por que a descrição escrita precede qualquer discussão sobre qual sistema está certo; e a letra (d) explica por que a discussão não termina na descrição.
Um método que funciona nos três, e que eu uso quando o problema resiste. Comece traduzindo o enunciado em objetos: conjunto, cadeia, produção, derivação, árvore, artefato, máquina. Enquanto o problema estiver descrito em prosa, a intuição opina; descrito em objetos, ele passa a ter resposta que outra pessoa consegue conferir.
Depois, a cada afirmação que for escrever sobre classe, pergunte o que a máquina precisaria lembrar para sustentá-la. Quem só sabe em que estado está não sabe quantas vezes já entrou nele. É esse o critério que separa os degraus — nunca o tamanho do texto, a estranheza da notação ou a profundidade aparente dos parênteses.
Por último, desconfie de toda resposta que você der sem fazer conta alguma nos dois primeiros problemas. Ambos foram construídos em torno de um número, e o número é o que impede a discussão de virar troca de impressões. No terceiro, o mesmo vale para a última letra.