4 AnaliseLexica Parte2 - Compiladores CEFET MG

Prévia do material em texto

Compiladores 
Prof.ª Kecia Aline Marques Ferreira 
CEFET-MG 
 
Análise Léxica 
1 
Análise Léxica 
• Implementação de Analisador Léxico 
• Geradores de Analisadores Léxicos 
 
2 
3 
Implementação de Analisador 
Léxico 
Implementação de Analisador Léxico 
 
• Uma estratégia para implementação de Analisador Léxico consiste em: 
 
– Combinar todos os diagramas de transição em um único diagrama (AFD) 
 
– A entrada é processada até que não haja mais estado possível seguinte 
 
– Há duas maneiras principais de se implementar código a partir de um AFD: 
implementação dirigida por tabela de transição (baseada nos estados) e 
codificar comportamento direto no código. 
 
 
 
 
 
 
 
4 
Implementação de Analisador Léxico 
 
1. Implementação dirigida por tabela de transição: 
 
– Usa uma variável estado: armazena o estado corrente do AFD 
– Loop até encontrar fim de arquivo: verifica o caractere lido e computa o novo estado 
– Implementação gasta a maior parte do tempo computando o novo estado 
 
caractere = nextChar(); 
estado = estadoInicial; 
enquanto (não fim de arquivo){ 
 escolha (estado){ 
 0: se (caractere == ‘<’) estado = 1; 
 senão se (caractere == ‘=’) estado = 5; 
 ... 
 1: caractere = nextChar(); 
 se (caractere == ‘=’) estado = 3; 
 senão estado = 4; 
 ... 
 5: reconhece operador relacional de igualdade 
 estado = estadoInicial; 
 pare; 
 ... 
 } 
 
} 
 
 
 
 
5 
Implementação de Analisador Léxico 
 
2. Codificar comportamento direto no código 
 
– É uma maneira alternativa de implementar o comportamento do AFD 
 
– Não usa explicitamente uma variável para armazenar o estado corrente do 
AFD 
 
– Loop até encontrar fim de arquivo: verifica o caractere lido e computa 
aceitação 
 
 
 
 
 
 6 
Implementação de Analisador Léxico 
 
Exemplo de implementação: 
 
– Tag: classe que define as constantes para os tokens 
 
– Token: representa um token genérico. Contém a constante que representa o 
token. 
 
– Num: representa um token número 
 
– Word: representa um token de palavras reservadas, identificadores e tokens 
compostos como && e != 
 
– Lexer: classe que implementa o analisador léxico. Seu constrututor insere as 
palavras reservadas na tabela de símbolos. Possui um método scan que 
devolve um Token 
 
 
7 
Classe Tag 
public class Tag { 
 public final static int 
 //Palavras reservadas 
 PRG = 256, 
 BEG = 257, 
 END = 258, 
 TYPE = 259, 
 INT = 260, 
 CHAR = 261, 
 BOOL = 262, 
 … 
 //Operadores e pontuação 
 ... 
 EQ = 288, 
 GE = 289, 
 LE = 290, 
 NE = 291, 
 ... 
 //Outros tokens 
 NUM = 278, 
 ID = 279; 
} 
 
 
 
8 
Classe Token 
public class Token { 
 
 public final int tag; //constante que representa o token 
 
 public Token (int t){ 
 tag = t; 
 } 
 
 public String toString(){ 
 return "" + tag; 
 } 
} 
 
 
 
9 
Classe Num 
public class Num extends Token{ 
 
 public final int value; 
 
 public Num(int value){ 
 super(Tag.NUM); 
 this.value = value; 
 } 
 
 public String toString(){ 
 return "" + value; 
 } 
} 
 
 
10 
Classe Word 
public class Word extends Token{ 
 
 private String lexeme = ""; 
 
 public static final Word and = new Word ("&&", Tag.AND); 
 public static final Word or = new Word ("||", Tag.OR); 
 public static final Word eq = new Word ("==", Tag.EQ); 
 public static final Word ne = new Word ("!=", Tag.NE); 
 public static final Word le = new Word ("<=", Tag.LE); 
 public static final Word ge = new Word (">=", Tag.GE); 
 public static final Word True = new Word ("true", Tag.TRUE); 
 public static final Word False = new Word ("false", Tag.FALSE); 
 
 
 public Word (String s, int tag){ 
 super (tag); 
 lexeme = s; 
 } 
 
