Well, here you are. Here is the free information you have all been waiting for, with some extra bits of advice:
Please note that there is no obligation to produce a machine readable solution for this section. Coco/R and other files are provided so that you can enhance, refine, or test your solution if you desire. If you choose to produce a machine readable solution, you should create a working directory, unpack EXAM.ZIP, modify any files that you like, and then copy all the files back to the blank diskette that will be provided.
During the translators course we have made frequent use of the Cocol/EBNF notation for expressing production rules, and in particular the use of the {} and [] meta-brackets introduced by Wirth in his 1977 paper. An example of a system of productions using this notation is as follows:
Home = Family { Pets } [ Vehicle ] "house" .
Pets = "dog" [ "cat" ] | "cat" .
Vehicle = ( "scooter" | "bicycle" ) "fourbyfour" .
Family = Parents { Children } .
Parents = "Dad" "Mom" | "Mom" "Dad" .
Parents = "Dad" | "Mom" .
Child = "Margaret" | "Janet" | "Anne" | "Ntombizodwa" | "Ntombizanele" .
In analysing such productions and/or testing the grammar it has often been suggested that:
(a) they be rewritten without using the Wirth brackets, but using right recursive productions and an explicit e, as for example
Home = Family AllPets Transport "house" .
AllPets = Pets AllPets | e .
Transport = Vehicle | e .
Pets = "dog" PussyCat | "cat" .
PussyCat = "cat" | e .
Vehicle = ( "scooter" | "bicycle" ) "fourbyfour" .
Family = Parents Offspring .
Offspring = Offspring Children | e .
Parents = "Dad" "Mom" | "Mom" "Dad" .
Parents = "Dad" | "Mom" .
Child = "Margaret" | "Janet" | "Anne" | "Ntombizodwa" | "Ntombizanele" .
(b) a check be made to see that all the non-terminals have been defined (this does not occur in the above case - Children is undefined);
(c) a check be made to see that each non-terminal is defined only once (this does not occur in the above case - there are two rules for Parents);
(d) a check be made to see that each non-terminal (other than the goal) must appear on the right side of at least one production (this does not occur in the above case; Child defines a non-teminal which does not appear in any other production).
As a useful service to others who might take this course in future years (and hopeful that, although you might encourage others to do so, you are not forced to do so yourself!), develop a system using Coco/R that will carry out the above transformations and checks.
Here are some suggestions for deriving a complete system:
(a) In the exam kit (EXAM.ZIP) you will find the executables and support files for Coco/R, as used in the practical course. There is also the skeleton of a grammar file EBNF.ATG with suitable definitions of character sets and tokens similar to those you have seen before.
(b) It should be obvious that you will need to set up a "symbol table". In the exam kit is supplied the skeleton of an "include file" EBNF.H, which has a rudimentary form of table that you might like to extend. The template list handler file LIST.H familiar from earlier practicals has also been supplied.
(c) Inventing additional non-terminal names (without clashing with others that might already exist) might be done with the aim of deriving, for example
Home = Family HomeSeq1 HomeOpt2 "house" .
(d) In the exam kit will be found some other example data and production sets to assist in your development of the system, and an executable derived from a model solution.
(e) After converting a set of productions from EBNF to BNF, try converting the BNF productions once again to check that your system works consistently.
COMPILER EBNF $XCN
/* Convert a set of EBNF productions to use BNF conventions, and carry out
some rudimentary checks on their being properly defined.
YOUR IDENTITY HERE */
#include "ebnf.h"
CHARACTERS
cr = CHR(10) .
lf = CHR(13) .
letter = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz" .
lowline = "_".
digit = "0123456789" .
noquote1 = ANY - "'" - cr - lf .
noquote2 = ANY - '"' - cr - lf .
IGNORE CHR(9) .. CHR(13)
COMMENTS FROM "(*" TO "*)" NESTED
TOKENS
nonterminal = letter {letter | lowline | digit} .
terminal = "'" noquote1 {noquote1} "'" | '"' noquote2 {noquote2} '"' .
PRODUCTIONS
EBNF
= (. TABLE_InitTable(); .)
{ Production }
EOF .
Production
= (. char Name[MaxName];
int i; .)
SYNC nonterminal (. LexString(Name, sizeof(Name) - 1);
TABLE_Add(Name, i);
.)
WEAK "=" /* obviously more needed here */
SYNC "."
.
END EBNF.
// Various common items for grammar handler
#ifndef EBNF_H
#define EBNF_H
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdarg.h>
#include <ctype.h>
#include <limits.h>
#define boolean int
#define bool int
#define true 1
#define false 0
#define TRUE 1
#define FALSE 0
#define maxint INT_MAX
#if __MSDOS__ || MSDOS || WIN32 || __WIN32__
# define pathsep '\\'
#else
# define pathsep '/'
#endif
static void appendextension (char *oldstr, char *ext, char *newstr)
// Changes filename in oldstr from PRIMARY.xxx to PRIMARY.ext in newstr
{ int i;
char old[256];
strcpy(old, oldstr);
i = strlen(old);
while ((i > 0) && (old[i-1] != '.') && (old[i-1] != pathsep)) i--;
if ((i > 0) && (old[i-1] == '.')) old[i-1] = 0;
if (ext[0] == '.') sprintf(newstr,"%s%s", old, ext);
else sprintf(newstr, "%s.%s", old, ext);
}
const int MaxName = 50;
typedef struct {
char name[MaxName];
// you may need other members
} ENTRIES;
const int TABLE_MaxEntries = 1000; // limit on table size
static int TABLE_NEntries; // number of active entries
static ENTRIES TABLE_Table[TABLE_MaxEntries]; // the table itself
static void TABLE_InitTable() {
// Initialise table
TABLE_NEntries = 0;
}
static void TABLE_Add (char *name, int &position) {
// Attempt to add name to the table, and return position as the
// index where it was either added previously or added by this call
if (TABLE_NEntries == TABLE_MaxEntries) {
fprintf(stderr, "Table Overflow"); exit(1);
}
strcpy(TABLE_Table[TABLE_NEntries + 1].name, name); // sentinel
position = 1;
while (strcmp(name, TABLE_Table[position].name)) position++;
if (position > TABLE_NEntries) TABLE_NEntries++; // new entry
}
static void TABLE_ListProductions() {
// List all entries to standard output file
for (int i = 1; i <= TABLE_NEntries; i++)
printf("%s\n", TABLE_Table[i].name);
printf("\n");
}
#endif /* EBNF_H */