KOI: Lab Exercise 5

This exercise is about abstract syntax trees.

Resources

The course book by Aho, Sethi and Ullman discusses syntax tree in section 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 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:

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 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:
  +
    +
      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 })

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. (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@tech.oru.se) January 12, 2004