1. As many of you know, my brother Peter occasionally brightens up your TV screens with good advice as to how to keep your toilets clean using Domestos and your bathroom walls beautiful with tiles from CTM. (I suspect he may teach you more useful skills than I do!) What you may not know is that he worked for State Theatre in Pretoria, which recently folded, so he is dependent more than ever before on what the SABC pay him. He has asked me to write a system to allow him to analyse the offerings of the SABC to determine the number of times he appears on screen for each company. I have got as far as the following grammar
COMPILER SABCTV $XCN
IGNORE CHR(1) .. CHR(31)
PRODUCTIONS
SABCTV = { Programme } "Closedown" .
Programme = "Announcement" { QualityShow }
"Reminder" /* you know it's the right thing to do */ .
QualityShow = "Programme" { Advert } .
Advert = "CTMTiles" | "Domestos" | "Reminder" | "VodaCom" | "Nando's" | "LGDigital" .
END SABCTV.
Would Coco/R object to the fact that I have used the word Programme in two ways? Explain.
Have I produced an LL(1) grammar? If not, where not?
Assume for the remaining questions that any LL(1) violations are not important and that the use of the word Programme in two ways is unimportant.
How do I add the actions to be able to count his appearances?
The SABC fear that he may be suffering from over-exposure and have asked me to extend/write a system to allow them to check that he never appear in two advertisements in a row (that is, that the Domestos and CTM adverts must be separated by at least one other advert). How do I add the actions to be able to check that aspect of my brother's appearances?
Does your grammar check his appearances within one burst of adverts only, or across a whole evening? If you wanted it the other way around, what would you have to change?
2. Some languages, notably Pascal, Modula-2, C, C++, and Ada, allow programmers the flexibility to define what are often known as enumeration types, or simply enumerations.
enum INSTRUMENTS { Drum, Bass, Guitar, Trumpet, Trombone, Saxophone, Bagpipe } JazzBand[41];
enum CARS { Golf, Tazz, Sierra, BMW316 } CarHireFleet[101]; /* C or C++ */
Sometimes the variables are declared in terms of enumerations like this:
enum COLOURS { Red, Orange, Yellow, Green, Blue, Indigo, Violet };
COLOURS Walls, Ceiling, Roof;
The big idea here is to introduce a distinct, usually rather small, set of values which a variable can legitimately be assigned. Internally these values are represented by small integers - in the case of the CarHireFleet example the "value" of Golf would be 0, the value of Tazz would be 1, and so on.
In the C/C++ development of this idea the enumeration, in fact, results in nothing more than the creation of an implicit list of const int declarations. Thus the code
enum CARS { Golf, Tazz, Sierra, BMW316 } CarHireFleet[101];
is semantically completely equivalent to
const int Golf = 0; const int Tazz = 1; const int Sierra = 2, const int BMW316 = 3;
int CarHireFleet[101];
and to all intents and purposes this gains very little, other than possible readability; an assignment like
CarHireFleet[N] = Tazz;
might mean more to a reader than the operationally identical
CarHireFleet[N] = 1;
Enumerations are a "luxury" - clearly they are not really needed, as all they provide is a slightly safer way of programming with small integers. Not surprisingly, therefore, they are not found in languages like Java (simplified from C++) or Oberon (simplified from Modula-2). In Modula and Pascal they are, however, strictly typed and distinct from integers in the programmer's eye.
How would you add the ability to declare variables of such enumeration types in Parva++ programs? Consider the modifications you would need to make to the symbol table handling and to the routines for declaring variables.
COMPILER Parva $CX
#include ...
typedef Set<7> classset;
typedef Set<4> typeset;
typeset arithtypes, booltypes;
int maxframe;
bool compatible (TABLE_types atype, TABLE_types btype)
// returns true if atype is compatible with btype
{ return arithtypes.memb(atype) && arithtypes.memb(btype)
|| booltypes.memb(atype) && booltypes.memb(btype);
}
PRODUCTIONS
Parva
= (. int framesize;
CGEN_labels enterlabel; .)
"void" "main" "(" [ "void" ] ")"
(. arithtypes = typeset(TABLE_none, TABLE_ints, TABLE_chars);
booltypes = typeset(TABLE_none, TABLE_bools);
framesize = 0; maxframe = 0;
CGen->openstackframe(enterlabel); .)
Block<framesize> (. CGen->fixup(enterlabel, maxframe);
CGen->leaveprogram(); .) .
VarDeclarations<int &framesize>
= (. TABLE_types type; .)
( "int" (. type = TABLE_ints .)
| "char" (. type = TABLE_chars .)
| "bool" (. type = TABLE_bools .)
)
OneVar<framesize, type> { WEAK "," OneVar<framesize, type> } WEAK ";" .
OneVar<int &framesize, TABLE_types type>
= (. TABLE_entries entry; TABLE_types exptype;
entry.idclass = TABLE_vars; entry.v.size = 1;
entry.v.scalar = true; entry.type = type;
entry.v.offset = framesize + 1; .)
Ident<entry.name>
[ ArraySize<entry.v.size> (. entry.v.scalar = false; .)
] (. Table->enter(entry);
framesize += entry.v.size;
if (framesize > maxframe) maxframe = framesize; .)
[ AssignOp (. if (!entry.v.scalar) SemError(210);
CGen->stackaddress(entry.v.offset); .)
Expression<exptype> (. if (!compatible(entry.type, exptype)) SemError(218);
else CGen->assign(entry.type == TABLE_chars); .)
] .
3. Brinch Hansen introduced an extended form of the WHILE loop into his language Edison:
WhileStatement = "WHILE" Condition "DO" Statement
{ "ELSE" Condition "DO" Statement }
"END" .
The Conditions are evaluated one at a time in the order written until one is found to be true, when the corresponding Statement is executed, after which the process of evaluating conditions is repeated. If no Condition is true, the loop terminates.
How could stack machine code generation for this be implemented?
SABCTV
=
{ Programme
} "Closedown"
.
Programme
=
"Announcement"
{ QualityShow
}
"Reminder"
. /* you know it's the right thing to do */
QualityShow
=
"Programme"
{ Advert
}
.
Advert
=
"CTMTiles"
| "Domestos"
| "Reminder"
| "VodaCom"
| "Nando's"
| "LGDigital"
.