KOI: Lab Exercise 5

This exercise is about abstract syntax trees.

Resources

Part A: Building syntax trees

Continue building on the compiler from the previous assignment by modifying your Bison parser from lab 3 so that it accepts a sequence of expression statements. An expression statement is an expression terminated by a semicolon. Example input: 
10+20*30+x+y;   
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 Bison'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 syntax tree (that is, a pointer to its root node) 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:
  +
    +
      x
      7
    y
;
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. It also prints every one-hundreth i. 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. 

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

It is a good idea to have a token that marks the end of the program, such as done in my example above, instead of using the normal end of file. In the next assignment you will modify your compiler so it actually executes the program, and not just prints syntax trees. Among other things it will read input from the user with the read statement. That can be difficult if the standard input has reached end of file.

Report

There are two ways to pass this lab. Ideally you should do this: But as an alternative, you can instead do this.

About sources and collaboration:
  • Each group (which normally consists of one or two students) must make its own solution to each assignment, and submit or present it, but it is not forbidden to collaborate or ask other students for help. However, in that case you must clearly state who you have collaborated with. Each solution must include the name of everyone who contributed to the work, Collaboration is thus perfectly fine, but must be clearly stated.
  • You must add an LLM statement to the lab report, where you state if and how you have used large language models, and some experiences from that. Was the LLM helpful, and in what way? Did it help your learning, or maybe in some way hinder it?
  • All sources (such as books, web pages, colleagues and LLMs) used in the solution of the assignment must be stated.

Thomas Padron-McCarthy (thomas.padron-mccarthy@oru.se) August 28, 2025