 public String toString(){ 
 return "" + lexeme; 
 } 
} 
11 
Lexer 
import java.io.*; 
import java.util.*; 
 
 
public class Lexer { 
 public static int line = 1; //contador de linhas 
 private char ch = ' '; //caractere lido do arquivo 
 private FileReader file; 
 
 private Hashtable words = new Hashtable(); 
 
 /* Método para inserir palavras reservadas na HashTable */ 
 private void reserve(Word w){ 
 words.put(w.getLexeme(), w); // lexema é a chave para entrada na 
 //HashTable 
 } 
 
 
12 
Lexer 
 /* Método construtor */ 
 public Lexer(String fileName) throws FileNotFoundException{ 
 
 try{ 
 file = new FileReader (fileName); 
 } 
 catch(FileNotFoundException e){ 
 System.out.println("Arquivo não encontrado"); 
 throw e; 
 } 
 
 //Insere palavras reservadas na HashTable 
 reserve(new Word ("if", Tag.IF)); 
 reserve(new Word ("program", Tag.PRG)); 
 reserve(new Word ("begin", Tag.BEG)); 
 reserve(new Word ("end", Tag.END)); 
 reserve(new Word ("type", Tag.TYPE)); 
 reserve(new Word ("int", Tag.INT)); 
 ... 
 } 
13 
Lexer 
 
 /*Lê o próximo caractere do arquivo*/ 
 private void readch() throws IOException{ 
 ch = (char) file.read(); 
 } 
 
 
 
 /* Lê o próximo caractere do arquivo e verifica se é igual a c*/ 
 private boolean readch(char c) throws IOException{ 
 readch(); 
 if (ch != c) return false; 
 ch = ' '; 
 return true; 
 } 
14 
Lexer 
 public Token scan() throws IOException{ 
 
 //Desconsidera delimitadores na entrada 
 for (;; readch()) { 
 if (ch == ' ' || ch == '\t' || ch == '\r' || ch == '\b') continue; 
 else if (ch == '\n') line++; //conta linhas 
 else break; 
 } 
 
 
 switch(ch){ 
 //Operadores 
 case '&': 
 if (readch('&')) return Word.and; 
 else return new Token('&'); 
 case '|': 
 if (readch('|')) return Word.or; 
 else return new Token('|'); 
 case '=': 
 if (readch('=')) return Word.eq; 
 else return new Token('='); 
15 
Lexer 
 case '<': 
 if (readch('=')) return Word.le; 
 else return new Token('<'); 
 case '>': 
 if (readch('=')) return Word.ge; 
 else return new Token('>'); 
 } 
 
 
 //Números 
 if (Character.isDigit(ch)){ 
 int value=0; 
 do{ 
 value = 10*value + Character.digit(ch,10); 
 readch(); 
 }while(Character.isDigit(ch)); 
 return new Num(value); 
 } 
16 
Lexer 
 //Identificadores 
 if (Character.isLetter(ch)){ 
 StringBuffer sb = new StringBuffer(); 
 do{ 
 sb.append(ch); 
 readch(); 
 }while(Character.isLetterOrDigit(ch));String s = sb.toString(); 
 Word w = (Word)words.get(s); 
 if (w != null) return w; //palavra já existe na HashTable 
 w = new Word (s, Tag.ID); 
 words.put(s, w); 
 return w; 
 } 
 
 //Caracteres não especificados 
 Token t = new Token(ch); 
 ch = ' '; 
 return t; 
 
 } 
 
 
} 
17 
18 
Geradores de Analisadores 
Léxicos 
Gerador de Analisador Léxico 
 
• Lex, Flex, Javacc e Jflex 
 
• Jflex é um gerador de analisador léxico para Java 
 
• http://jflex.de 
 
• Executar java –jar Jflex.jar 
 
• Entrada para Jflex: um arquivo com extensão .flex contendo especificação léxica da 
linguagem 
 
• Saída de Jflex: um arquivo denominado Yylex.java que contém a implementação em Java de 
um analisador léxico para a linguagem especificada. 
 
 
 
 
19 
Gerador de Analisador Léxico 
 
 
 
 
20 
Gerador de Analisador Léxico 
 
• O arquivo de entrada para Jflex é constituído por três partes, separadas por 
%% 
 
