plp-aula04-cap4Sebesta

Prévia do material em texto

Paradigmas de 
Linguagem de 
Programação
Análise Léxica e Sintática
 
Tópicos
 Análise léxica.
 O problema da análise sintática:
Construção da árvore de análise:
• Análise cima-baixo.
• Análise baixo-cima.
Análise descendente recursiva.
 
Introdução
 Os analisadores sintáticos são baseados 
em uma descrição formal da sintaxe do 
programa. O formalismo mais usual é a 
gramática livre de contexto ou BNF:
Suas descrições de sintaxe de programa 
são claras e concisas, tanto para leitores 
humanos como para os sistemas de 
software que as utilizam.
As implementações baseadas em BNF são 
relativamente fáceis de manter, devido a sua 
modularidade.
 
Introdução
 Praticamente todos os compiladores separam a 
tarefa de análise sintática em duas partes distintas:
 Simplicidade: técnicas para análise léxica são menos 
complexas do que as exigidas para análise sintática.
 Eficiência: Separação facilita otimização seletiva 
(apenas na análise sintática).
 Portabilidade: analisador léxico lê arquivos de 
entrada contendo o programa (de certa forma 
dependente de plataforma). O analisador sintático 
pode ser independente da plataforma.
 
Introdução
 Análise léxica – trata as construções 
de pequena escala: nomes e literais 
numéricos.
 Análise sintática propriamente dita – 
trata as construções de larga escala: 
expressões, instruções e unidades de 
programa.
 
Resultados
Unidades
léxicas
Árvores de
análise
Código
intermediário 
Analisador
sintático
Gerador de código 
intermediário
Computador
Tabela de
símbolos
Analisador
léxico
Gerador de 
código 
Otimização
Programa
Fonte
Linguagem
de máquina
Dados de
entrada
O processo da compilação
 
Análise léxica
 
Análise léxica
 Um analisador léxico é uma ferramenta de 
 casamento de padrões:
 Tenta encontrar subcadeia de uma cadeia de 
caracteres que casa com o padrão dado.
 Um programa de entrada para um 
compilador aparece como uma única 
cadeia de caracteres → o analisador 
léxico coleta caracteres em grupamentos 
lógicos (lexemas) e atribui códigos 
internos (símbolos/tokens) aos 
grupamentos de acordo com sua estrutura.
 
Análise léxica
 Lexemas – grupamentos de caracteres.
 Símbolos (tokens) – códigos internos.
 Ex: Soma = SomaVelha – Valor / 100;
Símbolo Lexema
Identificador Soma
Op_atribuição =
Identificador SomaVelha
Op_subtração -
Identificador Valor
Op_divisão /
Literal_int 100
PontoeVírgula ;
 
Análise léxica
 O processo do analisador léxico inclui:
 Saltar comentários e brancos fora dos lexemas (são 
irrelevantes para o significado do programa).
 Inserção dos lexemas de nomes definidos pelo 
programador na tabela de símbolos.
 Detectar erros de sintaxe dos símbolos e reportar 
esses erros ao usuário.
 O analisador léxico produz o próximo lexema e seu 
símbolo associado e retorna para o analisador 
sintático:
 O analisador sintático tem como única visão do 
programa a saída do analisador léxico, um lexema 
por vez.
 
Análise léxica
 Exemplo:
Analisador léxico que reconheça 
apenas nomes de programas, 
palavras reservadas e literais inteiros.
 Construção do analisador léxico:
Diagrama de estados:
• Estados e transições para cada padrão 
de símbolos.
Código.
 
Análise léxica
AcrescentaCaracter;
ObtemCaracter;
id
int
início
retorna pesquisa(lexema)
retorna Lit_Int
Letra
Digito
AcrescentaCaracter;
ObtemCaracter;
AcrescentaCaracter;
ObtemCaracter;
Letra/Digito
AcrescentaCaracter;
ObtemCaracter;
Digito
Subprogramas utilitários:
ObtemCaracter: pega o 
próximo caractere do programa 
fonte e coloca na variável 
ProximoCaracter. Determina a 
classe a que o caractere 
pertence e coloca-o na variável 
ClasseCaracter. 
AcrescentaCaracter: coloca o 
caractere do ProximoCaracter 
na variável lexema.
Pesquisa: determina se o 
lexema é uma palavra 
reservada ou um nome 
(retorna zero).
Diagrama de estados para reconhecer nomes, 
palavras reservadas e literais inteiros
 
