Autor

Afiliações

Moacyr Francischetti Corrêa, Bacharel em Ciência da Computação, Licenciado em Computação, Especialista em Ciência de Dados e Inteligência Artificial, PhD em Biotecnologia in Silico

UNIMAR - Universidade de Marília

1 Expressões regulares e linguagens regulares — 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

flowchart LR
    A["modulo anterior<br/>alfabeto, cadeia, linguagem<br/>e a hierarquia lida pela memoria"] --> B

    subgraph B["este modulo"]
        direction TB
        B1["a notacao: sintaxe indutiva,<br/>precedencia e associatividade"] --> B2["a semantica:<br/>a linguagem denotada"]
        B2 --> B3["acucar sintatico e o<br/>nucleo que sobra"]
        B3 --> B4["fechamento, equivalencia<br/>e o limite da classe"]
    end

    B --> P["modulo seguinte:<br/>a maquina que le a cadeia<br/>e responde sim ou nao"]
    P --> Q["construcao, determinizacao<br/>e minimizacao"]
    B3 -. "arvore reduzida ao nucleo" .-> P

A turma chega aqui achando que já sabe o assunto, e essa é a diferença mais importante entre este módulo e o anterior. Metade da sala já usou expressão regular num editor de texto, num campo de busca ou numa validação de formulário, e o uso prático produz uma confiança que a definição não sustenta: pergunte quanto vale o fecho aplicado à expressão que denota o conjunto vazio e você verá a confiança evaporar em silêncio. O módulo existe para trocar familiaridade por definição, e o preço de não fazer essa troca é cobrado três módulos adiante, quando a construção do autômato tiver de tratar oito casos internos em vez de três.

A decisão que organiza o roteiro é apresentar cada construção da notação junto do conjunto que ela denota, e nunca junto do que ela costuma servir para casar. Um estudante que sai daqui dizendo que a expressão reconhece a cadeia levou embora a confusão que apaga a razão de os módulos seguintes existirem: a expressão descreve um conjunto, e quem lê a entrada e responde sim ou não é uma máquina que ainda não foi construída. Corrija essa palavra todas as vezes, inclusive quando o resto da frase estiver certo.

A segunda decisão é aritmética. Este é o primeiro módulo do percurso em que uma escolha de projeto vira número no quadro, e o número é pequeno de propósito. Medir a conta barata agora é o que torna previsível a forma dela quando reaparecer, no fim do semestre, em ordens de grandeza maiores.

1.2 Objetivos, Competências e Habilidades

Objetivos de Aprendizagem. Tratar a expressão regular como objeto matemático com sintaxe e semântica próprias, e não como recurso prático de uso corrente. Ao final, o estudante deve escrever a expressão correta para uma especificação dada em prosa e decidir se duas expressões distintas denotam a mesma linguagem.

Competências a desenvolver. Especificar formalmente um conjunto de cadeias por meio de uma notação declarativa. Reduzir notação de conveniência a um núcleo mínimo de operadores, e justificar a redução. Raciocinar sobre equivalência de especificações, e não apenas sobre a correção de uma delas.

Habilidades a adquirir. Determinar a linguagem denotada por uma expressão dada, incluindo casos de borda. Aplicar as propriedades de fechamento para compor especificações sem sair da classe. Converter classes de caracteres e quantificadores em composições do núcleo.

As três listas se verificam por instrumentos diferentes, e a mais fácil de medir errado é a do meio. Escrever a expressão certa para uma prosa dada se cobra no quadro, com a turma inteira olhando o mesmo enunciado. Decidir equivalência não cabe em resposta curta, porque o estudante que responde “sim” acerta metade das vezes por sorteio — cobre-se pedindo a cadeia que separa as duas linguagens, ou a redução que faz as duas convergirem. Já a redução ao núcleo produz artefato, e se confere na tutoria contra o documento do grupo: para cada operador mantido, a tentativa escrita de reduzi-lo aos outros.

1.3 Estrutura das Aulas

1.3.1 Aula Teórica — A notação que descreve o infinito numa linha

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 é estrita nos quatro primeiros — a semântica precisa da sintaxe fechada, a redução precisa da semântica, o limite precisa da redução — e afrouxa depois, de modo que, precisando comprimir, comprima do bloco da equivalência para trás. O bloco de construção ao vivo não aceita compressão: ele é a primeira peça de código do percurso, e a tutoria da semana pressupõe que a turma já viu o analisador nascer.

Bloco de abertura — o padrão que derrubou o serviço. Comece pelo estrago, e só depois pela teoria. Em 2 de julho de 2019 a Cloudflare publicou o relatório assinado por John Graham-Cumming sobre uma interrupção causada por uma única regra nova de filtragem, e o relatório nomeia o fragmento culpado: .*.*=.*. Escreva-o no quadro e pergunte à turma o que há de errado ali. Ninguém vê nada, e é essa a resposta que interessa — o padrão está bem escrito, denota exatamente o que quem o escreveu queria, e mesmo assim derrubou o serviço.

