6 AnaliseSintatica Parte5 - 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 5 
 
• Análise Sintática Ascendente 
 
– Usando gramáticas ambíguas 
 
 
• Geradores de Analisadores Sintáticos 
 
 
 
2 
Gramáticas Ambíguas 
• Nenhuma gramática ambígua é LR(k) 
 
• A tabela de parser LR(k) sempre possuirá conflitos 
 
• Entretanto, gramáticas ambíguas podem ser úteis se houver 
uma maneira de contornar o conflito 
 
• Dois casos: else pendente, gramática de expressões 
 
 
 
 
 
 
3 
Gramáticas Ambíguas 
• Caso do else pendente: 
 
S → if E then S else S 
 | if E then S 
 | other 
 
Para a entrada if a then if b then s1 else s2 há duas 
interpretações: 
 
1) if a then {if b then s1 else s2} 
 
2) if a then {if b then s1} else s2 
 
 
 
 
4 
S → i S e S 
 | i S 
 | a 
resumidamente 
Gramáticas Ambíguas 
• A tabela de parser LR para a gramática contém conflitos 
 0. S’ → S$ 
1. S → i S e S 
2. | i S 
3. | a 
 
 
 
 
 
 
 
 
 
 
5 
S’ → S • $ 
S’ → • S$ 
S → • i S e S 
S → • i S 
S → • a 
e ... $ 
... 
4 s5/r2 r2 
... 
0 
1 
2 
S → i • S e S 
S → i • S 
S → • i S e S 
S → • i S 
S → • a 
S → a • 
3 
S → i S • e S 
S → i S • 
S → i S e • S 
S → • i S e S 
S → • i S 
S → • a 
S → i S e S • 
6 
4 
5 
S 
a 
i 
S e 
S 
i a 
FOLLOW(S) = {$, e} 
i 
a 
Opta-se pelo shift 
Gramáticas Ambíguas 
 
 
 
 
• Nesta situação, em vez de reescrever a gramática, pode-se 
tolerar o conflito, optando-se por realizar o shift em vez de 
realizar a redução 
 
• Mas isso deve ser utilizado com cuidado: situações de 
conflito são sintomas de gramática mal formulada e devem 
ser contornados eliminando-se a ambiguidade da gramática. 
 
 
 
6 
S → if E then S • else S 
 S →if E then S • 
Gramáticas Ambíguas 
• Caso da gramática de expressões aritméticas: 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
7 
Gramática ambígua 
 
E → E + E 
 | E * E 
 | (E) 
 | id 
 
Gramática não ambígua 
 
E → E + T | T 
T → T * F | F 
F → (E) | id 
 
Gramáticas Ambíguas 
• A tabela de parser LR para a gramática contém conflitos 
 0. E’ → E$ 
1. E → E + E 
2. | E * E 
3. | (E) 
4. | id 
 
 
 
 
 
 
 
 
 
8 
E’ → E • $ 
E → E • + E 
E → E • * E 
E’ → • E$ 
E → • E + E 
E → • E * E 
E → • (E) 
E → • id 
E → E + • E 
E → • E + E 
E → • E * E 
E → • (E) 
E → • id 
E 
+ 
x + ) $ E 
... 
7 s/r1 s/r1 r1 r1 
8 s/r2 s/r2 r2 r2 
... 
0 1 
E → E * • E 
E → • E + E 
E → • E * E 
E → • (E) 
E → • id 
* 
4 
5 
E → E + E • 
E → E • + E 
E → E • * E 
7 E → E * E • 
E → E • + E 
E → E • * E 
8 
E 
E 
Gramáticas Ambíguas 
• A tabela completa de parser LR para a gramática. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
9 
id + * ( ) $ E 
0 s3 s2 g1 
1 s4 s5 acc 
2 s3 s2 g6 
3 r4 r4 r4 r4 
4 s3 s2 g7 
5 s3 s2 g8 
6 s4 s5 s9 
7 r1/s4 r1/s5 r1 r1 
8 r2/s4 r2/s5 r2 r2 
9 r3 r3 r3 r3 
Gramáticas Ambíguas 
• A ambiguidade neste caso pode ser resolvida utilizando-se a 
informação de precedência e associatividade de operadores 
 
• Considere a entrada id + id * id 
 
• Após processar id + id, o parser estará no estado 7 
 
• Neste estado: 
– Como * tem precedência sobre + , o parser deverá 
transferir (fazer um shift) de * para a pilha e, na 
sequência, reduzirá o * e os dois símbolos id ao seu redor 
para uma expressão 
 
 
 
10 
Gramáticas Ambíguas 
• Considere a entrada id + id + id 
 
• Após processar id + id, o parser estará no estado 7 
 
• Neste caso : 
– Como o operador + é associativo à esquerda, os símbolos 
id ao redor do primeiro + precisam ser agrupados primeiro 
– A ação correta, então, é a redução 
 
