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
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 for the relevant sections:
// +++++++++++++++++++++++++++++++ Scanner ++++++++++++++++++++++++++++++++++
// Declaring sym as a global variable is done for expediency - global variables
// are not always a good thing
static Token sym;
static void GetSym() {
// Scans for next sym from input
while (ch > EOF && ch <= ' ') GetChar();
StringBuilder symLex = new StringBuilder();
int symKind = noSym;
if (Char.IsLetter(ch)) { // variable or key word
symLex.Append(ch); GetChar();
if (!Char.IsLetter(ch)) symKind = varSym; // must be a single character variable name
else {
while (Char.IsLetter(ch)) {
symLex.Append(ch); GetChar();
}
switch (symLex.ToString().ToUpper() ) { // check against list of key words
case "TRUE" : symKind = trueSym; break;
case "FALSE" : symKind = falseSym; break;
case "AND" : symKind = andSym; break;
case "OR" : symKind = orSym; break;
case "NOT" : symKind = notSym; break;
default : symKind = noSym; break; // if no match, must be noSym
}
}
}
else { // single character tokens
symLex.Append(ch); // remember to put into the StringBuilder
switch (ch) {
case EOF:
symLex = new StringBuilder("EOF"); // special representation
symKind = EOFSym; // no need to GetChar here, of course
break;
case '=' :
symKind = assignSym; GetChar(); // all the others need to call GetChar to
break; // get lined up for the next call to GetSym
case '.' :
case '&' :
symKind = andSym; GetChar();
break;
case '+' :
case '|' :
symKind = orSym; GetChar();
break;
case '(' :
symKind = lparentSym; GetChar();
break;
case ')' :
symKind = rparentSym; GetChar();
break;
case '\'' :
symKind = quoteSym; GetChar();
break;
case '0' :
symKind = falseSym; GetChar();
break;
case '1' :
symKind = trueSym; GetChar();
break;
default :
symKind = noSym; GetChar();
break;
}
}
sym = new Token(symKind, symLex.ToString()); // finally construct the complete token
} // GetSym
// +++++++++++++++++++++++++++++++ Parser +++++++++++++++++++++++++++++++++++
static IntSet // these will make life and testing easier
FirstExp = new IntSet(varSym, notSym, lparentSym, trueSym, falseSym),
FirstMoreFactors = new IntSet(varSym, notSym, lparentSym, trueSym, falseSym, andSym);
// One of the reasons for using Accept methods is that it gives a uniform way of reporting on errors
// If you want to change that way, there is the one common place to do it, not a whole lot of
// changes needed all over the code.
// Note that I have used an unguarded "GetSym" when it is obviously quite safe to do so (because the
// test for an acceptable token has already been done).
static void Accept(int wantedSym, string errorMessage) {
// Gets next token if the current token matches wantedSym
if (sym.kind == wantedSym) GetSym(); else Abort(errorMessage);
} // Accept
static void Accept(IntSet allowedSet, string errorMessage) {
// Gets next token if the current token matches one of allowedSet
if (allowedSet.Contains(sym.kind)) GetSym(); else Abort(errorMessage);
} // Accept
static void Bool() {
// Bool = { Expression "=" }
while (FirstExp.Contains(sym.kind)) {
Expression();
Accept(assignSym, " == expected");
}
Accept(EOFSym, " EOF Expected");
} // Bool
static void Expression() {
// Expression = Term { Or Term } .
Term();
while (sym.kind == orSym) {
GetSym(); Term();
}
} // Expression
static void Term() {
// Term = Factor { [ And ] Factor } .
Factor();
while (FirstMoreFactors.Contains(sym.kind)) {
if (sym.kind == andSym) GetSym();
Factor();
}
} // Term
static void Factor() {
// Factor = "NOT" Factor | Primary { "'" } .
if (sym.kind == notSym) {
GetSym(); Factor();
}
else {
Primary();
while (sym.kind == quoteSym) GetSym();
}
} // Factor
static void Primary() {
// Primary = True | False | variable | "(" Expression ")" .
switch (sym.kind) {
case trueSym :
case falseSym :
case varSym :
GetSym();
break;
case lparentSym :
GetSym(); Expression();
Accept(rparentSym, " ) expected");
break;
default : // essentially, all bad expressions are caught here
Abort(" invalid primary expression"); // (no tests needed in Expression, Term or Factor)
break;
} // switch
} // Primary
Home © P.D. Terry