6 AnaliseSintatica Parte1 - Compiladores CEFET MG

Prévia do material em texto

Compiladores 
Prof.ª Kecia Aline Marques Ferreira 
CEFET-MG 
 
Análise Sintática 
1 
Análise Sintática – Parte 1 
• O papel do Analisador Sintático 
 
• Definição da Sintaxe 
– Gramáticas Livres de Contexto 
– Derivações 
– Árvores de Derivação 
– Associatividade de operadores 
– Precedência de operadores 
 
• Análise Sintática Descendente 
 
2 
O papel do Analisador Sintático 
 
• Linguagens de Programação possuem regras precisas para descrever a 
estrutura sintática de um programa bem formado 
 
• A estrutura sintática das construções de uma linguagem de programação é 
especificada pelas regras gramaticais de uma linguagem livre de contexto. 
 
• O papel do analisador sintático (parser) é verificar se o programa fonte 
está sintaticamente correto 
 
• O analisador sintático recebe do analisador léxico o fluxo de tokens que 
constituem o programa fonte 
 
• O analisador sintático deve verificar se a ordem em que estes tokens 
aparecem no programa fonte está de acordo com as regras sintáticas da 
linguagem de programação 
 
 
 
3 
O papel do Analisador Sintático 
 
 
 
 
 
 
 
 
 
4 
Analisador 
Léxico 
Analisador 
Sintático 
Restante do 
front-end: 
analisador 
semântico e 
gerador de 
código 
intermediário 
Programa 
fonte 
Token getToken() 
Token 
Representação 
intermediária 
Tabela de 
Símbolos 
Definição da Sintaxe 
 
• Uma gramática livre de contexto possui os seguintes componentes: 
 
– Símbolos terminais: são os símbolos elementares da linguagem 
(tokens). 
 
– Não terminais (ou variáveis sintáticas): símbolos a partir dos quais 
podem ser derivados outros símbolos ou cadeias de símbolos 
(terminais e/ou não terminais) 
 
– Produções: especifica as formas que um não terminal pode ser 
derivado 
 
– Símbolo inicial 
5 
Definição da Sintaxe 
 
Exemplo: 
 
 S → S; S | id := E | print (L) 
 E → id | num | E + E | (S, E) 
 L → E | L, E 
 
 
6 
Definição da Sintaxe 
 
• Derivações: 
 
– Uma gramática deriva cadeias começando com o símbolo inicial e 
substituindo repetidamente um não terminal pelo corpo de uma 
produção para esse não terminal 
 
– As cadeias de terminais que podem ser derivadas do símbolo inicial 
formam a linguagem definida pela gramática 
 
– A análise sintática consiste em, a partir de uma cadeia de terminais, 
tentar descobrir como derivá-la a partir do símbolo inicial da 
gramática 
7 
Definição da Sintaxe 
 
Exemplo: 
 
S 
S; S 
S; id := E 
id := E; id:= E 
id := num ; id:= E 
id := num ; id:= E + E 
id := num ; id:= E + (S, E) 
id := num ; id:= id + (S, E) 
id := num ; id:= id + (id:=E, E) 
id := num ; id:= id + (id:=E + E, E) 
id := num ; id:= id + (id:=E + E, id) 
id := num ; id:= id + (id:=num+ E, id) 
id := num ; id:= id + (id:=num+ num, id) 
 
 
8 
Definição da Sintaxe 
• Derivação mais à esquerda (leftmost derivation): é aquela na qual o 
símbolo não terminal mais à esquerda é expandido primeiro 
 
• Derivação mais à direita (rightmost derivation): é aquela na qual o símbolo 
não terminal mais à direita é expandido primeiro 
 
Exemplo de derivação mais à esquerda: 
 
S 
S; S 
id := E; S 
id := num; S 
id := num; id := E 
id := num; id := E + E 
... 
9 
Definição da Sintaxe 
 
• Árvores de Derivação: 
 
– Uma árvore de derivação representa como o símbolo inicial de uma 
gramática deriva uma cadeia na linguagem 
 
• Ambiguidade: 
 
– Uma gramática é ambígua se existe mais de uma árvore de derivação 
para alguma sentença que ela gera. 
 
