KOI: Exercise 10: Review

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.

This exercise is inteneded as a review session. Most of these questions are from previous exams in the course.

Question 1

We are writing a program that implements a guessing game. The player thinks of a number, and the computer tries to guess the number. Here is an example, with the user's input underlined: 

Think of a number and hit ENTER.

Is it 7?
no
Is it 7?
no
Is it 7?
va?
Answer yes or no!
Is it 7?
sluta
Answer yes or no!
Is it 7?
no
Is it 7?
yes
I won!

As we can see, the computer always guesses 7, until the user gives up and answers "yes".

We have written the program in C, but we made some mistakes, and when we try to build (that is, compile and link) and run the program we will get the error and warning messages shown below. In which of the compiler phases, or at other times, are each of these errors and warnings detected?

(Some of the errors may have to be fixed before we can continue the build an get the other errors.)

The program Messages
#include <stdio.h

int question(void) {
    char reply[10000000];
    while (true) {
        gets(guess);
        if (strcmp(guess, "yes") == 0)
            return 1; @
        else if (strcmp(guess, no) == 0)
            return 0;
        else {
            printf("Answer yes or no!\n");
            return;
        }
    }
}

int Main(void) {
    int answer;
    printf("Think of a number\n");
    printf("and hit ENTER.\n");
    while (getchar() != "\n")
        ;
    do {
        printf("Is it 7?\n");
    } while (question() != 1e);
    printf("I won!\n")
} /* main

(1) missing terminating > character


(2) Segmentation fault (core dumped)
(3) 'true' undeclared
(4) 'guess' undeclared
(5) implicit declaration of 'strcmp'
(6) stray '@' in program
(7) 'no' undeclared



(8) 'return' with no value




(9) undefined reference to 'main'
(10) unused variable 'answer'


(11) comparison between pointer and integer



(12) exponent has no digits
(13) expected ';' before '}' token
(14) unterminated comment

Scenario

Rabbits

Some biologists are making an inventory of the anmials in an area, and they need a language to write down and process their observations. The language should allow them to first declare a number of species, and then a number of observations of individual animals of those species. A complete input in this language might look like this: 

species rabbit
species lion
declarations done
observation rabbit 1
observation lion 30
observation rabbit 3
observations done

This means that the animals we observe are rabbits and lions, and we have observed first a rabbit, then thirty lions, and finally three more rabbits. After listing the species, the "declarations" part of the input is ended with declarations and done. After listing the observations, the "observations" part of the input is ended with observations and done.

Animal names are single words that consist of lower-case letters.

It should be possible to write the input in free format, such as in most common programming languages, for example like this: 

species rabbit species lion declarations

done observation rabbit 1
    observation

lion 30 observation                    rabbit 3 observations done

Question 2

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

Question 3

Out of the terminals, some will not have fixed lexemes. Write regular expressions for each such terminal.

Question 4

Write a grammar for the animal language. The start symbol should be input, which represents a complete input according to the scenario above.

Question 5

Write a Flex scanner specificaction for the animal language.

Question 6

Write a Bison parser specificaction for the animal language. You don't need to perform any actions, just parse the input to see if it is valid input.

Question 7

Write a predictive recursive-descent parser for the animal language, in a language that is at least similar to C, C++, C# or Java. You do not have to write exactly correct program code, but it should be clear which procedures exist, how they call each other, and what comparisons with token types are made. You can assume there is a function called scan, which returns the type of the next token, and a function called error, which you can call when something went wrong and which prints an error message and terminates the program.

Question 8

Add some more terms to this table:

American English British English Swedish Incorrect Swedish
optimize optimise optimera optimisera
optimizer optimiser optimerare optimiserare
compile compile kompilera kompajla
compiler compiler kompilator

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

Thomas Padron-McCarthy (thomas.padron-mccarthy@oru.se) December 1, 2021