COMS W4115
Programming Languages and Translators
Lecture 16: Syntax-directed Translation Schemes
March 26, 2008

Lecture Outline

1. Syntax-directed translation schemes
2. Transforming an SDTS by left factoring
3. SDTSs for translating infix to postfix
4. Translation of while-statements

1. Syntax-directed Translation Schemes

• A syntax directed translation scheme is a context-free grammar with program fragments in the right-hand sides of its productions.
• A postfix SDTS has all of its program fragments at the right end of each production.

2. Transforming an SDTS by Left-factoring

• Given a postfix SDTS with left recursion:

   A → A1 Y     { A.s = g(A1.s, Y.s); }
   A → X        { A.s = f(X.s); }
  

We can left factor the productions, introduce inherited attribute R.i and synthesized attribute R.s for the nonterminal R, and transform the semantic actions as follows to produce an equivalent SDTS.

   A → X  { R.i = f(X.s); }  R  { A.s = R.s; }
   R → Y  { R1.i = g(R.i, Y.s);  R1  { R.s = R1.s; }
   R → ε  { R.s = R.i; }
  

3. SDTSs for Translating Infix to Postfix

• Example 1: Here is a postfix SDTS that translates infix arithmetic expressions into postfix notation. The translation can be done during bottom-up parsing.

   E → E + T     { print('+'); }
   E → T
   T → T * F     { print('*'); }
   T → T
   F → ( E )
   F → digit     { print(digit.lexval); }
  

• Example 2: Here is an SDTS based on an LL(1) grammar that translates infix arithmetic expressions into postfix notation. The translation can be done during top-down parsing parsing.

   E → T A
   A → + T { print('+'); } A
   A → ε
   T → F B
   B → * F { print('*'); } B
   B → ε
   F → ( E )
   F → digit { print(digit.lexval); }
  

4. Translation of while-statements

• Consider the production S → while ( C ) S1 for while-statements. The shape of the code for implementing this production can take the form:

   label L1: // beginning of code for S
      code to evaluate C
      if C is true goto C.true // C.true will be set to L2
      if C is false goto C.false // C.false will be set to S.next
   label L2:
      code to evaluate S1
      goto L1
   S.next:  // this is where control flow will go after executing S
  

• Here is an SDD for this translation:

   S → while ( C ) S1  {
      L1 = newlabel();
      L2 = newlabel();
      S1.next = L1;
      C.false = S.next;
      C.true = L2;
      S.code = label || L1 || C.code || label || L2 || S1.code
   }
  

• We can transform this SDD into the following SDTS:

   S → while (
            { L1 = newlabel(); L2 = newlabel();
              C.false = S.next; C.true = L2;
            }
            C ) { S1.next = L1; }
            S1
            { S.code = label || L1 || C.code || label || L2 || S1.code;
            }
  

5. Reading

• ALSU, Section 5.5.