6 AnaliseSintatica Parte4 - 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 4 
• Análise Sintática Ascendente 
 
– Parser SLR 
– Parser LR(1) 
– Parser LALR 
 
 
 
2 
Analisador Sintático LR(0) 
• O analisador sintático LR(0): 
 
– não precisa de lookahead; 
 
– em cada estado pode-se realizar um shift ou um reduce, mas não 
ambos. 
 
 
 
 
 
 
 
 
 
3 
Analisador Sintático SLR 
• Seja a gramática G a seguir, seus respectivos diagrama LR(0) e 
tabela de parser LR(0): 
 
0. S → E $ 
1. E → T + E 
2. | T 
3. T → x 
 
 
 
 
 
 
 
 
4 
E → T • + E 
E → T • 
S → •E $ 
E → • T + E 
E → • T 
T → • x 
S → E • $ 
T → x • 
E → T + • E 
E → • T + E 
E → • T 
T → • x 
E → T + E • 
E 
T 
x 
x 
E 
T + 
x + $ E T 
1 s5 g2 g3 
2 a 
3 r2 s4,r2 r2 
4 s5 g6 g3 
5 r3 r3 r3 
6 r1 r1 r1 
1 
2 
3 
4 
5 
6 
Analisador Sintático SLR 
• No estado 3, com símbolo +, há entrada duplicada na tabela: 
 
– A entrada indica que o parser deve realizar um shift e também uma 
redução. 
 
– Isto representa um conflito e indica que a linguagem não é LR(0), ou 
seja, não há uma parser LR(0) para essa gramática. 
 
– É necessário, então, um parser mais poderoso para ela. 
 
 
 
 
 
 
5 
Analisador Sintático SLR 
• Uma maneira simples de construir um parser mais poderoso 
do que o LR(0) é o SLR 
 
• SLR corresponde a Simple LR (LR simples) 
 
• A construção do SLR é a mesma do LR(0), exceto que: 
 
– Ações de redução são inseridas na tabela apenas nas colunas 
correspondentes ao conjunto FOLLOW do termo à esquerda da 
produção 
 
 
 
 
 
6 
Analisador Sintático SLR 
• No exemplo, a tabela de parser SLR fica assim: 
 
0. S → E $ 
1. E → T + E 
2. | T 
3. T → x 
 
 
 
 
 
 
 
 
 
7 
E → T • + E 
E → T • 
S → •E $ 
E → • T + E 
E → • T 
T → • x 
S → E • $ 
T → x • 
E → T + • E 
E → • T + E 
E → • T 
T → • x 
E → T + E • 
E 
T 
x 
x 
E 
T + 
x + $ E T 
1 s5 g2 g3 
2 a 
3 s4 r2 
4 s5 g6 g3 
5 r3 r3 
6 r1 
1 
2 
3 
4 5 
6 
FOLLOW(E) = {$} 
FOLLOW(T) = {$, +} 
FOLLOW(E) = {$} 
Analisador Sintático SLR 
• Uma gramática é SLR quando a sua tabela de parser SLR não 
possuir conflitos (entradas duplicadas). 
 
• A gramática do exemplo é SLR, assim como muitas gramáticas 
úteis em linguagens de programação. 
 
 
 
 
 
 
 
 
 
8 
Analisador Sintático LR(1) 
• O parser LR(1) é ainda mais poderoso do que o SLR 
 
• A maior parte das linguagens de programação são descritas 
por gramáticas LR(1) 
 
• O parser LR(1) é similar ao LR(0), mas trabalha com um token 
como lookahead 
 
• A diferença básica entre esses dois analisadores sintáticos é a 
noção de item: 
– No LR(1), um item é uma produção da gramática, a posição do ponto 
na análise e um símbolo lookahead. 
 
 
 
9 
Analisador Sintático LR(1) 
• Um item (A → α•β, x) indica que 
 
– A sequência α está no topo da pilha 
 
– E a entrada começa com uma sequência derivada de βx 
 
• Ou seja, o item (A → α•β, x) representa uma situação em 
que “α já foi lido da entrada e está na pilha; o processo está 
no início do reconhecimento de β e, depois que β for 
reconhecido, deve vir um x na entrada”. 
 
