Content

Overview

Deals with values (attributes) of symbols; attaches actions to each grammar rule.
Grammars with attributes are attribute grammars.

• Constant: attribute value
• Variable: attribute type

Attribute

Synthesize Attributes

Passing attributes up a parse tree: synthesize attributes. Natural for buttom-up parsing.

X -> Y1Y2...Yn
X.a = f(Y1.a,Y2.a,...,Yn.a)

Ex.

int1 -> digit | int2 digit

int1 and int2 are subscripts: different instances of the same grammar symbol.

Inherited Attributes

Passing attributes down a parse tree: inherit attributes. Natural for top-down parsing.

X -> Y1Y2...Yn
Yk.a = f(Y1.a,Y2.a,...,Yk-1.a,Yk+1.a,Yn.a)

Ex.

P -> DS {S.dl = D.dl} // dl = declared list
D1 -> var V; D2 {D1.dl = addlist(V.name, D2.dl)}
      | ε {D1.dl = NULL}
S1 -> V := E; S2 {check(V.name, S1.dl); S2.dl = S1.dl;}
      | ε
V -> x {V.name = 'x'}
   | y {V.name = 'y'}
   | z {V.name = 'z'}

Ex. Inherited Attributes for Buttom-Up Parsers

P -> DS {S.dl = D.dl} will only get executed after {check(V.name, S1.dl); S2.dl = S1.dl;}!

Solution 1

// .l
%%
...
x { yylval = 1; return x; }
y { yylval = 2; return y; }
z { yylval = 4; return z; }
E { return E; }
var { return var; }
[=;] { return *yytext; }
\n
.
%%

// .y
%{
...
int dl = 0;
%}

%token var x y z E

%%
P: D S ;
D: var V ';' D { dl += $2; } | ;
S: V '=' E ';' S { printf($1 & dl ? "YES\n" : "NO\n"); } | ;
V: x | y | z ;
%%

• Problems

  - Assignments accumulate on the stack due to right recursion
  - Assignments won't be executed until the end
  

Solution 2

// .y
%{
...
int dl = 0;

%}

%token var x y z E

%%
P: D S ;
D: var V ';' D { dl += $2; } | ;
S: V '=' E ';' { printf($1 & dl ? "YES\n" : "NO\n"); } S | ;
V: x | y | z ;
%%

Fix with mid-rule action.

• Problem

  - Assignments accumulate on the stack due to right recursion
  

Solution 3

// .y
%token var x y z E

%%
P: D S ;
D: D var V ';' { $ $ = $1 + $3; } | { $$ = 0; } ;
S: S V '=' E ';' { printf($2 & $0 ? "YES\n" : "NO\n"); } | ;
V: x | y | z ;
%%

Fix with left recursion.