KOI: Some solutions to exercise 10

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

Question 1

  1. Preprocessor
  2. Program execution
  3. Semantic analysis
  4. Semantic analysis
  5. Semantic analysis
  6. Scanner
  7. Semantic analysis
  8. Semantic analysis
  9. Linker
  10. Optimizer or semantic analysis
  11. Semantic analysis
  12. Scanner
  13. Parser
  14. Scanner

Question 2

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

Answer:

Name (of a species), number (of observed animals), and the keywords species, declarations, done, observation and observations.

Question 3

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

Answer:

name: [a-z]+
number: [0-9]+

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.

Answer:

input -> manydeclarations declarations done manyobservations observations done
manydeclarations -> onedeclaration manydeclarations | ε
onedeclaration -> species name
manyobservations -> oneobservation manyobservations | ε
oneobservation -> observation name number

Question 5

Write a Flex scanner specificaction for the animal language.

Download a solution: animals.l 

%{
    #include "animals.tab.h"
%}

%%

[\n\t ]         { /* Ignore whitespace */ }
"species"       { return SPECIES; }
"declarations"  { return DECLARATIONS; }
"done"          { return DONE; }
"observation"   { return OBSERVATION; }
"observations"  { return OBSERVATIONS; }
[A-ZÅÄÖa-zåäö]+ { return NAME; }
[0-9]+          { return NUMBER; }
.               { fprintf(stderr, "[scanner: ignoring unknown character: '%c' (%d)]\n", *yytext, *yytext); }

%%

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.

Download a solution: animals.y

This Makefile might be useful: Makefile. Type "make animals" to build the Flex- and Bison-based program. Type "make animalsparser" to build the program based on the hand-coded parser in question 7 below. 

%{
    #include <stdio.h>
    extern void yyerror(const char *);
    extern int yylex(void);
%}

%token SPECIES DECLARATIONS DONE NAME OBSERVATION OBSERVATIONS NUMBER
%define parse.error verbose
%start input

%%

input : manydeclarations DECLARATIONS DONE manyobservations OBSERVATIONS DONE { printf("Done!\n"); }
      ;

manydeclarations : onedeclaration manydeclarations
                 | %empty
                 ;

onedeclaration : SPECIES NAME
               ;

manyobservations : oneobservation manyobservations
                 | %empty
                 ;

oneobservation : OBSERVATION NAME NUMBER
               ;

%%

int main() {
    printf("Enter a complete animal input. End with the keyword \"done\" and EOF.\n");
    yyparse();
    printf("Ok!\n");
    return 0;
}

void yyerror(const char *s) {
    printf("Incorrect animal input! Error message: %s\n", s);
}

int yywrap(void) {
    return 1;
}

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.

Download a solution: animalsparser.c

Since the grammar given as a solution above already is suitable for constructing a predictive recursive-descent parser, we can use it as is. Otherwise, we would have had to make some transformations. 

int lookahead;

void match(int expected) {
    if (lookahead != expected)
        error();
    else
        lookahead = scan();
}

void input(void) {
    manydeclarations(); match(DECLARATIONS); match(DONE); manyobservations(); match(OBSERVATIONS); match(DONE);
}

void manydeclarations(void) {
    if (lookahead == SPECIES) {
        onedeclaration(); manydeclarations();
    }
    else {
        /* Empty */
    }
}

void onedeclaration(void) {
    match(SPECIES); match(NAME);
}

void manyobservations(void) {
    if (lookahead == OBSERVATION) {
        oneobservation(); manyobservations();
    }
    else {
        /* Empty */
    }
}

void oneobservation(void) {
    match(OBSERVATION); match(NAME); match(NUMBER);
}

void parse() {
    lookahead = scan();
    input();
    printf("Ok.\n");
}

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