Projete 02_retrocesso.mmd e conduza o mecanismo devagar, porque ele é a única parte do bloco que exige atenção sustentada. O motor escolhe uma extensão para o primeiro coringa, tenta casar o resto, falha, volta, escolhe outra extensão, e repete o processo inteiro a cada posição da linha. Diga o resultado sem enfeite: o custo cresce com o cubo do comprimento da linha, de modo que dobrar o tamanho da entrada multiplica o trabalho por oito.

Recue então cinquenta anos, e faça o recuo em três marcas com data. Em 15 de dezembro de 1951, Stephen Kleene escreveu o memorando RM-704 da RAND, cujo assunto declarado eram as redes de neurônios; o texto saiu em 1956 em Automata Studies, coletânea organizada por Shannon e McCarthy. Em junho de 1968, nos Bell Labs, Ken Thompson publicou nas Communications of the ACM o artigo Regular Expression Search Algorithm, aos 25 anos: um programa que lia uma expressão regular e escrevia, a partir dela, código de máquina do IBM 7094 para procurar o padrão no texto. Aquele método decide numa passada, sem retroceder. E em 1973, a pedido de Doug McIlroy, o g/re/p foi extraído de dentro do editor ed e virou programa próprio.

A terceira data é a que fecha o bloco, e vale dita com todas as letras: a técnica de 1968 circulava havia quarenta e seis anos quando o incidente aconteceu. A distância entre as duas datas foi escolha de projeto, e não indisponibilidade da técnica. Enuncie daí a frase que o módulo inteiro retoma no fechamento — a garantia é da classe; a conta é da implementação — e deixe-a escrita no quadro. Kleene comparece aqui como quem descreveu redes de neurônios; a busca em texto é uso posterior, e inverter isso inverte o episódio.

Bloco da sintaxe — o que conta como expressão. Enuncie a definição de expressão regular na forma indutiva, com as três cláusulas de base e as três de composição, e detenha-se na última linha: nada mais é expressão regular. Pergunte à turma para que serve aquela frase, porque ninguém a lê na primeira passada. Sem ela, a definição enumeraria coisas que são expressões e não impediria nada de sê-lo; com ela, todo objeto que alguém apresentar tem de exibir a sequência de aplicações que o produziu. É a mesma cláusula de fechamento que a construção do autômato, dois módulos adiante, vai percorrer ao contrário.

Passe à precedência projetando 02_precedencia.mmd, com o par que decide tudo: a|bc contra (a|b)c. Resolva os dois no quadro, dizendo qual conjunto cada um denota — o primeiro aceita a letra sozinha ou a dupla bc, o segundo exige a segunda letra em toda cadeia. A precedência escolhe qual das duas linguagens alguém escreveu, e o parêntese é o que permite escolher a outra.

Trate a associatividade pela árvore, e não por convenção escrita ao lado. Desenhe abc como concatenação de ab com c, e diga que a convenção não está registrada em lugar nenhum do sistema: ela é a forma da árvore. Feche pelo detalhe que surpreende, e que rende a primeira reação visível da semana: o grupo não sobrevive à leitura. A árvore de (ab)c e a de abc são a mesma, porque parênteses existem para o leitor humano dizer onde a precedência muda, e depois que a estrutura está construída não há o que um nó de agrupamento guardasse.

Questão conceitual — o fecho de nada. Aplique no início do bloco da semântica, no formato completo: voto individual, discussão em duplas, segundo voto, e só então o seu fechamento.

Sobre um alfabeto qualquer, quanto vale a linguagem denotada por \emptyset^*?

\emptyset, porque o fecho de um conjunto sem elementos não tem o que produzir. — Vence o primeiro voto com folga e o argumento parece impecável, o que a torna a alternativa mais útil do item. Ignora que o fecho inclui a concatenação de zero cópias, e essa concatenação existe para qualquer conjunto, inclusive para o vazio.
\{\varepsilon\}. — Correta. O fecho reúne todas as potências a partir da de expoente zero, e essa primeira potência vale sempre a linguagem cuja única cadeia é a vazia.
A linguagem de todas as cadeias do alfabeto. — Confunde o fecho aplicado ao conjunto vazio com o fecho aplicado ao alfabeto inteiro. Quem marca isto leu o asterisco como “qualquer coisa”, que é o significado que ele tem num campo de busca de arquivos e não nesta notação.
A expressão é malformada, porque não se aplica fecho ao conjunto vazio. — Aplica à notação uma restrição que a definição não faz. Peso aqui significa que a cláusula de composição foi lida como se exigisse operando não vazio, e se conserta relendo a definição no quadro.

Feche pela cardinalidade, escrita no quadro em duas linhas: a expressão que denota o conjunto vazio denota um conjunto com nenhum elemento; a que denota a cadeia vazia denota um conjunto com um elemento. Esta é a mesma confusão que o módulo anterior atacou pela potência zero, agora vestida de notação, e ela ainda vai voltar na determinização. Se (A) passar de metade no segundo voto, refaça a definição de potência antes de seguir.