• Um estado LR(1) é um conjunto de itens LR(1) 
 
 
 
10 
Analisador Sintático LR(1) 
• As operações CLOSURE e GOTO são similares àquelas do LR(0), 
porém incorporam o lookahead 
 
Closure(I) = 
 repita 
 para todo item (A → α •X β , z) em I 
 para toda produção X → γ 
 para todo w Є FIRST (βz) 
 Insira (X → • γ , w) em I 
 
 até que I não mude mais 
 retorne I 
 
 
 
11 
Analisador Sintático LR(1) 
 
Goto(I, X) = 
 inicie J com conjunto vazio 
 
 para todo item (A → α •X β , z) em I 
 insira (A → α X • β , z) em J 
 
 retorne Closure(J) 
 
 
 
 
 
 
12 
Analisador Sintático LR(1) 
• O estado inicial é o CLOSURE do item 
 
 (S’ → •S$, ?) 
 
• Neste item, o símbolo lookahead não importa (?), pois nunca 
haverá uma operação de shift para o marcador de fim de 
arquivo 
 
 
 
 
 
 
 
13 
Analisador Sintático LR(1) 
• Exemplo: 
0. S’ → S $ 
1. S → V = E 
2. | E 
3. E → V 
4. V → x 
5. | *E 
 
 
 
 
 
 
 
 
14 
S’ → •S$, ? 
S → • V = E $ 
S → • E $ 
V → • x = 
V → • *E = 
E → • V $ 
V → • x $ 
V → • *E $ 
 
 
 
1 
FIRST ($?) = {$} 
FIRST (=E$) = {=} 
FIRST ($) = {$} 
 
 
FIRST($) = {$} 
 
Primeiro estado: CLOSURE de ( S’ → •S$, ?) 
Analisador Sintático LR(1) 
GOTO do estado 1: 
 
 
0. S’ → S $ 
1. S → V = E 
2. | E 
3. E → V 
4. V → x 
5. | *E 
 
 
 
 
 
 
 
15 
S’ → • S$ ? 
S → • V = E $ 
S → • E $ 
V → • x =,$ 
V → • *E =,$ 
E → • V $ 
 
 
 
 
 
 
1 
S → V • = E $ 
E → V • $ 
 
3 
S → E • $ 
5 
V → x • =, $ 
8 
V → * • E =,$ 
E → • V =,$ 
V → • x =, $ 
V → • *E =, $ 
 
 
 
6 
S’ → S • $ ? 
2 
S V 
E 
* 
FIRST (=) = {=} e FIRST ($) = {$} 
FIRST (=) = {=} e FIRST ($) = {$} 
 
x 
Analisador Sintático LR(1) 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
16 
S’ → • S$ ? 
S → • V = E $ 
S → • E $ 
V → • x =,$ 
V → • *E =,$ 
E → • V $ 
 
 
 
 
1 
S → V • = E $ 
E → V • $ 
 
3 
S → E • $ 
5 
V → x • =, $ 
8 
V → * • E =,$ 
E → • V =,$ 
V → • x =, $ 
V → • *E =, $ 
 
 
 
6 
S’ → S • $ ? 
2 
S 
V 
E 
* 
x 
S → V = • E $ 
E → • V $ 
V → • x $ 
V → • *E $ 
 
 
4 
= 
S → V = E • $ 
9 
V → * • E $ 
E → • V $ 
V → • x $ 
V → • *E $ 
13 
V → * E • $ 
14 
E → V • $ 
7 
V → x • $ 
11 
E → V • =,$ 
12 
V → * E • =,$ 
10 
E 
V 
x 
* 
E 
V 
x 
* 
* 
x 
V 
E 
Analisador Sintático LR(1) 
• As regras de redução são escolhidas (inseridas na tabela de 
parser) da seguinte maneira: 
 
 Para cada estado I no diagrama 
 Para cada item (A → α •, z) em I 
 Entre na tabela, para o estado I e símbolo z, 
 a ação rn, onde n é o número da regra A → α 
 
