Syntax directed translation , definition and actions

Question

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?

I appreciate all answers, I read wiki but did not help.

Thanks.

Answer 1

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