Bloco da semântica — a linguagem denotada. Enuncie a definição da linguagem denotada pela mesma indução da sintaxe, cláusula a cláusula, e faça a turma notar que as operações do lado direito são exatamente as três do módulo anterior — união, concatenação e fecho sobre linguagens. A notação nova não trouxe operação nova; trouxe um jeito finito de escrever a combinação delas.

Ataque na sequência o palpite mais teimoso do módulo: o de que expressão curta denota linguagem pequena. Escreva a expressão de duas posições que denota o conjunto infinito de todas as repetições de uma letra e mande a turma listar os elementos até desistir. Tamanho do texto e tamanho da linguagem não se correspondem em direção alguma, e essa é a razão de a notação existir.

Feche fixando o que “regular” significa aqui: uma linguagem é regular quando existe uma expressão regular que a denota. A correspondência com máquinas é dos dois módulos seguintes, e anunciá-la agora como resultado já demonstrado tira da turma a única surpresa genuína do arco de autômatos. Anuncie a promessa, e guarde o teorema.

Bloco do açúcar sintático — o núcleo se define por uma recusa. Abra pela pergunta operacional: de tudo o que a notação de uso corrente oferece, o que precisa mesmo ser tratado? O critério é a impossibilidade de reduzir, e aplicá-lo deixa três operadores — concatenação, alternância e fecho — mais duas folhas, o símbolo literal e a cadeia vazia. Escreva as reduções em pares no quadro, projetando 02_reducao.mmd e 02_convergencia.mmd: a+ vira a concatenação da subexpressão com o fecho dela; x? vira a alternância entre a subexpressão e a cadeia vazia; [abc] vira a|b|c; e a faixa [a-c] vira a enumeração, que já era açúcar sobre a alternância.

Agora a conta, e ela é o centro do bloco. Escreva o padrão antes de somar, sempre, porque a turma que soma sem ver o texto na frente perde o ponto. Uma faixa de n símbolos produz n folhas e n-1 alternâncias, ou seja, 2n-1 nós. A faixa dos dez dígitos custa 19 nós. A faixa das vinte e seis letras custa 51 nós para três caracteres digitados, o que dá dezessete nós por caractere escrito. Sob fecho positivo a subárvore aparece duas vezes, mais o nó do fecho e o da concatenação: 51 + 51 + 1 + 1 = 104. Sob o opcional, a folha da cadeia vazia e a alternância: 53. Três faixas de letras concatenadas somam 3 \times 51 + 2 = 155. E o mesmo trio agrupado sob fecho positivo, escrito com 18 caracteres, chega a 312 nós.

Diga em voz alta o que a turma vai encontrar na tutoria: o padrão real de cada grupo tem separadores entre as faixas, e cada separador também é duplicado pelo fecho. A conta cresce por multiplicação, e ninguém a estima direito de cabeça.

Duas exceções acompanham a conta, e as duas se registram com a razão ao lado. O coringa é redutível — é a alternância de todos os símbolos do alfabeto —, e mesmo assim fica no núcleo como folha própria, porque a expansão produziria quase uma centena de folhas por ocorrência para dizer o que uma folha diz. A razão é de tamanho, e não de expressividade. O quantificador contado também é redutível, e por isso caberia no critério; ficou de fora da notação inteira por utilidade, já que r{50} produz cinquenta cópias da subárvore e surpreende quem escreveu o padrão.

Feche o bloco com a leitura do degrau e com a frase que a acompanha. A máquina, aqui, é a construção do autômato: ela só conhece as seis cláusulas do núcleo. O tradutor é a leitura da expressão, e é ela que paga a conveniência de quem escreve — em nós de árvore. Diga então, em voz alta e sem número novo: o que a máquina não faz, o tradutor faz por ela — e cobra em instruções. A moeda deste módulo são nós; a moeda com instruções chega no fim do percurso, e prometê-la agora é o suficiente.

Bloco do limite — o fechamento é uma cerca. Enuncie o fechamento sob as três operações e mostre por que a demonstração é imediata: dadas duas expressões, a alternância delas, a concatenação delas e o fecho de uma delas são expressões regulares por construção da própria definição. Extraia a consequência de engenharia, que é o que a turma leva embora: o analisador combina subárvores sem jamais perguntar se o resultado ainda pertence à classe, e é por isso que essa pergunta não aparece em nenhum ponto do código.

Diga também o que não decorre disso, porque a inferência errada é comum e soa razoável. A classe é fechada sob complemento e sob interseção; a notação não oferece operador para nenhum dos dois. Fechamento é propriedade da classe, e operador é decisão de projeto. A demonstração dos dois casos exige a máquina determinística completa, e ela chega no módulo da minimização — apresentá-la aqui seria cobrar da turma uma ferramenta que ela ainda não tem.

