|
|
| Line 1: |
Line 1: |
| == Problema ==
| | #REDIRECT [[ist:Attribute Grammars/Exercise 11: Operadores Lógicos]] |
| | |
| Pretende-se construir uma gramática atributiva (em C++) que avalie expressões lógicas. As expressões podem ser constituídas por literais '''p''' ou '''q''', ou por aplicações dos operadores lógicos: '''#''' (conjunção lógica – operador binário), '''@''' (disjunção lógica inclusiva – operador binário), '''/''' (negação lógica – operador unário). Assuma que os terminais '''p''' e '''q''' têm definido o atributo booleano '''val''' (respectivamente, igual ao valor C++ '''true''', para ''verdadeiro''; e '''false''', para ''falso''). O operador unário tem precedência superior aos binários e '''#''' tem precedência superior a '''@'''. É possível usar parênteses (curvos) para alterar as precedências.
| |
| | |
| # Identifique a gramática atributiva correspondente ao problema. Descreva o significado e o tipo de cada atributo. Que tipo de gramática obteve?
| |
| # Identifique a árvore de sintaxe decorada (apresentando o valor lógico da expressão no nó raiz da árvore) e o grafo de dependências para a expressão '''(p@q)#/(p#q)'''
| |
| # Escreva uma especificação YACC que implemente a gramática descrita em 1. Codifique toda a especificação (incluindo as zonas de declarações e de regras) e todas as funções auxiliares. '''Não utilizar variáveis globais.'''
| |
| | |
| == Gramática Atributiva ==
| |
| | |
| '''disj''' representa uma disjunção; '''conj''' representa uma conjunção; '''uni''' representa expressões unárias; e '''elm''' representa elementos mais simples. O atributo booleano '''val''' representa o valor lógico associado a cada expressão.
| |
| | |
| <text>
| |
| disj → disj @ conj { disj_0.val = disj_1.val || conj.val; }
| |
| disj → conj { disj.val = conj.val; }
| |
| conj → conj # uni { conj_0.val = conj_1.val && uni.val; }
| |
| conj → uni { conj.val = uni.val; }
| |
| uni → / elm { uni.val = !elm.val; }
| |
| uni → elm { uni.val = elm.val; }
| |
| elm → ( disj ) { elm.val = disj.val; }
| |
| elm → p { elm.val = p.val; }
| |
| elm → q { elm.val = q.val; }
| |
| </text>
| |
| | |
| Como se pode ver pelas acções semânticas associadas à gramática, todos os atributos são sintetizados, pelo que a gramática é do tipo S.
| |
| | |
| == Árvore Sintáctica Decorada e Grafo de Dependências ==
| |
| | |
| == Especificação YACC (versão directa a partir da gramática acima) ==
| |
| | |
| <text>
| |
| %union{ bool val; }
| |
| %type<val> 'p' 'q' disj conj uni elm
| |
| %%
| |
| disj : disj '@' conj { $$ = $1 || $3; };
| |
| disj : conj { $$ = $1; };
| |
| conj : conj '#' uni { $$ = $1 && $3; };
| |
| conj : uni { $$ = $1; };
| |
| uni : '/' elm { $$ = !$2; };
| |
| uni : elm { $$ = $1; };
| |
| elm : '(' disj ')' { $$ = $2; };
| |
| elm : 'p' { $$ = $1; };
| |
| elm : 'q' { $$ = $1; };
| |
| %%
| |
| </text>
| |
| | |
| == Especificação YACC (versão "compacta") ==
| |
| | |
| <text>
| |
| %union{ bool val; }
| |
| %type<val> 'p' 'q' expr
| |
| %left '@'
| |
| %left '#'
| |
| %nonassoc '/'
| |
| %%
| |
| expr : expr '@' expr { $$ = $1 || $3; }
| |
| | expr '#' expr { $$ = $1 && $3; }
| |
| | '/' expr { $$ = !$2; }
| |
| | '(' expr ')' { $$ = $2; }
| |
| | 'p' { $$ = $1; }
| |
| | 'q' { $$ = $1; }
| |
| ;
| |
| %%
| |
| </text>
| |
| | |
| [[category:Compiladores]] | |
| [[category:Ensino]]
| |