Análise Léxical

Análise Léxical

Princípios

O objetivo da análise léxica é, dada uma sequência de texto:

• Produzir uma sequência de tokens;
• Limpar espaços em branco e comentários.
• Não é muito complicada em tempo de execução,
• Podemos usar funcionalismos interessantes e bastante gerais.

Tokens Lexicais

Pertencem a um conjunto finito de tipos:

1. ID: foo, n14
2. NUM: 73, 0
3. REAL: 0.0, 5.5e-10
4. IF: if
5. COMMA: ,
6. NOTEQ: !=
7. LPAREN: (
8. RPAREN: )

Comentários, directivas e macros do preprocessador, e espaços em branco não geram tokens!

Tokens Lexicais: um exemplo

float match0(char *s) /* find a zero */
{ if (!strncmp(s,"0.0", 3))
    return 0.;
}

results in:

FLOAT ID(match0) LPAREN CHAR STAR ID(s) RPAREN LBRACE IF LPAREN BANG ID(strncmp) LPAREN ID(s) COMMA STRING(0.0) COMMA NUM(3) RPAREN RPAREN RETURN REAL(0.0) SEMI RBRACE EOF

Expressões Regulares

Linguagem é um conjunto de sequências de símbolos (strings). Símbolos são obtidos de alfabetos.

Expressões regulares descrevem linguagens:

Símbolo:

se a é símbolo, a é expressão regular;

Alternação:

M|N.

Concatenação:

M . N (ou MN).

Epsilon:

eps é a linguagem cuja única expressão é a string vazia.

Repetição:

M^* é o fecho de Kleene, isto é uma concatenação de 0 ou mais strings em M.

Exemplos: (0|1)*0; b^*(abb^*)^*(a|eps); (a|b)^*aa(a|b)^*.

Abbrv: [abw-z], M⁺.

Expressões Regulares: Análise Léxical

if                   {return IF;}
[a-z][a-z0-9]*       {return ID;}
[0-9]+               {return NUM;}
([0-9]+"."[0-9]*)|
 ([0-9]+"."[0-9]*)   {return REAL;}
("--"[a-z]*"\n")|
 (" "|"\n"|"\t")+    {/* do nothing */}
.                    { error(); }

Regras:

• Completa: tudo deve ser capturado!
• Desambiguação:
  • Emparelhamento Máximo (longest match) ganha;
  • Prioridade de regras.

Autómatos Finitos

Para implementar expressões regulares:

• Número finito de Estados;
• Arestas que ligam estados;
• cada aresta é nomeada com um simbolo;
• Um estado é o estado inicial;
• Alguns estados são finais.

Deterministicos:

se duas aresta saindo do mesmo estado nunca têm o mesmo símbolo;

Aceita string:

Depois de seguir n transições para string de tamanho n chega a estado final.

Linguagem:

strings aceites.

Autómatos Finitos: exemplos

IF:

ID:

NUM:

REAL:

Autómatos Finitos: Combinação

Autómato Combinado:

Codificação: matriz de transição

int edges[][256] = { 
/*      {......,0 1 2,..-..,e f g h i j...}*/
/* 0 */ {0,0,..,0,0,0,..0..,0,0,0,0,0,0...},
/* 1 */ {0,0,..,7,7,7,..9..,4,4,4,4,2,4...},
/* 2 */ {0,0,..,4,4,4,..0..,4,3,4,4,2,4...},
.....
}

Matriz de finalidade: cada estado final corresponde a acções.

Autómatos Finitos: Solução Máxima

Ideia:

• Lembrar a última vez que estivemos num estado final:
  1. LastFinal: número do último estado final;
  2. InputPositionAtLastFinal
• Quando encontramos um estado morto (não final sem transições) voltamos para esse estado.

Como gerar o nosso autómato finito?

Autómatos Finitos Não-Deterministicos

Alguns exemplos, strings com tamanho múltiplo de 2 ou 3:

a mesma linguagem:

É fácil gerar autómatos não determínisticos a partir de expressões regulares:

Autómatos Finitos Não-Deterministicos

a

eps

M|N

Autómatos Finitos Não-Deterministicos

M.N

M^*

Conversão de NFA para DFA

Ideia: tentar todas as possibilidades ao mesmo tempo,

1. edge(s,c) é o conjunto de todos os estados que se podem atingir seguindo vértice c desde o estado s.
2. fecho(S) em que S é um conjunto de estados, é o conjunto de estados que se podem atingir através de vértices eps.
3. DFAedge(d,c) = fecho(uniao(edge(s,c), s  em d));
4. Começamos a partir de s₁ e seguimos toadas as transições possíveis.
5. Estado é final se algum estado correspondente da DFA é final.
6. Termina? Óptimo?

Programa Lex

Cada tipo é associado a uma expressão regular e uma acção:

1. includes e declarações.
2. abreviações e declarações de estado,

   digits [0-9]+ substituido por {digits}.

3. Expressões regulares e acções (código C).
4. Variáveis: yytext, texto, yyleng, charPos, EM_tokPos usa ADJ para saber posições inicial do erro, yylval (uma union) para valores semânticos.

Lex: Exemplo

{
/* Declarações C */
#include "tokens.h"
#include "errormsg.h"
union {int ival; string sval; double fval;}
    yylval;
int charPos = 1;
#define ADJ (EM_tokPos=charPos,charPos+=yyleng)
%}
/* Definições Lex */
digits [0-9]+
%%
/* Expressões regulares e acções */
if                {ADJ; return IF;}
[a-z][a-z0-9]*    {ADJ;
                   yylval.sval=String(yytext);
                   return(ID);}
{digits}          {ADJ; yylval.ival =
                   atoi(yytext);return(NUM);}
({digits}"."[0-9]*)|([0-9]*"."{digits}) 
                  {ADJ; yylval.fval=
                   atof(yytext);return(REAL);}
("--"[a-z]*"\n"*"\n")|(" "|"\n"|"\t")+ {ADJ;}
. {ADJ; EM_error("illegal character");}

Lex: Estados Iniciais

Às vezes é conveniente misturar espaços e expressões regulares (eg, comentários).

%start INITIAL COMMENT
%%
<INITIAL>if      {ADJ; return IF;}
<INITIAL>[a-z]+  {ADJ;
                   yylval.sval=String(yytext);
                   return(ID);}
<INITIAL>"(*"    {ADJ; BEGIN COMMENT;}
<INITIAL>.       {ADJ;
                   EM_error("illegal char");}
<COMMENT>"*)"    {ADJ; BEGIN INITIAL;}
<COMMENT>.       {ADJ;}
                 {BEGIN INITIAL; yyless(1);}

Comentários aninhados?

Análise Léxical