Assignment Two, CS351 S2001
Designing a Parser's API
In this assignment you will design an API for a simple parser,
motivate your design, and document the design. The documentation
will include some sample programs that use the API.
The basic idea is to write a system that takes a specification for a
small ``expression language'' and gives the program the ability to
read from a stream and parse it up into the elements of this language,
represented in a form suitable for further processing by the program
that uses the parser. The range of languages allowed is quite
limited: they are simple expression languages, with no precedence ie
only left-to-write association of operators.
The expression language consists of two sorts of tokens: operators,
which are one character long, and variables, which are sequences of
characters. The characters allowed in variables (called
constituent characters) are disjoint from those allowed in
operators. Parenthesis '(' and ')' can be used for grouping. Each
operator is either unary (prefix) or binary (infix), and these two
classes of operator are disjoint.
The expression "(var1 opA var2 opB var3)" is equivalent to "(var1 opA
(var2 opB var3))". Whitespace can occur anywhere except inside a
variable. Unary operators bind ``tighter'' than binary ones, so "(op1
var1 op2 var2)" where op1 is unary and op2 is binary is identical to
"((op1 var1) op2 var2)".
Which characters are constituents, and the identity and nature of the
operators, can change from run to run - so your API must have a way of
getting this information from the program using it.
Expressions can be thought of as representing trees whose leaves are
"variables" and whose internal nodes are tagged with operators. There
would be two kinds of internal nodes: ones with two children which are
tagged with binary operators, and ones with one child which are tagged
with unary operators.
You will need to be represent the expressions that are read in a
fashion that allows the program using the library to examine and
manipulate them sensibly. Hint: define a separate API for objects
representing expressions and portions thereof.
Here is a formal grammar, in BNF.
EXPR := VAR | EXPR OP2 EXPR | OP1 EXPR | '(' EXPR ')'
OP1 := ... list of possible single chars, eg: '-' | '~'
OP2 := ... list of possible single chars, eg: '+' | '*' | '/'
VAR := CONSTITUENT+
CONSTITUENT := ... list of constituent chars, typically: '1' | '2' | 'a'
Note that the characters '(', ')', constituent characters, and OP1
characters, and OP2 characters are disjoint. Ie if '-' in a
unary operators then '-' is not a binary operator, or a constituent
What you should turn in
All the below should be ASCII files, handed in by running the
cs351-handin program on a directory containing only the files you wish
to hand in. The documentation can be html format if you'd like.
Please do not use any binary format files. The file parser.h should
be legal C++ code. None of the member functions should have bodies,
ie none of them should be inline. The bodies will be defined in the
companion parser.cc file you will write later.
Design Constraints and Motivation
This explains how you thought about the problem, and gives the
criteria you thought the library needs to satisfy. It is motivation
for the exact decisions explained below. Eg if the program using the
library first has to do some setup before it can do real work, the
reason you thought this was reasonable and the reasoning behind why
you put the division between the various stages where you did should
be explained here.
This formally sets out the classes and member functions in your API.
Documentation with Examples
This documents what all the (public) stuff in parser.h is for. After
reading this, a competent programmer should be able to write a program
that uses a library that meets your API.
Due date: 2pm Mon Feb 12.