silo tips_analise-lexica-o-papel-do-analisador-lexico_2

Prévia do material em texto

Compiladores – 1 
 http://erinaldosn.wordpress.com 
Análise Léxica 
 A varredura, ou análise léxica, é a fase de um compilador que lê o programa-
fonte como um arquivo de caracteres e o separa em marcas. Essas marcas são como 
palavras em uma linguagem natural. 
Exemplos de símbolos léxicos são as palavras reservadas, os identificadores, a 
constantes e os operadores da linguagem. Durante o processo de análise léxica, são 
desprezados caracteres não significativos como espaços em branco e comentários. 
Além de reconhecer os símbolos léxicos, o analisador também realiza outras 
funções, como armazenar alguns desses símbolos (identificadores e constantes) em 
tabelas internas e indicar a ocorrência de erros léxicos. 
Para implementar um analisador léxico à mão, é importante começar com um 
diagrama ou outra descrição para os lexemas de cada token. Podemos escrever código 
para identificar a cada ocorrência de cada lexema na entrada e retoranr informações 
sobre o token identificado. 
A tarefa efetuada pelo sistema de varredura é um caso especial de casamento de 
padrões. Os métodos de especificação e reconhecimento de padrões que se aplicam no 
processo de varredura são basicamente os de expressões regulares e autômatos finitos. 
Podemos produzir um analisador léxico automaticamente especificando os 
padrões dos lexemas para um gerador de analisador léxico e compilando esses padrões 
em código que funciona como um analisador léxico. 
O papel do analisador léxico 
A tarefa principal do analisador léxico é ler os caracteres da entrada do programa 
fonte, agrupá-los em lexemas e produzir como saída uma sequência de tokens para cada 
lexema no programa fonte. 
 Token: é um par consistindo em um nome e um valor de atributo opcional. 
 Padrão: é uma descrição da forma que os lexemas de um token podem assumir 
 Lexema: é uma sequência de caracteres no programa fonte que casa com o padrão 
para um token e é identificado pelo analisador léxico como uma instância desse 
token. 
O fluxo de tokens é enviado ao analisador sintático para que a análise seja 
efetuada 
Interações entre o analisador léxico e o analisador sintático: 
 
 
 
 
 
 
 
 
O analisador léxico é a parte do compilador que lê o texto fonte, ele pode 
realizar outras tarefas, como remover comentários e o espaço em branco. Outra tarefa é 
correlacionar as mensagens de erro geradas pelo compilador com o programa fonte. 
Os motivos que separam as fases de análise léxica e análise sintática são: 
1. Simplicidade do projeto. 
Programa 
fonte 
Analisador 
léxico 
Analisador 
sintático 
para análise 
semântica 
token 
obter 
token 
Tabela de 
símbolos 
Expressões Regulares 
 http://erinaldosn.wordpress.com 
2. A eficiência do compilador é melhorada. 
3. A portabilidade do compilador é melhorada. 
Os analisadores léxicos são divididos em uma cascata de dois processos: 
1. O escandimento consiste no processo simples de varredura da entrada sem se 
preocupar com a remoção de comentários e a compactação de espaços em branco 
consecutivos em apenas um caractere. 
2. A análise léxica, onde o analisador léxico produz a sequência de tokens como saída. 
Atributos de tokens 
 Quando mais de um lexema casar com um padrão, o analisador léxico precisa 
oferecer às fases subsequentes do compilador informações adicionais sobre qual foi o 
lexema em particular casado. 
Exemplo: o padrão para o token number casa com 0 e 1. 
 Assim, em muitos casos, o analisador léxico retorna ao analisador sintático o 
nome do token e um valor de atributo que descreve o lexema representado pelo token. O 
nome do token influencia as decisões durante a análise sintática, enquanto o valor do 
atributo influencia a tradução dos tokens após o reconhecimento sintático. 
 Normalmente as informações sobre um identificador (associa muitas 
informações ao token) são mantidas na tabela de símbolos. Assim, o valor de atributos 
apropriado para um identificador é um apontador para a sua entrada na tabela de 
símbolos. 
 Em certos pares (operadores, pontuação e palavras chave) não há necessidade de 
