KOI: Lab Exercise 5

This exercise is about abstract syntax trees.


Part A: Building syntax trees

Modify your Yacc parser from lab 3 so that it accepts a sequence of expression statements. An expression statements is an expression terminated by a semicolon. Example input:
a = 10 + b;
Note that the assignment operator "=" is just another operator, so an expression, in this context, can be an assignment.

Let your parser construct a syntax tree of the entire source input. Do not calculate the values of the expressions at this time. Just build the syntax tree. Use Yacc's attribute values ("$$", "$1", etc.).

You may look at some hints about how to build the tree.

Part B: Printing syntax trees

Write a function that takes (a pointer to) a syntax tree as input, and prints it on the standard output or to a file, with proper indentation. You can print the tree using the same format as the source language, or in some other nice and pretty way.

It doesn't have to be very good-looking, just good enough so you can easily verify that the constructed syntax trees are correct.

A minimally pretty output for the syntax tree representing the expression statement x + 7 + y; would look something like this:

Syntax tree:
You may look at some hints about how to print the tree.

Part C: More statements

Add the following statement types, besides expression statements. You'll have to modify all three of the parser, the syntax tree construction, and the syntax tree printer.
  1. while statements
  2. if statements with an optional else part
  3. Block statements (that is, a sequence of statements enclosed by { and })
  4. print statements, which can print at least a single variable
  5. read statements, which can ask for a value of a variable from the user
Write a short program in the language you have just designed. Try to demonstrate everything it can do.

For inspiration, here is a test program I once used for one of many possible languages in this exercise. It reads an integer n, and then calculates and prints the sum and product of the integers from 1 to n. The language you create doesn't have to look like this, but it should be possible to write a program that does the same thing.

product = 1;
while (i < n) {
    if (i % 100 > 0) { } else { print(i); }
    sum = sum + i;
    product = product * i;
    i = i + 1;


Show your results and discuss them with the teacher,
send an e-mail with clear and full explanations of what you have done. Include well-chosen and commented test runs with input and output. (Send your e-mail in plain text format, not as HTML or Word documents or with unnecessary attachments.) Include relevant source code, with any changes clearly marked.

Thomas Padron-McCarthy (Thomas.Padron-McCarthy@oru.se) May 8, 2013