KOI: Some solutions to exercise 7

Please note that these are suggested solutions. There can be other solutions that are also correct.

Question 1

a) Yes. For example, the expression { 1 } union { 2 } union { 3 } can be parsed either as ( { 1 } union { 2 } ) union { 3 } or as { 1 } union ( { 2 } union { 3 } )

b) One. That a grammar is ambiguous means that for some input, more than one parse tree can be constructed. Not for all input!

c) The parse tree:

A parse tree

d) The parse tree decorated with the values of the result attribute:

A decorated parse tree

e)

Production Semantic Rule
expression -> set-literal expression.result = set-literal.result
expression1 -> expression2 union expression3 expression1.result = union(expression2.result, expression3.result)
set-literal -> { number-list } set-literal.result = number-list.result
number-list1 -> number number-list2 number-list1.result = prepend(number.value, number-list2.result)
number-list -> empty number-list = { }

f) ...

Question 2

a) ...

b) ...

c)

Production Semantic Rule
expression -> set-literal expression.type = set
expression1 -> expression2 union expression3 if (expression2.type == set && expression3.type == set)
expression1.type = set
else
expression1.type = error
set-literal -> { number-list } set-literal.type = set
number-list1 -> number number-list2 number-list1.type = set
number-list -> empty number-list.type = set
expression -> number expression.type = int
expression1 -> expression2 in expression3 if (expression2.type == int && expression3.type == set)
expression1.type = bool
else
expression1.type = error

Some of the semantic rules contain error checking, but some don't need it, because the grammar doesn't allow for an expression with the wrong type. For example, in the first production, it is impossible to write a syntactically correct set-literal with a data type that is not set.

d) ...

e) Yes.

f) No.


Thomas Padron-McCarthy (thomas.padron-mccarthy@oru.se) November 16, 2021