Análise SintácticaTopIntrodução aos CompiladoresAnálise Léxical

Análise Léxical

Princípios

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

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:

Autómatos Finitos

Para implementar expressões regulares:

Características:
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:

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 s1 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?


vitor@cos.ufrj.br

Análise SintácticaTopIntrodução aos CompiladoresAnálise Léxical