KOI: Exercise 7: syntax-directed translations, type systems

You can do this exercise in any size group you wish. Don't worry if you find some of the questions difficult to answer, since they may be intended to initiate a discussion rather than have a single correct answer.

Preparations

Before this exercise you should have:

Question 1

Here is a grammar for a simple language for working with sets of numbers. For example, the expression { 1 3 } union { 2 3 5 } union { } should evaluate to { 1 2 3 5 }. The start symbol is expression.

expression -> set-literal
expression -> expression union expression
set-literal -> { number-list }
number-list -> number number-list
number-list -> empty

empty should be written using the "e" symbol for an empty string, but it is difficult to write in HTML in a way that is guaranteed to work in all web browsers.

a) Is the grammar ambiguous?

b) How many different parse trees can be constructed for the input { 1 2 } union { 3 }?

c) Draw a parse tree for the input { 1 2 } union { 3 }. A parse tree has a node for each production used to generate the expression from the start symbol, or, which is the same thing in reverse, used to reduce the expression to the start symbol.

d) Add an attribute result to each node in the parse tree, that contains the values of each sub-expression, and the value it has at each node.

e) Write a syntax-directed definition for calculating those values. A syntax-directed definition associates a semantic rule with each production in the grammar, stating how to calculate the values of the attributes on the left-hand side of the production from the values of the attributes on the right-hand side of the production. You can assume that the standard set operations, such as union, are available as functions that you can call.

f) Verify that the calculated values, using the syntax-directed definition, for the parse tree in (a) above agree with what you wrote in (d).

Question 2

A slightly more advanced version of the language in the question above allows not only for set literals, such as { 1 2 3 }, but also free-standing integer literals, such as 3. We add a new operator, in, that will check if an integer is a member of a set. Here are some examples of valid input:

{ 1 3 } union { 2 3 5 } union { }
3 in { 1 2 3 }
3 in { 1 3 } union { 2 3 5 } union { }

Here is a grammar for the new language. The start symbol is still expression, and the grammar is the same as in the question above, except for the two new productions at the end.

expression -> set-literal
expression -> expression union expression
set-literal -> { number-list }
number-list -> number number-list
number-list -> empty
expression -> number
expression -> expression in expression

You can only take the union of two sets, and the in operator must have an integer and a set as operands. This grammar, however, doesn't care about data types. The following expressions are all syntactically correct, but they each contain a type error:

{ 1 3 } in { 2 3 5 }
{ 1 3 } in 4
3 in 3
{ 1 3 } union 4
4 union { 1 3 }
3 union 3

a) The grammar is ambiguous. The expression 1 in { 2 } union { 3 } can be parsed in two ways according to our grammar. Draw both parse trees.

b) Add an attribute type to each node in each parse tree, and the value it has at each node. The values of the type attribute are the data types int, set, bool and error. (bool is the result of the in operator, and error is the result of a type error.)

c) Write a syntax-directed definition for deriving the type values.

d) Verify that the calculated values, using the syntax-directed definition, for the parse trees in (a) above agree with what you wrote in (b).

e) Discuss: Is it a good idea to have a grammar that allows for type errors, and leave type checking to the next phase after parsing, the semantic analyzer?

f) Discuss: Is it a good idea to have an ambiguous grammar, which is made un-ambiguous when removing all parse trees that result in a type error?

There are some solutions to some of the questions, but try to solve them yourself first.

Thomas Padron-McCarthy (thomas.padron-mccarthy@oru.se) September 25, 2023