Análise léxica
/* lex - um analisador léxico simples */
int lex(){
ObtemCaracter(); 
switch(ClasseCaracter){
/* analisa identificadores e palavras reservadas */
case LETRA:
AcrescentaCaracter();
ObtemCaracter();
while (ClasseCaracter == LETRA || ClasseCaracter 
== DIGITO){
AcrescentaCaracter();
ObtemCaracter();
}
return pesquisa(lexema);
break;
 
Análise léxica
/* lex - um analisador léxico simples */
/* analisa literais inteiros */
case DIGITO:
AcrescentaCaracter();
ObtemCaracter();
while (ClasseCaracter == DIGITO){
AcrescentaCaracter();
ObtemCaracter();
}
return LIT_INT;
break;
} /* Fim do switch*/
} /* Fim da função lex*/
 
Exercício 1
 Faça um diagrama de estados que 
reconheça uma forma de comentários 
das linguagens baseadas no C, aquela 
que começa com /* e termina com */
 
Solução 1
ObtemCaracter;
corpo com
início
/*
ObtemCaracter;
Letra/Digito
*/
Letra/Digito
Subprogramas utilitários:
ObtemCaracter: pega o 
próximo caractere do programa 
fonte e coloca na variável 
ProximoCaracter. Determina a 
classe a que o caractere 
pertence e colocá-la na 
variável ClasseCaracter. 
AcrescentaCaracter: coloca o 
caractere do ProximoCaracter 
na variável lexema.
Pesquisa: determina se o 
lexema é uma palavra 
reservada ou um nome 
(retorna zero).
n_comObtemCaracter;
 
Exercício 2
 Faça um diagrama de estados para 
reconhecer literais de números reais 
em C.
 
Solução 2
id
int
início
retorna Lit_int
retorna Lit_real
Letra
Digito
AcrescentaCaracter;
ObtemCaracter;
AcrescentaCaracter;
ObtemCaracter;
Digito . (ponto)
AcrescentaCaracter;
ObtemCaracter;
real
AcrescentaCaracter;
ObtemCaracter;
ObtemCaracter;
Digito
 
Análise sintática
 
Análise sintática
 Os analisadores de LP constroem árvores de análise 
para os programas.
 A informação necessária para construir a árvore é 
criada durante o processo de análise.
 As árvores de análise e as derivações incluem toda a 
informação sintática necessária para um processador 
de linguagem.
 Metas:
 Verificar se programa de entrada está 
sintaticamente correto.
• Quando erro é encontrado, deve produzir mensagem 
de diagnóstico. 
 Produzir uma árvore de análise (completa ou 
esboçar a sua estrutura).
 O resultado da análise sintática é usado como base 
para a tradução.
 
Análise sintática
 Os analisadores são classificados de 
acordo com a direção na qual eles 
constroem a árvore de análise:
Cima-baixo (top-down)
Baixo-cima (bottom-up)
 Os analisadores operam sob a 
obrigação de que eles jamais olharão 
à frente mais do que um símbolo no 
programa de entrada.
 
Analisador cima-baixo
 Analisador cima-baixo (top-down):
Utiliza derivação mais à esquerda.
Constrói árvore em pré-ordem.
• Visitar nó da raiz.
• Percorrer em pré-ordem subárvore esquerda.
• Percorrer em pré-ordem subárvore direita.
 
Percurso em pré-ordem
A
B C
E F
H IG
D
Percurso em pré-ordem:
Visitar nó da raiz.
Percorrer em pré-ordem subárvore esquerda.
Percorrer em pré-ordem subárvore direita.
A B D G C E H I F
 
Analisador cima-baixo
 Dada uma forma sentencial encontrar a próxima 
derivação:
 Regras: A → bB, A → cBb e A → a
 Escolher entre as regras para gerar a próxima forma 
sentencial sob a restrição de um símbolo considerado à 
frente.
 A forma geral de uma forma sentencial à esquerda é 
xAα:
 x é uma cadeia de símbolos terminais.
 A é um não terminal.
 α é uma cadeia mista.
 A é o não terminal maisà esquerda, então deve ser 
expandido para se obter a próxima forma sentencial na 
derivação mais à esquerda. A próxima forma sentencial 
pode ser:
 xbBα ou xcBbα ou xaα
 
Analisador baixo-cima
 Analisador baixo-cima (bottom-up):
Produz o inverso da derivação mais à 
direita.
• Produz a árvore das folhas para a raiz.
Gramática:
• S → Ax, A → a | b
• Derivações para ax:
• Cima-baixo:
• S => Ax => ax
• Baixo-cima:
• a <= Ax <= S
 
