# Introduction to Programming Languages/Syntax Directed Translation

Jump to navigation Jump to search

### Syntax Directed Translation

A compiler is a program that converts code written in a programming language into code written in a different programming language. Typically a compiler is used to convert code written in a high-level language into machine code. Like in the case of interpreters, grammars also provide the key data structure that a compiler uses to do its work. As an example, we will implement a very simple compiler that converts programs written in our language of arithmetic expressions to the polish notation. The attribute grammar that does this job can be seen below:

```expr(L) --> mulexp(L1), [+], expr(L2), {append([+], L1, LX), append(LX, L2, L)}.
expr(L) --> mulexp(L).

mulexp(L) --> rootexp(L1), [*], mulexp(L2), {append([*], L1, LX), append(LX, L2, L)}.
mulexp(L) --> rootexp(L).

rootexp(L) --> ['('], expr(L), [')'].
rootexp(L) --> number(L).

number([N]) --> digit(N).
number([ND|LL]) --> digit(ND), number(LL).

digit(N) --> [0], {N is 0}
; [1], {N is 1}
; [2], {N is 2}
; [3], {N is 3}
; [4], {N is 4}
; [5], {N is 5}
; [6], {N is 6}
; [7], {N is 7}
; [8], {N is 8}
; [9], {N is 9}.
```

In this example we dump the transformed program into a list L. The `append(L1, L2, LL)` predicate is true whenever the list LL equals the concatenation of lists L1 and L2. The notation `[ND|LL]` implements the cons operation so common in functional programming. In other words, `[ND|LL]` represents a list that contains a head element `ND`, and a tail `LL`. As an example of use, the execution section below shows a set of queries using our new grammar, this time implemented in a file called `compiler.pl`:

```?- consult(compiler).
true.

?- expr(L, [2, *, 1, 2, 3, +, 3, 2, 1], []).
L = [+, *, 2, 1, 2, 3, 3, 2, 1] ;
false.

?- expr(L, [2, *, '(', 1, 2, 3, +, 3, 2, 1, ')'], []).
L = [*, 2, +, 1, 2, 3, 3, 2, 1] ;
false.
```