6 AnaliseSintatica Parte3 - 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 3 
• Análise Sintática Ascendente 
– Reduções 
– Analisador sintático shift-reduce 
– Parsing LR(k) 
– Parsing LR(0) 
• CLOSURE 
• GOTO 
• Conjunto de itens canônicos 
• Diagrama de transição 
• Tabela de parser 
• Algoritmo do parser 
 
 
 2 
Analisador Sintático Ascendente 
 
• A característica de um parser LL(1) é que ele deve definir a 
produção a ser utilizada conhecendo apenas o primeiro 
próximo token na entrada 
 
• Uma outra abordagem de análise sintática é adiar a decisão 
da escolha da produção a ser aplicada até ver os tokens 
correspondentes ao lado direito completo da produção 
 
• Essa abordagem é a análise sintática ascendente 
 
 
 
 
 
3 
Analisador Sintático Ascendente 
 
• A análise sintática ascendente corresponde à construção de 
uma árvore de derivação para uma cadeia de entrada a partir 
das folhas em direção à raiz. 
 
• Exemplo: considere a gramática a seguir: 
 
 E → E + T | T 
 T → T * F | F 
 F → (E) | id 
 
 
 
 
 
4 
Analisador Sintático Ascendente 
O reconhecimento ascendente da sequência de tokens id * id é: 
 
 
 
 
 
 
 
 
 
 
 
 
5 
id * id id F * 
id 
id 
F 
* 
id 
T 
F 
* 
id 
T F 
id 
F 
* 
id 
T F 
id 
T 
F 
* 
id 
T F 
id 
T 
E 
E → E + T | T 
T → T * F | F 
F → (E) | id 
 
Analisador Sintático Ascendente 
 
No exemplo, a análise realizada corresponde à seguinte 
derivação: 
 
 
Esta é uma derivação mais à direita. 
 
• A análise sintática ascendente ao ler a entrada da esquerda 
para a direita, constroi uma derivação mais à direita ao 
inverso. 
 
 
 
 
 
6 
Analisador Sintático Ascendente – LR(k) 
 
• Reduções: 
 
– O processo de análise sintática ascendente pode ser visto 
como reduzir uma cadeia w (o programa) para o símbolo 
inicial da gramática. 
 
– Em cada passo do processo, uma subcadeia específica é 
casada com o lado direito de uma produção e , então, é 
substituída pelo não-terminal da cabeça dessa produção 
 
– Por definição, uma redução é o inverso de uma derivação 
 
 
 
7 
Analisador Sintático Ascendente 
 
– Principais decisões da análise sintática ascendente: 
 
• Determinar quando reduzir 
• Determinar a produção a ser utilizada para que a 
análise prossiga 
 
 
 
 
 
 
 
 
 
 
8 
Analisador Sintático Ascendente Shift-Reduce 
• O analisador sintático ascendente shift-reduce possui: 
 
– Uma pilha: na qual são empilhados símbolos da gramática 
(terminais e não terminais) 
 
– A entrada: contém o restante da cadeia a ser reconhecida 
 
• Inicialmente, a pilha está vazia 
 
• O símbolo $ é utilizado para marcar o final da cadeia de 
entrada 
 
 
 
9 
Analisador Sintático Ascendente Shift-Reduce 
• O analisador sintático ascendente baseia-se em quatro 
operações: 
 
– Shift (transfere): lê o próximo token da entrada e o 
empilha 
 
– Reduce (reduz): realiza uma redução. 
• Escolhe a regra da gramática X → ABC 
• Desempilha C, B, A 
• Empilha X 
 
 
 
 
10 
Analisador Sintático Ascendente Shift-Reduce 
 
– Accept (aceita): anuncia o término bem sucedido da 
análise 
 
– Error (erro): ao descobrir um erro de sintaxe, chama uma 
rotina de recuperação de erro 
 
 
 
 
 
 
 
 
 
11 
Analisador Sintático Ascendente Shift-Reduce 
 
• Durante a leitura da entrada da esquerda para a direita, o 
analisador sintático: 
 
– Transfere zero ou mais símbolos da entrada para a pilha 
 
– Quando uma cadeia β de símbolos do topo da pilha casa com o 
lado esquerdo que uma produção apropriada, uma operação de 
redução (reduce) é realizada 
 
