This prac is due for submission by lunch time on your next practical day, correctly packaged in a transparent folder as usual. Pracs should please be deposited in the hand-in box outside the lab. Only one set of listings is needed for each group, but please enclose as many copies of the cover sheet as are needed, one for each member of the group. These will be returned to you in due course.
The objectives of this practical are to familiarize you with simple applications of the Coco/R parser generator, and to give you practice in writing grammars that describe simple language features.
This week you are required to hand in, besides the cover sheet:
I do NOT require listings of any C++ code produced by Coco/R.
Keep the prac sheet and your solutions until the end of the semester. Check carefully that your mark has been entered into the Departmental Records.
You are referred to the rules for practical submission which are clearly stated on page 13 of our Departmental Handbook. However, for this course pracs must be posted in the "hand-in" box outside the laboratory and not given to demonstrators.
A rule not stated there, but which should be obvious, is that you are not allowed to hand in another student's work as your own. Attempts to do this will result in (at best) a mark of zero and (at worst) severe disciplinary action and the loss of your DP. You are allowed - even encouraged - to work and study with other students, but if you do this you are asked to acknowledge that you have done so.
Unpack the prac kit PRAC09.ZIP.
In this file will be found a whole host of goodies. Among them are:
*.ATG, *.PAV, *.TXT *.BAD
In the kit you will find CALC.ATG. This is essentially the calculator grammar from section 5.9.5 of the text, with a slight (cosmetic) change of name.
Use Coco/R to generate a parser for data for this calculator. You do this most simply by giving the command
CR CALC.ATG
Used like this, Coco/R will simply generate three important components of a calculator program - the parser, scanner, and main driver program. Cocol specifications can be programmed to generate a complete calculator too (ie one that will evaluate the expressions, rather than simply check them for syntactic correctness), but that will have to wait for the early hours of another day.
(Wow! Have you ever written a program so fast in your life before?)
Of course, having Coco/R write you a program is one thing. But it might also be fun and interesting to compile the program and see that it works. How you do this depends on what system you want to use.
For C++ systems you can keep firing up those large environments, creating project files, specify all sorts of other paths and options, and generally have lots of fun getting lost, but for our purposes the best idea is to make use of the "make" system.
MAKE is a utility that allows one to specify various component parts of a large system and how they are interrelated, and to recompile and relink the system easily when part of it is updated. MAKE takes its parameters from a so-called "makefile" - if you study these you will see that a fairly understandable pattern emerges. However, generating makefiles is sometimes awkward, so I have developed a program, included in the C++ kit, that will generate you a makefile for Coco/R projects, suitable for using either Borland C++ or Visual C++, as you prefer.
Assuming that your grammar has a start symbol called XXXX, and that the file specifying the grammar is called XXXX.ATG, issuing the command
GENMAKE XXXX BORL31 (for Borland C++ 3.1)
or
GENMAKE XXXX BORL55 (for Borland C++ 5.5)
or
GENMAKE XXXX VISUAL (for Microsoft Visual C++)
will generate a file XXXX.MAK that you can then apply as a parameter to the MAKE command (for Borland C++) or as a parameter to the NMAKE command (for Visual C++). After generating the makefile (which you need do only once for each task), a command like
MAKE -f XXXX.MAK (for Borland C++ 3.1)
or
NMAKE /f XXXX.MAK (for Microsoft Visual C++)
will (a) generate the system from the grammar (b) compile the parts of the system and (c) link it all together, whereafter a command like
XXXX DATA.TXT
will run the program XXXX.EXE and try to parse the file DATA.TXT, sending error messages to the screen. Giving the command in the form
XXXX DATA.TXT /L
will send an error listing to the file DATA.LST, which might be more convenient. Try this out on the calculator:
GENMAKE CALC BORL55 GENMAKE CALC VISUAL
MAKE -f CALC.MAK or NMAKE /f CALC.MAK
CALC DATA.TXT CALC DATA.TXT
CALC DATA.BAD /L CALC DATA.BAD /L
The makefile also allows you some other options. Specifically
MAKE -f CALC.MAK GENERATE will simply run the Coco/R phase for CALC
MAKE -f CALC.MAK CLEAN will simply delete the OBJ and EXE files for CALC
MAKE -f CALC.MAK NEW will cleanup and remake the CALC system from scratch
Well, you did all that. Well done. What next?
For some light relief and interest you might like to look at the code the system generated for you - you don't have to comment this week, simply gaze in awe. Don't take too long over this, because now you have the chance to be more creative!
Wait - we have not finished yet. Modify the grammar so that you can use parentheses and leading signs in your expressions, and also give the calculator a factorial function as in -4! + (3 - 4) .
Well, of course, it does not have any real "calculator" capability - it cannot calculate anything (yet). It only has the ability to recognise or reject expressions at this stage. Try it out with some expressions that use the new features, and some that use them incorrectly.
Warning. Language design and grammar design is easy to get wrong. Think hard about these problems before you begin, and while you are doing them.
The file EBNF.ATG contains a Cocol grammar that describes EBNF using EBNF conventions, which might be familiar from lectures. Try this out "as is" to begin with, for example:
GENMAKE EBNF BORL55
MAKE -f EBNF.MAK
EBNF EBNF.TXT
EBNF EBNF.BAD /L
Next, use the grammar as a guide to develop a new system that will recognise or reject a set of productions written one to a line in "traditional" BNF notation, like those below (these examples can be found in the file BNF.TXT; note that you can obtain the e character by using ALT-238 on the numeric keypad).
<name> ::= <title> <first part> <surname>
<title> ::= Mr | Miss | Ms | Dr | Prof | e
<first part> ::= <name> | <first part> <name> | e
<surname> ::= <name>
<name> ::= <letter> | <letter> <name>
<letter> ::= <first half letter> | <second half letter>
<first half letter > ::= a | b | c | d | e | f | g | h | i | j | k | l | m
<second half letter> ::= n | o | p | q | r | s | t | u | v | w | x | y | z
In the prac kit you will find an extract from the index to my forthcoming bestseller "Hacking out a Degree", in the file INDEX.TXT. It looks something like this:
abstract class 12, 45
abstraction, data 165
advantages of Modula-2 1-99, 100-500, Appendix 4
aegrotat examinations -- see unethical doctors
class attendance, intolerable 745
deadlines, compiler course -- see sunrise
horrible design (C and C++) 34, 45, 56-80
lectures, missed 1, 3, 5-9, 12, 14-17, 21-25, 28
loss of DP certificate 2002
recursion -- see recursion
senility, onset of 21-24, 105
subminimum 40
supplementary exams 45 - 49
wasted years 2000-2002
Develop a grammar INDEX.ATG that describes this and similar indexes (indices?) and create a program that will analyse an index and accept or reject it (syntactically).
Parva and Clang really are horrid little languages, aren't they? But their simplicity means that it is easy to devise Terry Torture on the lines of "extend them".
In the prac kit you will find the grammar for a subset of Parva rather like the Clang language on page 112 of the text. Generate a program from this that will recognise or reject very simple Parva programs, and verify that the program behaves correctly with the two sample programs in the kit VOTE.PAV and BAD.PAV.
GENMAKE PARVA0 BORL55
MAKE -f PARVA0.MAK
PARVA0 VOTE.PAV
and
PARVA0 BAD.PAV /L
You might also compile BAD.PAV with the "proper" Parva compiler, and compare the error messages. Why do you suppose the proper compiler detects errors that the simpler parser does not?
Now go on to extend the grammar so that you can
(a) allow an else part to an if statement;
(b) recognise a do - while statement;
(c) allow a read statement to incorporate prompt strings, as in read("Age? ", age).
(d) allow increment and decrement statements like Curse++; and Bug[N]--;
(e) allow character and string literals to have escape sequences, as in " quote \" and tab \t".
(f) declare (and refer to) variables of rather more interesting types than at present. Allow a programmer to declare variables of int, char or boolean types, arrays of these types, and even structures containing fields of these types, and have expressions that use operands of these types. As an example of the sort of thing we have in mind, consider the following code (VARS.PAV):
void main () {
// Demonstrate extended variable declarations and access to them
int I, J, List[10];
char String[100];
boolean Found, Searching, Sieve[100];
struct {
char Surname[25], FirstName[25];
boolean Clever;
int Age;
} Lecturer, Students[55];
read("Supply I", I);
read(Students[I].Clever, Lecturer.Name[12]);
boolean WithItClass = true;
int i = 0;
while (i < 55) {
if (!Students[i].Clever || Students[i].Age > 23) {
WithItClass = false;
}
i++;
}
List[I] = Lecturer.Age;
}
(g) Optional extra - bonus marks. Extend your Parva grammar so that Parva programs can also include "inline" stack assembler code. Some compilers allow the programmer to program mainly in high-level code, but to inject low-level code where this might lead to greater efficiency than otherwise possible, or to produce special effects which the high level code is not suited or able to do. Here is an example of a program with such code (in the file INLINE.PAV) - of course this example program is not supposed to "do" anything, simply to demonstrate the idea:
void main () {
// Demonstrate in-line assembler code
int I, J, K;
read(I);
inline // layout unimportant
PSH -1
LIT 6 ADD
POP -2
end;
while (I < 10) {
inline
ADR -1
VAL
PRS 'The value of I is'
PRN
end;
I = I + 3;
};
if (I > 12) { inline HLT end } // give up
}
Hint: All we require at this stage is the ability to describe these features. You do not have to try to give them any semantic meaning or write code to allow you to use them in any way. In later pracs we might try to do that, but please stick to what is asked for this time, and don't go being over ambitious.
Firstly, note that the QEdit editor system has been configured for you so that you can easily edit and check Cocol files, provided that these have the standard suffix .ATG. Thus a recommended way to proceed is as follows:
Start the editor
Q GRAMM.ATG
and then edit your grammar in the usual way.
From within the QEdit editor CTRL-F9 or CTRL-F10 will invoke the Coco/R compiler CR.EXE. If there are any errors, you will be able to move from one error location to the next by using the F4 key (the reason for the error is given in the lower window), or by using ALT-1 through ALT-9 to move to the 1st through 9th errors.
You can, of course, prepare ATG files with other ASCII editors. UltraEdit has also been configured to link to Coco/R by using options in the "advanced" pull down menu - one invokes Coco/R, and it is easy enough to set up one to invoke Make (to use the latter you should rename your makefile as MAKEFILE). Finally, you can also run Coco/R free standing with a command like:
CR XXXX.ATG
in which case the system will produce you a listing of the grammar file and the associated error messages, if any, in a corresponding file XXXX.LST.
For ease of use with the makefile concept and with various DOS file handling conventions, please
Since you will be using C++, make sure that the grammar includes the "pragma" $X (which generates C++ code, rather than C code).
The first line of your grammar description should thus always read something like
COMPILER Name $NCX /* Standard pragmas for Pascal, Modula or C++ */
Error checking by Coco/R takes place in various stages. The first of these relates to simple syntactic errors - like leaving off a period at the end of a production. These are usually easily fixed. The second stage consists of ensuring that all non-terminals have been defined with right hand sides, that all non-terminals are "reachable", that there are no cyclic productions, no useless productions, and in particular that the productions satisfy what are known as LL(1) constraints.
We shall be discussing LL(1) constraints in class during the week, and for this prac we shall simply hope that they do not become tiresome. The most common way of violating the LL(1) constraints is to have alternatives for a nonterminal that start with the same piece of string. This means that a so-called LL(1) parser (which is what Coco/R generates for you) cannot easily decide which alternative to take - and in fact will run the risk of going badly astray. Here is an example of a rule that violates the LL(1) constraints:
assignment = variableName ":=" expression
| variableName index ":=" expression.
index = "[" subscript "]" .
Both alternatives for assignment start with a variableName. However, we can easily write production rules that do not have this snag:
assignment = variableName [ index ] ":=" expression .
index = "[" subscript "]" .
A moment's thought will show that the various expression grammars that we have discussed in class - the left recursive rules like
expression = term | expression "-" term .
also violate the LL(1) constraints, and so have to be recast (see the PARVA0.ATG file) as
expression = term { "-" term } .
to get around the problem.
For the moment, if you encounter LL(1) problems, please speak to the long suffering demonstrators who will (hopefully) be able to help you resolve them.
COMPILER Parva0 $XCN
/* Parva level 0 grammar - no methods, parameters
P.D. Terry, Rhodes University, 2002 */
CHARACTERS
cr = CHR(13) .
lf = CHR(10) .
back = CHR(92) .
letter = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz" .
digit = "0123456789" .
instring = ANY - '"' - "'" - cr - lf - CHR(0) .
IGNORE CHR(9) .. CHR(13)
COMMENTS FROM "//" TO lf
COMMENTS FROM "/*" TO "*/"
TOKENS
identifier = letter { letter | digit | "_" } .
number = digit { digit } .
string = '"' { instring | "'" } '"' .
character = "'" ( instring | '"' ) "'" .
PRODUCTIONS
Parva0 = "void" "main" "(" ")" Block .
Block = "{" { Declaration | Statement } "}" .
Declaration = ConstDeclaration | VarDeclarations .
Statement = SYNC (
Block | Assignment | WhileStatement | IfStatement
| ReadStatement | WriteStatement
| ReturnStatement | EmptyStatement
).
ConstDeclaration = "const" identifier "=" number WEAK ";" .
VarDeclarations = "int" OneVar { "," OneVar } WEAK ";" .
OneVar = identifier [ ArraySize ] .
ArraySize = "[" number "]" .
Assignment = Variable "=" Expression WEAK ";" .
Variable = Designator .
Designator = identifier [ "[" Expression "]" ] .
IfStatement = "if" "(" Condition ")" Block .
WhileStatement = "while" "(" Condition ")" Block .
ReadStatement = "read" "(" Variable { "," Variable } ")" WEAK ";" .
WriteStatement = "print" "(" WriteElement { "," WriteElement } ")" WEAK ";" .
WriteElement = string | Expression .
ReturnStatement = "return" WEAK ";" .
EmptyStatement = WEAK ";" .
Condition = Expression [ RelOp Expression ] .
Expression = Term { AddOp Term } .
Term = Factor { MulOp Factor } .
Factor = Designator | number | "(" Expression ")" .
AddOp = "+" | "-" .
MulOp = "*" | "/" | "%" .
RelOp = "==" | "!=" | "<" | "<=" | ">" | ">=" .
END Parva0.