Copyright © 2006 Gradiance Corporation.

 

 

     

Syntax-Directed Translations

 

 

 

SDT's.

 

1.  

Convert the following SDT: 

A → A{a}B | B{b}
B → 0{c}

to a SDT that:

  1. Is a postfix SDT.
  2. Has no left-recursion in the underlying grammar.

Here, A is the start symbol, and a, b, and c are actions.

Which of the following is a SDT that meets the two conditions above?

 

 

 

 a) 

A → A1A3

A3 → B{b}

A1 → A2BA1 | ε

A2 → {a}

B → 0{c}

 

 b) 

A → A3A1

A3 → B{b}

A1 → A2BA1 | ε

A2 → {a}

B → 0{c}

 

 c) 

A → A1B | B{b}

A1 → A{a}

B → 0{c}

 

 d) 

A → B{b}A1

A1 → {a}BA1 | ε

B → 0{c}

 

 

 

 

 

2.  

Here is a SDT with embedded actions: 

S → cS {print "z"} S
S → a {print "x"}
S → b {print "y"}

Suppose we execute this SDT in connection with a top-down parse. What will be printed in response to the input ccaba?

 

 

 

 a) 

zxyxz

 

 b) 

xzyzx

 

 c) 

zzxyx

 

 d) 

zxyzx

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

3.  

Here is a postfix SDT: 

S → aS {print "x"}
S → bS {print "y"}
S → a {print "z"}
S → b {print "z"}

Suppose we execute this SDT in connection with a bottom-up parse. What will be printed in response to the input ababb?

 

 

 

 a) 

zyxyx

 

 b) 

yyxyx

 

 c) 

xyxyy

 

 d) 

xyxyyz