– O analisador repete este ciclo 
• até que um erro é detectado na entrada ou 
 
• até que a pilha contenha apenas o símbolo inicial da 
gramática 
 
 
12 
Analisador Sintático Ascendente Shift-Reduce 
• Exemplo: 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
13 
Pilha Entrada Ação 
 id1 * id2 $ Shift 
 id1 * id2 $ Reduce F → id 
 F * id2 $ Reduce T → F 
 T * id2 $ Shift 
 T * id2 $ Shift 
 T * id2 $ Reduce F → id 
 T * F $ Reduce T → T *F 
 T $ Reduce E → T 
E $ Accept 
E → E + T | T 
T → T * F | F 
F → (E) | id 
 
Analisador Sintático LR(k) 
 
• A forma de analisador sintático ascendente prevalente é o 
LR(k): 
 
– L indica left-to-right parse: a entrada é processada da 
esquerda para a direita; 
 
– R indica rightmost-derivation: a derivação é mais à direita 
ao reverso; 
 
– k indica k-token lookahead: necessidade de ler k tokens à 
frente. Na prática, k=0 ou k=1. 
 
 
 
14 
Analisador Sintático LR(k) 
 
• Quando um analisador sintático shift-reduce sabe quando 
transferir para a pilha (shift) ou quando reduzir (reduce)? 
 
• Por exemplo, considerando a gramática a seguir, e os estados 
da pilha e da entrada 
 Pilha Entrada 
E → E + T | T T * id2 $ 
T → T * F | F 
F → (E) | id 
 
 Como o analisador descobre que a ação apropriada é shift e 
não uma redução E → T? 
 
 
15 
Analisador Sintático LR(k) 
• O analisador sintático ascendente faz isso mantendo estados para 
acompanhar onde se encontra a análise. 
 
• Para entender o algoritmo de construção de um parser LR(1), é útil 
compreender primeiro o algoritmo de construção de um parser 
LR(0) 
 
• As gramáticas LR(0) são aquelas para as quais é possível construir 
um parser analisando apenas a pilha, ou seja, sem token algum 
como lookahead 
 
• Embora essa classe de gramática não seja usual para representar 
construções em linguagens de programação, o algoritmo de 
construção de seu parser provê uma introdução à construção de 
parser LR(1) 
 
 
16 
Analisador Sintático LR(0) 
• Os estados representam conjuntos de itens. 
 
• Um item LR (0) (ou simplesmente item) de uma gramática G é 
uma produção de G com um ponto (•) em alguma posição do 
seu lado direito. 
 
• Exemplo: A produção A→ XYZ gera os quatro itens a seguir 
A→ •XYZ 
A→ X • YZ 
A→ XY • Z 
A→ XYZ • 
 
 
 
17 
Analisador Sintático LR(0) 
• A produção A→ λ gera apena um item: 
A→ • 
 
• Um item indica quanto de uma produção já foi visto em 
determinado ponto no processo de reconhecimento sintático. 
 
• Por exemplo: 
– A→ •XYZ: indica o início da busca de uma cadeiaderivável de XYZ 
– A→ X • YZ: indica que uma cadeia derivável de X foi encontrada e que 
espera-se encontrar em seguida uma cadeia derivável de YZ 
– A→ XYZ •: indica que o lado direito XYZ já foi derivado e que pode ser 
o momento de reduzir XYZ para A. 
 
 
 
18 
Analisador Sintático LR(0) 
• Coleção LR(0) canônica: é a coleção de itens LR(0) de uma 
gramática 
 
• Essa coleção oferece a base para a construção de um AFD 
(autômato finito determinístico) 
 
• O AFD, denominado autômato LR(0), é usado para dirigir as 
decisões durante a análise 
 
• Cada estado no AFD corresponde a um conjunto de itens na 
coleção LR(0) canônica 
 
• A seguir, é apresentado como este AFD é construído 
 
 
19 
Analisador Sintático LR(0) 
• O AFD é aplicado aos estados da pilha e não à entrada 
 
• As arestas do AFD são rotuladas com os símbolos terminais e 
não terminais que podem aparecer na pilha 
 
• A tabela de transição é rotulada com quatro tipos de ações: 
– sn: shift e vá para estado n; 
– gn: vá para (goto) estado n; 
– rk: redução pela regra k; 
– a: aceitação; 
– entrada em branco: erro. 
 
 
 
 
20 
Analisador Sintático LR(0) 
• Considere a gramática a seguir e o que o parser para ela realizará 
 