um valor de atributo. 
 Um compilador típico armazena uma cadeia de caracteres representando uma 
constante e como valor de atributo um apontador para essa cadeia. 
Erros léxicos 
 É difícil para um analisador léxico saber, sem o auxílio de outros componentes, 
que existe um erro no código fonte. 
 Por exemplo, um analisador léxico não tem como saber se fi é a palavra-chave 
if escrita errada ou um identificador de função não declarada. Como fi é um lexema 
válido para o token id, o analisador léxico precisa retornar o token id ao analisador 
sintático e deixar que alguma outra fase do compilador trate o erro devido à 
transposição das letras. 
O processo de varredura 
As unidades lógicas geradas pela varredura são denominadas marcas (tokens). 
As marcas são entidades lógicas, usualmente definidas como um tipo enumerado. 
typedef enum { 
 if, then, else, plus, minus, num, id,... 
} TokenType; 
 Em uma linguagem sem tipos enumerados, como em C, temos que definir as 
marcas diretamente como valores numéricos simbólicos. 
# define IF 256 
# define THEN 257 
# define ELSE 258 
… 
 Esses números começam em 256 para evitar confusão com valores numéricos da 
tabela ASCII. 
 Compiladores – 3 
 http://erinaldosn.wordpress.com 
 Um sistema de varredura deve computar pelo menos tantos atributos de uma 
marca quanto necessário para possibilitar a continuidade do processamento. Como o 
sistema de varredura precisará possivelmente computar diversos atributos para cada 
marca, é frequentemente útil coletar todos os atributos em um único tipo de dado 
estruturado, denominado registro marca (TokenRecord). 
 Esse registro poderia ser declarado em C como: 
typedef struct { 
 TokenType tokenval; 
 char * stringval; 
 int numval; 
} TokenRecord; 
 Um arranjo mais comum é o sistema de varredura retornar apenas o valor da 
marca e colocar os outros atributos em variáveis que possam ser acessadas por outras 
partes do compilador. 
 A varredura não converte todo o programa fonte em uma sequência de tokens de 
uma vez. A varredura ocorrerá sob o controle de uma analisador sintático, retornando a 
marca seguinte demandada por meio de uma função com a seguinte declaração em C: 
TokenType getNextToken(void); 
 A função getNextToken retornara a próxima marca fornecida, bem como 
computadrá aributos adicionais, como o valor em caracteres da marca. A cadeia de 
caracteres de entrada geralmente é armazenada em um repositório ou fornecida pelos 
recursos de entrada do sistema. 
Exemplo: considere a seguinte linha de código fonte em C: 
a[index] = 4 + 2; 
 Suponha que essa linha de código seja armazenada em um repositório de 
entrada, com o próximo caractere de entrada indicado pela seta: 
 a [ i n d e x ] = 4 + 2 
 
 
 A ativação de getNextToken precisará saltar o quatro brancos seguintes, 
reconhecer a cadeia de caracteres ‘a’ como a próxima marca, e retornar o valor de marca 
ID como próxima marca. 
 a [ i n d e x ] = 4 + 2 
 
 
 Uma chamada subsequente de getNextToken iniciará o reconhecimento a partir 
do caractere de colchete à esquerda. 
Bufferes de entrada 
 Devido à quantidade de tempo necessária para processar caracteres e o grande 
número de caracteres que precisam ser processados durante a compilação de um 
programa fonte grande, foram desenvolvidas técnicas especializadas de buffering para 
reduzir o custo exigido no processamento em um único caractere de entrada. 
 Um esquema importante envolve dois bufferes que são recarregados 
alternadamente. 
 E = M * C * * 2 EOF 
 
 forward 
 lexemeBegin 