• Resumindo: no estado 7, 
– Deverá ocorrer shift, se o próximo símbolo for * 
– Deverá ocorrer redução se o próximo símbolo for + 
 
 
 
 
11 
Gramáticas Ambíguas 
• Seguindo o mesmo raciocínio, no estado 8: 
 
– No topo da pilha há E * E 
 
– Deverá haver redução quando houver + (pois * tem 
precedência sob +) ou * (pois * é associativo à esquerda) 
na entrada 
 
 
 
 
 
 
 
 
12 
Gramáticas Ambíguas 
– Tabela de parser para a gramática após resolução de conflitos aplicando-se 
convenientemente as regras de associatividade e precedência de operadores 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
13 
id + * ( ) $ E 
0 s3 s2 g1 
1 s4 s5 acc 
2 s3 s2 g6 
3 r4 r4 r4 r4 
4 s3 s2 g7 
5 s3 s2 g8 
6 s4 s5 s9 
7 r1 s5 r1 r1 
8 r2 r2 r2 r2 
9 r3 r3 r3 r3 
Geradores de Analisadores Sintáticos 
• Há um grande número de geradores de analisadores sintáticos 
 
• São exemplos: 
 
– Yacc (yet another compiler-compiler): um gerador de 
parser LALR para C 
 
• O uso do Yacc está descrito na seção 4.9 do livro 
 
 
 
 
 
 
14 
Geradores de Analisadores Sintáticos 
– CUP: gerador de parser LALR para Java 
 
– JavaCC: gerador de parser recursivo descendente para Java 
 
– Um catálogo de geradores de compiladores pode 
ser encontrado em 
 http://catalog.compilertools.net/ 
 
 
 
 
 
 
15 
CUP 
• CUP (Java Based Constructor of Useful Parsers ) 
 
http://www2.cs.tum.edu/projects/cup/ 
 
– CUP recebe como entrada um arquivo Parser.cup que 
contém a especificação da gramática para a qual será 
gerado o parser 
 
– A saída de CUP são dois arquivos: 
• sym.java: contém declarações de constantes para os símbolos 
terminais (tokens). 
• parser.java: contém a implementação do parser. 
 
 
16 
CUP 
• Estrutura do arquivo de especificação da 
gramática: 
 
– O arquivo de entrada Parser.cup possui as seções: 
 
1. Especificação de pacotes e importações 
2. Código de componentes do usuário 
3. Lista de símbolos terminais e não terminais 
4. Declarações de precedência 
5. Especificação da gramática 
 
 
 
17 
CUP 
1. Especificação de pacotes e importações 
 
– É uma seção opcional 
 
– Contém o nome do pacote para o qual deseja-se que as 
classes sejam geradas 
 package name; 
 
– Após a definição do pacote, pode-se incluir os import 
necessários: 
import package_name.class_name; 
import package_name.*; 
 
 
18 
CUP 
2. Código de componentes do usuário 
 
– É uma seção opcional 
 
– Contém uma série de declarações que permitem que 
código do usuário seja incluído como parte do parser 
gerado 
 
– Uma classe não pública denominada 
CUP$Parser$actions é gerada contendo todo o código do 
usuário 
 
 
 
19 
CUP 
– action code {: código :}; 
 
• Rotinas e variáveis para uso do código inserido na 
gramática podem ser incluídas nesta seção . Um 
exemplo típico disso são as rotinas de manipulação da 
tabela de símbolos. 
 
 
 
 
 
 
 
 
20 
CUP 
– parse code {: código :}; 
 
• Permite que métodos e/ou variáveis sejam incluídas 
diretamente na classe de parser gerada. 
 
• Isso não é muito usual, mas é possível, por exemplo, 
incluir métodos de análise léxica dentro do parser e 
sobrecarregar as rotinas padrão de recuperação de 
erro. 
 
 
 
 
 
21 
CUP 
– init with{: código:}; 
 
• Esta declaração fornece o código que será executado 
pelo parser antes da solicitação do primeiro token. 
 
• Tipicamente, esta declaração é utilizada para inicializar 
o analisador léxico, tabela de símbolos e outras 
estruturas de dados que sejam necessárias pelas ações 
semânticas. 
 
 
 
 
 
22 
CUP 
– scan with{: código :}; 
 
• Esta declaração indica como o parser deve solicitar pelo 
próximo token. 
 
• O código informado será o corpo de um método no 
parser que retorna um objeto do tipo 
java_cup.runtime.Symbol. 
 
• Desta forma, o código informado deverá retornar um 
valor deste tipo. 
 
 
 
23 
CUP 
3. Lista de símbolos 
 
– É uma seção obrigatória 
 
– Nesta seção são declarados cada terminal e não terminal 
que aparecem na gramática. 
 
– Para cada não terminal e terminal devem ser indicados 
seus respectivos tipos 
 
 
 
 
 
24 
CUP 
 terminal classname name1, name2, ...; 
 non terminal classname name3, name4, ...; 
 
 terminal name1, name2, ...; 
 non terminal name3, name4, ...; 
 
