%%{init: {"flowchart": {"useMaxWidth": false}, "sequence": {"useMaxWidth": false}, "class": {"useMaxWidth": false}, "state": {"useMaxWidth": false}, "er": {"useMaxWidth": false}}}%%
flowchart TD
T["recorte pedido ao programa:<br/>comprimento máximo 2"]
A0["andar 0<br/>cadeias sem símbolo algum"]
A1["andar 1<br/>uma cadeia por símbolo do alfabeto"]
A2["andar 2<br/>toda emenda de dois símbolos"]
A3["andar 3 e acima<br/>o teto corta aqui"]
S["saída impressa na tela,<br/>separada por vírgulas"]
T --> A0
T --> A1
T --> A2
T -.-> A3
A0 --> S
A1 --> S
A2 --> S
1 Linguagens formais e a arquitetura de um compilador — Exercícios
Os três problemas a seguir cobram o vocabulário do capítulo e nada além dele: alfabeto, cadeia, cadeia vazia, linguagem como conjunto, as operações sobre conjuntos de cadeias, a gramática como descrição finita, o critério de memória que separa os degraus da hierarquia e a cadeia de seis fases de um tradutor. Nenhum deles pede código escrito, e todos se resolvem com papel, lápis e paciência para conferir uma conta pequena duas vezes. Resolva na ordem — o segundo usa a notação que o primeiro trata como conjunto, e o terceiro precisa dos dois.
1.1 Exercício 1: O conjunto que sai da tela com um elemento a menos
Nível Básico
Imagine um programinha que materializa linguagens como listas de cadeias, do jeito que o capítulo descreveu. Você passa a ele o alfabeto \Sigma = \{a, b, c\}, pede o fecho de Kleene \Sigma^* e, como nenhum computador guarda conjunto infinito, informa um teto: comprimento máximo 2. O programa devolve as cadeias separadas por vírgula, entre chaves, e imprime cada uma exatamente como ela é — sem nenhum tratamento especial para a cadeia de comprimento zero, aquela que o capítulo escreve \varepsilon e que não usa símbolo algum.
O diagrama abaixo mostra como o programa organiza o trabalho: um andar por comprimento, e o teto cortando o resto fora.
Um colega roda o programa, olha a tela, conta os elementos com o dedo e anuncia o total. Depois pergunta ao programa se a cadeia bca está no conjunto, recebe um “não” e conclui que bca não pertence ao fecho de Kleene do alfabeto. As duas conclusões dele estão erradas, e por razões diferentes.
O que peço de você: três respostas curtas, escritas nesta ordem. (a) Calcule quantas cadeias o fecho truncado em comprimento 2 tem sobre esse alfabeto, apresentando a soma parcela por parcela, um andar de cada vez, e diga que conta de contagem gera o tamanho de cada andar. (b) Explique em duas ou três frases por que o total que o seu colega contou na tela ficou uma unidade abaixo do valor calculado em (a), e descreva a correção de impressão que resolve o caso. (c) Escreva o que a resposta “não” do programa significa a respeito de bca e o que ela não significa — a diferença cabe em duas frases, e é ela que separa uma leitura correta da saída de uma conclusão invertida.
Eu mesmo contei errado essa tela na primeira vez, e o incômodo de conferir a soma à mão é o que faz o defeito aparecer. Você terá terminado quando conseguir apresentar o total de (a) com as parcelas visíveis, justificar a diferença de (b) sem recorrer a defeito de programação, e enunciar em (c) a distinção entre estar fora do recorte e estar fora do conjunto.
1.2 Exercício 2: A cadeia é da linguagem, a árvore não é da gramática
Nível Intermediário
Alguém precisa descrever listas de itens que podem, elas próprias, conter listas. O rascunho da gramática G tem terminais \Sigma = \{\texttt{p}, \texttt{,}, \texttt{[}, \texttt{]}\}, não terminais V = \{L, I\}, símbolo inicial L e quatro produções:
O símbolo p faz as vezes de um item qualquer, e os colchetes marcam o encaixe de uma lista dentro de outra. Quatro regras, e o conjunto que elas geram não acaba.
Um desenho chegou junto do rascunho, apresentado como a árvore de derivação de uma cadeia dessa gramática. Uma árvore de derivação, como o capítulo definiu, tem a raiz rotulada com o símbolo inicial, os nós internos rotulados com não terminais, as folhas rotuladas com terminais, e cada nó interno formando, com seus filhos na ordem em que aparecem, exatamente uma produção da gramática. Leia o desenho com essa definição na mão, porque ele tem um problema.
%%{init: {"flowchart": {"useMaxWidth": false}, "sequence": {"useMaxWidth": false}, "class": {"useMaxWidth": false}, "state": {"useMaxWidth": false}, "er": {"useMaxWidth": false}}}%%
flowchart TD
L0["L"]
L1["L"]
V[","]
I3["I"]
P2["p"]
I1["I"]
AB["#91;"]
I2["I"]
FE["#93;"]
P1["p"]
L0 --> L1
L0 --> V
L0 --> I3
I3 --> P2
L1 --> I1
I1 --> AB
I1 --> I2
I1 --> FE
I2 --> P1
O que peço de você: quatro partes, na ordem de dependência. (a) Derive a cadeia [p,p] a partir de L, escrevendo uma linha por passo e anotando ao lado a produção aplicada. (b) Determine quantas cadeias distintas de comprimento no máximo 3 a gramática gera, listando-as e justificando por que nenhuma outra cabe nesse limite. (c) Leia as folhas do diagrama da esquerda para a direita, escreva a cadeia que elas formam, aponte o único nó interno que a gramática não licencia e diga qual produção ele imita sem ser. (d) Decida se a cadeia lida em (c) pertence a L(G) e explique por que a resposta a essa pergunta é independente do defeito do desenho.
Feche relacionando os dois lados do assunto: diga que memória uma máquina precisaria ter para reconhecer L(G), apontando qual das quatro produções é a responsável por essa exigência. A pista está em qual delas pode voltar a ocorrer dentro de si mesma sem teto declarado.
Você terá terminado quando a derivação de (a) fechar sem sobrar não terminal, a lista de (b) estiver completa e defendida, o nó apontado em (c) vier com a produção verdadeira ao lado, e a sua resposta a (d) distinguir com todas as letras a pergunta “esta cadeia está no conjunto?” da pergunta “este desenho é uma derivação desta gramática?”.
1.3 Exercício 3: O nome que precisa voltar no fechamento
Nível Desafiador
Uma equipe está projetando uma linguagem pequena para arquivos de configuração, e escreveu a especificação antes de qualquer linha de código, como o capítulo recomenda. O texto se organiza em blocos. Um bloco abre com a palavra bloco seguida de um nome, contém linhas de ajuste, e fecha com a palavra fim seguida do mesmo nome. Duas decisões já estão travadas na especificação, e é a combinação delas que cria o problema. A primeira: blocos podem conter blocos, sem limite de encaixe declarado. A segunda: o nome é escolhido por quem escreve o arquivo, é uma sequência de letras e não tem comprimento máximo — rede, interfaces, interfacesdeadministracaoremota, qualquer coisa.
A equipe quer que a recusa de bloco rede ... fim disco seja obrigatória, e discute onde essa exigência mora. Uma parte do grupo quer escrevê-la nas regras da própria gramática; a outra quer aceitar qualquer nome no fechamento e conferir a igualdade depois, quando o texto já estiver organizado em árvore. O diagrama põe os dois caminhos lado a lado, com a pergunta que cada um deixa em aberto.
%%{init: {"flowchart": {"useMaxWidth": false}, "sequence": {"useMaxWidth": false}, "class": {"useMaxWidth": false}, "state": {"useMaxWidth": false}, "er": {"useMaxWidth": false}}}%%
flowchart TD
R["exigência do projeto:<br/>o fechamento repete o nome da abertura"]
C1["caminho 1<br/>exigir a igualdade dentro da gramática"]
C2["caminho 2<br/>aceitar qualquer nome na gramática<br/>e conferir a igualdade depois"]
D1["uma produção por nome possível"]
D2["a árvore chega verificada,<br/>com os nomes guardados numa tabela"]
Q1["quantos nomes o projeto admite?"]
Q2["quem ainda tem a posição<br/>em que o nome apareceu?"]
M["mensagem devolvida a quem escreveu o texto"]
R --> C1
R --> C2
C1 --> D1 --> Q1
C2 --> D2 --> Q2
Q1 -.-> M
Q2 --> M
O que peço de você: uma análise em quatro partes, escrita em prosa, cada uma apoiada no que este capítulo estabeleceu. (a) Argumente por que o encaixe sem limite já basta para pôr esse texto fora do alcance de uma máquina de memória fixa: suponha uma máquina com k estados, com k decidido antes de ela ligar, alimente-a com profundidades de abertura crescentes e mostre o que acontece quando duas profundidades distintas terminam no mesmo estado. (b) Mostre por que a proposta de exigir a igualdade dentro da gramática, escrevendo uma produção para cada nome possível, não produz uma gramática — a razão está na definição do capítulo, e é uma palavra dela. (c) Escolha um dos dois caminhos do diagrama e defenda a escolha dizendo, entre as seis fases do tradutor, qual delas confere a igualdade dos nomes, que estrutura de dados ela usa para isso, e qual das duas metades do percurso tem permissão para recusar o arquivo. (d) Descreva o que a mensagem devolvida a quem escreveu o arquivo precisa carregar além do nome divergente, diga em que fase essa informação nasce, e explique o que acontece com a mensagem se alguma das formas intermediárias do caminho deixar de carregá-la adiante.
Termine com um parágrafo de julgamento, que é o que amarra as quatro partes. Quem escreve arquivo de configuração raramente escreveu um tradutor, e uma recusa que aponta a linha errada custa a essa pessoa uma tarde de procura num lugar sem defeito nenhum. Diga, com base nas suas respostas a (c) e a (d), qual dos dois caminhos deixa a recusa mais precisa, e nomeie o preço que esse caminho cobra de quem constrói o sistema — porque ele cobra um.
Você terá terminado quando o argumento de (a) se sustentar sozinho, sem apelar a nenhum número de estados em particular; quando (b) apontar a exigência da definição que a proposta viola; quando (c) nomear fase, estrutura e metade sem hesitação; e quando o parágrafo final apresentar a escolha com o custo dela escrito ao lado, em vez de apresentá-la como a opção obviamente melhor.
Três hábitos de método valem para os três problemas acima. O primeiro: confira toda contagem em dois caminhos independentes — some os andares e depois recomponha o total por outra via; quando os dois números discordam, você achou o defeito sem precisar procurá-lo. O segundo: diante de qualquer conjunto, pergunte quantos elementos ele tem antes de perguntar quais são, porque a diferença entre nenhum elemento e um elemento invisível responde sozinha metade das confusões deste ponto do percurso. O terceiro: sempre que precisar classificar uma linguagem, troque a pergunta “isso parece difícil?” pela pergunta “o que essa máquina precisaria lembrar para decidir?” — a aparência do texto nunca respondeu a isso, e a memória exigida sempre responde.