Refaça agora o argumento das casas de pombo, e diga que está refazendo, porque ele já foi feito no módulo anterior sobre outro objeto. Projete 02_cerca.mmd e conduza no quadro: fixe uma máquina com k estados escolhidos antes de ela rodar; apresente k+1 profundidades de abertura; duas delas caem no mesmo estado; apresente o fechamento correto de uma, e a máquina responde igual para a outra. O argumento se refaz para qualquer k finito, e vale dizer isso antes que alguém proponha aumentar o número. Mande a turma escrever a frase: quem só sabe em que estado está não sabe quantas vezes já entrou nele.

O remate do bloco é afirmativo, e é ele que fixa o conceito: o fechamento é uma cerca, e ela delimita por dentro. Todo o terreno cercado está disponível, a cerca não se move, e compor não a atravessa. Feche mostrando o que a cerca deixa passar, porque a turma sai daqui com a ideia oposta se você não disser: aninhamento até profundidade três é um conjunto finito de formas, conjunto finito é regular, e a expressão pode ser escrita por enumeração. O que a cerca barra é o “sem profundidade máxima”. Restringir a profundidade por escrito é decisão de projeto defensável; descobrir a restrição por acidente, três módulos adiante, é outra história.

Questão conceitual — a cerca lida como escada. Aplique logo depois do remate, no mesmo formato de voto, discussão e revoto. Ela existe porque a saída que a turma inventa sozinha é sempre a mesma.

Um grupo precisa reconhecer trechos com parênteses corretamente balanceados, sem profundidade máxima, e propõe acrescentar operadores à notação até conseguir. Que afirmação está correta?

Basta acrescentar operadores suficientes, já que a notação é extensível. — É a alternativa que mais aparece, e a que mais rende no fechamento. Lê o fechamento como escada: se compor sempre devolve algo regular, compor mais vezes alcançaria o aninhamento. Devolva a pergunta de sempre, e não a resposta — o que essa máquina precisaria lembrar para decidir?
Nenhum acréscimo à notação alcança o requisito, porque ele exige lembrar uma quantidade sem teto. — Correta. União, concatenação e fecho são exatamente as três operações que a máquina finita executa sem memória extra; compor não sai da classe, e é por isso que compor não chega ao aninhamento.
O requisito é alcançável se o grupo fixar a profundidade máxima em três níveis. — Verdadeira sobre outro requisito, e é o distrator que separa quem entendeu de quem decorou. Com profundidade fixa a linguagem é finita, e portanto regular. Quem marca isto acertou a teoria e trocou o enunciado no meio do caminho.
O requisito sai da classe porque a notação não tem operador de recursão. — Troca a causa. O que barra o requisito é a memória que a máquina teria de ter, e não o repertório da notação. Peso aqui significa que o bloco do limite não pegou, e vale refazer o argumento dos k estados.

Não apresse o fechamento. Peça a quem marcou (A) que escreva a expressão para profundidade arbitrária, e deixe a sala perceber que o texto não termina. Registre a regra de trabalho para o semestre: diante de qualquer requisito novo, pergunte o que a máquina precisaria lembrar, e nunca quantos operadores ela teria.

Bloco da equivalência — duas escritas, uma linguagem. Defina equivalência entre expressões como igualdade entre as linguagens denotadas, e insista que a relação é entre os conjuntos, e não entre os textos nem entre as estruturas construídas a partir deles. Mostre em seguida a convergência que a redução produz: a árvore de a+ e a de aa* são a mesma, a de [abc] e a de a|b|c são a mesma, e essa comparação de texto é a verificação mais barata que existe desta etapa.

Depois mostre o limite dessa verificação, com o par que a turma não esquece: as duas expressões que denotam todas as cadeias sobre dois símbolos, escritas uma como fecho da alternância e outra como fecho da concatenação de dois fechos. Denotam a mesma linguagem e produzem árvores diferentes, e o comparador responde “árvores diferentes” — a resposta certa para a pergunta que ele faz, e a errada para a pergunta que ele não faz. A equivalência plena tem resposta, e ela passa pela comparação das máquinas mínimas, que é do módulo da minimização.

Feche pelos casos em que a intuição falha, três deles, resolvidos no quadro. O fecho positivo e o fecho de Kleene sobre a mesma subexpressão denotam linguagens diferentes, porque só a segunda contém a cadeia vazia. As formas com sufixos repetidos, como a** e a+*, são redundantes e o analisador as aceita de propósito: a definição de fecho tolera ser aplicada sobre o próprio resultado, e recusar o inofensivo ensina quem escreve o padrão a desconfiar das mensagens que importam. E a expressão que denota o conjunto vazio, concatenada a qualquer outra, denota o conjunto vazio — a concatenação com nenhuma cadeia não tem par algum a formar.

