CS246 [Winter 2012] Assignment 6

Version 1.1 120320 Fixed ‘put’ statement in grammar

Version 1.2 120321 Removed ‘insert’ statement from grammar

Version 1.3 120322 Made file poly3.h available

You are to produce an interpreter for a language called Paula that has polynomials as its only form of data.  It has declarations, assignments, and output for polynomials. 

In Assignment 5 you were to create simple interpreter, which supported no interesting form of expressions.  For A6 you are to implement a language called Paula (defined here just for A6) that will have operators such as + and == with precedence as well as nesting using parentheses.

The Paula language.  Here is an example program in the Paula language.

message ”This is a demo”;    // Print out message: This is a demo

poly abc = 1.1x^2 + 1.2x^3;  // Variable abc is declared

                             // and initialized to contain

                             //     two terms

put abc;                     // Print to std output the polynomial abc

poly s = 1.0x^1 + abc;       // Declare s, initialized with 3 terms

poly tmp;                    // Declare tmp, initially null

tmp = s – abc;               // tmp becomes s without abc

poly eq = tmp == s;          // Set eq to null polynomial (false)

Paula has no comments, so it does not allow // at the right part of a line.  A variable must be declared, by a “poly” statement as illustrated above. Declaration before use (DBU) is required. Variables cannot be re-declared.  If these rules are violated, an error message should be printed.  If it is easy, your program (the Paula driver) should recover and continue.

The operators supported in Paula expressions are +, *, - (polynomial add, multiply, subtraction) as well as these comparison, i.e., polynomial equality.  Operators are executed from left to right, with priority levels, from high to low: complement ~, *, + and -, comparison ==, or |, and &.  Comparisons return a boolean value of ”true” as 1.0x^0 or ”false” as null.

As per Assignment 5, Boolean operators, & | ~, can be applied to polynomials, taking null as false and non-null (default 1.0x^0) as true.

Polynomial values are assigned using the = operator, in the assignment statement.

Polynomial terms, such as 7.9x^3 can be used in expressions. Negative terms must have the minus sign adjacent to the (rest of the) coefficient, as in -8.4x^2.

Expressions occur on the right side of assignment statements and declarations.

Scanner provided.  You will be given a scanner (which you are to use).  It reads programs and translates them to sequences of tokens.  For example, the above program would be translated to the following.

x:message

”:This is a demo

;

x:poly

x:abc

=

T:1.1x^2

+

T:1.2x^3

;

x:put

x:abc

;

x:poly

x:s

=

T:1.0x^1

+

x:abc

;

x:poly

x:tmp

;

x:tmp

=

x:s

-

x:abc

;

x:poly

x:eq

=

x:tmp

e

x:s

;

E

As can be seen, each token appears on a separate line.  There are two kinds of tokens: skinny and fat.  A skinny token, such as = or +, appears as a single character. A fat token is written as a character, such as x then a colon : and then the “value” of the token.  For example, x:abc represents the identifier abc while the fat token

”:Alice       (Note: no right quote mark)

 represents the string

Alice

See file tokennames.h for a listing of all tokens.  The final token E (for EOF) is added by the scanner for convenience of the interpreter.

A token in the source program, such as “Alice” is called a raw token.  A token that has been scanned, such as “:Alice is called a cooked token.  The scanner translates each raw token into a cooked token (it “cooks” the token).

The scanner can be used for various languages.  As a result, some tokens, such as >>, may be recognized by the scanner, but not accepted by your interpreter.  This does not cause problems.  When >> is (erroneously) part of the user program, it is scanned without error message, but it will cause a syntax error in the interpreter.

The “driver” program.  You are to write a C++ program called “driver” which reads a token stream (as illustrated above) for a Paula program from the standard input and executes it, producing output on the standard output stream for each Paula “put” or “message” statement.

Language grammar.  The grammar for the Paula language is as follows:

program    ::= statements

statements ::= { message | declaration | assignment

                 | put | exit }

message    ::= x:message stringconst ”;”

declaration::= x:poly x [ ”=” expression ] ”;”

assignment ::= x ”=” expression ”;”

put        ::= x:put x “;”

exit       ::= x:exit “;”

expression ::= ands { ”|” ands }

ands       ::= compares { ”&” compares }

compares   ::= adds { ”==” adds }

adds       ::= mults { (”+” | ”-” ) mults }

mults      ::= factor { ”*” factor }

factor     ::= ”~” factor | polyterm | x | ”(” expression ”)”

In the grammar, the notation “x:ccc” for example, x:message means the identifier message.  Similarly for x:exit etc.  By itself x means any identifier.

In the grammar, the notation “polyterm” means polynomial term, e.g., -76.45x^12.

