Analisador Léxico

Prévia do material em texto

Analisador 
Léxico – parte I 
Compiladores 
 
Mariella Berger 
Sumário 
 
• Analisador Léxico 
• Tokens, Lexemas e Padrões 
• Processo da Análise Léxica 
• Como implementar um analisador léxico? 
• Como descrever tokens? 
• Notação de expressões regulares 
SÍNTESE 
ANÁLISE 
As fases de um Compilador 
Análise Léxica 
Análise Sintática 
Análise Semântica 
Gerador de Código 
Intermediário 
Otimizador de 
Código 
Gerador de Código 
Analisador Léxico 
 
• O analisador léxico lê o programa fonte 
(caractere por caractere) e retorna os tokens 
formadores deste; 
 
• Um token descreve um padrão de caracteres 
tendo algum significado no programa fonte: 
• Identificadores 
• Operadores 
• Palavras chave 
• Números 
• Delimitadores, etc 
Análise Léxica 
montante := deposito_inicial + 60; 
montante Identificador 
:= Símbolo de atribuição 
deposito_inicial Identificador 
+ Símbolo de adição 
60 Número 
; Símbolo ponto e vírgula 
Analisador Léxico 
 
• Insere informação sobre identificadores na 
tabela de símbolo. 
 
• Expressões regulares são usada para descrever 
tokens (lexical constructs). 
 
• Um autômato finito (determinístico) pode ser 
usado na implementação de um analisador 
léxico. 
Tokens, Lexemas e Padrões 
 
• Um lexema é um conjunto de caracteres no 
programa-fonte que é reconhecido pelo padrão de 
algum token. 
• Exemplo: const pi = 3.1416; 
• A subcadeia pi é um lexema para o token identificador 
 
• Tratamos os tokens como símbolos terminais na 
gramática para a linguagem fonte. 
 
• São instâncias de uma mesma classe léxica 
(identificadores, número, etc) 
Tokens, Lexemas e Padrões 
 
• Na maioria das linguagens as seguintes construções 
são tratadas como tokens: 
• Palavraschave, operadores, identificadores, constantes, 
literais, strings, símbolos de pontuação (parênteses, 
vírgulas, etc) 
 
• Quando a sequência de caracteres pi aparece no 
programa fonte, um token representando um 
identificador é repassado ao parser 
 
• Na implementação transmitisse um inteiro associado 
ao token 
Exemplo de Tokens 
Processo de Análise Léxica 
Processo de Anáalise Léxica 
 É importante salientar que o Analisador Léxico 
desconsidera: 
 Espaços em branco 
 Tabs 
 Comentários de bloco 
 Comentários de linha 
Como implementar um 
Analisador Léxico? 
 
• Utilizar uma ferramenta que permita produzir 
um analisador léxico a partir de uma 
especificação baseada em expressões 
regulares 
 
• A partir de uma linguagem de programação 
convencional 
Como descrever Tokens 
 
• Expressões regulares são uma notação importante 
para especificar padrões 
• Cada padrão corresponde a um conjunto de 
cadeias 
• Em pascal, um identificador é uma letra seguida 
por zero ou mais letras ou dígitos 
 letra ( letra | dígito ) * 
• Nesta notação, a barra vertical significa ou, os 
parênteses servem para agrupar subexpressões, o 
asterisco significa “zero ou mais instâncias” com o 
resto da expressão significa concatenação 
Como descrever Tokens 
 
• Uma expressão regular (RE) é formada por um 
conjunto de regras. 
• Cada expressão regular denota uma 
linguagem L(R) 
Exemplo de linguagens 
 
• L(R) = é um linguagem definida por R 
 
 L(abc) = {abc} 
 
 L(hello|goodbye) = { hello, goodbye } 
 
 L(1(0|1)*) = todos os números binários que iniciam 
 com 1 
 
 L((a | b)(a | b)) = {aa, ab, ba, bb} 
 
 L((a)*) = {ε , a, aa, aaa, …} 
 
 L(a | a*b) = {?} 
Notação de Expressões 
Regulares 
Exemplos 
Exercícios 
 Defina expressões regulares para: 
 Números Romanos 
 Endereços de ips 
 Placas de carros 
 Números de telefones celulares no Brasil 
 Prefixos de rádios FM (102,3 MHz) 
 Número de matrícula na UFES 
 URL de páginas Web