Bloco de construção ao vivo — o analisador, uma função por produção. 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 — o estado ao fim do módulo anterior, com os dois pares de arquivos e o ponto de entrada próprio já compilando —, e projete a gramática do padrão antes de escrever qualquer função. São cinco produções, e a ordem em que elas se chamam é a coisa mais importante do bloco.

Escreva as funções na ordem da gramática: a alternância chama a concatenação, que chama a repetição, que chama o átomo. Verbalize enquanto digita que a precedência não está em tabela nem em comentário — quem lê o código lê a precedência, e não há duas descrições para desalinhar. Este é o erro que vale antecipar em voz alta, porque ele funciona na primeira versão: uma tabela de prioridades consultada pelo analisador produz o resultado certo até a primeira mudança de gramática, e nada acusa o desalinhamento.

Duas decisões de representação merecem ser ditas enquanto o código nasce. A primeira é que os nós vivem num vetor e se referenciam por índice, nunca por ponteiro: a árvore fica copiável sem escrever construtor de cópia, não vaza memória, e a duplicação que a redução do fecho positivo exige vira cópia de faixa de vetor. Separe o que o conceito pede do que aquele projeto decidiu, como no módulo anterior. A segunda é que a redução acontece durante a leitura: o que sai do analisador já não conhece o fecho positivo, o opcional nem a classe de símbolos, e nenhuma peça construída daqui em diante precisará aprendê-los.

Pare na duplicação e faça o erro ao vivo, porque ele é silencioso e caro. Digite primeiro a versão que compartilha o mesmo índice nas duas posições, rode e mostre a contagem de nós cair. Diga por que a queda é má notícia: dois pais apontando o mesmo índice produzem um grafo, e a construção do autômato do módulo seguinte percorreria duas vezes os mesmos estados, ligando ao mesmo trecho de máquina o que deveriam ser duas passagens distintas. Corrija clonando, rode de novo, e deixe a contagem maior no quadro.

Termine pela recusa com posição, que a turma tenta tratar como acabamento. O analisador devolve um resultado que traz a árvore ou traz o erro com a posição, sem lançar exceção e sem encerrar o programa, e é isso que permite exibir quatro expressões malformadas seguidas sem que a primeira interrompa as outras. Mostre onde o cursor cai em cada uma: no grupo não fechado ele cai no fim do texto, que é onde a falta se constata e onde alguém vai digitar o parêntese; no operador de repetição sem operando ele cai no primeiro símbolo, com a mensagem nomeando o que faltou. Depois que o analisador 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. Quem estiver com a máquina fora do ar acompanha pelo binário do marco, que já está construído e roda a demonstração inteira.

Bloco de fechamento — a expressão descreve, e ainda não reconhece. Volte ao quadro da abertura, onde .*.*=.* continua escrito, e projete 02_saldo.mmd. A turma agora tem vocabulário para dizer o que falta: existe a descrição finita do conjunto infinito, existe a árvore reduzida ao núcleo, e não existe nada que leia uma cadeia e responda sim ou não. Nomeie as três peças ausentes na ordem em que os módulos seguintes as entregam, e diga que a equivalência plena, deixada em aberto no bloco anterior, só se decide quando a última delas existir.

Feche pelas duas famílias de motor, projetando 02_motores.mmd. A família com retrocesso, representada pelo PCRE, escrito por Philip Hazel em Cambridge em 1997, aceita operadores que saem da classe e abre mão da garantia de tempo. A família sem retrocesso, representada pelo RE2, publicado pelo Google em 2010, recusa esses operadores e decide numa passada. O operador que força a escolha é a retrovisão: para conferir que um trecho já casado se repete é preciso lembrá-lo inteiro, e ele não tem tamanho limitado — de novo a memória finita. O preço tem nome e fonte: casar padrão com retrovisor é NP-completo, conforme Aho, no Handbook of Theoretical Computer Science, de 1990. Diga também quem não sai da classe, porque a turma agrupa as quatro construções por aparência: verificação adiante, captura e quantificador não guloso apenas parecem pular a cerca.

Retome a frase da abertura e encerre com ela: a garantia é da classe, e a conta é da implementação. A turma sai sabendo que escolher o motor é decisão de projeto com fatura, e é essa a pergunta que a tutoria devolve para o padrão de cada grupo.

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 da semântica e ponha o tempo liberado no bloco do açúcar sintático 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 blocos da sintaxe e da semântica 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: as peças do módulo anterior mais o analisador que entra aqui, com 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. O marco anterior continua existindo e continua rodando, e vale executar os dois em sequência uma vez: a comparação entre o que o percurso imprimia na semana passada e o que imprime agora é o retorno mais barato que a turma recebe sobre o próprio avanço.

O executável imprime três demonstrações, na ordem em que os conceitos se apoiam: os padrões lidos e reduzidos, cada um com a árvore e a contagem de nós; as quatro convergências de notação, com a resposta “mesma árvore” em todas; e as quatro expressões malformadas, cada uma com o cursor sob a posição do problema. Confira as convergências antes de rodar diante da turma, porque uma delas falhando localiza o defeito sozinha: redução aplicada num caminho do analisador e esquecida no outro.

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. O comando de aula é o que não termina sozinho; o de demonstração serve para verificar, e não para projetar.