– Código do usuário: contém o código que o usuário deseja que seja incluído no topo da classe 
gerada por Jflex 
 
– Opções e declarações: contém opções, código a ser incluído na classe gerada e macros 
(abreviações para expressões regulares utilizadas nas especificações léxicas) 
 
– Regras léxicas: contém expressões regulares e ações a serem executadas quando uma 
sequência de caracteres casar com o padrão especificado pela expressão regular. 
 
Código do usuário 
%% 
Opções e declarações 
%% 
Regras léxicas 
 
21 
Gerador de Analisador Léxico 
 
• Em qualquer parte do arquivo de entrada do Jflex, comentários são 
permitidos. 
 
• Comentários são do tipo /* */ ou // (como em Java e C/C++) 
 
 
 
22 
Gerador de Analisador Léxico 
 
• Código do usuário: contém o código que o usuário deseja que seja 
incluído no topo da classe gerada por Jflex 
 
– imports 
 
– comentários 
 
 
• Opções e declarações: 
 Cada linha contendo uma opção deve começar com %. 
 
– %class “classname”: indica o nome da classe a ser gerada por Jflex . No exemplo, a 
classe gerada será nomeada como Lexer: %class Lexer 
 
 
 23 
Gerador de Analisador Léxico 
 
– %implements “interface name” [, interface name 2, ...]: faz a classe gerada implementar 
a interface indicada. Se houver mais de uma linha deste tipo, a classe gerada 
implementará todas as interfaces correspondentes. 
 
– %extends “class name”: faz a classe gerada estender a classe indicada. Deve haver 
apenas uma opção deste tipo no arquivo. 
 
– %public: faz a classe gerada ser pública. Por padrão, a classe gerada não tem 
modificador de acesso. 
 
– %{ ... %} : define variáveis membro ou funções membro a serem incluídas na classe 
gerada. Esses membros podem ser utilizadas nas ações descritas na definição léxica. 
 
Exemplo: o código abaixo indica que a classe gerada deverá conter o atributo indicado 
%{ 
 private int comment_count = 0; 
%} 
 
 
24 
Gerador de Analisador Léxico 
 
 
– %line: indica que o analisador léxico deve possuir um contador de linhas. A variável no 
código gerado que representa esse contador é yyline. 
 
– %column: indica que o analisador léxico deve possuir um contador de colunas. A 
variável no código gerado que representa esse contador é yycolumn. 
 
– %switch: indica que o código da análise léxica deve ser a implementação de um AFD. 
 
 
 
 
 
 
25 
Gerador de Analisador Léxico 
• Após as opções, indicam-se as macros 
 
• Macros são abreviações para expressões regulares 
 
• Macros são utilizadas para facilitar a especificação léxica 
 
• Uma declaração de macro é constituída por 
 macroIdenficador = expressão regular que a macro representa 
 
• Essa expressão regular também pode conter macros definidas. 
 
• A expressão regular não deve conter os caracteres ^, \ e $ 
 
 
26 
Gerador de Analisador Léxico 
• Notação para expressão regular no Jflex: 
 
– [0-9]: dígitos de 0 a 9 
 
– [a-z]: letras minúsculas 
 
– [a -zA-z]: letras minúsculas e maiúsculas 
 
– [a-zA-Z0-9]: letras e dígitos 
 
– [a-zA-Z0-9_]:letras, dígitos e underscore 
 
– [abc]: equivale a a | b | c 
 
 
 
 
 
 
27 
Gerador de Analisador Léxico 
 
Se a e b são expressões regulares: 
 
– a | b : a ou b (a + b) 
 
– ab: concatenação 
 
– a*: fecho de Kleene 
 
– a+: equivale a aa* 
 
– a?: equivale a a | λ 
 
– !a: todas as cadeias, exceto aquela representada por a 
 
– ~a: “até a”. Casa com tudo até a primeira ocorrência de a (incluindo a). Por exemplo, 
“/*” ~”*/” é uma expressão regular para comentários em C. 
 
 
 
28 
Gerador de Analisador Léxico 
 
– a{n}: a repetido n vezes. Por exemplo, a{3} representa a cadeia aaa 
 
– a{n,m}: a repetido pelo menos n e no máximo m vezes. 
 
– (a) : o mesmo que a 
 
– ^a: indica que a deve aparecer no início de uma linha 
 
