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.
Ja, well, no, fine. All you folks who thought this was a bit of a jorl so far, think again. But the objectives of this practical are to allow you to learn how to get Coco/R to do most of the work in writing syntax directed systems. Cheer up - it's not as bad as it might appear!
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.
In the kit PRAC11.ZIP you will find some goodies than usual. And you might find it useful to visit the web page at http://www.cs.ru.ac.za/CSc301/Translators/cocotips.htm.
(This task is based on a problem set in last year's examination. In the examination, candidates were given the grammar and asked to suggest the actions that had to be added.)
As you should be aware, IP addresses as used in Internet communication are typically expressed in "dotted decimal" form, as exemplified by 146.231.128.6. The IP address actually represents a 32 bit integer; the four numbers in the quadruple corresponding to successive 8 bit components of this integer. For humans, machine addressing is usually more memorable when expressed in "DNS" format, as exemplified by terrapin.ru.ac.za. Some systems maintain tables of matching addresses, for example
146.231.122.13 cspt1.ict.ru.ac.za #comments appear like this
146.231.128.6 terrapin.ru.ac.za
146.231.56.10 thistle-sp.ru.ac.za
147.28.0.62 psg.com
When we moved our CS and IS departments to new premises last year, a decision was made to rename and uniquely renumber all the many machines in our possession. Our system administrators tried to draw up a table like the one above, which was then merged with the existing table in the IT division. Unfortunately, a few mistakes were made, which caused havoc until they were ironed out. For example, there were lines reading
146.231.122.11235 cspt1.ict.ru.ac.za #invalid IP address
146.231.122.15 cspt2.ict.ru.ac.za
146.231.122.15 cspt3.ict.ru.ac.za # non-unique IP address
The ATG file below shows how Coco/R might be used to develop a system that would enable a file in this format quickly to be checked and the errors identified.
COMPILER Check $XCN
#include "check.h"
IGNORE CASE
IGNORE CHR(1) .. CHR(31)
CHARACTERS
digit = "0123456789" .
letter = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz" .
eol = CHR(10) .
COMMENTS FROM "#" TO eol
TOKENS
number = digit { digit } .
name = letter { letter | digit | "." | "-" } .
PRODUCTIONS
Check
= (. IPList L; .)
{ Entry<L> }
EOF (. if (Successful()) printf("\n all correct"); .)
.
Entry<IPList &L>
= IPNumber<L> name .
IPNumber<IPList &L>
= (. long n, m; .)
Number<n>
"." Number<m> (. n = 256 * n + m; .)
"." Number<m> (. n = 256 * n + m; .)
"." Number<m> (. n = 256 * n + m;
if (L.isMember(n)) SemError(1001);
else L.add(n); .) .
Number<long &n>
= (. char str[100] .)
number (. LexString(str, sizeof(str) - 1);
n = atoi(str);
if (n > 255) SemError(1000); .) .
END Check.
Start off by studying this grammar carefully, and then making and executing the program.
To make and run the program proceed as you did in an earlier practical, for example
GENMAKE CHECK BORL55
MAKE -f CHECK.MAK
CHECK IPLIST
Please ask the demonstrators if there are things you don't understand in the grammar.
As you may know, multiple names may be given to a host (associated with one IP number) on the Internet. On the basis that we might wish to do this for the computers in our building, but still only assign each name once, extend the application so that it might react sensibly to data of a form exemplified below.
146.231.122.13 cspt1.ict.ru.ac.za #comments appear like this
scifac.ru.ac.za #another name for it
www.scifac.ru.ac.za #and yet another
146.231.128.6 terrapin.ru.ac.za
147.28.0.62 psg.com
147.28.0.67 psg.com #invalid - name already in use
146.231.122.1123 cspt1.ict.ru.ac.za #invalid - bad IP address
146.231.122.15 cspt2.ict.ru.ac.za
146.231.122.15 cspt3.ict.ru.ac.za #invalid - non-unique IP address
Hint: This is not hard to do. You should use the List template to create two different lists. You will need to add a bit to the grammar, edit check.h, and add to check.frm.
All you have ever wanted - turn an enormous Wintel machine into a calculator!
Since the question in Practical 9 dealing with extended expression grammars in Parva was not very well done, let us try to reinforce the concepts by constructing a calculator that can (a) deal with Boolean or Integer expressions (b) store and retrieve values in variables of the user's choice (c) guard against mixed-mode errors (such as dividing Boolean values or applying the NOT operator to an integer value). This is complex, so do it in stages:
A grammar describing the input to such a calculator (CALC.ATG) appears below. The hierarchy of the set of productions for Expression imposes a precedence ordering on operators similar to the one used in C++/Java.
COMPILER Calc $XNC
// Put your names and a description here
IGNORE CHR(1) .. CHR(9) + CHR(13) .. CHR(31)
CHARACTERS
digit = "0123456789" .
letter = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz" .
eol = CHR(13) .
TOKENS
number = digit { digit } .
identifier = letter { letter | digit } .
EOL = eol .
PRODUCTIONS
Calc = { Print | Assignment } "quit" .
Assignment = Variable "=" Expression SYNC ";" .
Print = "print" Expression { WEAK "," Expression } SYNC ";" .
Expression = AndExp { "||" AndExp } .
AndExp = OrExp { "&&" OrExp } .
OrExp = AddExp [ RelOp AddExp ] .
AddExp = MultExp { AddOp MultExp } .
MultExp = UnaryExp { MulOp UnaryExp } .
UnaryExp = Factor | "+" UnaryExp | "-" UnaryExp | "!" UnaryExp .
Factor = Variable | Number | "true" | "false" | "(" Expression ")" .
Variable = identifier .
Number = number .
MulOp = "*" | "/" | "%" .
AddOp = "+" | "-" .
RelOp = "==" | "!=" | "<" | "<=" | ">" | ">=" .
END Calc.
To make up a parser proceed in the usual way
GENMAKE CALC BORL55
MAKE -f CALC.MAK
CALC CALC.TXT
If you do that the results will not be very interesting - you will be able to parse expressions, and detect syntactically incorrect expressions, but not much more.
Add actions to this grammar so that it will be able to evaluate the expressions. To start with, assume that expressions will not make use of any "variables". (CALC.ATG is already "spread out" to help in this regard).
Hints:
Bonus: Can anything go wrong in evaluating simple expressions? If so, how do you detect the fact and report it?
Extend the system so that values can be stored in and retrieved from variables.
Hints:
Just because in C++ you can mix integer and Boolean operands in almost any way in expressions does not mean that this is sensible. Extend your system so that it keeps track of the types of operands and expressions, and forbids mixing of the wrong types.
Hint: You might like to define an enumeration
enum TYPES { none, ints, bools };
to represent the various types that might be encountered. ints and bools are associated with correctly formed and defined operands and expressions, while none can be associated with expressions and operands where the type is incorrect. Thus for example
4 + 5 is of type ints
true || false is of type bools
4 == 5 is of type bools
4 && 5 is of type none
(4 == 5) && !false is of type bools
/* Simple generic linked list template class. (Interface only)
Closely based on one by George Wells -- 27 February 1996
Modifications by Pat Terry -- April 2002 */
template<class T> class List
{ public:
List (void); // Constructor
List (const List& lst); // Copy constructor
~List (void); // List destructor
void add (T item, int position = INT_MAX); // Place new item in a List
void remove (int position, T &item); // Remove item at position in List
int length (void); // Return number of elements in List
T& operator[] (int index); // Subscript a List
int position (T item); // Return position item in a List (or -1)
int isMember (T item); // True if item is in List
int isEmpty (); // Return true if list has no members
}; // class List
// Demonstration program showing simple (integer) use of the List class
// P.D. Terry, Rhodes University, 2002
#include "misc.h"
#include "list.h"
typedef List<int> INTLIST;
void AddElements (INTLIST &List) {
// Add some even numbers into List
for (int i = 0; i < 10; i+=2) List.add(i);
}
void main (void) {
INTLIST myList;
AddElements(myList); // add some even numbers
printf("length = %d\n", myList.length()); // how many went in?
for (int i = 0; i < 12; i++) // see which numbers are present
printf("%d %d\n", i, myList.isMember(i));
for (int j = 0; j < myList.length(); j++) // show indexing capability
printf("%d ", myList[j]);
printf("\n");
int d;
while (!myList.isEmpty()) { // take out elements from front
myList.remove(0, d);
printf("%d ", d, myList.length());
}
}
// Demonstration program showing simple (structure) use of the List class
// with static (perhaps wasteful) allocation of strings
// P.D. Terry, Rhodes University, 2002
#include "misc.h"
#include "list.h"
struct myStruct {
char str[1000]; // the lookup (key) field
int len; // the length of the string
// "I get by with a little help from my friends"
friend int operator == (myStruct x, myStruct y)
{ return strcmp(x.str, y.str) == 0; }
friend int operator != (myStruct x, myStruct y)
{ return strcmp(x.str, y.str) != 0; }
};
typedef List<myStruct> StructList;
void AddElements (StructList &List) {
// Add some structures into List
myStruct S;
for (int i = 0; i < 4; i++) {
gets(S.str); // from stdin
S.len = strlen(S.str); // set length attribute
printf("%s\n", S.str); // echo for user
List.add(S);
}
}
void main (void) {
StructList myList;
AddElements(myList); // add some structures
printf("length = %d\n", myList.length()); // how many went in?
myStruct S; // test membership
strcpy(S.str, "Hello");
printf("%s %d\n", S.str, myList.isMember(S));
for (int j = 0; j < myList.length(); j++) // show indexing capability
printf("%s\n", myList[j].str);
printf("\n");
while (!myList.isEmpty()) { // take out elements from front
myList.remove(0, S);
printf("%s | %d\n", S.str, S.len);
}
}