Expressões Regulares 
 http://erinaldosn.wordpress.com 
 Cada buffer possui o mesmo tamanho N, e N normalmente corresponde ao 
tamanho de um bloco de disco (4096 bytes). 
 Usando um sistema de leitura do sistema, podemos ler N caracterespara um 
buffer. Se restarem menos de N caracteres no arquivo de entrada, então um caractere 
especial, representado por eof, marca o fim do arquivo fonte. 
 São mantidos dois apontadores para a entrada: 
 lexemeBegin marca o início do lexema corrente; 
 forward lê adiante, até que haja casamento de padrão 
Uma vez que o próximo lexema é determinado, forward é configurado para 
apontar para o seu último caractere à direita, e lexemeBegin é configurado para apontar 
para o caractere imediatamente após o lexema recém-encontrado. 
Sentinelas 
 Se usarmos o esquema de pares de buffer precisaremos verificar, sempre que 
avançarmos o apontador forward, se o movemos para fora de um dos buffers; nesse 
caso também precisaremos recarregar o outro buffer. 
 Para cada caractere lido fazemos dois testes: um para o fim do buffer e o outro 
para determinar qual caractere foi lido. 
 Sentinela é um caractere especial que não pode fazer parte do programa fonte, e 
uma escolha natural é o caractere de fim de arquivo, eof. 
 E = M * EOF C * * 2 EOF EOF 
 
 forward 
 lexemeBegin 
switch (* forward++) { 
 case eof: 
 if (forward está no fim do primeiro buffer){ 
 recarrega segundo buffer; 
 forward = início do segundo buffer; 
 } 
 else if (forward está no fim do segundo buffer){ 
 recarrega primeiro buffer; 
 forward = início do primeiro buffer; 
 } 
 else /* eof dentro de um buffer marca o fim da 
entrada */ 
 termina análise léxica; 
 break; 
 casos para os outros caracteres 
} 
Gramáticas e linguagens regulares 
 Uma gramática G é um mecanismo para gerar as sentenças (ou palavras) de uma 
linguagem e é definida pela quádrupla: 
(N, T, P, S) 
onde: 
 N é um conjunto de símbolos não-terminais (variáveis). 
 T é um conjunto de símbolos terminais (constantes), e T N = . 
 P é um conjunto de regras de produção (regras sintáticas). 
 Compiladores – 5 
 http://erinaldosn.wordpress.com 
 S é o símbolo inicial da gramática (S N). 
 As regras de produção são representadas por → e definem o mecanismo de 
geração das sentenças da linguagem. 
Cadeias e linguagens 
 Um alfabeto é qualquer conjunto finito de símbolos (letras, dígitos e sinais de 
pontuação). 
 O conjunto {0, 1} é o alfabeto binário. ASCII é um alfabeto usado em muitos 
sistemas de software. Unicode é um alfabeto do mundo inteiro, que inclui 
aproximadamente 100.000 caracteres. 
 Uma cadeia (string) em um alfabeto é uma sequência finita de símbolos retirada 
desse alfabeto. Sentença e palavra são sinônimos de cadeia. 
 O tamanho de uma cadeia s é o número de ocorrências de símbolos em s. 
Exemplo: banana é uma cadeia de tamanho seis. A cadeia vazia, indicada por , é 
uma cadeia de tamanho zero. 
 Uma linguagem é qualquer conjunto contável de cadeias de algum alfabeto fixo. 
Linguagens abstratas como (conjunto vazio) ou (conjunto contendo apenas a 
cadeia vazia) são linguagens com essa definição, assim como todos os programas C 
sintaticamente bem formados. 
Operação sobre linguagens 
 Na análise léxica, as operações mais importantes sobre as linguagens são união, 
concatenação e fechamento. 
Operação Definição e notação 
União de L e M L M = {s | s está em L ou s está em M} 
Concatenação de L e M LM = {st | s está em L e t está em M} 
Fecho Kleene de L L* = 
 A união é a conhecida operação sobre conjuntos. 
