# Syntax directed translation , definition and actions

I have trouble understanding Syntax directed translation/definition/actions. I am reading dragon book but it confuses me even more.

Having production for simple arithmetic

$$\mathit{expr} \rightarrow \mathit{expr} + \mathit{expr} \mathbin{|} \mathit{expr} - \mathit{expr} \mathbin{|} \mathit{num}$$

$$\mathit{num} \rightarrow 0 \mathbin{|} 1 \mathbin{|} 2 \mathbin{|} \dots \mathbin{|} 9$$

If I understood it correctly, SDT just adds attributes to the nodes and define rules.

for this production rules can looks like

$$\mathit{expr}.\mathit{val} = \mathit{expr}.\mathit{val} + \mathit{expr}.\mathit{val} \mathbin{|} \mathit{expr}.\mathit{val} - \mathit{expr}.\mathit{val} \mathbin{|} \mathit{num}.\mathit{val}$$

$$\mathit{num}.\mathit{val} = 0 \mathbin{|} 1 \mathbin{|} \dots \mathbin{|} 9$$

this all together is called Syntax directed definiton.

Now what starts to confuse me:

It is often written that SDT is used to transfer infix to postfix notation e.g

$\mathit{expr} \rightarrow \mathit{expr} + \mathit{expr}$ will have semantic rule such as $\mathit{expr}.\mathit{val} = \mathit{expr}.\mathit{val} \mathbin{\|} \mathit{expr}.\mathit{val} \mathbin{\|} \text{'+'}$, where $\|$ represents concating of strings.

Is STD strictly defined to trasnform notation to postfix?

Also, where in this fall actions?

By definition

A syntax-directed translation scheme is a notation for specifying a translation by attaching program fragments to productions in a grammar. A translation scheme is like a syntax-directed definition, except that the order of evaluation of the semantic rules is explicitly specified. Program fragments embedded within production bodies are called semantic actions

and example

$$\mathit{expr} \rightarrow^{+} \mathit{expr}\ \ \{\, \mathit{print}(\text{'+'}) \,\}\ \ \mathit{expr}$$

I cannot find what is the usage of this. Which leads to sum of questions: What is STD (rules) for and what are uses of actions in it?

Thanks.

Syntax directed translation uses the hierarchical structure of the input to generate the output. In other words, you exploit the grammar structure to help you to translate the program.

Translating using semantic rules

Semantic actions allow to embed code into a cfg which helps you to translate the program/source code. The following Ruby code should help you to figure out how things work. The following simple translator translates a single line infix expression into postfix expression.

First of all note that I use grammar that is suitable for top-down recursive descent parser, namely without left recursion and unambiguous. Transformation of this grammar is given in your book. So, you have to be familiar at least with a top-down recursive descent parsing method which is simple if you understand and have no problems with direct/indirect recursive calls.

Also please pay attention to how I embedded prints into while loops in order to emit postfix notation. As an exercise try to move the print to another line to get infix notation.

I wrote deliberately in Ruby so that you could play with the code and see it in action and modify it easily. If you have Ruby installed just type ruby parser.rb and see output.

@source = "1*2-3*4"
@index = 0

def get_token()
@token = @source[@index]
@index+=1
end

def exp()
term()
while(@token == '+' || @token == '-')
op = @token #store the operator + or -
get_token() #move to the next input symbol
term()
print op # <= semantic action (print operator + or -)
end
end

def term()
factor()
while(@token == '*' || @token == '/')
op = @token #store the operator
get_token() #move to the next input symbol
factor()
print op # <= semantic action (print operator * or /)
end
end

def factor()
if ('0'..'9').include?(@token) #if @token is a digit
tk = @token #store in temp variable
get_token() #move to the next input symbol
print tk # <= semantic action (print a digit)
else
puts 'Syntax Error'
end
end

get_token()
puts exp()


Example outputs:

1*2-3*4 is translated into 12*34*-
1+2-3*7 is translated into 12+37*-

Computing expression value using node attributes

The following piece of code demonstrates node attributes in action to compute the value of an infix expression. Semantic actions this time around are lines which compute attribute of each tree node, that is, actual value of the expression.

@source = "9*3-3*7-2"
@index = 0

def get_token()
@token = @source[@index]
@index+=1
end

def exp()
exp_t = term()
while(@token == '+' || @token == '-')
op = @token
get_token()
term_t = term()
# compute attribute of the tree node
if op == '+'
exp_t += term_t
else
exp_t -= term_t
end
end

return exp_t #return attribute to one level up in the tree
end

def term()
term_t = factor()
while(@token == '*' || @token == '/')
op = @token
get_token()
val = factor()
# compute attribute of the tree node
if op == '*'
term_t *= val
else
term_t /= val
end
end

return term_t #return attribute to one level up in the tree
end

def factor()
if ('0'..'9').include?(@token) #if @token is a digit
tk = @token #store in temp variable
get_token() #move to the next input symbol
return tk.to_i #to_i means convert to integer
else
puts 'Syntax Error'
end
end

get_token()
puts exp()


Examples:
9*3-3*7-2 results in 4
9*3-3*7 results in 6
1-1+1*1 results in 1