KOI: Exercise 2: Grammars and languages

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

A language contains the terminals good, morning, day and evening. The grammar for the language contains the non-terminals greeting and time-specification, and the following productions: 
greeting -> good time-specification
time-specification -> morning
time-specification -> day
time-specification -> evening
time-specification -> good
The start symbol is greeting.

What is the language that this grammar describes? Answer by listing all strings (that is, sequences of terminals) that can be expressed in the language.

How did you find the answer?

Question 2

Here is another grammar: 
several-greetings -> greeting
several-greetings -> greeting several-greetings
greeting -> good time-specification
time-specification -> morning
time-specification -> day
time-specification -> evening
time-specification -> good
The start symbol is several-greetings.

What is the language that this grammar describes?

Question 3

Here is a third grammar: 
time-specification -> boat | boat time-specification
boat -> good several-greetings
several-greetings -> morning | day | evening | good
The start symbol is time-specification.

a) What is the language that this grammar describes?

b) What can we learn from this question?

A Scenario

We are going to write a program where the user can type in the following holiday greetings: A complete input consists of one or more such greetings, with "Done!" at the end. Example: 

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

Question 4

Which terminals are needed to write a grammar for the language in the scenario?

Question 5

Write a grammar for one greeting in the language. The start symbol should be greeting, which represents one greeting according to the scenario.

Question 6

Write a grammar for the greetings language. The start symbol should be input, which represents a complete input according to the scenario. The complete input consists of one or more greetings, followed by "Done!".

Hint: Make a non-terminal called several-greetings, which represents one or more greetings. Several-greetings kan either be a single greeting, or a single greeting followed by several greetings.

Question 7

Here is a grammar for a subset of C: 
statement-list -> statement statement-list | empty
statement -> variable = integer-literal ;
condition -> variable < variable
statement -> if ( condition ) statement
The terminal variable is a variable name, and consists of one or more lower-case letters. The terminal integer-literal is an integer literal, and consists of one or more normal decimal digits. Empty stands for an empty production. The start symbol is statement-list.

Show how the following input can be divided into tokens, and how the token sequence can be derived from the start symbol statement-list using the productions in the grammar. 

if (hjalmar < hulda) if (z < x) w = 33; kalle = 17;

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

Thomas Padron-McCarthy (thomas.padron-mccarthy@oru.se), October 27, 2022