flowchart LR
ESP["especificação<br/>escrita por gente"]
ER["expressão regular<br/>GERADOR<br/>diz como produzir as cadeias"]
AFD["autômato finito<br/>RECONHECEDOR<br/>diz se a cadeia pertence"]
EXEC["execução sobre a entrada<br/>um passo por símbolo"]
ESP --> ER
ER -->|"tradução automática<br/>teorema de Kleene"| AFD
AFD --> EXEC
ER -.->|"curta, legível,<br/>não se executa"| ER
AFD -.->|"volumosa, ilegível,<br/>trivial de executar"| AFD
1 Módulo 03: Autômatos Finitos Determinísticos
Bem-vindo ao módulo em que a teoria começa a rodar. Até agora nós descrevemos linguagens; a partir daqui nós as decidimos. Ao fim desta leitura você deve conseguir ler uma descrição em português de um conjunto de cadeias, desenhar sem tentativa e erro a máquina que o reconhece, e traduzir esse desenho em estrutura de dados sem perder nada no caminho.
1.1 O problema: descrever não é decidir
Vamos por partes, começando por um incômodo que eu deixei propositalmente sem solução no módulo anterior. Nós tínhamos linguagens definidas como conjuntos de cadeias, operações para combiná-las e uma notação finita — as expressões regulares — capaz de descrever conjuntos infinitos. Faltava o essencial: responder à pergunta que qualquer compilador faz milhares de vezes por segundo. Esta cadeia pertence a esta linguagem? Tudo o que sabíamos fazer era gerar cadeias e comparar, e isso não é lentidão, é impossibilidade: um conjunto infinito não cabe em memória, por mais memória que se compre.
Este módulo resolve o problema por um caminho que vai se repetir até o fim do curso: em vez de melhorar o método de enumeração, trocamos de objeto. Saímos do lado dos geradores e passamos para o dos reconhecedores. E a máquina do primeiro andar da hierarquia é constrangedoramente simples — lê a entrada uma vez, da esquerda para a direita, sem voltar atrás e sem escrever nada, e a única memória que tem é saber em qual de um número finito de situações ela se encontra.
Vale precisar de onde vem o desconforto que abre o capítulo, porque ele não é retórico: ele é uma limitação concreta da implementação de referência tal como ela ficou no capítulo anterior.
Ao construir as operações sobre linguagens, eu representei uma linguagem como um conjunto ordenado de cadeias e implementei união, interseção, diferença, concatenação, potência e fecho. As cinco primeiras são honestas. O fecho não é: um fecho de Kleene é infinito por definição, e nenhum conjunto em memória o comporta. O que eu implementei foi um fecho limitado por comprimento — todas as cadeias do fecho até um tamanho máximo dado como parâmetro. A mesma limitação atingiu a comparação entre a linguagem descrita por uma expressão regular e a linguagem esperada: comparar até um comprimento é evidência, não prova.
Essa era a maior dívida técnica deixada em aberto, e ela é da natureza da representação, não da qualidade do código. Enquanto uma linguagem for representada pela lista dos seus elementos, um objeto infinito continuará cabendo apenas por truncamento. O autômato é o que salda a dívida: ele representa a linguagem infinita por uma máquina finita e responde à pergunta de pertinência para uma cadeia de qualquer comprimento, em tempo proporcional a esse comprimento, sem limite arbitrário. É por isso que este capítulo é o ponto em que a implementação de referência deixa de simular o infinito e passa a lidar com ele.
A segunda dívida em aberto era outra e se salda aqui também. No capítulo anterior eu escrevi, para cada categoria léxica da linguagem do caso conduzido, dois conjuntos de cadeias: as que devem ser aceitas e as que devem ser rejeitadas. Chamei-os de corpora e admiti, na ocasião, que eles eram contrato e não teste — não havia nada que os executasse. A partir deste capítulo há.
1.2 A máquina que só sabe onde está
Parece pouco, e é pouco mesmo: este é, com folga, o modelo mais fraco do curso. A tese que eu defendo é que a fraqueza é a origem da utilidade.
Uma expressão regular é um gerador: descreve a linguagem dizendo como produzir os seus elementos. Um autômato é um reconhecedor: diz como testar a pertinência. A expressão é curta, legível e não se executa; o autômato é volumoso e trivial de executar. A saída dessa tensão é a que qualquer engenheiro adotaria: especifica-se na forma conveniente para gente e traduz-se automaticamente para a forma conveniente para máquinas — tradução sempre possível nos dois sentidos, o que é o teorema de Stephen Kleene. Aqui eu construo os autômatos à mão sabendo que em uma semana isso ficará desnecessário, por um motivo pedagógico: quem desenhou cinco estados no papel e descobriu no meio do desenho que precisava de um sexto olha para a construção automática com compreensão.
E o que significa “memória finita”? Todo computador real tem memória finita, então a expressão, ao pé da letra, não distingue nada. O que caracteriza o autômato finito é ter memória limitada por uma constante fixada antes de ver a entrada: o número de estados é escolhido no projeto.
Guarde esta frase. Tudo o que a máquina sabe sobre o que já leu está codificado em qual estado ela ocupa; não existe outro lugar onde guardar informação. Se dois prefixos diferentes levam ao mesmo estado, a máquina os considera indistinguíveis daí em diante. É o critério de projeto deste módulo, a base da minimização e o mecanismo do lema do bombeamento.
Há uma segunda restrição, igualmente definidora: a leitura é de mão única e toda decisão é irrevogável. É ela que garante o custo linear e que torna o projeto uma atividade de antecipação — você decide, antes de ler o próximo símbolo, o que precisará lembrar depois.
Quanto à origem, tenho impaciência com a fórmula “os autômatos surgiram como modelo abstrato de computação”, que é verdadeira e não informa nada. As origens são datáveis e são quatro, independentes: McCulloch e Pitts modelando o neurônio como dispositivo de limiar em 1943; Kleene, em relatório de 1951 publicado em 1956 na coletânea Automata Studies; a engenharia de circuitos sequenciais, com Huffman em 1954, Mealy em 1955 e Moore em 1956; e Rabin e Scott em 1959, com o modelo não determinístico.
E o modelo mais fraco é o mais usado por três propriedades que só ele reúne: o custo, de um passo por símbolo; a previsibilidade, porque não existe entrada patológica; e a decidibilidade completa de tudo o que se queira perguntar sobre ele.
1.3 A definição formal, componente por componente
Um autômato finito determinístico é uma quíntupla
M = (Q, \Sigma, \delta, q_0, F),
em que Q é um conjunto finito e não vazio de estados; \Sigma é um alfabeto finito e não vazio; \delta : Q \times \Sigma \to Q é uma função total, a função de transição; q_0 \in Q é o estado inicial; e F \subseteq Q é o conjunto dos estados finais.
flowchart TB
M["autômato finito determinístico<br/>quíntupla"]
Q["Q — conjunto finito de estados<br/>a única memória da máquina"]
S["Sigma — alfabeto finito<br/>define quais entradas fazem sentido"]
D["delta — função de transição TOTAL<br/>um destino, e só um, por par"]
I["q0 — estado inicial<br/>um só, porque escolha é proibida"]
F["F — subconjunto dos estados finais<br/>pode ser vazio, pode ser todo Q"]
M --> Q
M --> S
M --> D
M --> I
M --> F
Repara que a definição descreve o dispositivo parado: o comportamento vem numa segunda camada, na próxima seção.
Nada além de finitude é exigido de Q: estados são elementos abstratos, e damos a eles nomes falantes por conveniência nossa — por isso, na implementação, podem ser simples números inteiros com total fidelidade à teoria. Já \delta é onde mora todo o comportamento, e sobre ela a definição faz a exigência mais atropelada: ela é total, isto é, todo par formado por estado e símbolo tem um destino, e ele é único.
O estado inicial é um só, não um conjunto. Já F é subconjunto qualquer, o que admite três extremos: vazio, e nenhuma cadeia é aceita; igual a Q, e toda cadeia é aceita; e contendo q_0, e então a cadeia vazia é aceita. Este último é fonte de erro sistemático: se a linguagem contém a cadeia vazia, o estado inicial tem de ser final; se não contém, não pode ser. É a primeira coisa a conferir num autômato recém-desenhado, e a que mais frequentemente está errada.
O adjetivo “determinístico” é carregado pela palavra “função” na assinatura de \delta, e diz duas coisas: cada par tem no máximo um destino e pelo menos um destino. No módulo seguinte abandonaremos a unicidade, e abandoná-la abandona junto a totalidade, porque o conjunto vazio passa a ser resposta legítima. Daí também a assimetria da definição: vários estados iniciais introduziriam escolha logo no começo, e escolha é o que o determinismo proíbe, ao passo que um conjunto de finais só pede um teste de pertinência ao fim.
1.4 Pondo a máquina em movimento
Vale a paciência com o vocabulário desta seção: é nele que se demonstram, adiante, a determinização, a minimização e o bombeamento.
Uma configuração instantânea é o par (q, w) formado pelo estado corrente e pela porção da entrada ainda não lida. Duas componentes, e mais nada — o que já foi lido não pode ser revisitado e não precisa ser guardado. A de um autômato de pilha tem três, e a de uma máquina de Turing descreve a fita inteira: o tamanho da configuração mede o poder do modelo.
O passo de computação escreve-se
(q, aw) \vdash_M (\delta(q,a), w),
e a relação \vdash_M^{*} é o seu fecho reflexivo e transitivo. Escrever a entrada não lida como aw já embute que ela é não vazia. Como cada passo consome um símbolo, a computação sobre uma cadeia de comprimento n tem n passos e termina sempre.
Para falar de aceitação precisamos do efeito de uma cadeia inteira, e a maneira limpa de dizê-lo é definir a função de transição estendida \hat\delta : Q \times \Sigma^* \to Q por indução:
\hat\delta(q, \varepsilon) = q, \qquad \hat\delta(q, wa) = \delta\big(\hat\delta(q, w),\, a\big).
Leia a segunda cláusula devagar, porque a ordem das operações é a confusão mais comum daqui: para saber onde wa leva, primeiro descubra onde o prefixo w leva e só então aplique um passo com a. A recursão desce pelo prefixo, não pelo primeiro símbolo. E a função estendida e a relação de passo dizem a mesma coisa em registros diferentes: vale \hat\delta(q,w) = q' exatamente quando (q,w) \vdash_M^{*} (q', \varepsilon).
O primeiro resultado do módulo é modesto e muito usado: para todo estado e todas as cadeias x e y,
\hat\delta(q, xy) = \hat\delta\big(\hat\delta(q, x),\, y\big).
Processar a cadeia partida em duas partes dá o mesmo que processá-la inteira, e a demonstração é por indução sobre o comprimento de y. O teorema sustenta o traçado incremental, a correção do casamento mais longo no analisador léxico e o argumento do bombeamento.
Com isso, aceitação cabe numa linha: w é aceita quando \hat\delta(q_0, w) \in F, e a linguagem reconhecida é
L(M) = \{\, w \in \Sigma^* \mid \hat\delta(q_0, w) \in F \,\}.
Uma linguagem é regular quando existe algum autômato finito determinístico que a reconhece.
flowchart LR
C0["(q0, -0.5)<br/>nada lido"]
C1["(q1, 0.5)<br/>sinal consumido"]
C2["(q2, .5)<br/>parte inteira"]
C3["(q3, 5)<br/>separador consumido"]
C4["(q4, vazio)<br/>parte fracionária"]
V["q4 pertence a F<br/>cadeia ACEITA"]
C0 -->|"lê -"| C1
C1 -->|"lê 0"| C2
C2 -->|"lê ."| C3
C3 -->|"lê 5"| C4
C4 --> V
Duas armadilhas aqui. A primeira: a aceitação depende apenas do estado em que a computação termina, e não do caminho — quem traça cadeias à mão costuma dar a cadeia por aceita assim que passa por um estado final. A segunda: dizer que uma linguagem é regular é afirmar que existe um autômato, não exibir um; para mostrar que é regular basta construir um, mas para mostrar que não é, é preciso um argumento que descarte todos os autômatos possíveis de uma vez.
Dois autômatos são equivalentes quando reconhecem a mesma linguagem — relação entre comportamentos, não entre estruturas. E como existe um autômato mínimo canônico para cada linguagem regular, dois projetistas que resolvam corretamente o mesmo problema chegam a autômatos idênticos após minimização: o projeto manual tem gabarito objetivo, não é matéria de gosto.
1.5 Duas representações e a conversão entre elas
Ninguém escreve autômatos como quíntuplas: usam-se duas representações, uma para pensar e outra para calcular, e a fluência na conversão entre elas é a habilidade central deste módulo.
flowchart TB
A["mesmo autômato<br/>duas representações"]
DIA["diagrama de estados<br/>grafo com círculos e setas"]
TAB["tabela de transição<br/>matriz estado x símbolo"]
HUM["serve ao raciocínio humano<br/>exibe a topologia:<br/>ciclos, alcançabilidade, becos"]
MAQ["serve à máquina<br/>exibe a função:<br/>consulta indexada por par"]
LIM["limite de escala:<br/>deixa de ser desenhável<br/>bem antes do que se espera"]
PRA["prática recomendada:<br/>projetar no diagrama,<br/>implementar pela tabela"]
A --> DIA
A --> TAB
DIA --> HUM
TAB --> MAQ
DIA --> LIM
HUM --> PRA
MAQ --> PRA
Cada estado é um círculo com o nome dentro; o inicial recebe uma seta vinda de lugar nenhum, cada final é desenhado com círculo duplo, e um estado pode acumular as duas marcas. Cada transição é uma seta rotulada com o símbolo, e as que ligam o mesmo par costumam virar uma seta só, com os símbolos separados por vírgula — abreviação de rótulo, apenas. A virtude é tornar visível a estrutura de caminhos: percebe-se de imediato que há um ciclo, que certo estado só é alcançável passando por outro, que existe um estado do qual não se sai. O defeito é não escalar — com quarenta estados o desenho já é um emaranhado.
As linhas são indexadas pelos estados, as colunas pelos símbolos, a célula guarda o destino, e duas marcas indicam qual estado é o inicial e quais são finais. A virtude é que a tabela é executável: começa-se na linha do inicial, salta-se a cada símbolo lido para a linha indicada pela célula e consulta-se, ao fim, se a linha atual está marcada como final. É literalmente um laço com uma indexação por iteração, e por isso a tabela é a representação da máquina. O defeito é o simétrico do outro: ela esconde a topologia.
Um exemplo fixa a ideia: o autômato que reconhece as cadeias em que o número de a é múltiplo de três tem três estados, com q_i significando “li um número de a congruente a i módulo 3”.
| Estado | a | b |
|---|---|---|
| q_0 (inicial e final) | q_1 | q_0 |
| q_1 | q_2 | q_1 |
| q_2 | q_0 | q_2 |
O símbolo b não altera a contagem, e por isso a coluna dele é a diagonal; o a avança a contagem, e a coluna dele é a permutação cíclica. O inicial é final porque zero é múltiplo de três.
As conversões são mecânicas e precisam ficar automáticas para você. Do diagrama para a tabela: uma linha por círculo, as marcas, e depois percorra cada seta, expandindo rótulos abreviados de modo que uma seta rotulada com dez símbolos produza dez células. Da tabela para o diagrama: um círculo por linha, as marcas, e cada célula vira uma seta. Ao terminar, duas conferências: a de contagem, porque um autômato com n estados sobre alfabeto de k símbolos tem exatamente n \times k células preenchidas; e a das marcas, exatamente uma de inicial e as de final nos estados que você pretendia.
A tabela que não cabe na página. Alfabetos de texto têm dezenas de símbolos, e a matriz deixa de ser imprimível. Liste, por estado, os destinos precedidos dos símbolos que levam a eles, agrupando símbolos consecutivos em faixas e envolvendo cada um em delimitadores — sem eles, uma faixa do hífen ao ponto sai como traços e pontos que ninguém interpreta.
1.6 O estado de erro e a completude
A definição diz que \delta é total: ao pé da letra, sobre um alfabeto de cem símbolos você deveria desenhar cem setas saindo de cada estado. Ninguém desenha nem implementa assim — declaram-se as transições interessantes e deixam-se as demais em branco, entendendo tacitamente que cair numa transição em branco é rejeitar. Isso é violação da definição ou abreviação legítima?
É abreviação legítima, e o que a legitima é o teorema do completamento: para todo autômato de transição parcial existe um de transição total que reconhece a mesma linguagem, com no máximo um estado a mais. Acrescenta-se um estado novo d, manda-se para ele toda transição indefinida, e as que saem de d apontam para o próprio d — um estado morto, não final e absorvente.
flowchart LR
Q0(["q0 inicial"])
Q1["q1"]
Q2(["q2 final"])
D["d — estado morto<br/>não final e absorvente"]
Q0 -->|"sinal"| Q1
Q0 -->|"dígito"| Q2
Q1 -->|"dígito"| Q2
Q2 -->|"dígito"| Q2
Q0 -.->|"qualquer outro símbolo"| D
Q1 -.->|"qualquer outro símbolo"| D
Q2 -.->|"qualquer outro símbolo"| D
D -.->|"todo símbolo do alfabeto"| D
A demonstração se separa em dois casos: ou a computação do autômato parcial consome a cadeia inteira, e então os dois autômatos terminam no mesmo estado; ou ela trava num prefixo, e então o parcial rejeita por não consumir a cadeia enquanto o completado entra em d e termina fora de F. Daí sai a leitura que interessa: o estado morto sempre existe, mesmo quando não é desenhado, e a escolha entre as duas formas é de custo de representação, não de semântica.
Decorre também uma distinção que terá consequência no analisador léxico. Um autômato rejeita por duas razões estruturalmente diferentes: ou consome a cadeia inteira e para num estado não final — a entrada estava na trilha certa e terminou cedo demais, como um literal numérico interrompido logo após o separador decimal —, ou encontra um símbolo sem transição definida e saiu completamente da trilha. Para quem constrói compilador, são mensagens diferentes: “faltou alguma coisa” e “isto não pertence aqui”. A informação que as distingue existe exatamente no instante em que o autômato para, e é perdida se o reconhecedor devolver apenas um booleano.
Falta a decisão de engenharia. A representação densa é a matriz completa, com consulta em tempo constante, ao custo de reservar uma posição por símbolo do alfabeto em cada estado; a esparsa guarda só as transições declaradas e paga com consulta logarítmica. Extraia daqui o método de decidir: pergunte quantas vezes a tabela é consultada e quantas vezes é transformada. Dentro do compilador cada determinização percorre as transições existentes, o que favorece a esparsa; no artefato final a tabela é só consultada, o que favorece a densa.
1.7 Projetar autômatos a partir de descrições informais
Esta é a parte que não se aprende lendo: projetar autômatos fica automático pela repetição e não de outro jeito. O que eu ofereço aqui é um método, dois casos trabalhados e o catálogo dos erros que se repetem.
A pergunta de projeto. Suponha que eu tenha lido um prefixo da entrada e que a leitura continue. Qual é a menor informação sobre o prefixo lido que eu preciso reter para decidir corretamente o resto da computação? Cada resposta possível a essa pergunta é um estado.
A força está no “menor”. Sempre dá para responder “preciso lembrar o prefixo inteiro”, e essa resposta produz infinitos estados — o que não é um autômato. O trabalho é descobrir quais prefixos podem ser confundidos sem prejuízo, porque o futuro deles é idêntico. Para as cadeias que terminam em a, basta lembrar se o último símbolo foi a: duas respostas, dois estados. Já para as cadeias com tantos a quanto b, a resposta é a diferença entre as contagens, um inteiro sem limite — infinitas respostas, não há autômato finito. Repara que o método avisa que vai falhar, e pelo motivo certo.
O procedimento tem quatro movimentos, e a ordem importa. Primeiro, escreva exemplos antes de desenhar: as cadeias que devem ser aceitas e as que devem ser rejeitadas, com os casos de fronteira, porque escrever essa lista depois é escrevê-la para concordar com o que você já fez. Segundo, nomeie os estados por significado — “ainda não li nada”, “li o sinal e nenhum dígito” —, porque assim o nome do estado responde quando falta uma transição. Terceiro, marque os finais antes das transições, perguntando se a cadeia é válida caso a entrada acabe ali. Quarto, confira a completude estado por estado, concordando explicitamente com cada transição que vai para o estado morto.
Apliquemos ao caso mais instrutivo do repertório: um número é uma sequência de dígitos, opcionalmente precedida de sinal de menos e opcionalmente seguida de um separador decimal com mais dígitos depois. Antes de desenhar, os exemplos: devem ser aceitas 0, 42, -7, 3.5 e -0.25, e devem ser rejeitadas a cadeia vazia, o sinal sozinho, a iniciada pelo separador, a terminada no separador, a que tem dois separadores, a notação exponencial e o sinal de mais.
flowchart LR
INI["início"]
Q0["q0<br/>não li nada"]
Q1["q1<br/>gastei o sinal,<br/>nenhum dígito ainda"]
Q2(["q2 final<br/>parte inteira"])
Q3["q3<br/>gastei o separador,<br/>nenhum dígito depois"]
Q4(["q4 final<br/>parte fracionária"])
INI --> Q0
Q0 -->|"-"| Q1
Q0 -->|"dígito"| Q2
Q1 -->|"dígito"| Q2
Q2 -->|"dígito"| Q2
Q2 -->|"."| Q3
Q3 -->|"dígito"| Q4
Q4 -->|"dígito"| Q4
Agora a pergunta de projeto, aplicada. Antes de ler qualquer coisa não posso aceitar: primeiro estado, não final. Se leio o sinal, já o gastei e ainda não posso parar: segundo estado, não final. Se leio um dígito, estou na parte inteira e posso parar: terceiro estado, final. O separador me leva a um lugar onde não posso parar: quarto estado, não final. Dali um dígito me leva à parte fracionária: quinto estado, final.
O ponto pedagógico está nos dois estados não finais do meio, que existem por uma única razão: exigir que venha pelo menos mais um dígito. A tentação é economizar, mandando o sinal direto para a parte inteira — o desenho fica com três estados e parece mais elegante, e aí o sinal sozinho passa a ser aceito. Generalizando: toda construção opcional que exige “pelo menos um” de alguma coisa pede um estado não final entre o gatilho e a repetição.
Compare com o identificador — uma letra minúscula seguida de qualquer sequência de letras, dígitos e sublinhados. A expressão regular não é mais curta que a do número, e o autômato tem dois estados, porque a dificuldade não se mede pelo tamanho da descrição e sim por quantas vezes a decisão depende do que já foi lido. E o autômato da contagem módulo três, que parece contar, guarda o resto e não a contagem: contar módulo k custa k estados, contar sem módulo é impossível, e é por isso que parênteses balanceados não são reconhecíveis aqui.
Um último padrão, que aparece ao reconhecer delimitadores: nas cadeias que não contêm certa subcadeia proibida, o que se lembra é quanto do padrão já se viu no final do prefixo — e ler de novo o primeiro símbolo do padrão não volta ao estado inicial, porque a nova ocorrência pode ser o começo de uma ocorrência.
| Erro de projeto | Como se manifesta | Como se pega |
|---|---|---|
| Estado final prematuro | aceita construção incompleta | lista de rejeições escrita antes |
| Inicial mal marcado quanto à cadeia vazia | erra numa cadeia só, a que ninguém testa | conferir se a linguagem contém a cadeia vazia |
| Transição esquecida | rejeita silenciosamente cadeias válidas | conferência de contagem das células |
| Retorno indevido ao inicial | funciona na maioria das entradas | exemplos com ocorrência parcial do padrão |
| Estado supérfluo | não é defeito de correção, só de economia | corrigido pela minimização |
E como saber se acertou? Projetar sem verificar é adivinhar. O primeiro instrumento é a lista de exemplos: trace cada cadeia de aceitação anotando o estado após cada símbolo, e confira que cada cadeia de rejeição falha — e por qual dos dois modos ela falha, porque uma cadeia que falha pelo motivo errado esconde um defeito que ainda não se manifestou. O segundo é a conferência de contagem. O terceiro só passa a existir no módulo seguinte: confrontar o desenho manual com o autômato produzido por algoritmo.
1.8 Da definição à estrutura de dados
A quíntupla é objeto matemático; o programa precisa de tipos, campos e laços. São quatro decisões, e o motivo de gastá-las agora, quando os autômatos ainda têm cinco estados, é que são caras de rever depois.
flowchart TB
DEF["a quíntupla da definição"]
IDX["estados como índices inteiros<br/>num vetor, nunca referências"]
SIM["símbolo em tipo sem sinal<br/>convertido na fronteira da leitura"]
ESP["transições esparsas por estado<br/>dentro do compilador"]
LAC["reconhecimento em laço<br/>a indução desenrolada"]
GAN["copiar, comparar, serializar<br/>e usar conjuntos de estados<br/>como chave fica barato"]
SEG["byte alto não vira índice negativo"]
ALG["determinização e minimização<br/>percorrem o que existe"]
PIL["nenhum estouro de pilha<br/>em arquivo grande"]
DEF --> IDX --> GAN
DEF --> SIM --> SEG
DEF --> ESP --> ALG
DEF --> LAC --> PIL
A primeira é a mais consequente, e é justamente a que a orientação a objetos sugere errado: representar cada estado como objeto e cada transição como referência de um objeto para outro. Parece limpo e começa a ranger no terceiro algoritmo, porque um autômato é um grafo dirigido com ciclos, e grafo cíclico manipulado por referência levanta a questão de propriedade. A alternativa é representar estados por índices inteiros num vetor: copiar o autômato vira copiar vetores, comparar estados vira comparar inteiros, e os conjuntos de estados de que a determinização precisará serão conjuntos de inteiros, baratos de comparar e usar como chave.
A segunda parece detalhe de linguagem e não é. Um símbolo, quando a entrada é texto, é um byte, e a armadilha é que o tipo de caractere natural de várias linguagens é assinado: um byte acima de cento e vinte e sete vira número negativo, que como chave produz ordenação incorreta e como índice produz acesso fora dos limites. O defeito é silencioso enquanto a entrada for texto sem acentos, passa por toda a bateria de testes escrita em inglês e explode na primeira palavra acentuada. A providência é fixar num único ponto do programa um tipo próprio para o símbolo, explicitamente sem sinal.
A terceira já foi discutida: estrutura esparsa dentro do compilador, matriz densa no artefato final, porque determinização e minimização percorrem as transições existentes de cada estado, enquanto a densa obriga a varrer o alfabeto inteiro descartando o que não existe.
A quarta é sobre a função estendida. Ela é recursiva, e a transcrição literal seria uma função recursiva sobre a cadeia — não faça isso, porque a profundidade seria o comprimento da entrada e o reconhecedor rodará sobre arquivos inteiros. A implementação é um laço, e isso não é desvio da definição: é a indução desenrolada, a mesma recorrência calculada de baixo para cima. Cuide da transição indefinida no meio da cadeia, porque um laço que continue depois de cair fora do autômato pode ler um valor que corresponde a estado válido e acabar aceitando cadeia inválida. A providência é um valor sentinela para “não há estado”, verificado a cada iteração: é a tradução direta do estado morto absorvente.
E uma ferramenta de retorno desproporcional ao esforço: além da função que devolve aceita ou rejeita, implemente uma que devolva a sequência de configurações instantâneas percorrida. É uma dúzia de linhas, e mostra em que símbolo a computação saiu do trilho.
1.9 O reconhecedor do caso conduzido
Tudo o que discuti até aqui é neutro quanto ao objeto que se reconhece. A aplicação é o primeiro código de verdade do compilador: a estrutura de autômato que os módulos seguintes vão herdar, os primeiros autômatos projetados à mão a partir da especificação léxica do módulo anterior, e a verificação contra as listas de cadeias que ficaram lá como promessa.
1.9.1 8.1 A estrutura de autômato que o projeto vai carregar
A primeira peça é a estrutura que representa a quíntupla, e ela é o artefato mais duradouro deste capítulo: o mesmo tipo será produzido pela construção do capítulo seguinte, transformado pela determinização e pela minimização, combinado por produto no capítulo sobre fechamento, executado pelo analisador léxico e, por fim, serializado dentro do programa objeto. As decisões tomadas aqui atravessam o livro inteiro.
03_afd.h
#ifndef PENEIRA_03_AFD_H
#define PENEIRA_03_AFD_H
#include <cstddef>
#include <map>
#include <string>
#include <vector>
#include "02_cadeia.h"
namespace peneira {
// Estados são índices num vetor, nunca ponteiros. Um autômato é um grafo com
// ciclos, e grafo cíclico manipulado por ponteiro é a origem mais comum de
// defeito de memória num projeto como este. Com índice, copiar o autômato é
// copiar dois vetores, e comparar estados é comparar inteiros.
using Estado = std::size_t;
// O símbolo é sem sinal de propósito. Com `char` simples, um byte acima de 127
// vira valor negativo na plataforma e desordena o mapa de transições — defeito
// que só aparece com entrada acentuada e é difícil de rastrear.
using Simbolo = unsigned char;
// Ausência de estado. Usado como resultado de uma transição não definida e
// como marcador de autômato ainda sem estado inicial.
inline constexpr Estado kSemEstado = static_cast<Estado>(-1);
// Autômato finito determinístico: a quíntupla da definição formal, com os
// estados numerados de zero a n-1.
//
// A função de transição é representada por um mapa esparso por estado, e não
// por matriz densa. O alfabeto tem 256 símbolos e um estado típico define
// transição para uns poucos; a matriz densa gastaria 256 posições por estado
// para usar meia dúzia.
class Afd {
public:
explicit Afd(std::string nome);
Estado novoEstado(bool final);
void definirInicial(Estado e);
void adicionarTransicao(Estado de, Simbolo simbolo, Estado para);
// Atalho para declarar uma faixa contígua de símbolos com o mesmo destino,
// como `[0-9]`. Evita vinte e seis chamadas para declarar as letras.
void adicionarFaixa(Estado de, Simbolo inicio, Simbolo fim, Estado para);
const std::string& nome() const noexcept;
std::size_t quantidadeDeEstados() const noexcept;
Estado inicial() const noexcept;
bool ehFinal(Estado e) const;
// A função de transição da definição formal. Devolve kSemEstado quando não
// há transição declarada — é o estado de erro implícito.
Estado transicao(Estado de, Simbolo simbolo) const;
// Função de transição estendida a cadeias, definida por indução: a cadeia
// vazia leva ao próprio estado, e uma cadeia com um símbolo a mais leva ao
// resultado de aplicar a transição ao estado alcançado pelo prefixo.
Estado deltaEstendido(Estado de, const Cadeia& s) const;
// A cadeia é aceita quando a função estendida, partindo do inicial, chega
// a um estado final.
bool aceita(const Cadeia& s) const;
// Símbolos que aparecem em alguma transição. É o alfabeto efetivamente
// usado, que não precisa ser o alfabeto inteiro da linguagem.
std::vector<Simbolo> simbolosUsados() const;
// A definição formal exige função de transição TOTAL. A representação
// esparsa deixa o estado de erro implícito; este método o torna explícito,
// acrescentando um estado não final que absorve tudo que não estava
// declarado. O autômato resultante reconhece a mesma linguagem.
bool ehCompleto() const;
Afd completado() const;
// Tabela de transição em texto, com símbolos consecutivos de mesmo destino
// agrupados em faixa. Sem o agrupamento, a tabela do identificador teria
// trinta e sete colunas e seria ilegível.
std::string tabelaDeTransicao() const;
// Sequência de configurações instantâneas ao processar a cadeia: em que
// estado o autômato está e o que falta ler, passo a passo.
std::string tracar(const Cadeia& s) const;
private:
std::string nome_;
Estado inicial_ = kSemEstado;
std::vector<bool> finais_;
std::vector<std::map<Simbolo, Estado>> transicoes_;
};
} // namespace peneira
#endif // PENEIRA_03_AFD_H
Leia a interface contra as seções anteriores, porque ela é a tradução delas quase linha a linha.
O apelido de estado é um inteiro sem sinal de tamanho de índice, pelo argumento da Seção 7.1; o apelido de símbolo é explicitamente sem sinal, pelo argumento da Seção 7.2. A constante que marca ausência de estado é o valor sentinela da Seção 7.4, e ela cumpre dois papéis: resultado de transição não declarada e marcador de autômato ainda sem inicial definido. As transições são um vetor de mapas ordenados, um por estado — a representação esparsa da Seção 7.3 —, e o método que declara uma faixa contígua de símbolos existe por conveniência de escrita: sem ele, declarar as letras minúsculas custaria vinte e seis chamadas em vez de uma, e a legibilidade do código de construção é o que permite conferi-lo contra o desenho.
Há dois métodos que correspondem diretamente à Definição 3.3 e à Definição 3.4, e a separação entre eles é deliberada. Um calcula a função estendida e devolve o estado alcançado; o outro consulta se esse estado é final. Manter os dois separados custa nada e permite que o traçado, os relatórios e o analisador léxico usem o estado alcançado para outros fins que não a resposta booleana — que é exatamente o que a Seção 5.3 pedia ao dizer para não descartar cedo demais a distinção entre os dois modos de rejeição.
Os três últimos métodos são instrumentos e não fazem parte da definição: o que devolve o autômato completado é a construção do Teorema 5.1, o que imprime a tabela agrupada em faixas é a saída discutida na Seção 4.5, e o que traça a computação é o instrumento defendido na Seção 7.5.
1.9.2 8.2 Os dois autômatos projetados à mão
Com a estrutura no lugar, projetei os autômatos das categorias léxicas especificadas no capítulo anterior. Não os seis — dois, e a escolha dos dois tem razão.
Escolhi a categoria dos literais numéricos porque ela é a menos trivial da especificação: tem o sinal opcional, tem a fronteira entre parte inteira e separador decimal, e tem a parte fracionária opcional, que são os três pontos de decisão trabalhados na Seção 6.3. E escolhi a categoria dos identificadores como contraste, pelo argumento da Seção 6.4: dois estados contra cinco, com expressões regulares de tamanho comparável, o que torna visível que o custo vem do número de decisões dependentes do passado e não do tamanho da descrição.
03_reconhecedores.h
#ifndef PENEIRA_03_RECONHECEDORES_H
#define PENEIRA_03_RECONHECEDORES_H
#include <cstddef>
#include <string>
#include <vector>
#include "03_afd.h"
namespace peneira {
// Autômatos projetados à mão, a partir das categorias léxicas especificadas no
// módulo 2. São dois de propósito: um trivial e um com pontos de decisão, para
// que a diferença de esforço fique visível.
//
// Construí-los à mão é trabalho que a construção automática do módulo 4 vai
// eliminar. O ponto de fazê-lo agora é sentir o custo que ela poupa.
Afd afdNumero();
Afd afdIdentificador();
// Resultado da verificação de um autômato contra os corpora do módulo 2.
struct ResultadoVerificacao {
std::string categoria;
std::size_t aceitasEsperadas = 0;
std::size_t aceitasObtidas = 0;
std::size_t rejeitadasEsperadas = 0;
std::size_t rejeitadasObtidas = 0;
std::vector<std::string> divergencias;
bool passou() const;
};
// Roda o autômato contra os dois corpora da categoria de mesmo nome na
// especificação léxica. É aqui que os corpora escritos no módulo 2 deixam de
// ser contrato e passam a ser executáveis.
ResultadoVerificacao verificar(const Afd& automato, const std::string& categoria);
} // namespace peneira
#endif // PENEIRA_03_RECONHECEDORES_H
03_reconhecedores.cpp
#include "03_reconhecedores.h"
#include "02_lexico.h"
namespace peneira {
Afd afdNumero() {
// Reconhece -?[0-9]+(\.[0-9]+)?
//
// q0 inicial: aceita sinal ou entra direto na parte inteira
// q1 depois do sinal: exige pelo menos um digito
// q2 parte inteira, FINAL: mais digitos, ou o ponto
// q3 depois do ponto: exige pelo menos um digito
// q4 parte fracionaria, FINAL
//
// Os dois estados não finais no meio (q1 e q3) são o que impede "-" e "5."
// de serem aceitos. Foi ao desenhar que percebi que precisava deles
// separados de q2 e q4.
Afd a("NUMERO");
const Estado q0 = a.novoEstado(false);
const Estado q1 = a.novoEstado(false);
const Estado q2 = a.novoEstado(true);
const Estado q3 = a.novoEstado(false);
const Estado q4 = a.novoEstado(true);
a.definirInicial(q0);
a.adicionarTransicao(q0, '-', q1);
a.adicionarFaixa(q0, '0', '9', q2);
a.adicionarFaixa(q1, '0', '9', q2);
a.adicionarFaixa(q2, '0', '9', q2);
a.adicionarTransicao(q2, '.', q3);
a.adicionarFaixa(q3, '0', '9', q4);
a.adicionarFaixa(q4, '0', '9', q4);
return a;
}
Afd afdIdentificador() {
// Reconhece [a-z][a-z0-9_]*
//
// q0 inicial: exige letra minuscula
// q1 FINAL: letra, digito ou sublinhado, indefinidamente
//
// Dois estados bastam. O contraste com o autômato do número mostra que a
// dificuldade não vem do tamanho da expressão, e sim da quantidade de
// pontos em que a decisão depende do que já foi lido.
Afd a("IDENTIFICADOR");
const Estado q0 = a.novoEstado(false);
const Estado q1 = a.novoEstado(true);
a.definirInicial(q0);
a.adicionarFaixa(q0, 'a', 'z', q1);
a.adicionarFaixa(q1, 'a', 'z', q1);
a.adicionarFaixa(q1, '0', '9', q1);
a.adicionarTransicao(q1, '_', q1);
return a;
}
bool ResultadoVerificacao::passou() const {
return divergencias.empty() && aceitasObtidas == aceitasEsperadas &&
rejeitadasObtidas == rejeitadasEsperadas;
}
ResultadoVerificacao verificar(const Afd& automato,
const std::string& categoria) {
ResultadoVerificacao resultado;
resultado.categoria = categoria;
for (const CategoriaLexica& c : especificacaoLexica()) {
if (c.nome != categoria) {
continue;
}
resultado.aceitasEsperadas = c.aceitas.size();
resultado.rejeitadasEsperadas = c.rejeitadas.size();
for (const Cadeia& cadeia : c.aceitas) {
if (automato.aceita(cadeia)) {
++resultado.aceitasObtidas;
} else {
resultado.divergencias.push_back(
"deveria aceitar e rejeitou: \"" + cadeia + "\"");
}
}
for (const Cadeia& cadeia : c.rejeitadas) {
if (!automato.aceita(cadeia)) {
++resultado.rejeitadasObtidas;
} else {
resultado.divergencias.push_back(
"deveria rejeitar e aceitou: \"" + cadeia + "\"");
}
}
return resultado;
}
resultado.divergencias.push_back("categoria ausente na especificacao: " +
categoria);
return resultado;
}
} // namespace peneira
Repare que o código de construção é praticamente a transcrição do desenho: um estado por linha, com a marca de final decidida ali mesmo, e uma transição por linha em seguida. O comentário no topo de cada função carrega o desenho em texto, com o significado de cada estado escrito por extenso — porque é o desenho que explica o código, e não o contrário, e porque quem for reler isto em dois capítulos precisará do significado dos estados, não da lista de transições.
Registro, porque é o tipo de coisa que os livros costumam apagar, que os dois estados intermediários não finais do autômato numérico eu não os previ. Desenhei primeiro a versão econômica, com o sinal indo direto para a parte inteira, e ela passou nos casos que eu tinha em mente. Foi a lista de rejeições, escrita antes, que a derrubou: o sinal sozinho era aceito. Os dois estados nasceram dessa falha, e é por isso que insisti tanto, na Seção 6.2, em escrever a lista antes de desenhar.
1.9.3 8.3 A verificação, e a promessa cumprida
A terceira peça é a que salda a dívida do capítulo anterior. A função de verificação percorre a especificação léxica, encontra a categoria de mesmo nome, roda o autômato sobre cada cadeia dos dois conjuntos e conta os acertos, registrando separadamente cada divergência entre o esperado e o obtido.
Vale examinar a estrutura de resultado, porque ela contém uma decisão de projeto que eu defendo. Ela carrega, para cada um dos dois conjuntos, o número esperado e o número obtido em campos separados, além da lista de divergências. Isso é redundante de propósito. Um relatório que só sabe dizer “treze de treze passaram” não prova nada, porque pode ser que ele sempre diga isso; com o esperado e o obtido calculados por caminhos diferentes e impressos lado a lado, uma contagem inconsistente aparece mesmo que a lista de divergências esteja vazia. É a versão em miniatura do princípio que fecha o capítulo — duas vias independentes para a mesma grandeza —, e ela vai reaparecer, com consequências bem maiores, nos capítulos sobre geração de código.
O resultado da execução foi o seguinte: para a categoria numérica, seis de seis cadeias do conjunto de aceitação foram aceitas e sete de sete do conjunto de rejeição foram rejeitadas; para a categoria dos identificadores, seis de seis e cinco de cinco. Nenhuma divergência.
Vale olhar quais rejeições passaram, porque não são todas triviais e cada uma exercita uma característica diferente do desenho. A cadeia com separador decimal inicial e a cadeia terminada no separador falham por causa dos dois estados intermediários não finais — sem eles, seriam aceitas. A cadeia com dois separadores falha por não haver transição de separador saindo da parte fracionária. A cadeia com notação exponencial falha na letra, que não pertence ao alfabeto declarado. A cadeia com sinal de mais falha porque apenas o sinal negativo tem transição, que é uma decisão da especificação e não um esquecimento. E a cadeia vazia e o sinal isolado falham por parar em estado não final. Note que essas seis rejeições se repartem exatamente nos dois modos da Seção 5.3, e que a lista de exemplos, escrita um capítulo antes, cobriu os dois sem que isso tivesse sido planejado.
Na categoria dos identificadores, o caso que mais rende é o de uma palavra iniciada por maiúscula, que é rejeitada porque o alfabeto da categoria não inclui maiúsculas. Não é limitação acidental da implementação, é a restrição declarada da linguagem, e o corpus a documenta.
Quatro das seis categorias — texto entre delimitadores, literal de padrão, pontuação e espaço — continuam sem autômato ao fim deste capítulo, e isso é decisão e não pendência. Construí-las à mão seria trabalho jogado fora, porque a partir do capítulo seguinte a construção passa a ser automática a partir da expressão regular. Escolhi as duas que ensinam mais por unidade de esforço e parei.
1.9.4 8.4 O estado de erro, feito explícito
Falta materializar o Teorema 5.1, e há uma razão para não deixá-lo apenas no enunciado.
A representação esparsa que adotei viola, à primeira vista, a exigência de totalidade da Definição 2.1: o mapa simplesmente não tem entrada para os pares indefinidos. A conciliação, como o teorema mostra, é que existe um estado de erro implícito — a consulta devolve o sentinela, o processamento termina e a cadeia é rejeitada. Comportamento idêntico ao de um estado morto explícito, representação diferente.
Para que essa afirmação não fique só no discurso, implementei a conversão. O método que completa o autômato cria um estado novo, não final, e o torna absorvente: todas as transições indefinidas passam a apontar para ele, e todas as que saem dele apontam para ele mesmo — exatamente a construção da demonstração do Teorema 5.1. O autômato numérico passa de cinco para seis estados, e a função de transição passa a ser total sobre o alfabeto efetivamente usado.
A demonstração executável roda a mesma verificação nos dois autômatos, o esparso e o completado, sobre os mesmos corpora, e os dois produzem o mesmo resultado. É a evidência de que a completude é escolha de representação e não mudança de linguagem, que é precisamente o que o teorema afirma.
Registro por que não deixei o autômato completado como representação padrão, já que ele é o que a teoria descreve. Completar exige fixar o alfabeto, e o alfabeto natural sobre bytes teria duzentos e cinquenta e seis símbolos, o que faria cada estado carregar duzentas e cinquenta e seis transições: o autômato numérico passaria de dezesseis transições declaradas para mil e quinhentas. A representação esparsa guarda o mínimo e devolve o mesmo comportamento; a completa existe como transformação, para quando exibi-la for pedagogicamente útil.
1.9.5 8.5 A tabela impressa, e um detalhe que se paga
Encerro com a saída do programa, porque ela é o objeto que se confere a olho e porque ilustra a discussão da Seção 4.5 melhor do que qualquer descrição.
tabela de transicao de NUMERO (5 estados)
q0 inicial
'-' -> q1
'0'..'9' -> q2
q1
'0'..'9' -> q2
q2 final
'.' -> q3
'0'..'9' -> q2
q3
'0'..'9' -> q4
q4 final
'0'..'9' -> q4Cinco estados, oito linhas de transição. Sem o agrupamento de símbolos consecutivos em faixa, seriam trinta e duas linhas, uma por dígito de cada estado de repetição, e a tabela dos identificadores teria trinta e sete. É a diferença entre uma saída que se confere em dez segundos e uma que ninguém lê.
E é aqui que as aspas simples em torno de cada símbolo se pagam, exatamente pelo motivo antecipado na Seção 4.5. No autômato completado, o estado de erro recebe a faixa que vai do sinal de menos ao separador decimal, e ela sai delimitada de forma legível; sem os delimitadores, sairia como uma sequência de dois traços e um ponto, que ninguém interpretaria. É um detalhe de apresentação de dez minutos que decide se a saída serve para conferir ou para decorar.
O que quero deixar registrado sobre este bloco de código é que ele é o último em que se constrói autômato à mão. A partir do capítulo seguinte, a expressão regular vira autômato por algoritmo, e o trabalho manual feito aqui passa a servir de gabarito: o autômato que o algoritmo produzir para a mesma expressão deve reconhecer exatamente as mesmas cadeias que este, e é contra este que ele será conferido.
1.10 Síntese
Um autômato finito determinístico é uma quíntupla formada por um conjunto finito de estados, um alfabeto, uma função de transição total, um estado inicial e um conjunto de estados finais. A restrição definidora não é ter memória limitada, é tê-la limitada por uma constante fixada antes de ver a entrada — do que decorre que tudo o que a máquina sabe sobre o passado está codificado em qual estado ela ocupa. O comportamento vem em duas camadas: a configuração instantânea e, sobre ela, o passo de computação, sobre o qual se define por indução a extensão da função de transição, com a qual a aceitação cabe numa linha.
Há duas representações divididas por função — o diagrama exibe a topologia e serve ao projeto, a tabela exibe a função e serve à execução —, e a totalidade concilia-se com a prática de declarar só as transições interessantes, porque toda transição ausente equivale a uma transição para um estado morto. O projeto a partir de descrições informais se apoia numa pergunta só, cujas respostas possíveis são os estados. E a travessia para a estrutura de dados tem quatro decisões que valem para o resto do curso: estados por índice, símbolo sem sinal, estrutura esparsa dentro do compilador e reconhecimento em laço.
Volto ao incômodo da abertura: queríamos decidir pertinência para cadeias de qualquer comprimento, e agora temos uma máquina finita que representa um conjunto infinito e responde em tempo proporcional ao tamanho da cadeia. O preço foi construir os autômatos à mão, e no módulo seguinte ele deixa de ser pago — o autômato passa a ser produzido por algoritmo a partir da expressão regular, por um desvio que parece retrocesso: uma máquina que, diante de uma escolha, faz todas ao mesmo tempo. O trabalho manual que você fez aqui ganha então o papel de gabarito.