Copyright © 2006 Gradiance Corporation.

 

 

     

Syntax-Directed Definitions

 

 

 

SDD's.

 

1.  

Here is a SDD that produces an inherited translation T.p and synthesized translations S.q and T.q: 

S → T
          {T.p = 1;
           S.q = T.q;
          }
T → T1T2
          {T1.p = T.p + 1;
           T2.p = T.p + 2;
           T.q = T1.q * T2.q;
          }
T → a
          {T.q = T.p + 4}
T → b
          {T.q = T.p + 1}

Apply this SDD to the following parse tree:

Note that the letters A, B, C, D, and E are used to refer to the interior, nonroot nodes of this parse tree, and are not part of the grammar or the SDD. Each of the interior nodes is labeled by variable T. The leaves are labeled only by one of the terminals, a or b; the root is labeled S, and these nodes have no names. Also note that the subscripts 1 and 2 on T in the rule for T → TT are not part of the grammar or the translation; they are just used to distinguish different uses of variable T.

Evaluate S.q at the root. Then, identify its value from the choices below.

 

 

 

 a) 

120

 

 b) 

150

 

 c) 

144

 

 d) 

132

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

2.  

Here is a SDD that produces an integer-valued translation S.t for the variable S: 

S → S1S2c    {S.t = S1.t + S2.t}
S → a        {S.t = 4}
S → b        {S.t = 7}

Apply this SDD to the following parse tree:

Note that the letters A, B, C, D, and E are used to refer to the interior nodes of this parse tree, and are not part of the grammar or the SDD. Each of the interior nodes is labeled by variable S. The leaves are labeled only by one of the terminals, a, b, or c, and these nodes have no names. Also note that the subscripts 1 and 2 on S in the rule for S → SSc are not part of the grammar or the translation; they are just used to distinguish different uses of variable S.

Choose, from the list below, value of S.t at the root of the parse tree (the node named A).

 

 

 

 a) 

17

 

 b) 

19

 

 c) 

18

 

 d) 

16

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

3.  

The following syntax-directed translation scheme uses an inherited attribute A.p and synthesized attributes S.v and A.v:

S → A

{A.p = 0; S.v = A.v}

A → aA1

{A1.p = A.p + 1; A.v = A1.v}

A → bA1

{A1.p = A.p + 1; A.v = A1.v + 2A1.p}

A → ε

{A.v = 0}

Note that the subscript 1 appearing on certain occurrences of attribute A is there only to distinguish A's appearing in the body and head of the productions. Describe the translation performed by this SDT. Demonstrate your understanding by identifying below a pair (w,x), where w is a string of a's and b's, and x is the value of S.v at the root of the parse tree for w, when that tree is annotated with the values of p and v according to this SDT.

 

 

 

 a) 

(abb, 3)

 

 b) 

(babb, 26)

 

 c) 

(babb, 11)

 

 d) 

(bbab, 11)

 

 

 

 

 

4.  

Here is a SDD that produces an integer-valued translation S.t for the variable S: 

S → S1S2c    {S.t = f(S1.t, S2.t)}
S → a        {S.t = 0}
S → b        {S.t = 1}

It is not important what function f does. Suppose this SDD were applied to the following parse tree:

Note that the letters A, B, C, D, and E are used to refer to the interior nodes of this parse tree, and are not part of the grammar or the SDD. Each of the interior nodes is labeled by variable S. The leaves are labeled only by one of the terminals, a, b, or c, and these nodes have no names. Also note that the subscripts 1 and 2 on S in the rule for S → SSc are not part of the grammar or the translation; they are just used to distinguish different uses of variable S.

To evaluate this SDD on the given tree, we must evaluate S.t at each of the nodes A, B, C, D, and E, in an appropriate order. To find the appropriate orders, construct the dependency graph for the values of S.t at these five nodes, and find all the topological orders of that graph. Then, find one of these orders in the list below.

 

 

 

 a) 

E,B,D,C,A

 

 b) 

B,C,E,D,A

 

 c) 

C,B,E,D,A

 

 d) 

B,C,D,E,A

 

 

 

 

 

5.  

Here is a syntax-directed definition:

1)

S → S1 a

{S.t = a||S1.t||a}

2)

S → S1 b

{S.t = b||S1.t||b}

3)

S → c

{S.t = ε}

Note that:

  1. The subscript 1 on S is used only to distinguish the two occurrences of S within a production.
  2. || stands for string concatenation.

Describe the terminal strings generated by the grammar and their parse trees. Then describe how the translation t is computed for each node labeled S in the parse tree. Demonstrate your understanding by identifying in the list below the pair (x,y) such that y is the translation of x. That is, there is a parse tree with yield x and S.t at the root of this parse tree is y.

 

 

 

 a) 

(cba, aabb)

 

 b) 

(caab, baaaab)

 

 c) 

(cbaa, aabcbaa)

 

 d) 

(caab, aabbaa)

 

 

 

 

 

6.  

Here is a SDD that produces an integer-valued translation S.t for the variable S: 

S → S1S2c    {S.t = S1.t - S2.t}
S → a        {S.t = 5}
S → b        {S.t = 2}

Apply this SDD to the following parse tree:

Note that the letters A, B, C, D, and E are used to refer to the interior nodes of this parse tree, and are not part of the grammar or the SDD. Each of the interior nodes is labeled by variable S. The leaves are labeled only by one of the terminals, a, b, or c, and these nodes have no names. Also note that the subscripts 1 and 2 on S in the rule for S → SSc are not part of the grammar or the translation; they are just used to distinguish different uses of variable S.

Choose, from the list below, value of S.t at the root of the parse tree (the node named A).

 

 

 

 a) 

-2

 

 b) 

0

 

 c) 

-1

 

 d) 

1