Introdução

A construção de compiladores está intimamente ligada à teoria dos autômatos, linguagens formais e expressões regulares.

Esses conceitos fornecem a base matemática para o reconhecimento de padrões e estruturas em linguagens de programação.

Antes de um compilador conseguir analisar o código-fonte, ele precisa reconhecer palavras, símbolos e estruturas válidas da linguagem.

Linguagens Formais

Linguagens formais são conjuntos de cadeias de símbolos (strings) construídas a partir de um alfabeto definido, com regras específicas de formação.

No contexto de compiladores, elas são usadas para descrever a sintaxe de linguagens de programação.

Alfabeto: Um alfabeto (Σ) é um conjunto finito de símbolos. Por exemplo, o alfabeto binário é: Σ = {0, 1}.

Cadeia (ou palavra): Uma cadeia é uma sequência finita de símbolos do alfabeto. Exemplo: Se Σ = {a, b}, então "ab", "aab" e "bb" são cadeias válidas.

Linguagem: Uma linguagem formal é um conjunto de cadeias formadas a partir de um alfabeto. Exemplo: L = {w | w começa com 'a'} → L = {"a", "ab", "aa", "aab", ...}

Expressões Regulares

As expressões regulares (ERs) são uma forma compacta e poderosa de descrever linguagens formais.

Elas definem padrões que um analisador léxico pode usar para identificar tokens.