A concatenação de linguagens são todas as cadeias formadas a partir de uma 
cadeia da primeira linguagem e uma cadeia da segunda linguagem, em todas as formas 
possíveis, e concatenando-as. 
O fecho (Kleene) de uma linguagem L, indicado por L*, é o conjunto de cadeias 
obtidas concatenando L zero ou mais vezes. 
L
0
, concatenação de L zero vezes, { } 
L
i
 é 
Li-1 
L. 
L
+
 é o mesmo que o fecho Kleene, mas sem o termo L
0
. 
Derivação 
 Uma derivação é um par da relação denotada por , com domínio (N T)
+
 e 
contra-domínio em (N T)*, e é representada de forma infixada como . 
 O conjunto (N T)* é o conjunto de sentenças que podem ser formadas por 
símbolos de N e T, incluindo a palavra vazia (comprimento zero), e (N T)
+
 = (N 
T)* – { }. 
 As sequencias de símbolos de e são chamadas formas sentenciais. 
 Uma derivação é a substituição de uma sequência de símbolos numa forma 
sentencial de acordo com uma regra de produção. 
Expressões Regulares 
 http://erinaldosn.wordpress.com 
Linguagem gerada 
 A linguagem gerada por G, L(G), é o conjunto formado por todas as sentenças 
de símbolos terminais deriváveis a partir do símbolo inicial S: 
L(G) = {s | s é um elemento de T* e S 
+
 s} 
 As seguintes convenções representam os símbolos gramaticais (terminais e não-
terminais) e as formas sentenciais (sequência de símbolos terminais e não-terminais). 
1. Símbolos que representam terminais: 
 Letras minúsculas do alfabeto. 
 Operadores em geral. 
 Símbolos que representam pontuação e os delimitadores. 
 Dígitos. 
 Cadeias de caracteres como if, then, begin, ... 
2. Símbolos que representam não-terminais: 
 Letras maiúsculas do alfabeto. 
 Qualquer string delimitador por < e >. 
3. Símbolos que representam formas sentenciais: 
 As letras minúsculas do alfabeto grego: , , , ,... 
Expressões regulares 
 Expressões regulares representam padrões de cadeias de caracteres. Uma 
expressão regular r é completamente definida pelo conjunto de cadeias de caracteres 
com as quais ela casa. Esse conjunto é denominado linguagem gerada pela expressão 
regular e é denotado como L(r). 
 As expressões regulares descrevem todas as linguagens que podem ser formadas 
a partir de operadores sobre linguagem aplicados aos símbolos de algum alfabeto. 
 As expressão regulares são construídas recursivamente a partir de expressões 
regulares menores. Cada expressão regular r denota uma linguagem L(r), que também 
é definida recursivamente a partir das linguagens indicadas pelas subexpressões de r. 
Definição de expressões regulares 
 Aqui estão as regras que definem as expressões regulares para algum alfabeto 
e as linguagens que essas expressões denotam. 
Básicas 
 Dado um caractere a do alfabeto , indicamos que a expressão regular a casa 
com o caractere a escrevendo L(a) = {a}. 
 Símbolos adicionais necessários em situações especiais: 
1. é uma expressão regular, e L( ) é { }, a linguagem cujo único membro é a 
cadeia vazia. 
2. símbolo que não casa com nenhuma cadeia de caracteres, escrevemos L( ) = {}. 
Indução 
 Existem quatro partes na indução, por meio das quais expressões regulares 
maiores são construídas a partir das menores. Suponha que r e s sejam expressões 
regulares denotando as linguagens L(r) e L(s), respectivamente. 
1. (r) | (s) ou r | s é uma expressão regular denotando a linguagem L(r) 
 L(s). A barra vertical permite a escolha entre alternativas. 
 Compiladores – 7 
 http://erinaldosn.wordpress.com 
