# COMS W4115

Programming Languages and Translators

Lecture 16: Syntax-directed Translation Schemes

March 26, 2008

## Lecture Outline

- Syntax-directed translation schemes
- Transforming an SDTS by left factoring
- SDTSs for translating infix to postfix
- 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

aho@cs.columbia.edu