Latest revision as of 12:50, 12 February 2019

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.

1. Identifique a gramática atributiva correspondente ao problema. Descreva o significado e o tipo de cada atributo. Que tipo de gramática obteve?
2. 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)
3. 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.

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.

Árvore Sintáctica Decorada e Grafo de Dependências

Especificação YACC (versão directa a partir da gramática acima)

%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;       };
%%

Especificação YACC (versão "compacta")

%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;       }
     ;
%%