Complete solutions (sources) can be found on the course WWW pages in the file PRAC17A.ZIP.
All that was needed here was to extend the last production:
COMPILER Calc $XCN
/* Extended simple four function calculator
P.D. Terry, Rhodes University, 2001 */
CHARACTERS
digit = "0123456789" .
hexdigit = digit + "ABCDEF" .
IGNORE CHR(1) .. CHR(31)
TOKENS
decNumber = digit { digit } .
hexNumber = "$" hexdigit { hexdigit } .
PRODUCTIONS
Calc = { Expression "=" } EOF .
Expression = Term { "+" Term | "-" Term } .
Term = Factor { "*" Factor | "/" Factor } .
Factor = decNumber | hexNumber
| "sqrt" "(" Expression ")"
| "(" Expression ")" .
END Calc.
Be careful to split the opcodes into the three categories - those that take a numeric address, those that take no address, and PRS as a special case. Note how the optional sign is introduced into the number token. Here is a solution that uses the comment facility in Cocol. Note that we have to be very careful here, as line marks are actually significant in assembler:
COMPILER STASM1 $XCN
/* Grammar for simple stack assembler
P.D. Terry, Rhodes University, 2001 */
CHARACTERS
cr = CHR(13) .
lf = CHR(10) .
letter = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz" .
digit = "0123456789" .
noquote1 = ANY - "'" - lf - CHR(0) .
noquote2 = ANY - '"' - lf - CHR(0) .
IGNORE CHR(9) .. CHR(11)
IGNORE CHR(13)
COMMENTS FROM ";" TO cr
TOKENS
number = ["+" | "-" ] digit { digit } .
string = "'" noquote1 { noquote1 } "'" | '"' noquote2 { noquote2 } '"' .
EOL = lf .
PRODUCTIONS
STASM1 = { Statement EOL } EOF .
Statement = [ [ number ] /* ignored */
( OneWord | TwoWord | LoadString ) ] .
OneWord = "NEG" | "ADD" | "SUB" | "MUL" | "DVD" | "ODD" | "EQL"
| "NEQ" | "LSS" | "GEQ" | "GTR" | "LEQ" | "STK"
| "STO" | "HLT" | "INN" | "PRN" | "INC" | "PRC"
| "NLN" | "VAL" | "NOP" .
TwoWord = ( "LIT" | "ADR" | "DSP" | "BRN" | "BZE" ) number .
LoadString = "PRS" string .
END STASM1.
and here is a solution that defines comments as a special kind of TOKEN
COMPILER STASM2 $XCN
/* Grammar for simple stack assembler
P.D. Terry, Rhodes University, 2001 */
CHARACTERS
cr = CHR(13) .
letter = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz" .
digit = "0123456789" .
noquote1 = ANY - "'" - cr - CHR(0) .
noquote2 = ANY - '"' - cr - CHR(0) .
printable = CHR(31) .. CHR(255) .
IGNORE CHR(9) .. CHR(12)
TOKENS
number = ["+" | "-" ] digit { digit } .
string = "'" noquote1 { noquote1 } "'" | '"' noquote2 { noquote2 } '"' .
comment = ";" { printable } .
EOL = cr .
PRODUCTIONS
STASM2 = { Statement EOL } EOF .
Statement = [ [ number ] /* ignored */
( OneWord | TwoWord | LoadString ) ] [ comment ] .
OneWord = "NEG" | "ADD" | "SUB" | "MUL" | "DVD" | "ODD" | "EQL"
| "NEQ" | "LSS" | "GEQ" | "GTR" | "LEQ" | "STK"
| "STO" | "HLT" | "INN" | "PRN" | "INC" | "PRC"
| "NLN" | "VAL" | "NOP" .
TwoWord = ( "LIT" | "ADR" | "DSP" | "BRN" | "BZE" ) number .
LoadString = "PRS" string .
END STASM2.
The wheels came off in many solutions. It is quite hard to get right, and one cannot find an LL(1) grammar. Here is a simple first stab, but with no safety regulations.
COMPILER Train1 $XCN
/* Grammar for simple railway trains
P.D. Terry, Rhodes University, 2001 */
IGNORE CASE
IGNORE CHR(1) .. CHR(31)
COMMENTS FROM "(*" TO "*)" NESTED
PRODUCTIONS
Train1 = { OneTrain } EOF .
OneTrain = LocoPart GoodsPart HumanPart "." .
LocoPart = "loco" { "loco" } .
GoodsPart = Truck { Truck } .
HumanPart = "guard" | { "coach" } "brake" .
Truck = "coal" | "open" | "cattle" | "fuel" | "petrol" .
END Train1.
Here is an attempt at safety. But this one insists on at least two safe trucks in any train, and is not LL(1)
COMPILER Train2 $XCN
/* Grammar for safer railway trains
P.D. Terry, Rhodes University, 2001 */
IGNORE CASE
IGNORE CHR(1) .. CHR(31)
COMMENTS FROM "(*" TO "*)" NESTED
PRODUCTIONS
Train2 = { OneTrain } EOF .
OneTrain = LocoPart GoodsPart HumanPart "." .
LocoPart = "loco" { "loco" } .
GoodsPart = SafeTruck { AnyTruck } .
HumanPart = "guard" | SafeTruck { "coach" } "brake" .
SafeTruck = "coal" | "open" | "cattle" .
AnyTruck = SafeTruck | "fuel" | "petrol" .
END Train2.
Here is a better one, but still non-LL(1)
COMPILER Train3 $XCN
/* Grammar for safer railway trains
P.D. Terry, Rhodes University, 2001 */
IGNORE CASE
IGNORE CHR(1) .. CHR(31)
COMMENTS FROM "(*" TO "*)" NESTED
PRODUCTIONS
Train3 = { OneTrain } EOF .
OneTrain = LocoPart Load "." .
LocoPart = "loco" { "loco" } .
Load = SafeTruck Tail.
Tail = { AnyTruck } "guard"
| Passengers
| { AnyTruck } SafeTruck Passengers .
Passengers = { "coach" } "brake" .
SafeTruck = "coal" | "open" | "cattle" .
AnyTruck = SafeTruck | "fuel" | "petrol" .
END Train3.
and here is yet another, but still non-LL(1)
COMPILER Train4 $XCN
/* Grammar for safer railway trains
P.D. Terry, Rhodes University, 2001 */
IGNORE CASE
IGNORE CHR(1) .. CHR(31)
COMMENTS FROM "(*" TO "*)" NESTED
PRODUCTIONS
Train4 = { OneTrain } EOF .
OneTrain = LocoPart Load "." .
LocoPart = "loco" { "loco" } .
Load = SafeTruck Tail.
Tail = Passengers | { AnyTruck } SafeTail .
SafeTail = SafeTruck ( Passengers | "guard" ) .
Passengers = { "coach" } "brake" .
SafeTruck = "coal" | "open" | "cattle" .
AnyTruck = SafeTruck | "fuel" | "petrol" .
END Train4.
The solutions received were very mixed. Many didn't capture the idea that there should be N competitions each with M bands. A typical over simplified attempt looks like this
Gath1 = { Competition } .
Competition = SlowQuick | MSR | Medley .
SlowQuick = "SlowMarch" "March" .
MSR = "March" "Strathspey" "Reel" [ "March" ] .
Medley = OneTune { OneTune } .
OneTune = "March" | "SlowMarch" | "Jig" | "HornPipe" | "Reel"
| "Strathspey" { "Strathspey" } "Reel" .
If we want to introduce the idea that there are multiple competitions with multiple bands, then surely it makes sense to try
COMPILER Gath1 $XCN
/* Describes the Pipe Band events at a Highland Gathering
P.D. Terry, Rhodes University, 2001 */
IGNORE CHR(1) .. CHR(31)
PRODUCTIONS
Gath2 = { Competition } .
Competition = Band { Band } .
Band = SlowQuick | MSR | Medley .
SlowQuick = "SlowMarch" "March" .
MSR = "March" "Strathspey" "Reel" [ "March" ] .
Medley = OneTune { OneTune } .
OneTune = "March" | "SlowMarch" | "Jig" | "HornPipe" | "Reel"
| "Strathspey" { "Strathspey" } "Reel" .
END Gath2.
This is badly non LL(1) (It represents a continual wail of noise). We need to
get some sort of break between bands at least:
COMPILER Gath3 $XCN
/* Describes the Pipe Band events at a Highland Gathering
P.D. Terry, Rhodes University, 2001 */
IGNORE CHR(1) .. CHR(31)
PRODUCTIONS
Gath3 = { "AnnounceCompetition" Competition } .
Competition = Band { Band } .
Band = "AnnounceBand" ( SlowQuick | MSR | Medley ).
SlowQuick = "SlowMarch" "March" "break" .
MSR = "March" "Strathspey" "Reel" [ "March" ] "break" .
Medley = OneTune { OneTune } "break" .
OneTune = "March" | "SlowMarch" | "Jig" | "HornPipe" | "Reel"
| "Strathspey" { "Strathspey" } "Reel" .
END Gath3.
Even this is non-LL(1). We can get an LL(1) grammar if we make the right kind
of announcements:
COMPILER Gath4 $XCN
/* Describes the Pipe Band events at a Highland Gathering
P.D. Terry, Rhodes University, 2001 */
IGNORE CHR(1) .. CHR(31)
PRODUCTIONS
Gath4 = { "AnnounceCompetition" Competition } .
Competition = Band { Band } .
Band = "AnnounceSlow" SlowQuick
| "AnnounceMSR" MSR
| "AnnounceMedley" Medley .
SlowQuick = "SlowMarch" "March" "break" .
MSR = "March" "Strathspey" "Reel" [ "March" ] "break" .
Medley = OneTune { OneTune } "break" .
OneTune = "March" | "SlowMarch" | "Jig" | "HornPipe" | "Reel"
| "Strathspey" { "Strathspey" } "Reel" .
END Gath4.
Here is yet another solution:
COMPILER Gath5 $XCN
/* Describes the Pipe Band events at a Highland Gathering
P.D. Terry, Rhodes University, 2001 */
IGNORE CHR(1) .. CHR(31)
PRODUCTIONS
Gath5 = { Competition } .
Competition = "AnnounceSlow" SlowQuickComp
| "AnnounceMSR" MSRComp
| "AnnounceMedley" MedleyComp .
SlowQuickComp = SlowQuick { SlowQuick } .
SlowQuick = "SlowMarch" "March" "break" .
MSRComp = MSR { MSR } .
MSR = "March" "Strathspey" "Reel" [ "March" ] "break" .
MedleyComp = Medley { Medley } .
Medley = OneTune { OneTune } "break" .
OneTune = "March" | "SlowMarch" | "Jig" | "HornPipe" | "Reel"
| "Strathspey" { "Strathspey" } "Reel" .
END Gath5.
In all these notice that we have not fallen into the trap of defining:
OneTune = "March" | "SlowMarch" | "Jig" | "HornPipe" | "Reel"
| "Strathspey" { "Strathspey" } "Reel" { "Reel" } .
which is non-LL(1) again, or of trying to write
OneTune = "March" | "SlowMarch" | "Jig" | "HornPipe" |
| "Strathspey" { "Strathspey" } "Reel" { "Reel" } .
which is LL(1), but precludes reels being played without a strathspey
immediately before them.
These were very simple really. The extensions for expressions can be done in different ways, depending on the precedence ordering. The solution below is inspired by the way they are defined in Pascal, Modula and Oberon.
Condition = Expression .
Expression = SimpExpression [ RelOp SimpExpression ] .
SimpExpression = ( "+" Term | "-" Term | Term ) { AddOp Term } .
Term = Factor { MulOp Factor } .
Factor = Designator | number | "(" Expression ")" .
AddOp = "+" | "-" | "OR" .
MulOp = "*" | "/" | "AND" .
and here is a grammar based on that used in C and C++:
Expression = OrExp { "OR" OrExp } .
OrExp = AndExp { "AND" AndExp } .
AndExp = AddExp [ RelOp AddExp ] .
AddExp = MulExp { AddOp MulExp } .
MulExp = Factor { MulOp Factor } .
Factor = Primary | ( "+" | "-" ) Factor .
Primary = Designator | number | "TRUE" | "FALSE" | "(" Expression ")" .
CASE or SWITCH statements can be done in various ways. Here is one that captures the spirit of the example suggested in the question sheet
CaseStatement = "CASE" Expression "OF"
{ OneCase }
[ "DEFAULT" ":" StatementSequence ]
"END" .
OneCase = Label { "," Label } ":" StatementSequence .
StatementSequence = Statement { ";" Statement } .
Label = number .
It might be argued that the "default" arm be mandatory (it can always have
only an empty statement if you really want to mop up all "other" cases in the
same empty way):
CaseStatement = "CASE" Expression "OF"
{ OneCase }
"DEFAULT" ":" StatementSequence
"END" .
Notice that we do not use identifiers or strings as "labels". Identifiers are no use because they can also start statements, and to attempt to use them would cause LL(1) errors. Strings are not used because the expressions in Clang cannot yield anything but simple integer values to match against possible labels.