10 
Definição da Sintaxe 
Exemplo: duas árvores de derivação para a mesma cadeia: id := id + id + id 
 
11 
S 
id E := 
+ E E 
E + E 
id id 
id 
S 
id E := 
+ E E E 
+ E E 
id 
id id 
Definição da Sintaxe 
 
• Associatividade de operadores: 
 
Exemplos: 
9 - 5 + 2 
a = b = c 
 
 
– Quando um operando possui operadores do lado esquerdo e direito 
(de mesma precedência) é preciso decidir a qual deles o operando 
será associado 
 
– Por exemplo, a qual operador 5 se associa em 9 – 5 + 2 ? 
 
 
12 
Definição da Sintaxe 
 
– Associação à esquerda: o operando associa-se ao operador à sua 
esquerda 
 
• Operadores com associação à esquerda: aritméticos + - / * 
 9 – 5 + 3 equivale a ( 9 – 5 )+ 3 
 
– Associação à direita: o operando associa-se ao operador à sua direita 
 
• Operador de atribuição 
 
a = b = c equivale a a=(b=c) 
 
 
 
 
13 
Definição da Sintaxe 
 
– A gramática deve refletir a maneira pela qual os operadores são 
associados a seus operandos 
 
 
Exemplo de gramática associativa à esquerda: 
 
 E → E + digit | E – digit | digit 
 
 
Exemplo de gramática associativa à direita: 
 
 right → letter = right | letter 
 
14 
Definição da Sintaxe 
Exemplo: árvores de derivação para gramática associativa à esquerda e à 
direita 
 
15 
E 
E digit + 
2 E - digit 
5 
right 
right = 
= letter right 
letter 
b 
c 
digit 
9 
letter 
a 
Definição da Sintaxe 
 
• Precedência de operadores: 
 
9 + 5 * 2 
 
Deve ser interpretado como (9 + 5) * 2 ou 9+ (5 * 2) ? 
 
– As regras de associatividade aplicam-se na ocorrência de operadores 
iguais ou de mesma precedência 
 
– Regras que definem precedência de operadores devem estar 
presentes quando mais de um tipo de operador estiver presente 
 
 
16 
Definição da Sintaxe 
 
Exemplo: uma gramática para expressões aritméticas. 
 
Precedência 1: * / (associativos à esquerda) 
Precedência 2: + - (associativos à esquerda) 
 
Na gramática, são utilizados os seguintes não terminais: 
 
– term: para o primeiro nível de precedência 
 
– expr: para o segundo nível de precedência 
 
– factor: representa as unidades básicas da expressões (dígitos e 
expressões entre parênteses). 
 
17 
Definição da Sintaxe 
Os operadores de precedência mais alta ( * e / ) são associativos à esquerda 
 
term → term * factor | 
 term / factor | 
 factor 
 
Os operadores de precedência mais baixa ( + e - ) são associativos à esquerda 
 
expr → expr + term | 
 expr - term | 
 term 
 
A gramática resultante para este caso é: 
 
expr → expr + term | expr - term | term 
term → term * factor | term / factor | factor 
factor → digit | (expr) 
 
 
 
18 
Analisador Sintático Descendente 
 
• O método de análise sintática descendente constroi a árvore de derivação 
para a cadeia de entrada de cima para baixo, ou seja, da raiz para as 
folhas. 
 
• Esse método, então, produz uma derivação mais à esquerda para uma 
cadeia na entrada. 
 
• A cada passo da análise sintática descendente, o problema consiste em: 
 
– Determinar a produção a ser aplicada para um não terminal 
 
– “Casar” os símbolos terminais do corpo da produção com a cadeia de entrada 
 
 
 
 
19 
Analisador Sintático Descendente 
 
• Para algumas gramáticas é fácil construir um parser utilizando um 
algoritmo simples conhecido como recursivo descendente 
 
• Esse tipo de análise é denominada análise sintática de descida recursiva 
 
• Nesse método: 
 
– Um conjunto de procedimentos recursivos é usado para processar a 
entrada 
 
– Um procedimento é associado a cada não-terminal de uma gramática 
 
–Cada procedimento possui uma cláusula para cada produção do 
respectivo símbolo não-terminal 
 
 
 