Ou seja: no estado I, com lookahead z, reduza de acordo com a 
regra A → α. 
 
 
 
 
17 
Analisador Sintático LR(1) 
• Onde houver um • no final de uma produção, há umaredução para aquela produção na tabela de parser LR(1) 
– Na linha correspondente ao estado 
– Na coluna correspondente ao símbolo lookahead 
 
• Onde houver um • do lado esquerdo de um símbolo terminal, 
há uma ação shift desse símbolo 
 
• Onde houver um • do lado esquerdo de um símbolo não 
terminal, há uma ação goto. 
 
 
 
 
18 
Analisador Sintático LR(1) 
Tabela de parser LR(1) 
 para o exemplo: 
19 
x * = $ S E V 
1 s8 s6 g2 g5 g3 
2 a 
3 s4 r3 
4 s11 s13 g9 g7 
5 r2 
6 s8 s6 g10 g12 
7 r3 
8 r4 r4 
9 r1 
10 r5 r5 
11 r4 
12 r3 r3 
13 s11 S13 g14 g7 
14 r5 
Analisador Sintático LR(1) 
• A tabela de parser LR(1) pode ser muito grande 
 
• Uma tabela menor pode ser obtida a partir da união de dois 
estados que sejam idênticos, exceto pelo símbolo lookahead 
 
• O parser resultante é chamado LALR(1) 
– LA representa LookAhead 
 
• A seguir são identificados os estados idênticos do exemplo 
anterior e o resultado da união desses estados 
 
 
 
 
20 
Analisador Sintático LALR(1) 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
21 
S’ → • S$ ? 
S → • V = E $ 
S → • E $ 
V → • x =,$ 
V → • *E =,$ 
E → • V $ 
 
 
 
 
1 
S → V • = E $ 
E → V • $ 
 
3 
S → E • $ 
5 
V → x • =, $ 
8 
V → * • E =,$ 
E → • V =,$ 
V → • x =, $ 
V → • *E =, $ 
 
 
 
6 
S’ → S • $ ? 
5 
S 
V 
E 
* 
x 
S → V = • E $ 
E → • V $ 
V → • x $ 
V → • *E $ 
 
 
4 
= 
S → V = E • $ 
9 
V → * • E $ 
E → • V $ 
V → • x $ 
V → • *E $ 
13 
V → * E • $ 
14 
E → V • $ 
7 
V → x • $ 
11 
E → V • =,$ 
12 
V → * E • =,$ 
10 
E 
V 
x 
* 
E 
V 
x 
* 
* 
x 
V 
E 
Analisador Sintático LALR(1) 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
22 
S’ → • S$ ? 
S → • V = E $ 
S → • E $ 
V → • x =,$ 
V → • *E =,$ 
E → • V $ 
 
 
 
 
1 
S → V • = E $ 
E → V • $ 
 
3 
S → E • $ 
5 
V → x • =, $ 
8 
V → * • E =,$ 
E → • V =,$ 
V → • x =, $ 
V → • *E =, $ 
 
 
 
6 
S’ → S • $ ? 
5 
S 
V 
E 
* 
x 
S → V = • E $ 
E → • V $ 
V → • x $ 
V → • *E $ 
 
 
4 
= 
S → V = E • $ 
9 
V → * • E $ 
E → • V $ 
V → • x $ 
V → • *E $ 
6 
V → * E • $ 
10 
E → V • $ 
7 
V → x • $ 
8 
E → V • =,$ 
7 
V → * E • =,$ 
10 
E 
V 
x 
* 
E 
V 
x 
* 
* 
x 
V 
E 
Analisador Sintático LALR(1) 
Tabela de parser LALR(1) 
 para o exemplo: 
23 
x * = $ S E V 
1 s8 s6 g2 g5 g3 
2 a 
3 s4 r3 
4 s8 s6 g9 g7 
5 r2 
6 s8 s6 g10 g7 
7 r3 r3 
8 r4 r4 
9 r1 
10 r5 r5 
Referência Bibliográfica 
Compiladores – Princípios, técnicas e ferramentas. 
Aho, A. V et al. 2ª edição 
Seção 4.6.2 a 4.7.4 
 
Modern Compiler Implementation in Java. Second Edition. 
Andrew W. Appel. 
Capítulo 3. 
 
 
 
24