2. (r)(s) ou rs é uma expressão regular denotando a linguagem L(r)L(s). 
Representa a concatenação de duas expressões regulares. 
3. (r)* ou r* é uma expressão regular denotando L(r*) = L(r)* = 
(L(r))*. Asterisco representa a operação de repetição de uma expressão regular, 
também chamada fecho (de Kleene). 
4. (r) é uma expressão regular denotando L(r). Essa última regra diz que podemos 
acrescentar pares de parênteses adicionais em torno das expressões sem alterar a 
linguagem que eles denotam. Os parênteses não modificam a linguagem. 
As expressões regulares normalmente contêm pares de parênteses 
desnecessários. Podemos retirar certos pares de parênteses se adotarmos as convenções 
que: 
a) O operador unário * possui precedência mais alta e é associativo à esquerda. 
b) A concatenação tem a segunda maior precedência, e é associativa à esquerda. 
c) | tem a precedência mais baixa, e é associativa à esquerda. 
Exemplo: considere = {a, b}. 
1. A expressão regular a | b denota a linguagem {a, b}. 
2. (a | b) (a | b) denota {aa, ab, ba, bb}, a linguagem de todas ascadeias de tamanho 
dois sob o alfabeto . 
3. a* denota a linguagem consistindo em todas as cadeias de zero ou mais as, ou 
seja, { , a, aa, aaa, ...}. 
4. (a | b)* denota o conjunto de todas as cadeias consistindo em zero ou mais 
instâncias de as e bs: { , a, b, aa, ab, ba, bb, aaa, ...} 
5. a | a * b denota a linguagem {a, b, ab, aab, aaab, …}, a cadeia de a e todas as 
cadeias consistindo em zero ou mais as e terminando em b. 
Extensão de expressões regulares 
 Desde que Kleene (década de 1950) introduziu as expressões regulares com os 
operadores básicos para união, concatenação e fecho de Kleene, muitas extensões foram 
acrescentadas às expressões regulares para melhorar sua capacidade de especificar os 
padrões de cadeia. 
1. Uma ou mais instâncias (repetições). 
(r)+ denota a linguagem (L(r))+. 
r* = r+ | e r* = rr* = r*r. 
2. Zero ou uma instância. 
r? = r | ou, L(r?) = L(r?) { }. 
3. Classes de caracteres (intervalo de caracteres). 
[abc] = a | b | c = [a-c] 
[0-9] = 0 | 1 | 2 | ... | 9 
4. Qualquer caractere. 
.*b.* = todas as cadeia que contêm pelo menos um b. 
5. Qualquer caractere fora de um conjunto. 
~(a | b | c) = um caracter que não seja a nem b e nem c. 
~(a | b | c) = [^abc] (em Lex). 
Expressões regulares para marcas de linguagem de programação 
 As marcas de linguagem de programação tendem a se enquadrar em diversas 
categorias limitadas que são relativamente padronizadas para as diferentes linguagens 
de programação. 
Expressões Regulares 
 http://erinaldosn.wordpress.com 
Palavras reservadas e identificadores 
 Palavras reservadas (palavras-chave) são cadeias fixas de caracteres alfabéticos 