20 
Analisador Sintático Descendente 
• Algoritmo para um não-terminal A em um analisador descendente 
 
procedimento A(){ 
 Escolha uma produção A → X1X2...Xk 
 
 para i=1 até k{ //para cada símbolo da produção 
 
 se (Xi é um não terminal) 
 Chame procedimento Xi(); 
 
 senão 
 se (Xi é igual ao símbolo da entrada a) //casa com a 
 Avance na entrada para o próximo símbolo 
 
 senão 
 Trate ocorrência de erro; 
 } 
} 
21 
Analisador Sintático Descendente 
• Exemplo 
 
– Gramática: 
 
S → if E then S else S | 
 begin S L | 
 print E 
 
L → end | 
 ; S L 
 
E → num = num 
 
 
 
 
22 
Analisador Sintático Descendente 
– Parser recursivo descendente 
 
final int IF=1, THEN=2, ELSE=3, BEGIN=4; END=5; 
PRINT=6, SEMI=7, NUM=8, EQ=9; 
 
int tok = getToken(); //lê primeiro token 
 
void advance() { 
 tok = getToken(); //lê próximo token 
} 
 
void eat(int t){ 
 if (tok==t) advance(); 
 else error(); 
} 
 
 
23 
Analisador Sintático Descendente 
void S(){ 
 
 switch(tok){ 
 
 // S → if E then S else S 
 case IF: eat(IF); E(); eat(THEN); S(); 
 eat(ELSE); S(); break; 
 
 // S → begin S L 
 case BEGIN: eat(BEGIN); S(); L(); break; 
 
 // S → print E 
 case PRINT: eat(PRINT); E(); break; 
 
 default: error(); 
 } 
} 
24 
Analisador Sintático Descendente 
void L(){ 
 
 switch(tok){ 
 
 // L → end 
 case END: eat(END); break; 
 
 // L → ; S L 
 case SEMI: eat(SEMI); S(); L(); break; 
 
 default: error(); 
 } 
} 
25 
Analisador Sintático Descendente 
void E(){ 
 
 // E → num = num 
 eat(NUM); eat(EQ); eat(NUM); 
 
} 
26 
Analisador Sintático Descendente 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
27 
Entrada Execução 
if num=num then 
 print num=num 
else 
 print num = num 
 
tok = IF 
S() 
 case IF: eat(IF) , tok=NUM 
 E() 
 eat(NUM), tok = EQ 
 eat(EQ), tok = NUM 
 eat(NUM), tok=THEN 
 eat(THEN), tok= print 
 S() 
 case PRINT: eat(PRINT), tok=NUM 
 E() .... tok=ELSE 
 eat(ELSE), tok=print 
 S() 
 case PRINT : eat(PRINT), tok=NUM 
 E()... tok= Fim de arquivo 
 break; //fim da análise sintática 
Analisador Sintático Descendente 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
28 
Entrada Execução 
if num=num 
 print num=num 
else 
 print num = num 
 
tok = IF 
S() 
 case IF: eat(IF) , tok=NUM 
 E() 
 eat(NUM), tok = EQ 
 eat(EQ), tok = NUM 
 eat(NUM), tok=PRINT 
 eat(THEN) //ERRO! 
Exercício 
1) Mostre a execução do parser mostrado anteriormente para as 
seguintes entradas 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
29 
Entrada 1 Entrada 2 
if num=num then 
 begin 
 print num=num; 
 print num = num; 
 end 
 else 
 print num = num 
 
if num=num then 
 begin 
 print num=num; 
 print num = num 
 end 
 else 
 print num = num 
Exercício 
2) Mostre a implementação de um parser preditivo para a gramática a 
seguir (considere os termos em negrito como tokens) 
 
stmt → expr; 
 | if (expr) stmt 
 | for (optexpr; optexpr; optexpr) stmt 
 | other 
 
optexpr → λ 
 | expr 
30 
Referência Bibliográfica 
Compiladores – Princípios, técnicas e ferramentas. 
Aho, A. V et al. 2ª edição 
Capítulo 4 ,Seção 2.2, Seção 2.4.1 e 2.4.2 
 
Modern Compiler Implementation in Java. Second Edition. 
Andrew W. Appel. 
Capítulo 3. 
 
 
 
31