Projeto do compilador - expressões regulares

O analisador léxico precisa examinar e identificar apenas um conjunto finito de string / token / lexema válido que pertence ao idioma em questão. Ele procura o padrão definido pelas regras de linguagem.

As expressões regulares têm a capacidade de expressar linguagens finitas, definindo um padrão para cadeias finitas de símbolos. A gramática definida por expressões regulares é conhecida comoregular grammar. A linguagem definida pela gramática regular é conhecida comoregular language.

A expressão regular é uma notação importante para especificar padrões. Cada padrão corresponde a um conjunto de strings, portanto, as expressões regulares servem como nomes para um conjunto de strings. Os tokens de linguagem de programação podem ser descritos por linguagens regulares. A especificação de expressões regulares é um exemplo de definição recursiva. Linguagens regulares são fáceis de entender e têm implementação eficiente.

Existem várias leis algébricas que são obedecidas por expressões regulares, que podem ser usadas para manipular expressões regulares em formas equivalentes.

Operações

As várias operações em idiomas são:

• A união de duas línguas L e M é escrita como

  LUM = {s | s está em L ou s está em M}

• A concatenação de duas linguagens L e M é escrita como

  LM = {st | s está em L e t está em M}

• O fechamento de Kleene de uma linguagem L é escrito como

  L * = Zero ou mais ocorrências do idioma L.

Notações

Se r e s são expressões regulares denotando as linguagens L (r) e L (s), então

• Union : (r) | (s) é uma expressão regular denotando L (r) UL (s)

• Concatenation : (r) (s) é uma expressão regular denotando L (r) L (s)

• Kleene closure : (r) * é uma expressão regular denotando (L (r)) *

• (r) é uma expressão regular denotando L (r)

Precedência e Associatividade

• *, concatenação (.) e | (sinal de pipe) são associativos à esquerda
• * tem a precedência mais alta
• A concatenação (.) Tem a segunda precedência mais alta.
• | (barra vertical) tem a precedência mais baixa de todas.

Representando tokens válidos de uma linguagem em expressões regulares

Se x for uma expressão regular, então:

• x * significa zero ou mais ocorrências de x.

  ou seja, pode gerar {e, x, xx, xxx, xxxx,…}

• x + significa uma ou mais ocorrências de x.

  ou seja, pode gerar {x, xx, xxx, xxxx…} ou xx *

• x? significa no máximo uma ocorrência de x

  ou seja, ele pode gerar {x} ou {e}.

[az] são todos os alfabetos minúsculos do idioma inglês.

[AZ] são todas as letras maiúsculas do idioma inglês.

[0-9] são todos os dígitos naturais usados ​​em matemática.

Representando a ocorrência de símbolos usando expressões regulares

letra = [a - z] ou [A - Z]

dígito = 0 | 1 | 2 | 3 | 4 5 | 6 | 7 | 8 | 9 ou [0-9]

sinal = [+ | -]

Representando tokens de linguagem usando expressões regulares

Decimal = (sinal) ^? (dígito) ⁺

Identificador = (letra) (letra | dígito) *

O único problema que resta ao analisador léxico é como verificar a validade de uma expressão regular usada na especificação dos padrões de palavras-chave de uma linguagem. Uma solução bem aceita é usar autômatos finitos para verificação.