(→Gramática Atributiva) |
(→Especificação YACC) |
||
Line 27: | Line 27: | ||
== Árvore Sintáctica Decorada e Grafo de Dependências == | == Árvore Sintáctica Decorada e Grafo de Dependências == | ||
− | == Especificação YACC == | + | == 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:Compiladores]] | ||
[[category:Ensino]] | [[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.
<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.
<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>
<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>