RHODES UNIVERSITY
November Examinations 1998 - Solutions
Here are some model solutions for Section B. Full model solutions for
the whole paper may happen later.
Attribute free version
======================
COMPILER Mixed
CHARACTERS
letter = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz" .
digit = "0123456789" .
IGNORE CHR(9) .. CHR(13)
IGNORE CASE
COMMENTS FROM "(*" TO "*)" NESTED
TOKENS
ident = letter { letter | digit } .
integer = digit { digit } .
label = letter { letter | digit } ":" .
PRODUCTIONS
Mixed = "PROGRAM" Declarations CompoundStatement "." .
Declarations = { Type OneVar { "," OneVar } ";" } .
Type = "INT" | "BOOL" .
OneVar = Identifier .
CompoundStatement = "BEGIN" Statement { ";" Statement } "END" .
Statement = [ Assignment | IfStatement | AsmSequence | CompoundStatement ] .
Assignment = Variable ":=" Expression .
Variable = Identifier .
Expression = Variable | Integer .
IfStatement = "IF" Condition "THEN" Statement "ELSE" Statement .
Condition = Expression "=" Expression .
AsmSequence = "ASM" { AsmStatement } "END" .
AsmStatement = label | Identifier Operand [ "," Operand ] ";" .
Operand = Identifier | Integer | "[" Integer "]" .
Identifier = ident .
Integer = integer .
END Mixed.
C++ version
============
COMPILER Mixed $CXN
/* Pat Terry Mon 09-14-98 */
#include "misc.h"
CHARACTERS
letter = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz" .
digit = "0123456789" .
IGNORE CHR(9) .. CHR(13)
IGNORE CASE
COMMENTS FROM "(*" TO "*)" NESTED
TOKENS
ident = letter { letter | digit } .
integer = digit { digit } .
label = letter { letter | digit } ":" .
PRODUCTIONS
Mixed
= "PROGRAM" (. Initialize(); .)
Declarations CompoundStatement "." .
Declarations
= (. int NextAdr = 255; .)
{ Type OneVar<NextAdr>
{ "," OneVar<NextAdr> }
";" } .
Type = "INT" | "BOOL" .
OneVar <int &NextAdr>
= (. char Name[100]; .)
Identifier<Name> (. Insert(Name, NextAdr--); .) .
CompoundStatement
= "BEGIN"
Statement { ";" Statement }
"END" .
Statement
= [ Assignment
| IfStatement
| AsmSequence
| CompoundStatement
] .
Assignment
= (. int Pos; .)
Variable<Pos> (. printf(" MOV ");
WriteOperand(Pos); printf(", ") .)
":=" Expression (. printf("\n"); .) .
Variable <int &Pos>
= (. char Name[100]; bool found.)
Identifier<Name> (. Position(Name, Pos, found);
if (!found) SemError(104); .) .
Expression
= (. int Pos, Value; .)
Variable<Pos> (. WriteOperand(Pos); .)
| Integer<Value> (. printf("%d", Value); .) .
IfStatement
= "IF" Condition (. int Lab = NextLabel; NextLabel += 2;
printf(" BNZ L%d\n", Lab); .)
"THEN" Statement (. printf(" BRN L%d\n", Lab+1);
printf("L%d:\n", Lab); .)
"ELSE" Statement (. printf("L%d:\n", Lab+1); .) .
Condition
= (. printf(" CMP "); .)
Expression (. printf(", "); .)
"=" Expression (. printf("\n"); .) .
AsmSequence
= "ASM" { AsmStatement } "END" .
AsmStatement
= (. char OpCode[100];
TIPES Tipe;
bool Valid;
char LabelField[100]; .)
( label (. LexName(LabelField, 99);
puts(LabelField) .)
|
Identifier<OpCode> (. CheckOpCode(OpCode, Tipe, Valid);
if (!Valid) SemError(101);
else printf(" %s ", OpCode); .)
Operand<Tipe, TRUE>
( (. if (Tipe == Branch) SemError(102); .)
"," (. printf(", "); .)
Operand<Tipe, FALSE>
| (. if (Tipe != Branch) SemError(103); .)
) (. printf("\n"); .)
SYNC ";"
) .
Operand<TIPES Tipe, bool First>
= (. char Name[100]; int Value, Pos; bool found; .)
Identifier<Name> (. if (Tipe == Branch || ValidReg(Name))
printf("%s", Name);
else {
Position(Name, Pos, found);
if (!found) SemError(104);
else WriteOperand(Pos);
} .)
| Integer<Value> (. if (Tipe == Move && First) SemError(105);
printf("%d", Value); .)
| "[" Integer<Value> "]" (. printf("[%d]", Value); .)
.
Identifier <char * Id>
= ident (. LexName(Id, 99); .) .
Integer <int &N>
= (. char S[100]; .)
integer (. LexName(S, 99); N = atoi(S); .) .
END Mixed.
MISC.H
======
// Various common items
#ifndef MISC_H
#define MISC_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
# 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 LastValidReg = 5;
const int LastValidOpcode = 5;
typedef enum { Bad, Move, Branch, Compare } TIPES;
static int NextLabel; /* for branch statements */
static int LastVar; /* in symbol table */
typedef struct {
char Name[100];
int Address; /* allocated memory address */
} ENTRIES;
typedef struct {
char Name[100];
TIPES Tipe;
} OPCODES;
static ENTRIES Table[200];
static OPCODES OpCodes[LastValidOpcode+1];
static char ValidRegs [100] [LastValidReg+1];
static void Initialize(void) {
/* Initialize symbol tables etc */
NextLabel = 0; LastVar = 0;
Table[0].Address = 0;
strcpy(ValidRegs[1], "R1");
strcpy(ValidRegs[2], "R2");
strcpy(ValidRegs[3], "R3");
strcpy(ValidRegs[4], "R4");
strcpy(ValidRegs[5], "R5");
strcpy(OpCodes[0].Name, "BAD"); OpCodes[0].Tipe = Bad;
strcpy(OpCodes[1].Name, "MOV"); OpCodes[1].Tipe = Move;
strcpy(OpCodes[2].Name, "CMP"); OpCodes[2].Tipe = Compare;
strcpy(OpCodes[3].Name, "BNZ"); OpCodes[3].Tipe = Branch;
strcpy(OpCodes[4].Name, "BZE"); OpCodes[4].Tipe = Branch;
strcpy(OpCodes[5].Name, "BRN"); OpCodes[5].Tipe = Branch;
}
static void Insert (char *Name, int Address) {
/* Make new entry into user defined table */
LastVar++;
strcpy(Table[LastVar].Name, Name); Table[LastVar].Address = Address;
}
static void Position (char *ID, int &I, bool &found) {
// Locate ID in user defined table; return position and whether found
strcpy(Table[0].Name, ID);
I = LastVar;
while (strcmp(ID, Table[I].Name) != 0) I--;
found = I != 0;
}
static void WriteOperand (int I) {
printf("[%d]", Table[I].Address);
}
static bool ValidReg (char *R) {
/* Check that R is one of the reserved m/c register names */
strcpy(ValidRegs[0], R);
int I = LastValidReg;
while (strcmp(R, ValidRegs[I]) != 0) I--;
return I != 0;
}
static void CheckOpCode (char *O, TIPES &Tipe, bool &Valid) {
/* Check that O is one of the reserved m/c opcode mnemonics */
strcpy(OpCodes[0].Name, O);
int I = LastValidOpcode;
while (strcmp(O, OpCodes[I].Name) != 0) I--;
Valid = I != 0; Tipe = OpCodes[I].Tipe;
}
#endif /* MISC_H */
Pascal version
==============
COMPILER Mixed $CN
(* Pat Terry Mon 09-14-98 *)
CONST
LastValidReg = 5;
LastValidOpCode = 5;
TYPE
IDNAMES = STRING[20];
TIPES = (Bad, Move, Branch, Compare);
VAR
NextLabel : INTEGER; (* for branch statements *)
LastVar : INTEGER; (* in symbol table *)
Table : ARRAY [0 .. 200] OF (* user defined symbol table *)
RECORD
Name : IDNAMES;
Address : INTEGER; (* allocated memory address *)
END;
ValidRegs : ARRAY [0 .. LastValidReg] OF IDNAMES; (* m/c dependent *)
OpCodes : ARRAY [0 .. LastValidOpCode] OF (* m/c dependent *)
RECORD
Name : IDNAMES;
Tipe : TIPES
END;
PROCEDURE Initialize;
(* Initialize symbol tables etc *)
BEGIN
NextLabel := 0; LastVar := 0;
Table[0].Address := 0;
ValidRegs[1] := 'R1';
ValidRegs[2] := 'R2';
ValidRegs[3] := 'R3';
ValidRegs[4] := 'R4';
ValidRegs[5] := 'R5';
OpCodes[0].Name := 'BAD'; OpCodes[0].Tipe := Bad;
OpCodes[1].Name := 'MOV'; OpCodes[1].Tipe := Move;
OpCodes[2].Name := 'CMP'; OpCodes[2].Tipe := Compare;
OpCodes[3].Name := 'BNZ'; OpCodes[3].Tipe := Branch;
OpCodes[4].Name := 'BZE'; OpCodes[4].Tipe := Branch;
OpCodes[5].Name := 'BRN'; OpCodes[5].Tipe := Branch;
END;
PROCEDURE Insert (Name : IDNAMES; Address : INTEGER);
(* Make new entry into user defined table *)
BEGIN
INC(LastVar);
Table[LastVar].Name := Name; Table[LastVar].Address := Address;
END;
FUNCTION Position (ID : IDNAMES) : INTEGER;
(* Locate ID in user defined table; complain if not there *)
VAR
I : INTEGER;
BEGIN
Table[0].Name := ID; I := LastVar;
WHILE ID <> Table[I].Name DO DEC(I);
IF I = 0 THEN SemError(104);
Position := I
END;
PROCEDURE WriteOperand (I : INTEGER);
BEGIN
Write('[', Table[I].Address:1, ']');
END;
FUNCTION GetNumber (VAR Str : STRING) : INTEGER;
(* Convert latest token to integer value Int *)
VAR
Int, Error : INTEGER;
BEGIN
Int := 0;
Val(Str, Int, Error);
GetNumber := Int;
END;
FUNCTION ValidReg (R : IDNAMES) : BOOLEAN;
(* Check that R is one of the reserved m/c register names *)
VAR
I : INTEGER;
BEGIN
ValidRegs[0] := R; I := LastValidReg;
WHILE R <> ValidRegs[I] DO DEC(I);
ValidReg := I <> 0
END;
PROCEDURE CheckOpCode (O : IDNAMES; VAR Tipe : Tipes; VAR Valid : BOOLEAN);
(* Check that O is one of the reserved m/c opcode mnemonics *)
VAR
I : INTEGER;
BEGIN
OpCodes[0].Name := O; I := LastValidOpCode;
WHILE O <> OpCodes[I].Name DO DEC(I);
Valid := I <> 0; Tipe := OpCodes[I].Tipe;
END;
CHARACTERS
letter = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz" .
digit = "0123456789" .
IGNORE CHR(9) .. CHR(13)
IGNORE CASE
COMMENTS FROM "(*" TO "*)" NESTED
TOKENS
ident = letter { letter | digit } .
integer = digit { digit } .
label = letter { letter | digit } ":" .
PRODUCTIONS
Mixed
= "PROGRAM" (. Initialize .)
Declarations
CompoundStatement "." .
Declarations (. VAR NextAdr : INTEGER; .)
= (. NextAdr := 255 .)
{ Type OneVar<NextAdr>
{ "," OneVar<NextAdr> }
";" } .
Type = "INT" | "BOOL" .
OneVar <VAR NextAdr : INTEGER> (. VAR Name : IDNAMES; .)
= Identifier<Name> (. Insert(Name, NextAdr); DEC(NextAdr) .) .
CompoundStatement
= "BEGIN"
Statement { ";" Statement }
"END" .
Statement
= [ Assignment
| IfStatement
| AsmSequence
| CompoundStatement
] .
Assignment (. VAR Pos : INTEGER; .)
= Variable<Pos> (. Write(' MOV ');
WriteOperand(Pos); Write(', ') .)
":=" Expression (. WriteLn .) .
Variable <VAR Pos : INTEGER> (. VAR Name : IDNAMES; .)
= Identifier<Name> (. Pos := Position(Name) .) .
Expression (. VAR Pos, Value : INTEGER; .)
= Variable<Pos> (. WriteOperand(Pos) .)
| Integer<Value> (. Write(Value:1) .) .
IfStatement (. VAR Lab : INTEGER; .)
= "IF" Condition (. Lab := NextLabel; INC(NextLabel, 2);
WriteLn(' BNZ L', Lab:1); .)
"THEN" Statement (. WriteLn(' BRN L', Lab+1);
WriteLn('L', Lab:1, ':') .)
"ELSE" Statement (. WriteLn('L', Lab+1:1, ':') .) .
Condition
= (. Write(' CMP ') .)
Expression (. Write(', ') .)
'=' Expression (. WriteLn .) .
AsmSequence
= "ASM" { AsmStatement } "END" .
AsmStatement (. VAR
OpCode : IDNAMES;
Tipe : TIPES;
Valid : BOOLEAN;
LabelField : STRING; .)
= ( label (. LexName(LabelField);
WriteLn(LabelField) .)
|
Identifier<OpCode> (. CheckOpCode(OpCode, Tipe, Valid);
IF NOT Valid
THEN SemError(101)
ELSE Write(' ', OpCode, ' ') .)
Operand<Tipe, TRUE>
( (. IF Tipe = Branch THEN SemError(102) .)
"," (. Write(', ') .)
Operand<Tipe, FALSE>
| (. IF Tipe <> Branch THEN SemError(103) .)
) (. WriteLn .)
SYNC ";"
) .
Operand<Tipe : TIPES; First : BOOLEAN>
(. VAR
Name : IDNAMES;
Value : INTEGER; .)
= Identifier<Name> (. IF (Tipe = Branch) OR ValidReg(Name)
THEN Write(Name)
ELSE WriteOperand(Position(Name)) .)
| Integer<Value> (. IF (Tipe = Move) AND First THEN SemError(105);
Write(Value:1) .)
| "[" Integer<Value> "]" (. Write('[', Value:1, ']') .)
.
Identifier <VAR Id : IDNAMES> (. VAR S : STRING; .)
= ident (. LexName(S); Id := S .) .
Integer <VAR N : INTEGER> (. VAR S : STRING; .)
= integer (. LexName(S); N := GetNumber(S) .) .
END Mixed.