– a$: indica que a deve aparecer no final de uma linha 
 
Exemplos de macros: 
 
ALPHA=[A-Za-z] 
DIGIT=[0-9] 
Ident = {ALPHA} ({ALPHA}|{DIGIT}|_)* 
 
 
 
29 
Gerador de Analisador Léxico 
 
• Especificação Léxica: contém um conjunto de expressões regulares e 
ações a serem executadas quando o analisador léxico encontrar uma 
sequência de caracteres que casa com a expressão regular 
 
– A ação é 
• um trecho de código Java delimitado por { } ou 
• a ação especial |, que indica que a ação a ser tomada é a mesma da expressão 
seguinte 
 
expressão1 | 
expressão2 | 
expressão3 { ação 1} 
 
É o mesmo que 
 
expressão1 { ação1} 
expressão2 { ação1} 
expressão3 { ação1} 
 
 
30 
Gerador de Analisador Léxico 
 
• Jflex gera um arquivo contendo a classe que implementa o analisador 
léxico 
 
– Nome da classe: é aquele definido na opção %class. O nome padrão é Yylex.java 
 
– Construtor da classe: recebe como parâmetro um objeto do tipo java.io.Reader, que 
representa o arquivo fonte a ser analisado. 
 
– Método para análise léxica: yylex() retorna um Yytoken. Processa o arquivo de entrada 
até que haja um casamento com algum padrão definido na especificação léxica ou até 
que ocorra um erro ou final de arquivo seja encontrado. 
 
 
31 
Exemplo.jflex 
/* Este é um exemplo de utilização do JFlex */ 
 
%% 
 
 
%line 
%column 
 
%debug 
 
ALPHA=[A-Za-z] 
DIGIT=[0-9] 
NONNEWLINE_WHITE_SPACE_CHAR=[\ \t\b] 
NEWLINE=\r|\n|\r\n 
WHITE_SPACE_CHAR=[\n\r\ \t\b] 
Ident = {ALPHA}({ALPHA}|{DIGIT}|_)* 
 
%% 
 
 32 
Exemplo.jflex 
<YYINITIAL> { 
 "," { return (new Yytoken(0,yytext(),yyline,yychar,yychar+1)); } 
 ":" { return (new Yytoken(1,yytext(),yyline,yychar,yychar+1)); } 
 ";" { return (new Yytoken(2,yytext(),yyline,yychar,yychar+1)); } 
 "(" { return (new Yytoken(3,yytext(),yyline,yychar,yychar+1)); } 
 ")" { return (new Yytoken(4,yytext(),yyline,yychar,yychar+1)); } 
 "[" { return (new Yytoken(5,yytext(),yyline,yychar,yychar+1)); } 
 "]" { return (new Yytoken(6,yytext(),yyline,yychar,yychar+1)); } 
 "{" { return (new Yytoken(7,yytext(),yyline,yychar,yychar+1)); } 
 "}" { return (new Yytoken(8,yytext(),yyline,yychar,yychar+1)); } 
 "." { return (new Yytoken(9,yytext(),yyline,yychar,yychar+1)); } 
 "+" { return (new Yytoken(10,yytext(),yyline,yychar,yychar+1)); } 
 "-" { return (new Yytoken(11,yytext(),yyline,yychar,yychar+1)); } 
 "*" { return (new Yytoken(12,yytext(),yyline,yychar,yychar+1));} 
 "/" { return (new Yytoken(13,yytext(),yyline,yychar,yychar+1)); } 
 "=" { return (new Yytoken(14,yytext(),yyline,yychar,yychar+1)); } 
 "<>" { return (new Yytoken(15,yytext(),yyline,yychar,yychar+2)); } 
 "<" { return (new Yytoken(16,yytext(),yyline,yychar,yychar+1)); } 
 "<=" { return (new Yytoken(17,yytext(),yyline,yychar,yychar+2)); } 
 ">" { return (new Yytoken(18,yytext(),yyline,yychar,yychar+1)); } 
 ">=" { return (new Yytoken(19,yytext(),yyline,yychar,yychar+2)); } 
 "&" { return (new Yytoken(20,yytext(),yyline,yychar,yychar+1)); } 
 "|" { return (new Yytoken(21,yytext(),yyline,yychar,yychar+1)); } 
 ":=" { return (new Yytoken(22,yytext(),yyline,yychar,yychar+2)); } 
 
 33 
Exemplo.jflex 
 {DIGIT}+ { return (new 
Yytoken(42,yytext(),yyline,yychar,yychar+yylength())); } 
 
 {Ident} { return (new 
Yytoken(43,yytext(),yyline,yychar,yychar+yylength())); } 
} 
 