– Nome de terminais e não terminais não podem ser iguais 
às palavras reservadas de CUP: "code", "action", "parser", 
"terminal", "non", "nonterminal", "init", "scan", "with", 
"start", "precedence", "left", "right", "nonassoc", 
"import", and "package". 
 
 
 
 
25 
CUP 
4. Precedência e associatividade 
 
– É uma seção opcional 
– Especifica a precedência e associatividade de terminais 
– Isso é útil para a implementação de parser para gramática 
ambígua, como o caso de expressões aritméticas. 
– Há três tipos de declarações de precedência e 
associatividade: 
 precedence left terminal[, terminal...]; 
precedence right terminal[, terminal...]; 
precedence nonassoc terminal[, 
terminal...]; 
26 
CUP 
– Por exemplo: 
 
 precedence left ADD, SUBTRACT; 
 precedence left TIMES, DIVIDE; 
 
 Indica que multiplicação e divisão têm maior precedência 
do que soma e subtração e todos são associativos à 
esquerda 
27 
CUP 
5. A gramática 
– Esta seção começa opcionalmente com 
 
 start with non-terminal; 
 
• Isso indica o símbolo inicial da gramática 
• Se essa declaração não for realizada, o símbolo à esquerda da 
primeira produção é considerado o símbolo inicial 
 
– Cada produção da gramática é da forma: 
Não terminal seguido por “::=” seguido por sentenças 
separadas por “|” 
 
 
28 
CUP 
• Para executar CUP: 
 
java -jar java-cup-11a.jar parser.cup 
 
• Uso integrado de Jflex e CUP: 
 
– %cup: é a diretiva do JFlex que habilita a sua compatibilidade com CUP 
 
– Isso faz o Jflex gerar o analisador léxico com classes e métodos 
nomeados no padrão do CUP 
 
– O analisador léxico gerado pelo JFlex implementa a interface java 
cup.runtime.Scanner, usada no CUP 
 
 
29 
CUP 
• Exemplo: um parser para expressões aritméticas 
 
LEXP → LEXP EXP | EXP 
EXP → E; 
E → number 
 | E + E 
 | E * E 
 | (E) 
 
 
 
30 
CUP 
terminal SEMI, PLUS, TIMES, LPAREN, RPAREN; 
terminal Integer NUMBER; 
 
non terminal expr_list, expr_part; 
non terminal Integer expr; 
 
precedence left PLUS; 
precedence left TIMES; 
 
 
 
 
31 
CUP 
 
expr_list ::= expr_list expr_part | expr_part; 
expr_part ::= expr SEMI; 
expr ::= NUMBER 
 | expr PLUS expr 
 | expr TIMES expr 
 | LPAREN expr RPAREN 
 ; 
 
 
 
32 
CUP 
• Exemplos de entrada e saída do parser gerado: 
 
Entrada: 4 + 4; 
Saída: ok 
 
Entrada:4; 
Saída: ok 
 
Entrada:4+2*3; 
Saída: ok 
 
Entrada: 7 - (4+2)*3; 
Saída: Erro – caractere não reconhecido (-) 
 
Entrada:7 + (4+2)*3; 
Saída: =ok 
 
Entrada: 7 + (4+2()*3; 
Saída: Erro de sintaxe 
 
 
 
 
33 
CUP 
No arquivo de definição do parser são incluídas as ações semânticas 
 
 
expr_list ::= expr_list expr_part | expr_part; 
expr_part ::= expr:e {: System.out.println(" = "+e+";"); :} SEMI; 
expr ::= NUMBER:n 
 {: RESULT=n; :} 
 | expr:l PLUS expr:r 
 {: RESULT=new Integer(l.intValue() + r.intValue()); :} 
 | expr:l TIMES expr:r 
 {: RESULT=new Integer(l.intValue() * r.intValue()); :} 
 | LPAREN expr:e RPAREN 
 {: RESULT=e; :} 
 ; 
 
 
 
 
 
34 
CUP 
• Exemplos de entrada e saída do parser gerado com as ações semânticas implementadas: 
 
Entrada: 4 + 4; 
Saída: =8; 
 
Entrada:4; 
Saída: =4; 
 
Entrada:4+2*3; 
Saída: =10; 
 
Entrada: 7 - (4+2)*3; 
Saída: Erro – token não reconhecido (-) 
 
Entrada:7 + (4+2)*3; 
Saída: =25; 
 
Entrada: 7 - (4+2()*3; 
Saída: Erro 
 
 
 
 
 
35 
Referência Bibliográfica 
Compiladores – Princípios, técnicas e ferramentas. 
Aho, A. V et al. 2ª edição 
Seção 4.8 
 
Modern Compiler Implementation in Java. Second Edition. 
Andrew W. Appel. 
Capítulo 3. 
 
CUP User Manual 
http://www2.cs.tum.edu/projects/cup/ 
 
 
 
 
36