Please answer all questions in the space provided or on the back sides of the two pages. Max 25
This test is intended to check your ability to write simple scanners and parsers. It should only take you about 30 minutes at the most. Textbooks and computers and notes may not be used.
1. Your spot came up - lucky you! What are your first name (surname) and student number? [1]
Pat (Terry) 63T0844
2. Suppose we have a grammar with the PRODUCTIONS (possibly among others which might make reference to them):
PRODUCTIONS
A = { C [ B ] } [ B ] .
B = number | identifier .
C = '(' string ')' .
Assuming that you have Accept, GetSym and ReportError routines like the ones you used last week, and a scanner that can recognise tokens that might be described by the enumeration below, complete the parser routines [6]
EOFSym, noSym, numSym, identSym, stringSym, lParenSym, rParenSym
static void A () {
// A = { C [ B ] } [ B ] .
} //A
static void B () {
// B = number | identifier .
} // B
static void C () {
// C = '(' string ')' .
} // C
This is not an LL(1) grammar. Does this totally invalidate the parser? Explain why or why not - perhaps give an input string that might cause trouble. [3]
This was not always well done, and it is very easy. Indeed, some submissions were so badly wrong that I doubt whether the people concerned had done anything in the practical at all. An important idea that some people have missed is that parser routines are best "driven" by checking for FIRST tokens, not by negative tests for FOLLOW tokens. So we need something like this:
void A() {
// A = { C [ B ] } [ B ] .
while (sym.kind == lParenSym) {
C();
if (sym.kind == numSym || sym.kind == identSym) B();
}
if (sym.kind == numSym || sym.kind == identSym) B();
} //A
void B() { // one version
// B = number | identifier .
if (sym.kind == numSym || sym.kind == identSym) GetSym;
else reportError("invalid start to B");
} // B
void B() { // an alternative version
// B = number | identifier .
switch (sym.kind) {
case numSym:
case identSym : GetSym(); break;
default: abort("invalid start to B"); break;
}
} // B
void B() { // another alternative version
// B = number | identifier .
if (sym.kind == numSym) GetSym();
else Accept(identSym, "invalid start to B");
} // B
void C() {
// C = '(' string ')' .
Accept(lParenSym, "( expected");
Accept(stringSym, "string expected");
Accept(rParenSym, ") expected");
} // C
Alternatively we might try something like this. Note that the Accept() method is overloaded - one version has a simple int parameter, the other has an IntSet parameter.
static IntSet FirstB = new IntSet(numSym, identSym);
void A() {
// A = { C [ B ] } [ B ] .
while (sym.kind == lParenSym) {
C();
if (FirstB.Contains(sym.kind)) B();
}
if (FirstB.Contains(sym.kind)) B();
} // A
void B() {
// B = number | identifier .
Accept(FirstB, "invalid start to B");
} // B
Normally each routine should be written in its own "context", that is, be self-contained. The routine for A should not worry about what B has to do, other than to check whether B should be called. Coding like that below, which a few people tried, "works", but is illogical - it works only if there are no other productions in the system that depend on A, B or C (as you hade been warned in the question might be the case).
void A() {
// A = { C [ B ] } [ B ] .
while (sym.kind == lParenSym) {
GetSym(); C();
if (sym.kind == numSym || sym.kind == identSym) GetSym();
}
if (sym.kind == numSym || sym.kind == identSym) GetSym();
}
void B() {
// B = number | identifier .
// nothing, already handled in A
}
void C() {
// C = '(' string ')' .
// already accepted ( in A, so start from string
Accept(stringSym, "string expected");
Accept(RParenSym, ") expected");
}
This is not an LL(1) grammar, but it will not really invalidate the parser. It will, however, bind the first of any sequences derived from B to the { C [ B ] } construct.
So C B will be treated and parsed as C B eps and not as C eps B
A bit like a "dangling else", in a sense. Of course, in an application where any actions to be associated with B are different for each of the two Bs there might well be trouble, as would happen with
PRODUCTIONS
A (. String str; .)
= { C (. action after parsing C .)
[ B<out str> (. str = str.toUpperCase(); .)
] }
[ B<out str> (. str = str.toLowerCase(); .)
] .
B<out String str>
= ( number | identifier ) (. str = token.val; .)
C = '(' string ')' .
In general, try to avoid grammars with LL(1) problems if you are using Coco/R.
2. Suppose we wanted to write a scanner to match a specification expressed in Cocol as follows. Only three kinds of tokens are valid, as are comments - read the specification carefully.
CHARACTERS
digit = "0123456789" .
eol = CHR(10) .
COMMENTS FROM ";" TO eol
IGNORE CHR(0) .. CHR(32) /* character handler returns CHR(0) as EOF */
TOKENS
float = digit { digit } '.' { digit }
| "." digit { digit } .
integer = digit { digit } .
dotdot = ".." .
The routine must assign either floatSym, intSym or dotdotSym to sym.kind before leaving the routine (or assign the value of noSym if it comes across an invalid token, or EOFSym at the end of file). Complete the skeleton code below to show how this might be done. [15]
static void GetSym() { // Scans for next sym
StringBuilder symLex = new StringBuilder();
int symKind = noSym;
while (ch > EOF && ch <= ' ') GetChar();
In general this was badly answered (with some outstanding exceptions) . Some solutions submitted had not even thought to incorporate loops for reading the digits, and some had even confused the roles of scanner and parser. Most submissions did not deal with comments at all, which was alarming, as I know that this had caused some difficulty for some people in the practical.
One way to write the scanner would be as follows (note the detailed commentary, and also the careful placing and ordering of the calls to symLex.Append()):
void GetSym() { // Scans for next sym
while (ch > 0 && ch <= ' ') GetChar();
StringBuilder symLex = new StringBuilder();
int symKind = noSym;
while (ch > EOF && ch <= ' ') GetChar();
// Firstly, check to see if we found a comment (or, even a sequence of comments with
// nothing of much interest between them).
if (ch == ';') {
do GetChar(); while (ch != '\n' && ch != EOF);
// A comment is NOT a token, so if we skip over a comment we must still continue
// to search for the symbol that GetSym() is supposed to be returning. One way
// to do this is to make a recursive call to GetSym() - having first ensured that
// we are truly over the comment
// If we get to EOF the returned token will then be EOFSym; maybe issue a warning?
GetChar(); GetSym(); // get the hell out of here once we have the token
return; // that follows the comment, (or a sequence of
// comments in quick succession)
// (sym will be returned as EOFSym if unterminated
} // comment processor
// If we did not find a comment, we now proceed to recognise a proper token.
if (Char.IsDigit(ch) { // We must have found an integer or float number
symKind = intSym; // Make an initial assumption
do {
symLex.Append(ch); GetChar(); // Note that we add the digits to the buffer
} while (Char.IsDigit(ch)); // Scan over the only digits, or ones before the period.
if (ch == '.') { // Aha! - we must have a floating number in that case,
symKind = floatSym; // so change our assumption
do { // and incorporate the digits after the point.
symLex.Append(ch); GetChar();
} while (Char.IsDigit(ch);
}
} // finished dddd.dd or dddd. processing
else // did not start with digit
// the "else" is crucial - do you see why?
if (ch == '.') { // we must have found dotdot or a float number,
// like .ddd or a noSym, like .ball
symLex.Append(ch); GetChar(); // add to the buffer
if (ch == '.') { // Aha! - we found dotdot
symLex.Append(ch); GetChar();
symKind = dotdotSym;
}
else // But in this case we found .ddd or some .bad sequence
if (Char.IsDigit(ch) { // Aha! - we must have found a float number
symKind = floatSym;
do {
symLex.Append(ch); GetChar(); // keep adding digits to the buffer
} while (Char.IsDigit(ch)); // and looking for a non-digit to stop the loop
}
} // finished .dddd or .. or .bad processing
else // did not startt with period
// another crucial else
if (ch == EOF) {
symLex.Append("EOF"); // no need to GetChar() this time
sym.kind = EOFSym;
}
else { // invalid first character
symLex.Append(ch); GetChar(); // symKind is noSym anyway
}
sym = new Token(symKind, symLex.ToString());
} // GetSym
Another way might appear to be like this, which some people tried
...
if (Char.IsDigit(ch) { // must have found a number
symKind = intSym; // initial assumption
while (isdigit(ch) || ch == '.' ) { // scan over the rest
symLex.Append(ch); GetChar();
if (ch == '.') symKind = floatSym; // change our assumption
}
} else
...
but this is subtly WRONG - it would accept something like 45.67.89 as a valid floating number (can you see why? If not, better come to ask me!)