Análise Léxica

O token é a unidade que o analisador léxico emite ao ler o programa-fonte caractere a caractere: a tripla (classe, lexema, posição). Espaços e comentários avançam a leitura sem emitir token.

L(r) de cada classe, o AFND de Thompson e o AFD do scanner neste tópico — e gramáticas livres de contexto e análise sintática no tópico seguinte — partem dessa tripla e da regra do maior prefixo.

As páginas se agrupam em três blocos. O primeiro emite o átomo e corta a entrada: a tripla, a tabela de reservadas que troca a classe do identificador, e o maior prefixo entre padrões.

O segundo descreve o conjunto de cada classe: L(r) pelos construtores ∅, ε, símbolo, alternativa, concatenação e estrela, dito em palavras.

O terceiro constrói a máquina e a executa: Thompson traduz a ER em AFND com ε; subconjuntos produzem o AFD; o scanner emite o lexema do último estado final e recua a cabeça.

A tripla (classe, lexema, posição) e a tabela que, após o padrão de identificador, emite a classe da palavra reservada estão em Reconhecimento de Tokens. Escrever a ER e dizer quais cadeias entram em L(r) está em Expressões Regulares.

O casamento mais longo a partir da mesma posição, e o símbolo extra que r? pode consumir, estão em Reconhecimento de Tokens. Avançar o AFD até faltar sucessor, emitir o último final e recuar a cabeça está em Autômatos Finitos.

Montar L(r) com alternativa, concatenação e estrela, e r? = (r | ε), está em Expressões Regulares. Costurar cada construtor com ε (Thompson), determinizar pelo ε-fecho e contar |Q| pelos conjuntos alcançáveis está em Autômatos Finitos.