marcos/02/build/Debug/peneira02.exe

1.3.3 Tutoria do Projeto Integrador — o tema, o núcleo e a primeira peça de código

As duas sessões desta semana fecham quatro tarefas, e a primeira delas é a decisão mais cara de desfazer do percurso inteiro: a escolha do tema. As vinte propostas não se repetem entre grupos, então organize a ordem de escolha antes de abrir a sessão, registre quem ficou com o quê e mantenha a lista visível na sala — dois grupos que descobrem tarde ter escolhido o mesmo assunto perdem os dois. Grupo que queira tema próprio, fora das vinte, responde por escrito às perguntas de decisão que fecham a lista, e só com elas respondidas o tema entra.

O apoio começa a recuar aqui. Na semana passada você projetava o documento pronto e conferia entrada por entrada; nesta, a estrutura continua oferecida — as sete seções da especificação vêm escritas na própria tarefa, cada uma com a pergunta que responde e o sinal de que saiu errada —, e a conferência passa a ser por amostragem dirigida: você escolhe duas seções por grupo e cobra as duas a fundo. Anuncie a mudança numa frase, porque redução silenciosa é lida como descaso.

Primeira sessão — o tema e a especificação. Abra projetando a especificação do projeto de referência, a Peneira, e leia em voz alta a sexta seção, a que diz o que fica gravado quando o tradutor termina e quem lê aquilo depois. Ali está a decisão de maior alcance do documento inteiro: o tradutor grava um objeto e encerra, e outro componente lê esse objeto e o executa depois, sobre outra entrada, com o tradutor já fora do ar. É essa decisão que faz a teoria de autômatos aparecer duas vezes no artefato — uma como estrutura interna do reconhecedor, outra como o próprio conteúdo do objeto gravado. Interpretar a árvore direto seria mais curto e apagaria metade do percurso.

Mostre em seguida a quinta seção, a da verificação prévia, porque é a que os grupos escrevem com uma frase e deveriam escrever com quatro. Nomear as naturezas de valor da linguagem obriga a decidir uma assimetria: na Peneira, um trecho casado da entrada vale onde se espera texto e não vale onde se espera número, e ler o número escrito num trecho é pedido explícito. A alternativa era deixar o sistema adivinhar pela forma do que está escrito, e ela foi descartada por ser a maneira mais confiável de produzir o resultado errado sem ninguém perceber. Peça a cada grupo a mesma decisão, no domínio dele, com a alternativa recusada ao lado.

Cobre a seção do aninhamento com o exemplo de três níveis exigido, e cobre também o que a referência acrescentou por conta própria: o pedido que a Peneira não vai atender, que é encontrar trechos de parênteses balanceados. Sem essa linha escrita agora, a impossibilidade demonstrada no módulo do lema do bombeamento chega ao grupo como assunto novo, em vez de resposta a um limite que ele mesmo registrou. Aceite qualquer análogo, desde que venha com a razão junto.

A pergunta que desmonta a especificação em segundos, e que você faz em todas, inclusive nas impecáveis: mostre onde está escrito o que fica gravado quando o tradutor termina, e quem lê aquilo depois. A especificação que descreve um sistema executando direto passa numa leitura apressada, porque cobre reconhecimento, estrutura e verificação com competência. A resposta que denuncia é “o sistema mostra o resultado”. A lacuna só aparece no arco de geração de código, quando já existe código construído sobre ela.

Circule com uma segunda pergunta, repetida grupo a grupo: quantas construções diferentes existem nos seus exemplos? Três amostras que são o mesmo exemplo com nomes trocados passam despercebidas na leitura entusiasmada da própria proposta, que é a única leitura que a especificação recebe antes do código começar. Os quatro exemplos da referência sobem em degraus, e a progressão vira a ordem de construção dos capítulos seguintes: só padrão e emissão; dois padrões competindo pela mesma posição; a condição; a condição composta. Ninguém sai da primeira sessão sem as sete seções existindo, ainda que curtas.

Segunda sessão — o núcleo, e a conta que ele evita. Abra pela leitura de decisão, que é o que separa esta tarefa de uma escolha de gosto: redutibilidade decide o que pode sair do núcleo; tamanho e utilidade decidem o que convém que saia. São dois filtros e eles dão respostas diferentes — o coringa é redutível e fica, por razão de tamanho; o quantificador contado é redutível e sai, por razão de utilidade. Exija a decisão registrada em pares, com a notação de partida à esquerda e a expressão equivalente no núcleo à direita, e aplique a verificação operacional a cada operador mantido: peça a redução dele usando os outros, por escrito. Quem conseguir escrevê-la acabou de descobrir que aquele operador não pertence ao núcleo.