{NONNEWLINE_WHITE_SPACE_CHAR}+ { } 
 
{NEWLINE} { } 
 
. { 
 System.out.println("Illegal character: <" + yytext() + ">"); 
 Utility.error(Utility.E_UNMATCHED); 
} 
34 
Gerador de Analisador Léxico 
 
• O arquivo Exemplo.jflex é informado ao Jflex, que gera a classe chamada 
Yylex.java. 
 
• A classe Yylex utiliza as seguinte classes (de acordo com as ações 
especificadas) 
 
– Yytoken: especifica um token 
 
– Utility: contém mensagens de erro a serem exibidas 
 
 
 
 
35 
Yytoken.java 
 class Yytoken { 
 public int m_index; 
 public String m_text; 
 public int m_line; 
 public int m_charBegin; 
 public int m_charEnd; 
 
 Yytoken (int index, String text, int line, int charBegin, int charEnd) { 
 m_index = index; 
 m_text = text; 
 m_line = line; 
 m_charBegin = charBegin; 
 m_charEnd = charEnd; 
 } 
 
 public String toString() { 
 return "Text : "+m_text+ 
 "\nindex : "+m_index+ 
 "\nline : "+m_line+ 
 "\ncBeg. : "+m_charBegin+ 
 "\ncEnd. : "+m_charEnd; 
 } 
} 
 
 
 
36 
Utility.java 
 class Utility { 
 
 private static final String errorMsg[] = { 
 "Error: Unmatched end-of-comment punctuation.", 
 "Error: Unmatched start-of-comment punctuation.", 
 "Error: Unclosed string.", 
 "Error: Illegal character." 
 }; 
 
 public static final int E_ENDCOMMENT = 0; 
 public static final int E_STARTCOMMENT = 1; 
 public static final int E_UNCLOSEDSTR = 2; 
 public static final int E_UNMATCHED = 3; 
 
 public static void error(int code) { 
 System.out.println(errorMsg[code]); 
 } 
} 
 
 
 
 
37 
Execução do Analisador Léxico 
 
• Após a compilação das classes necessárias e da classe gerada por Jflex, 
para usar o analisador léxico 
 
 java Yylex nomeArquivoFonte 
 
 
• Exemplo 1: 
 
 b = 15023; 
 
 a=5; 
 
 soma = a + b; 
 
 
 
 
 
38 
Saída do Analisador Léxico 
 
 Saída do analisador léxico (em modo debug) 
 
line: 1 col: 1 match: --b-- 
action [49] { return (new Yytoken(43,yytext(),yyline,yychar,yychar+yylength()));} 
Text : b 
index : 43 
line : 0 
cBeg. : 0 
cEnd. : 1 
line: 1 col: 2 match: -- -- 
action [52] { } 
line: 1 col: 3 match: --=-- 
action [35] { return (new Yytoken(14,yytext(),yyline,yychar,yychar+1)); } 
Text : = 
index : 14 
line : 0 
cBeg. : 0 
cEnd. : 1 
line: 1 col: 4 match: -- -- 
action [52] { } 
line: 1 col: 5 match: --15023-- 
action [47] { return (new Yytoken(42,yytext(),yyline,yychar,yychar+yylength()));} 
Text : 15023 
index : 42 
line : 0 
cBeg. : 0 
cEnd. : 5 
... 
39 
Exercício 
Mostre uma implementação do método scan da classe Lexer que reconheça: 
 
- Identificadores: 
 letter_ → A | B | ... | Z | a | b | ... | z | _ 
 digit → 0 | 1 | ... | 9 
 id → letter_ (letter_| digit)* 
 
- Constantes numérica 
 0 | [1-9] ([0-9])* 
 
- Operadores 
 * / % != == > >= < <= 
40 
Referência Bibliográfica 
Compiladores – Princípios, técnicas e ferramentas. 
Aho, A. V et al. 2ª edição 
Capítulo 3 
Apêndice A: A.1, A.2 e A.3 
 
Jflex 
Disponível em http://jflex.de 
 
 
 
41