Análise descendente recursiva
 
Análise descendente 
recursiva
 Um analisador descendente recursivo consiste 
de uma coleção de subprogramas, muitos dos 
quais são recursivos, e produz uma árvore de 
análise cima-baixo (descendente).
 Natureza das linguagens de programação → 
várias estruturas recursivas:
 Análise de estruturas recursivas das LPs leva 
naturalmente a regras gramaticais recursivas.
 A EBNF é muito adequada para analisadores 
descendentes recursivos.
 Dada a gramática apropriada, o analisador 
descendente recursivo é relativamente simples de 
implementar.
 
EBNF 
 EBNF – versão estendida da BNF:
Não aumenta poder descritivo, mas 
aumenta sua legibilidade e 
capacidade de escrita.
 
EBNF – parte opcional
 Parte opcional de um lado direito, definida 
por colchetes:
 Exemplo em C:
EBNF:
• <seleção> → if (<expressão>) <instrução> [else 
<instrução>];
BNF:
• <seleção> → if (<expressão>) <instrução>;
• <seleção> → if (<expressão>) <instrução> else 
<instrução>;
 
EBNF – repetição 
 Indicar que o lado direito pode ser repetido 
indefinidamente ou omitido completamente, 
definido por chaves.
 Permite que listas sejam criadas com uma 
única regra, em vez de usar recursão e duas 
regras.
 Exemplo:
EBNF :
• <list_ident> → <identificador> {, <identificador>}
BNF:
• <list_ident> → <identificador> 
• <list_ident> → <identificador>, <list_ident>
 
EBNF – múltipla escolha
 Opções de múltipla escolha: quando um 
único elemento deve ser escolhido de um 
grupo, as opções são colocadas entre 
parênteses e separadas por OU ‘|’.
Exemplo em Pascal:
• EBNF:
• <inst_for> → for <var> := <expr> (to|downto) <expr> 
do <inst>
• BNF:
• <inst_for> → for <var> := <expr> to <expr> do <inst> 
• <inst_for> → for <var> := <expr> downto <expr> do 
<inst>
 
Análise descendente 
recursiva
 Um analisador descendente recursivo 
tem um subprograma para cada 
não-terminal da gramática.
 Cada subprograma deve:
Dada uma cadeia de entrada, investigar 
a árvore que pode ter como raiz o 
não-terminal e cujas folhas casam com a 
cadeia de entrada.
 Assumiremos que cada não-terminal 
possui uma única regra, possivelmente 
com múltiplos LD (lados direitos) 
separados por OU.
 
Análise descendente 
recursiva
 Analisador sintático (descendente recursivo):
 Um subprograma para uma regra com um único LD é 
relativamente simples.
 Para cada símbolo terminal no LD é feita uma 
comparação com proximoSimbolo:
• Se eles não casam → erro de sintaxe.
• Se eles casam → analisador léxico é chamado para obter 
o próximo símbolo de entrada.
 Para cada não-terminal o subprograma de análise 
correspondente é chamado.
 Analisador léxico:
 Função lex()
 Obtém o próximo lexema e coloca seu código de 
símbolo na variável proximoSimbolo:
• Ex: Codigo_Mais (constante nomeada para o símbolo +).
 
Análise descendente 
recursiva
 Expressões aritméticas simples:
<expr> → <termo> {(+ | -) <termo> }
<termo> → <fator> {(*|/) <fator>}
<fator> → ident | (<expr>)
 
Análise descendente 
recursiva
/* função expr – Analisa cadeias na linguagem gerada pela 
regra:
<expr> → <termo> {(+ | -) <termo>} */
void expr(){
/* Analisa o primeiro termo */
termo();
/* Enquanto o próximo símbolo for + ou -, chama lex para 
obter o próximo símbolo e analisa o próximo termo*/
while (proximoSimbolo == Codigo_Mais || proximoSimbolo 
== Codigo_Menos){
lex();
termo();
}
} /* Fim da função expr*/
 
/* função fator – Analisa cadeias na linguagem gerada pela regra:
<fator> → ident | (<expr>) */
void fator(){
/* Determina qual LD */
if (proximoSimbolo == codigo_ident)
 lex();
/* Se o LD (<expr>)*/
else if (proximoSimbolo == parent_esq){
 lex();
 expr();
 if (proximoSimbolo == parent_dir)
 lex();
 else
 erro();
}
else
 erro();
} /* Fim da função fator*/
Análise descendente 
recursiva
 
Exercício
 Escreva o subprograma descendente 