The notation in the grammar { …  } means zero or more replications while | means a choice.  The notation [ … ] means optional.

Use recursive descent.  Your interpreter should be structured as a recursive descent parser.  For discussion of this see:

http://en.wikipedia.org/wiki/Recursive_descent_parser

You should use one function for each non-terminal (left hand side) in the above grammar. Note that many of the non-terminals are recursive.  Besides parsing the program, you will also interpret it on the fly.  This means using the “driver” program to allocate (during declarations), assign (during assignments) and retrieve (during expressions and output) values of variables (always polynomials).  The output is printed on the terminal (to standard output).  The expression, compares, adds, etc. should return a polynomial.

Implementation.  Your “driver” program should begin by reading the entire token stream into a token buffer, which is implemented as a list (C++ template) of tokens.  Operations on this STL list, such as rewind, as provided by the list template can be used. The interpreter (implemented by the driver) will repeatedly request a token from the buffer, and the iterator can keep track of which token to fetch next from the list.  Each token is to be represented using the token class (see token.h).  You are to implement the token class (as token.cpp).  Note that token.h specifies some operations, such as output using <<, that you may not need to use.

Ideally you should use your poly class from a previous assignment, ideally from your A5.  If that is not possible for you, you can use a version from the provided files.

Use a C++ STL map to represent the variables in the program as a pair, where the name of the variable is the pair’s key and pair’s target is a poly object.

The provided files will include “tokennames.h”.  Use token names such as plusToken defined in that file rather than literal constants such as ‘+’.

The “dvr” shell script.  You are to create a shell script named dvr (make it executable with chmod +x dvr) which pipes the output of scan (provided to you) into driver (which you are to write).  The “dvr” script can be done this way.

./scan < $1 | ./driver # You write driver. Scan is given to you

I/O Files. Your program should use standard input and output (and error output). 

Hints. 

Note that ctrl-D typed at the terminal produces EOF.

You are to use an STL  “map” to store string sets and to look them up based on their declared names.    See Buhr notes.  You can use the “count” member of a map to determine if a particular variable name exists in the map.

To produce output from the Paula “put” statement, call the output function of the poly class.

Any error messages you produce should start with the word ERROR, should fit on a single line, and should be output to the error stream.

Generally, you do not need to try to recover from an error in the user program; you can just abort the program.

It is recommended that you write  a function that takes a polynomial term, e.g., 

-1.23x^31

and produces the coefficient -1.23 as a double the exponent 31 as an int.

Write an extended poly class.  You are to write a class called polynew (extended poly set) which inherits from the poly class.  The polynew class should add an equality comparison operator to the poly class (see Paula grammar).  The logic of your interpreter (your driver) can use objects of type poly --- except when using the equality operator.

Downcasting.  There is a problem in using the operators of poly, as follows.  Each poly operator (except ==), such as +, returns an object X of type poly (and not polynew).  Unfortunately, such an X cannot be supplied as an argument to the equality operator (==) in polynew, because == expects arguments of type polynew (not poly).  To solve this problem, we can downcast X to turn it into an object of class polynew.  Here is a function that can be used for this  downcasting:

polynew & poly2polynew (const poly& p) //Downcast from poly to polynew

     {   return *( polynew *)&p ;  }

This converts (downcasts) p from type poly to polynew as follows.  It takes the address of p (in &p), converts this pointer to a pointer to polynew, using (polynew *), and then uses * to return an object of type polynew.  You can use this function to convert a poly value so that it can be compared by ==.  This allows you to write your driver (interpreter) using the poly class (except with ==).

Downcasting can be dangerous, as the derived class may assume that there is data in the object which is not actually there.  In the case of downcasting poly to polynew there is no danger in that polynew contains no data.  See Buhr’s notes on “contravariance” for a discussion of this sort of need for downcasting.

You are to use these files:

scan – given to you as executable

token.h - given to you

token.cpp – you write this

tokennames.h – given to you

poly2.cpp – ideally yours from A5, but use the supplied poly3.o if needed

    You can slightly modify this file for your purposes.

poly3.h – use only if you are missing poly*.cpp

poly3.o – use only if you are missing poly*.cpp

polynew3.h – given to you

    You can slightly modify this file for your purposes.

polynew3.cpp – you write this

driver.cpp – you write this. This is a main program.  It operates as the interpreter

driver – executable version of driver.cpp that you write

dvr – you write this. It is the shell script that combines scan and driver.

driver-solution – given to you as an executable (this is a solution for driver)

makefile-suggest – this is a suggested makefiile that you can use.  You

can modify it if need be.  You should use a makefile

Provided files are in:

    ~holt/cp-for-students/cs/246/2012/asgn06