Agora ponha a conta na mesa, com o número da referência. O padrão de endereço escrito na especificação da Peneira tem 21 símbolos e produz 318 nós — três faixas de vinte e seis letras, cada uma expandida em alternâncias, todas duplicadas pelo fecho positivo, mais os separadores que também são duplicados. Mais de quinze vezes o tamanho do texto, e nada de errado aconteceu. Devolva a conta imediatamente como tarefa: cada grupo estima os nós do próprio padrão mais longo antes de haver código que os conte, escreve o palpite no diário, e mede depois que o analisador rodar. A distância entre o palpite e a medida é o conteúdo do exercício, e ela costuma ser grande.

O número medido entra no diário como a primeira medida do percurso. Diga em voz alta que ele volta, em ordens de grandeza maiores, quando a moeda deixar de ser nó de árvore — e não abra a discussão de como se responde a essa conta, que é assunto do último módulo.

A segunda metade da sessão é código: o analisador recursivo-descendente, uma função por produção, com a precedência na ordem das chamadas e nunca numa tabela. Três exigências valem a insistência, porque as três cobram caro se forem adiadas. A redução acontece durante a leitura, de modo que o que sai do analisador já não conhece fecho positivo, opcional nem classe de símbolos. Os nós vivem num vetor e se referenciam por índice, o que faz da clonagem de subárvore uma cópia de faixa. E a duplicação exigida pelo fecho positivo clona: compartilhar o mesmo índice nas duas posições produz um grafo, e a construção do autômato do módulo seguinte passaria duas vezes pelos mesmos estados, gerando máquina errada. O sintoma é a contagem de nós menor do que a esperada, e é por isso que o palpite escrito antes vale ouro.

A quarta tarefa fecha a sessão, e os grupos vão querer deixá-la para o fim. Não deixe. O resultado devolvido pelo analisador traz a árvore ou traz o erro com a posição, e essa forma é o que permitirá, adiante, que um padrão defeituoso não derrube a compilação do programa inteiro. Cobre a mensagem do grupo não fechado em toda revisão: o cursor tem de cair no fim do texto, que é onde a falta se constata, e não no parêntese que abriu. Cobre também a decisão registrada — a Peneira guarda o primeiro erro do padrão e ignora os seguintes, para não produzir cascata, enquanto o compilador da linguagem relata todos de uma vez. São decisões diferentes, em lugares diferentes, e o grupo precisa saber distinguir as duas antes de copiar uma delas para o lugar errado.

Programação em pares, com a gramática na mão do navegador. Um integrante digita a função da produção enquanto o outro acompanha pela gramática impressa, conferindo se a ordem das chamadas ainda reflete a precedência. Os papéis giram a cada produção concluída, o que dá cinco trocas por sessão e dispensa cronômetro. Grupos maiores se dividem em pares simultâneos sobre produções distintas; o integrante ímpar entra no rodízio de um par existente e nunca abre frente própria. Anuncie o revezamento você mesmo duas ou três vezes: nenhum grupo troca de piloto sozinho antes do terceiro módulo. O sintoma a caçar é o teclado que não muda de dono, e a intervenção não é repreensão — pergunte a quem está de fora qual produção chama qual, e a resposta separa quem participa de quem assiste.

O que vai aparecer, e o que fazer com cada caso. O primeiro é o grupo que trata todos os operadores diretamente. O sintoma é observável: o código cresce um caso por operador e o analisador nunca fecha. Devolva a pergunta e não a solução — quantos casos o seu tratamento precisa distinguir, e quantos precisaria se você reduzisse antes?

O segundo é o grupo que põe a precedência numa tabela de prioridades, e ele merece cuidado porque a versão dele funciona. Mostre o desalinhamento na prática: peça uma mudança pequena na gramática e deixe que o grupo descubra que nada acusou a divergência entre as duas descrições.

O terceiro é o grupo que reporta a posição em que o analisador está, e não aquela em que o problema é. As duas coincidem quase sempre, e o caso-teste que as separa é o grupo não fechado. Peça sempre essa mensagem primeiro.

O quarto é o grupo que compartilha a subárvore “para economizar memória”. Ele acha que otimizou. Peça a contagem de nós antes e depois, e depois pergunte o que acontece quando algo percorrer aquela estrutura a partir da raiz.

O quinto é o grupo que decalca a Peneira trocando os nomes, e ele se identifica sem esforço: a especificação 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 sexto é o grupo que escolheu um tema ambicioso prometendo restringir depois. Não discuta a ambição; peça os exemplos completos agora, nesse domínio. Os exemplos denunciam o tamanho sozinhos, e restrição que o grupo se impõe dura mais do que a imposta por você.

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 — e, nesta semana, também o palpite e a medida da contagem de nós. A especificação 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: um recorte que orfana geração de código, descoberto no módulo treze, não se conserta, porque o que existe foi construído sobre a lacuna.

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. Repita isso à turma antes do primeiro voto, mesmo tendo dito na semana passada: a sala silencia quando suspeita que está sendo medida, e o valor de votar está em errar cedo. Um erro sobre o fecho do conjunto vazio corrigido nesta semana custa uma frase; o mesmo erro descoberto na determinização custa uma tarde.