recursivo para a regra de termo:
<termo> → <fator> {(*|/) <fator>}
 
Solução
/* função termo – Analisa cadeias na linguagem gerada pela regra:
<termo> → <fator> {(* | /) <fator>} */
void termo(){
/* Analisa o primeiro fator */
fator();
/* Enquanto o próximo símbolo for * ou /, chama lex para obter 
o próximo símbolo e analisa o próximo fator*/
while (proximoSimbolo == Codigo_Vezes || proximoSimbolo == 
Codigo_Div){
lex();
fator();
}
} /* Fim da função termo*/
 
Análise descendente 
recursiva
 Um analisador descendente recursivo 
pode ser facilmente escrito se uma 
gramática apropriada estiver 
disponível para a linguagem.
 
Análise sintática
 Uma característica simples das 
gramáticas que causa um problema 
catastrófico para os analisadores 
cima-baixo é a recursão à esquerda:
• Direta:
• A → A + B
• Indireta:
• A → BaA, B → Ab
É preciso evitar a inclusão de 
recursão à esquerda nas regras 
da gramática.
A chama a si mesmo, 
que chama a si mesmo 
de novo, que ... não leva 
a lugar nenhum!!
 
Análise sintática
 O analisador cima-baixo realiza a escolha do 
LD baseado no próximo símbolo de entrada.
 Exemplo:
<seleção> → if (<expressão>) <instrução>; |
if (<expressão>) <instrução>; else 
<instrução>;
Conhece apenas o 
símbolo terminal if.
Como escolher entre 
as duas regras?
 
Análise sintática
 Existe um teste de gramáticas recursivas não 
à esquerda que indica se a escolha pode ser 
feita – teste de disjunção paritária:
Consiste em determinar um conjunto de 
símbolos terminais, chamado primeiro, com 
base nos LDs de um dado símbolo não 
terminal.
Para cada não terminal, A, na gramática que 
tenha mais de um LD:
• Para cada par de regras, A → αi e A → αj, 
• Deve ser constatado que primeiro(αi) ∩ 
primeiro(αj) = ø.
 
Análise sintática
 Exemplos de teste de disjunção paritária:
• A → aB | bAb | c
• Conjunto dos primeiros: {a}, {b} e {c} que são 
disjuntos.
• Essas regras passam no teste.
• A → aB | aAb 
• Conjunto dos primeiror: {a} e {a} que não 
são disjuntos.
• Essas regras não passam no teste.
 
Análise sintática
 Em muitos casos, a gramática que não passa pelo 
teste da disjunção paritária pode ser modificada 
através do processo chamado fatoração à 
esquerda.
 Exemplo:
 Antes da fatoração:
<seleção> → if (<expressão>) <instrução>; |
if (<expressão>) <instrução>; else 
<instrução>; 
 Após fatoração (passa no teste de disjunção 
paritária):
<seleção> → if (<expressão>) <instrução>; <nova> 
<nova> → є | else <instrução>; 
 
Exercício 1
 Para as seguintes regras 
gramaticais, faça o teste da 
disjunção paritária. 
a) A → aB | bA | aBb
b) A → aaA | b | caB
 
Solução 1
a) A → aB | bA | aBb
primeiro(aB) = {a}, primeiro(bA) = {b} , 
primeiro(aBb) = {a}
{a} ∩ {b} ∩ {a} = {a} ≠ ø Não passa no 
teste
a) A → aaA | b | caB
primeiro(aaA) = {a}, primeiro(b) = {b}, 
primeiro(caB) = {c}
{a} ∩ {b} ∩ {c} = ø Passa no teste
 
Exercício 2
 Escreva um subprograma 
descendente recursivo que analisa a 
linguagem gerada pelas regras:
A → aaA | b | caB
 
Solução 2
/* função A – Analisa cadeias na linguagemgerada pela regra:
A → aaA | b | caB */
void A(){
/* Determina qual LD */
if (proximoSimbolo == codigo_a){
lex();
if (proximoSimbolo == codigo_a){
lex();
A();
}
else
erro();
}
else if (proximoSimbolo == codigo_b)
lex();
 
Solução 2
/* função A – Analisa cadeias na linguagem gerada pela 
regra:
A → aaA | b | caB */
else if (proximoSimbolo == codigo_c){
lex();
if (proximoSimbolo == codigo_a){
 lex();
 B();
}
else
 erro();
}
else
erro();
} /* Fim da função A*/
 
Referências Bibliográficas
 Sebesta, R. Conceitos de 
Linguagens de programação. 5ª 
edição. Bookman, 2003. Cap 4.