com significado especial na linguagem. Outra categoria são os símbolos especiais 
(operadores aritméticos, de atribuição e de igualdade. Uma terceira categoria são os 
identificadores, sequências de letras e dígitos iniciado por uma letra. 
 As palavras reservadas são as mais simples de escrever como expressões 
regulares: 
reservadas → if | while | do | … 
 Um identificador deve iniciar com uma letra e conter somente letras e dígitos: 
letra_ → [a-zA-Z_] 
dígito → [0-9] 
id → letra_(letra | dígito)* 
Números 
 Podem se apenas sequências de dígitos, números decimais ou números com 
expoente: 
dígito → [0-9] 
dígitos → dígito+ 
número → [+ –]dígitos(.dígitos)?(E[+ –]? dígitos)? 
Comentários 
 Comentários são normalmente ignorados durante a varredura. Um sistema de 
varredura precisa reconhecê-los e descartá-los. Geralmente eles têm formato livre e são 
cercados por delimitadores ou iniciam por um ou mais caracteres especificados e vão 
até o final da linha. 
 É muito mais difícil escrever uma expressão regular para o caso de delimitadores 
com comprimento de mais de um caractere, como em C. 
/* comentário em C */ 
 O não é usualmente restrito a caracteres isolados, em vez de cadeias de 
caracteres. Uma solução: 
b*(a*~(a|b)b*)*a* 
Exercícios 
1. Divida o seguinte programa em C++: 
float limitedsquare(x) float x { 
 /*retorna x ao quadrado, mas nunca mais do que 100*/ 
 return (x <= -10.0 || x >= 10.0)?100:x*x; 
} 
em lexemes apropriados. Quais lexemas devem ter valores léxicos associados? 
Quais deverão ser esses valores? 
2. Defina: 
a) Gramática: 
b) Alfabeto: 
c) Cadeia: 
d) Linguagem: 
e) Derivação: 
f) Expressões regulares: 
3. O que são símbolos gramaticais? 
 Compiladores – 9 
 http://erinaldosn.wordpress.com 
4. Considere que L seja o conjunto de letras {A, B, ..., Z, a, b, ..., z} e D seja o 
conjunto de dígitos {0, 1, ..., 9}. A partir das linguagens L e D construa outras linguagens 
e determine suas cadeias usando os operadores de linguagens. 
5. Dada a expressão regular indique com quem ela casa: 
a) L(a) = 
b) L (a | b) = 
c) L (a | b | c | d) = 
d) L (a | ) = 
e) L ((a | b)c) = 
f) L (a | bb)* = 
g) L (a | b)* = 
h) L (a | (b*)) = 
i) L (a | bc*) = 
j) L (ab | c*d) = 
6. Substitua os parênteses desnecessários das expressões regulares abaixo: 
a) a | b(c*)) = 
b) (ab) | ((c*)d) = 
c) (a) | ((b)*(c)) = 
7. Considere o alfabeto simples composto por somente três caracteres alfabéticos: = 
{a, b, c}. Gere a expressão regular para o conjunto de cadeias abaixo: 
a) b, abc, abaca, baaaac, ccbaca, ccccccb 
b) o conjunto de todas as cadeias de caracteres que contêm no máximo um b. 
c) b, aba, aabaa, aaabaaa 
d) , a, c, aa, ac, ca, cc, ba, bc 
8. Escreve uma expressão regular para gerar um número natural, que deve ser uma 
sequência de dígitos, com pelo menos um dígito. 
9. Escreva uma expressão regular para gerar números binários sem admitir a cadeia 
vazia. 
10. Escreva uma expressão regular para comentários em Pascal 
{comentários em Pascal} 
11. Algumas linguagens de programação permitem comentários aninhados, como: 
(*esse é (*aninhado*)um comentário*) 
crie uma expressão que resolva esse problema. 
12. A palavra-chave SQL SELECT pode ser escrita como select, Select ou SeLEcT, por 
exemplo. Escreva uma expressão regular para uma palavra-chave em uma 
linguagem que não diferencie maiúsculo de minúsculo. 
Bibliografia 
Compiladores: princípios, técnicas e ferramentas 
Aho, Alfred. Lam, Monica. Sethi, Ravi. Ullman, Jeffrey D. 
São Paulo: Pearson Addison-Wesley, 2008. 
Compiladores: princípios e práticas 
Louden, Kenneth C. 
São Paulo: Pioneira Thomson Learning, 2004 
Implementação de linguagens de programação: Compiladores 
Price, Ana. Toscani, Simão 
Porto Alegre: Bookman: Instituto de Informática da UFRGS, 2008.