KOI: Lab Exercise 5

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

10+20*30+x+y;   
a = 10 + b;

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

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
;

Part C: More statements

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

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!