Autômatos Finitos, Expressões Regulares e Análise Léxica

Autômatos Finitos e Expressões Regulares

Uma máquina de estados finitos (MEF), ou autômato finito, é um modelo matemático de um sistema que recebe uma sequência de símbolos de um alfabeto e determina se a sequência pertence à linguagem que ele reconhece.

Formalmente, uma máquina de estados finitos pode ser descrita como uma quíntupla (S, Σ, T, s, A) onde:

• S: é um conjunto de estados
• Σ: é um alfabeto
• T: é a função de transição
• s: é o estado inicial
• A: é o conjunto de estados finais

Representação de Autômatos Finitos

Além de ser apresentada através de sua definição formal, uma máquina de estados finitos pode ser representada por outras notações que são mais convenientes. As mais comuns são tabelas de transição, diagramas de transição e expressões regulares.

Analisador Léxico

O analisador léxico tem como função principal receber uma sequência de caracteres do alfabeto da linguagem e classificá-la em categorias conhecidas como unidades lexicais (ou tokens). Essas unidades são utilizadas pelo analisador sintático para determinar se o código-fonte está gramaticalmente correto. Algumas unidades lexicais não são usadas pelo analisador sintático, mas são filtradas, como comentários, que documentam o programa mas não afetam a gramática, ou espaços em branco, que servem para dar maior clareza ao código.

Terminologia do Analisador Léxico

Na terminologia usada na construção de um analisador léxico, temos:

• Padrão: define a regra pela qual uma sequência de caracteres é reconhecida como uma unidade lexical específica.
• Lexema: é a ocorrência real de uma sequência de caracteres que corresponde a um padrão.
• Token: é o par (tipo de unidade lexical, valor do lexema), frequentemente representado por um inteiro para o tipo.
• Alfabeto: conjunto de caracteres válidos para uma linguagem.
• Unidades Lexicais: são as categorias que classificam as sequências válidas em uma linguagem.

O Papel do Analisador Léxico

Embora o analisador léxico seja o primeiro estágio do processo de compilação, ele não inicia o processo. O analisador sintático é quem realmente começa, solicitando tokens ao analisador léxico, que então realiza seu processamento e envia os resultados. Durante essas fases, uma estreita comunicação é mantida com a tabela de símbolos, que armazena informações sobre as entidades usadas nos programas.

Descrição de Padrões Léxicos

Existem três maneiras principais de descrever padrões léxicos: a descrição informal (usando linguagem natural), expressões regulares e autômatos finitos (como diagramas de transição).

Diagramas de Transição

Um diagrama de transição é a representação gráfica de um conjunto de estados (inicial, intermediário ou final) e das transições entre eles.

Os estados iniciais são representados por um círculo duplo e um zero (ou uma seta de entrada), os intermediários por um círculo e um número, e os finais por um círculo duplo e o número correspondente. Os estados se relacionam entre si por meio de transições rotuladas com o caractere ou conjunto de caracteres que as causam.

Características dos Diagramas de Transição

• Cada transição de estado é acionada por um conjunto específico de caracteres.
• Cada padrão possui um seletor de caracteres que permite uma forma única de reconhecimento.
• Para alcançar um estado de aceitação, deve haver uma transição do caractere que finaliza o padrão da unidade lexical.

Exemplos de Descrições Informais de Unidades Léxicas

• Identificador: é uma letra seguida ou não por outras letras, números ou sublinhados.
• Comentário: começam com /* e terminam com */. Podem conter qualquer símbolo, exceto o marcador de fim de arquivo.
• EOF (End Of File): indica o fim do arquivo.
• Erro: qualquer sequência de símbolos que não se enquadre nos padrões definidos anteriormente.