O que compõe nota. Ao fim do módulo o grupo entrega a especificação completa do sistema que vai construir, o registro do núcleo escolhido com as reduções em pares, e a primeira peça de código com a recusa posicionada funcionando. 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 continua dentro do 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.

Não crie instrumento com nota para este módulo. A tentação aqui vem do lado oposto à do módulo anterior: como agora há código rodando, parece natural atribuir nota ao que o analisador faz. Os dois itens da verificação individual já medem a teoria desta semana, sem consulta e sem ferramenta de geração automática de texto, e a rubrica do projeto foi publicada junto com a proposta, sem ajuste módulo a módulo. Multiplicar entregas avaliadas é a sobrecarga que esta disciplina evita de propósito.

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 a semântica ter sido tratada. Liberado antes, o estudante responde os itens de sintaxe por reconhecimento de símbolo — ele já viu asterisco e colchete em editor de texto — e conclui que o módulo é revisão, que é precisamente a conclusão que esta semana existe para desmontar.

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 potência zero que não fechou, e se resolve pela cardinalidade escrita no quadro; peso em (C) na primeira é o asterisco lido como “qualquer coisa”, e se resolve exibindo o conjunto denotado elemento a elemento; peso em (A) na segunda é a cerca lida como escada, e essa não cede a explicação — cede ao pedido de escrever a expressão para profundidade arbitrária, feito 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 grupo que trata todos os operadores de conveniência diretamente, em vez de reduzi-los. O sintoma é observável e aparece antes da queixa: o código cresce um caso por operador da notação e o analisador nunca fecha. Intervenha por pergunta, e não por solução — quantos casos o seu tratamento precisa distinguir, e quantos precisaria se você reduzisse antes? A conta certa é a dos quatro módulos seguintes, em que cada operador do núcleo vira um caso a mais na construção da máquina, na determinização e na tradução.

Os dois filtros que dão respostas diferentes. Redutibilidade decide o que pode sair do núcleo; tamanho e utilidade decidem o que convém que saia. O estudante que ouve só o primeiro filtro conclui que o núcleo é questão de gosto, e o que ouve só o segundo mantém no núcleo o que deveria reduzir. As duas exceções do módulo são o par que resolve isso, e vale exibi-las lado a lado: o coringa é redutível e fica, por razão de tamanho escrita ao lado; o quantificador contado é redutível e sai, por razão de utilidade.

A palavra que precisa ser corrigida todas as vezes. “A expressão reconhece a cadeia.” Ela denota um conjunto; quem reconhece é a máquina, e a máquina é dos módulos seguintes. Corrija sempre na mesma forma, inclusive quando o resto da frase estiver certo, porque a confusão apaga a razão de existirem três módulos de construção de autômato — se a expressão já reconhecesse, não haveria o que construir.

A confusão que atravessa o período, na sua segunda forma. A expressão que denota o conjunto vazio e a que denota a cadeia vazia são objetos distintos, e denotam conjuntos de cardinalidade zero e um. Ela reapareceu aqui vestida de notação, e vai reaparecer na construção do autômato e na determinização. Ataque-a duas vezes nesta semana, em formatos diferentes: pela questão conceitual e pelo código, mostrando o que a árvore da expressão do opcional guarda na folha.

A digressão previsível. Alguém perguntará por que não usar a biblioteca de expressões regulares que a linguagem já traz. Responda inteiro, uma vez só, e não volte ao assunto: o que o percurso constrói é o motor, e a biblioteca é justamente a caixa cujo interior é o conteúdo dos próximos cinco módulos. Some o argumento técnico, que encerra a pergunta melhor que o pedagógico — a biblioteca da linguagem pertence à família com retrocesso, e o objeto que este projeto vai gravar é uma máquina determinística que decide numa passada.

O erro que reaparece na correção da tutoria. O grupo reporta a posição em que o analisador está, e não aquela em que o problema é. As duas coincidem na maioria dos casos e divergem exatamente nos que confundem, e o caso-teste é sempre o mesmo: o grupo não fechado. Peça a mensagem de erro desse caso em toda revisão, antes de olhar qualquer outra parte do código.

Se o tempo apertar. Aceita compressão o bloco da equivalência, desde que a ressalva sobre a verificação estrutural sobreviva — sem ela, a turma conclui adiante que o comparador falhou, quando ele nunca prometeu decidir aquilo. Aceita compressão o bloco de fechamento, preservando as duas famílias de motor e a retrovisão, que são o que fecha o gancho da abertura. Não aceita compressão o bloco do açúcar sintático: sem a conta feita no quadro, a redução ao núcleo vira preferência estética, e o grupo que a lê assim mantém oito casos internos até descobrir o preço com código escrito por cima.

Reuso

CC BY-NC-ND 4.0