KOI: Lab Exercise 5

This exercise is about abstract syntax trees.

Resources

ALSU-07 5.3.1, Construction of Syntax Trees
(ASU-86 5.2, Construction of Syntax Trees)
Lecture 7 in this course covered that section of the book.
Thomas Niemann: A Compact Guide to Lex & Yacc has some examples of how to build syntax trees from expressions and statements.

Part A: Building syntax trees

Modify your Bison 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:

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 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:
  +
    +
      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.

while statements
if statements with an optional else part
Block statements (that is, a sequence of statements enclosed by { and })
print statements, which can print at least a single variable
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.

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);

Report!

Show your results and discuss them with the teacher,
or,
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. If you use attachments, send them as PDF and not Word. Also send the source code, as a Zip file or equivalent.

Thomas Padron-McCarthy (Thomas.Padron-McCarthy@oru.se) October 15, 2021