0. S’ → S$ 
1. S → (L) | 
2. x 
3. L → S | 
4. L, S 
 
• Inicialmente, a pilha está vazia e a entrada é S$ 
 
• Ou seja, o lado direito da produção S’ → S$ estará na entrada 
 
• Isso é indicado por S’ → •S$ 
 
 
 
21 
Analisador Sintático LR(0) 
• Neste estado, em que a entrada começa com S, significa que 
ela pode começar com qualquer lado direito possível de uma 
produção S. 
 
• Isso é indicado por: 
 
 
 
 
• Esse é o estado 1 
 
 
 
 
22 
S’ → •S$ 
S → •x 
S → •(L) 
1 
Analisador Sintático LR(0) 
• Ações shift: 
 
– No estado 1, considere o que ocorre se houver um shift de 
x 
• Neste caso, o topo da pilha é um x 
 
• Isso é representado pelo estado 
 
 
 
• No AFD, então, no estado 1, quando houver x na 
entrada, a ação é s2 
 
 
23 
S → x• 
2 
Analisador Sintático LR(0) 
– No estado 1, considere o que ocorre se houver um shift de 
( 
 
• S → (•L) 
 
• Neste caso 
– o topo da pilha é um ( ; 
– o restante da entrada começa com alguma cadeia 
derivada de L, seguido por ); 
– Quais tokens podem começar a entrada a partir 
deste ponto? 
 
24 
Analisador Sintático LR(0) 
– Isso é encontrado incluindo-se todas as produções L 
no conjunto de itens: L → •L,S e L → •S 
 
– Uma das produções incluídas é L → •S. Então, deve 
ser incluído neste estado também todas as 
produções S 
 
 
 
 
25 
S → (•L) 
L → •L,S 
L → •S 
S → •(L) 
S → •x 
3 
Analisador Sintático LR(0) 
• No AFD, então, no estado 1, quando houver ( na 
entrada, a ação é s3 
 
• No estado 3, quando houver ( na entrada, a ação é s3 
– Seguindo o mesmo raciocínio do estado 1, quando houver um 
shift de um ( no caso do item S → •(L), resultará em S → (•L), 
que corresponde ao próprio estado 3. 
 
 
 
 
26 
Analisador Sintático LR(0) 
• Ações goto: 
– No estado 1, considere o efeito de o parser ter passado 
por uma cadeia de tokens derivadas do não terminal S 
 
– O efeito disso é representado por 
 
 
– Neste caso, todos os símbolos à direita da produção S 
serão desempilhados, e o parser executará uma ação goto 
no estado 1 para o símbolo S 
 
– No AFD, então, no estado 1, quando houver uma redução 
de S na entrada, a ação é g4 (vá para o estado 4) 
 
 
27 
S’ → S•$ 
4 
Analisador Sintático LR(0) 
• Ações reduce: 
– No estado 2, há um • no final de um item 
 
 
– Isso significa que no topo da pilha há um lado direito 
completo de uma produção (no caso, a produção S → x), 
pronta para redução 
 
– Neste estado, o parser deve realizar uma redução 
– Na tabela de transição do AFD, todas as entradas 
referentes ao estado 2 são marcadas com r2 (redução 
segundo a regra 2) 
 28 
S → x• 
2 
Analisador Sintático LR(0) 
• As operações básicas exemplificadas anteriormente nos 
estados são : 
 
– Identificação do fechamento de conjunto de itens 
CLOSURE(I) 
 
– Função de transição GOTO(I,X) 
 
• I é um conjunto de itens 
 
• X é um símbolo terminal ou não terminal da gramática 
 
 29 
Analisador Sintático LR(0) 
• Fechamento de conjuntos de itens – CLOSURE(I) : 
– Se I é um conjunto de itens para uma gramática G, então CLOSURE(I) é 
o conjunto de itens construídos a partir de I pelas duas regras: 
 
1. Inicialmente, acrescente todo item de I no CLOSURE(I) 
 
2. Se A → α •X β está em CLOSURE(I) e X → γ é uma produção 
 
2.1 Adicione o item X → • γ em CLOSURE(I), se ele ainda não 
estiver lá 
 
2.2 Aplique essa regra até que nenhum outro item possa ser 
incluído no CLOSURE(I) 
 
30 
Analisador Sintático LR(0) 
Closure(I) = 
 repita 
 para todo item A → α •X β em I 
 para toda produção X → γ 
 Insira X → • γ em I 
 até que I não mude mais 
 retorne I 
 
 
 
 Exemplo de uso: 
 
 
31 
S → (•L) 
L → •L,S 
L → •S 
S → • (L) 
S → •x 
3 
Analisador Sintático LR(0) 
• Função de transição – GOTO(I,X): 
– É definida como o fechamento do conjunto de todos os itens 
 [A → α X • β ] tais que [A → α • X β] está em I 
 
– Intuitivamente, a função GOTO é utilizada para definir as transições no 
autômato LR(0) 
 
– Os estados no autômato são os conjuntos I 
 
– GOTO(I,X) especifica a transição do estado I para um novo estado I’ 
sob a entrada X 
 
 
32 
Analisador Sintático LR(0) 
Goto(I, X) = 
 inicie J com conjunto vazio 
 para todo item A → α •X β em I 
 insira A → α X • β em J 
 retorne Closure(J) 
 
Exemplo: 
 J={} 
 Item: S’ → •S$ 
 Inserir S’ → S • $ em J : J={[S’ → S • $]} 
 CLOSURE(J) = {[S’ → S • $]} 
 GOTO(1,S) = {[S’ → S • $]} 
 Significa que: no estado 1, havendo um processamento 
completo de S, vá para o estado I igual a {[S’ → S • $]}. No exemplo, este 
estado é o 4. 
 
 
33 
S’ → •S$ 
S → •x 
S → •(L) 
1 
Analisador Sintático LR(0) 
• Com as funções CLOSURE(I) e GOTO(I,X), a coleção canônica de 
itens LR(0) para uma gramática G é construída: 
 
 Inclua na gramática G uma produção inicial auxiliar S’→ S$ 
 itens(G) 
 início 
 C = CLOSURE({[S’→ •S$]}); 
 repita 
 para cada conjunto de itens I em C 
 para cada símbolo X da gramática 
 se GOTO(I,X) não é vazio e não está em C 
 Adicione GOTO(I,X) em C 
 até que nenhum novo conjunto de itens seja adicionado em C 
 fim 
 34 
Analisador Sintático LR(0) 
• Exemplo: construir a coleção canônica de itens LR(0) para a 
gramática 
0. S’ → S$ 
1. S → (L) | 
2. x 
3. L → S | 
4. L, S 
 
Passo 1: 
O primeiro item canônico é CLOSURE({[S’→ •S$]}) 
 
 
35 
1 
S’ → •S$ 
S → •x 
S → •(L) 
Analisador Sintático LR(0) 
Passo 2: 
Computar GOTO(I,X) para cada item na coleção para cada símbolo da 
gramáticaGOTO(1,x): 
 J = {[S → x • ]} 
 GOTO(1,x) = CLOSURE (J) = {[S → x• ]} 
 Como este item ainda não existe na coleção, ele é inserido 
 
 
36 
1 
S’ → •S$ 
S → •x 
S → •(L) 
1 
S’ → •S$ 
S → •x 
S → •(L) 
S → x• 
2 x 
Analisador Sintático LR(0) 
GOTO(1,(): 
 J = {[S → ( •L )]} 
 GOTO(1, () = CLOSURE (J) = {[S → ( •L )] , [L → •S], [L → •L,S] , [S → •(L) ], 
[S → •x ]} 
 Como este item ainda não existe na coleção, ele é inserido 
 
 
37 
1 
S’ → •S$ 
S → •x 
S → •(L) 
S → x• 
2 x 
S → (•L) 
L → •L,S 
L → •S 
S → • (L) 
S → •x 
3 
( 
Analisador Sintático LR(0) 
GOTO(1,S): 
 J = {[S’ → S • $]} 
 GOTO(1,S) = CLOSURE (J) = {[S’ → S • $]} 
 Como este item ainda não existe na coleção, ele é inserido 
 
 
38 
1 
S’ → •S$ 
S → •x 
S → •(L) 
S → x• 
2 x 
S → (•L) 
L → •L,S 
L → •S 
S → • (L) 
S → •x 
3 
( 
S’ → S•$ 
4 
S 
Analisador Sintático LR(0) 
GOTO(1,)), GOTO(1,L) e GOTO(1,,) são vazios pois não há itens no estado 1 
com o • antes de ) , L ou de ,. 
 
 
 
Em resumo: para cada estado I inserido da coleção canônica, para cada item 
dele, mover o ponto à frente do símbolo X e computar o CLOSURE. Inserir 
uma aresta de I para o novo estado criado, rotulada com o símbolo X. 
 
39 
Analisador Sintático LR(0) 
40 
S → (•L) 
L → •L,S 
L → •S 
S → • (L) 
S → •x 
3 
( 
1 
S’ → •S$ 
S → •x 
S → •(L) 
S → x• 
2 x 
S’ → S•$ 
4 
S 
Estado de aceitação 
Estado de redução 
S → (L•) 
L → L •,S 
5 L 
L → S• 
7 
Estado de redução 
S 
x 
S → (L)• 
6 
Estado de redução 
) 
( 
L → L, •S 
S → •(L) 
S → •x 
8 
x 
( 
Estado de redução 
L → L, S • 
9 
, 
S 
Analisador Sintático LR(0) 
• A partir da coleção canônica de itens LR(0), a tabela de parser 
da gramática é construída: 
 
– As linhas da tabela são os estados 
 
– As colunas da tabela são os símbolos da gramática 
 
– As entrada das tabelas são marcadas com as ações: sn, gn, rk, a ou 
branco. 
 
41 
Analisador Sintático LR(0) 
Tabela de parser para o exemplo: 
 
 
42 
( ) x , $ S L 
1 s3 s2 g4 
2 r2 r2 r2 r2 r2 
3 s3 s2 g7 g5 
4 a 
5 s6 s8 
6 r1 r1 r1 r1 r1 
7 r3 r3 r3 r3 r3 
8 s3 s2 g9 
9 r4 r4 r4 r4 r4 
Analisador Sintático LR(0) 
• O algoritmo do parser é: 
 
– Busque o estado no topo da pilha e o símbolo da entrada para obter 
a ação 
 
– Se a ação é: 
 
• Shift(n): 
– avance na entrada um token e o empilhe; 
– empilhe n. 
 
 
43 
Analisador Sintático LR(0) 
• Reduce(k): 
– desempilhe a quantidade de símbolos que houver do lado 
direito da regra k; 
– seja X o símbolo do lado esquerdo da regra k; 
– no estado que estiver no topo da pilha, busque a entrada da 
tabela para tal estado e para X, para obter “goto n”; 
– empilhe X; 
– empilhe n. 
 
• Accept: 
– finalize a análise; 
– informe sucesso. 
 
• Error: 
– finalize análise; 
– Informe erro. 
44 
Analisador Sintático LR(0) 
• Exemplo : executando o parser do exemplo anterior para a 
entrada (x,x) 
 
 
 
45 
Pilha Entrada Ação 
1 (x,x)$ shift (s3) 
1 (3 x,x)$ shift (s2) 
1 (3 x2 ,x)$ redução S → x 
1 (3 S7 ,x)$ redução L → S 
1 (3 L5 ,x)$ shift (s8) 
1 (3 L5 ,8 x)$ Shift (s2) 
1 (3 L5 ,8 x2 )$ redução S → x 
1 (3 L5 ,8 S9 )$ redução L → L, S 
1 (3 L5 )$ shift (s6) 
1 (3 L5 )6 $ redução S → (L) 
1 S4 $ accept 
( ) x , $ S L 
1 s3 s2 g4 
2 r2 r2 r2 r2 r2 
3 s3 s2 g7 g5 
4 a 
5 s6 s8 
6 r1 r1 r1 r1 r1 
7 r3 r3 r3 r3 r3 
8 s3 s2 g9 
9 r4 r4 r4 r4 r4 
0. S’ → S$ 
1. S → (L) | 
2. x 
3. L → S | 
4. L, S 
Referência Bibliográfica 
Compiladores – Princípios, técnicas e ferramentas. 
Aho, A. V et al. 2ª edição 
Seção 4.5, exceto 4.5.4 
Seção 4.6 - até 4.6.3 (inclusive) 
 
Modern Compiler Implementation in Java. Second Edition. 
Andrew W. Appel. 
Capítulo 3. 
 
 
 
46