(Created page with "== Problema == 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 ap...") |
|||
(7 intermediate revisions by the same user not shown) | |||
Line 1: | Line 1: | ||
== Problema == | == Problema == | ||
− | 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. | + | 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 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)''' | # 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. | + | # 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. | ||
+ | |||
+ | <source lang="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; } | ||
+ | </source> | ||
+ | |||
+ | 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) == | ||
+ | |||
+ | <source lang="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; }; | ||
+ | %% | ||
+ | </source> | ||
+ | |||
+ | == Especificação YACC (versão "compacta") == | ||
+ | |||
+ | <source lang="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; } | ||
+ | ; | ||
+ | %% | ||
+ | </source> | ||
+ | |||
+ | [[category:Compiladores]] | ||
+ | [[category:Ensino]] |
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.
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.
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; }
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.
%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; };
%%
%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; }
;
%%