KOI: Some solutions to exercise 2

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

Question 1

good morning
good day
good evening
good good

Question 2

One or more greetings as described above. As a list:

good morning
good day
good evening
good good
good morning good morning
good morning good day
good morning good evening
good morning good good
good day good morning
good day good day
good day good evening
good day good good
good evening good morning
good evening good day
good evening good evening
good evening good good
good good good morning
good good good day
good good good evening
good good good good
good morning good morning good morning
...

Question 3

a) The same language as in question 2 above.

b) Names are important in grammars, just as in programming. Programming is a form of communication, not with the computer but with other humans who will read your program, and you should help them understand the program. One part of that is to chose good names for variables and other things.

Question 4

These seven terminals:

Christmas!
Done!
Glad
Merry
Midsommar!
Påsk!
Trevlig

or perhaps these nine:

Christmas
Done
Glad
Merry
Midsommar
Påsk
Trevlig
Exclamation-mark
Newline

Question 5

...

Question 6

...

Question 7

The token sequence: if ( variable < variable ) if ( variable < variable ) variable = integer-literal ; variable = integer-literal ;

Deriving this token sequence from the start symbol statement-list, using the productions in the grammar. That a terminal is underlined just means that it will be expanded in the next step. We have always expanded the leftmost non-terminal, but that is not necessary. In the final step, we use the production statement-list -> empty.

statement-list
statement statement-list
if ( condition ) statement statement-list
if ( variable < variable ) statement statement-list
if ( variable < variable ) if ( condition ) statement statement-list
if ( variable < variable ) if ( variable < variable ) statement statement-list
if ( variable < variable ) if ( variable < variable ) variable = integer-literal ; statement-list
if ( variable < variable ) if ( variable < variable ) variable = integer-literal ; statement statement-list
if ( variable < variable ) if ( variable < variable ) variable = integer-literal ; variable = integer-literal ; statement-list
if ( variable < variable ) if ( variable < variable ) variable = integer-literal ; variable = integer-literal ;

Another way to show the derivation is as this tree:

Derivation

Thomas Padron-McCarthy (thomas.padron-mccarthy@oru.se) November 9, 2024