Análise Léxica

Análise Léxica 

Funções

·         Encontrar Lexemas

·         Guarda a numeração das linhas

·         Inserir ids na tabela de símbolos

·         Identificar tokens

·         Identificar constantes

·         Identificar Erros Léxicos

index = 2*cont + 17LL + 0.2 + 0x12;

Lexema	Token
index	identificador
=	sinal_igual
2	constante inteiro
*	Asterisco
cont	identificador
+	sinal_mais
17LL	constante long long
0.2	Constante float
0x12	Constante hexadecimal

Observe que o seguinte código não contém nenhum erro léxico:

if ( a > ) {

 a = 2;

}

Por outro lado, o seguinte trecho de código terá um erro léxico, lexema não identificado.

a = 2b;

Considerando que nenhum identificador pode começar com um dígito então 2b não é identificador válido.

Descrevendo Formal Tokens

Podemos descrever um identificador da seguinte maneira:

Uma letra minúscula ou maiúsculas ou underline seguida um ou mais letras minúsculas ou maiúsculas   ou um dígito ou um underline.

Podemos descrever formalmente utilizando o seguinte dispositivo formal:

Essa figura representa um autômato que pode ser descrito da seguinte maneira:

DFA = S,d,Q₀,F>

Q = conjunto de estados

S = Alfabeto

d Função de transição TOTAL

d : Q x S ® Q

A função recebe um estado e um símbolo do alfabeto e devolve um novo estado.

Q₀ Estado Inicial Q₀ Î Q

F    Estados Finais F Í Q

Exemplo:

Q = {q0,q1,q2,q3}

S = {a,b}

Q₀=q0

F = {q3}

d	a	b
q0	q1	q2
q1	q0	q3
q2	q3	q0
q3	q2	q1

Algumas strings que pertencem a essa linguagem do autômato L_A:

ab Î L_A

ba  Î L_A

bbab Î L_A

aaba Î L_A

Que linguagem está sendo descrita por esse autômato?

Observe que nesse autômato, todas as strings tem uma quantidade ímpar de a’s e b’s com tamanho maior que 1. Com um modelo simples descrevemos formalmente um dispositivo capaz de reconhecer qualquer string dessa linguagem.

Expressão Regular

É outra forma concisa e flexível de descrever unidades léxicas.

e é uma expressão regular.  (caractere vazio é uma expressão regular).

a Î S^* então a e (a) são expressões regulares. (qualquer string formada pelo nosso alfabeto é uma expressão regular).

 a e b são expressões regulares então

ab é uma expressão regular (concatenação)

a|b é uma expressão regular (união)

a⁺ é uma expressão regular (1 ou +)

a^* é uma expressão regular (0 ou +)

a? é uma expressão regular (0 ou 1)

Exemplos:

‘0’’1’ = {‘01’}

‘0’|’1’ = {‘0’,’1’}

‘0’⁺ = {‘0’,’00’,’000’,’0000’,...}

‘0’^* = {e,‘0’,’00’,’000’,’0000’,...}

‘0’? = {e,‘0’}

‘0’^*’1’⁺={‘1’,’’}

Identificador usando expressão regular

(‘a’...’z’|’A’...’Z’|’_’) (‘a’...’z’|’A’...’Z’|’_’|’0’...’9’)^*

ANTLR

Expressão regular

ID  :     ('a'..'z'|'A'..'Z'|'_') ('a'..'z'|'A'..'Z'|'0'..'9'|'_')*

    ;

Diagrama de Sintaxe