We're always interested in getting feedback. E-mail us if you like
this guide, if you think that important material is omitted, if you
encounter errors in the code examples or in the documentation, if you
find any typos, or generally just if you feel like e-mailing. Mail to
Frank Brokken
or use an
e-mail form.
Please state the concerned document version, found in
the title. If you're interested in a printable
PostScript copy, use the
form, or
better yet,
pick up your own copy by ftp
from ftp.icce.rug.nl/pub/http.
Another example digs into the peculiarities of using a parser- and scanner-generator with C++. Once the input for a program exceeds a certain level of complexity, it's advantageous to use a scanner- and parser-generator for creating the code which does the actual input recognition. The example describes the usage of these tool in a C++ environment.
A reoccurring task of many programs is the storage of data, which are then
sorted, selected, etc.. Storing data can be as simple as maintaining an array
of int
s, but can also be much more complex, such as maintaining file
system information by the kernel of an operating system.
Storage
is concerned, objects
can be added to the storage and objects can be obtained from the storage. Also
it must be possible to obtain the number of objects in the storage.
As far as the internal data organization of the storage is concerned, we
opt for an approach in which Storage
maintains an array which can be
reallocated, consisting of pointers to the stored objects.
The internal organization of the class Storage
is illustrated in
figure 11.
Storage
.
15.1.1.1: Interface functions of the class Storage
The usage (interface) of the class Storage
is contained in three member
functions. The following list describes these member functions and mentions
the class Storable
, more on this later.
add(Storable const *newobj)
adds an object to the
storage. The function reallocates the array of pointers to accommodate one
more and inserts the address of the object to store.
Storable const *get(int index)
returns a pointer
to the object which is stored at the index'th slot.
int nstored()
returns the number of objects in
the storage.
15.1.1.2: To copy or not to copy?
There are two distinct design alternatives for the function add()
. These
considerations address the choice whether the stored objects (the squares on
the right side of figure 11) should be copies of the
original objects, or the objects themselves.
In other words, should the function add()
of the class Storage
:
These considerations are not trivial. Consider the following example:
If we choose to store (addresses of) the objects themselves, then at the end
of the above code fragment, the object pointed to by retrieved
will equal
something
. A manipulation of previously stored objects thereby alters the
contents of the storage.
If we choose to store copies of objects, then obviously *retrieved
will not equal something
but will remain the original, unaltered, object.
This approach has a great merit: objects can be placed into storage as a
`safeguard', to be retrieved later when an original object was altered or even
ceased to exist. In this implementation we therefore choose for this approach.
The fact that copies of objects should be stored presents a small problem. If
we want to keep the class Storage
as universal as possible, then the
making of a copy of a Storable
object cannot occur here. The reason for
this is that the actual type of the objects to store is not known in advance.
A simplistic approach, such as the following:
shall not work. This code attempts to make a copy of obj
by using the
operator new
, which in turn calls the copy constructor of Storable
.
However, if Storable
is only a base class, and the class of the object to
store is a derived class (say, a Person
), how can the copy constructor of
the class Storable
create a copy of a Person
?
The making of a copy therefore must lie with the actual class of the
object to store, i.e., with the derived class. Such a class must have the
functionality to create a duplicate of the object in question and to
return a pointer to this duplicate. If we call this function duplicate()
then the code of the adding function becomes:
The function duplicate()
is called in this example by using a pointer to
the original object (this is the pointer obj
). The class Storable
is
in this example only a base class which defines a protocol, and not the class
of the actual objects which will be stored. Ergo, the function
duplicate()
need not be defined in Storable
, but must be
concretely implemented in derived classes. In other words, duplicate()
is
a pure virtual function.
Storable
.
The following questions are of importance:
Storable
need a default constructor, or
possibly other constructors such as a copy constructor?
<p>The answer is no. Storable
will be a bare prototype, from which
other classes will be derived.
Storable
need a destructor? Should this
destructor be (pure) virtual
?
<p>Yes. The destructor will be called when, e.g., a Storage
object
ceases to exist. It is quite possible that classes which will be derived
from Storable
will have their own destructors: we should therefore
define a virtual
destructor, to ensure that when an object pointed to
by a Storable*
is deleted, the actual destructor of the derived class
is called.
<p>The destructor however should not be pure virtual. It is quite
possible that the classes which will be derived from Storable
will
not need a destructor; in that case, an empty destructor function should
be supplied.
The class definition and its functions are given below:
15.1.2.1: Converting an existing class to a Storable
To show how (existing) classes can be converted to derivation from a
Storable
, consider the below class Person
from section
5. This class is re-created here, conforming to Storable
's
protocol (only the relevant or new code is shown):
When implementing the function Person::duplicate()
we can use either the
copy constructor or the default constructor with the overloaded assignment
operator. The implementation of duplicate()
is quite simple:
The above conversion from a class Person
to the needs of a Storable
supposes that the sources of Person
are at hand and can be modified.
However, even if the definition of a Person
class is not available, but
is e.g., contained in a run-time library, the conversion to the Storable
format poses no difficulties:
Storage
. The class definition is given
below:
Concerning the class definition we remark:
add()
, get()
and nstored()
. These functions were previously discussed (see section
11).
Storage
contains a
pointer, which addresses allocated memory.
Storage
itself is derived from Storable
, as can be seen
in the classname definition and in the presence of the function
duplicate()
. This means that Storage
objects can themselves be
placed in a Storage
, thereby creating `super-storages': say, a list
of groups of Person
s.
Storage
defines two private
functions
copy()
and destroy()
. The purpose of these primitive functions
is discussed in section 5.4.
The destructor, constructors and the overloaded assignment function are listed below:
The primitive functions copy()
and destroy()
unconditionally copy
another Storage
object, or destroy the contents of the current one. Note
that copy()
calls duplicate()
to duplicate the other's stored
objects:
The function duplicate()
, which is required since Storage
itself
should be a Storable
, uses the copy constructor to duplicate the current
object:
Finally, here are the interface functions which add objects to the storage,
return them, or determine the number of stored objects (
Note: the function realloc()
that is used in this section should actually
not be used. A better procedure would be to create a C++ variant for the
realloc()
function. A modification is in the pipeline....)
Storage
and Storable
(see section 15)
two separate classes are used: one to represent the tree itself, and one to
represent the objects which are stored in the tree. The classes will be
appropriately named Tree
and Node
.
Node
is an abstract (pure virtual) class, which defines the
protocol for the usage of derived classes with a Tree
. Concerning this
protocol we remark the following:
<p> This comparison must lie with Node
s: a Tree
itself cannot
know how objects should be compared. Part of the procotol which is
required by Node
is therefore:
The comparing function will have to be implemented in each derived class.
Storage
(see
section 15), a binary tree will contain copies of
objects. The responsibility to duplicate an object therefore also lies
with Node
, as defined in a pure virtual function:
in the class Node
, the responsibility to process an object is placed
with the derived class.
For these cases we define a virtual function already_stored()
, which
is however not pure virtual. The default implementation will take no
action. The function can however be redefined in a derived class:
The complete definition and declaration of the class Node
is given below:
Tree
is responsible for the storage of objects which are
derived from a Node
. To implement the recursive tree structure, the class
Tree
has two private
pointers as its data, pointing to subtrees: a
Tree *left
and Tree *right
. The information which is contained in a
node of the tree is represented as a private
field Node *info
.
To scan a binary tree, the class Tree
offers three methods: preorder,
inorder and postorder. When scanning in preorder first a leaf in a node is
processed, then the left subtree is scanned and finally the right subtree is
scanned. When scanning inorder first the left subtree is scanned, then the
leaf itself is processed and finally the right subtree is scanned. When
scanning in postorder first the left and right subtrees are scanned and then
the leaf itself is processed.
The definition of the class Tree
is given below:
15.2.2.1: The `standard' functions
As can be seen from the class definition, Tree
contains pointer fields.
This means that the class will need a destructor, a copy constructor and an
overloaded assignment function to ensure that no allocation problems occur.
15.2.2.2: Adding an object to the tree
The addition of a new object to the tree is a recursive process. When the
function add()
is called to insert an object into the tree, there are
basically only a few possibilities:
info
field of the current node can be a 0-pointer. In that
case, a duplicate of the object to add is inserted in the current node.
compare()
, a pure virtual function whose implementation is required
by Node
. Depending on the order the new object must be inserted in
the left
or in the right
subtree. These subtrees may first have
to be allocated.
already_stored()
is called.
The function add()
is listed below:
The class Tree
offers three methods of scanning a binary tree: preorder,
inorder and postorder. The three functions which define these actions are
recursive:
15.2.2.4: The primitive operations copy() and destroy()
The functions copy()
and destroy()
are two private
member
functions which implement primitive operations of the class Tree
: the
copying of the contents of another Tree
or the destroying of the tree.
Concerning this implementation we remark the following:
destroy()
is recursive, even though this is not
at once visible. A statement like delete left
will activate the
destructor for the Tree
object which is pointed to by left
; this
in turn will call destroy()
etc..
copy()
is recursive. The code <tt/left
= new Tree(*other.left)/ activates the copy constructor, which in turn
calls copy()
for the left branch of the tree.
add()
, nodes themselves are
duplicated with the function duplicate()
. This function is supplied
by a concrete implementation of a derived class of Node
.
Tree
and Node
with a program
that counts words in files. Words are defined as series of characters,
separated by white spaces. The program shows which words are present in which
file, and how many times.
Below is the listing of a class Strnode
. This class is derived from
Node
and implements the virtual functions. Note also how this class
implements the counting of words; when a given word occurs more than one time,
Tree
will call the member function already_stored()
. This function
simply increases the private counter variable times
.
flex
and the parser generator bison
. Both
bison
and flex
are well documented elsewhere. The original
predecessors of bison
and flex
, called yacc
and lex
are
described in several books, e.g. in O'Reilly's book `lex & yacc'.
However, the scanner and parser generators are also (and maybe even
more commonly, nowadays) available as free software. Both bison
and flex
can be obtained from prep.ai.mit.edu/pub/gnu. Flex
will create a C++
class
when called as flex++
, or when the -+
flag is used. With
bison
the situation is a bit more complex. Scattered over the
Internet several bison++
archives can be found (e.g., in
rzbsdi01.uni-trier.de). The
information in these archives usually dates back to 1993,
irrespective of the version number mentioned with the archive
itself. (However, the given ftp-archive also contains dos-executables,
for those who are interested....)
Using flex++
and bison++
a class
-based scanner and parser can be
generated. The advantage of this approach is that the interface to the scanner
and the parser tends to become a bit cleaner than without using the class
interface.
Below two examples are given. In the first example only a lexical scanner is
used to monitor the production of a file from several parts. This example
focuses on the lexical scanner, and on switching files while churning
through the parts. The second example uses both a scanner and a parser to
transform standard arithmetic expressions to their postfix notation, commonly
encountered in code generated by compilers and in HP
-calculators.
The second example focuses on the parser.
#include
statement, which is followed by a string indicating the
file which should be included at the location of the #include
.
In order to avoid complexities that have nothing to do with the current
example, the format of the #include
statement is #include <filepath>
.
The file specified between the pointed brackets should be available at
the location indicated by filepath
. If the file is not available,
the program should terminate using a proper error message.
The program is started with one or two filename arguments. If the program is
started with just one filename argument, the output is written to the standard
output stream cout
. Otherwise, the output is written to the stream whose
name is given as the program's second argument.
The program uses a maximum nesting depth. Once the maximum is exceeded, the program terminates with an appropriate error message. In that case, the filenamestack indicating where which file was included should be printed.
One minor extra feature is that comment-lines should be recognized: include
directives in comment-lines should be ignored, comment being the standard
C++ comment-types.
The program is created in the following steps:
lexer
is constructed, containing the
specifications of the input-language.
lexer
the requirements for the
class Scanner
evolve. The Scanner
class is a wrapper around
the class yyFlexLexer
generated by flex++
. The requirements
results in the specification of the interface for the class
Scanner
.
main()
function is constructed. A Startup
object
is created to inspect the commandline arguments. If successful,
the scanner
's member yylex()
is called to construct the
output file.
15.3.1.1: The flex++ specification file
The organization of the lexical scanner specification file is similar
to the one used with flex
. However, flex++
now creates a class
(yyFlexLexer
) from which the class Scanner
will be derived.
Here is the complete and annotated lexical scanner specification file
to be used with flex++
:
Since the derived class is able to access the information stored
within the lexical scanner itself (it can even access the information
directly, since the data members of yyFlexLexer
are
protected
, and thus accessible to derived classes), very much
processing can be left to the derived class. This results in a very
clean setup of the lexer specification file, in which hardly any code
is required in the preamble.
15.3.1.2: The derived class: Scanner
The class Scanner
is derived from the class yyFlexLexer
, generated by
flex++
. The derived class has access to the data controlled by the lexical
scanner. In particular, the derived class has access to the following data
members:
char *yytext
: contains the text matched by a regular expression
int yyleng
: the length of the text in yytext
int yylineno
: the current line number (only if %option yylineo
was specified in the lexer specfication file)
FlexLexer.h
, which is part
of the flex
distribution.
The class Scanner
has to perform two tasks: It should push file information
about the current file to a filestack, and should pop the information pushed
last once EOF
is detected on a file.
Several member functions are
needed for the accomplishment of these tasks. As they are auxiliary to the
switchSource()
and popSource()
functions, they are private members.
These private members are developed in practice once the need for them arises.
In the following interface of the Scanner
class the final header
file is given. Note that, apart from the private member functions, several
private data members are used as well. These members are initialized in the
constructor Scanner()
and are used in the private memberfunctions. They
are discussed below, in the context of the memberfunctions using them.
The switchSource()
memberfunction should interpret the information given
in yytext
: it is interpreted by scanYYText()
. If scanYYText()
can extract a filename from yytext
a switch to another file can be
performed. This switch is performed by performSwitch()
. If the filename
could not be extracted, a message is written to the outputstream. Here is
the code of switchSource()
:
The memberfunction scanYYText()
performs a simple scan of the information
in yytext
. If a name is detected following #include "
that name is
stored in the private data member nextSource
, and 1 is returned.
Otherwise, the information in yytext
is copied to yyout
, and 0 is
returned. Here is the source for scanYYText()
:
The function performSwitch()
performs the actual file-switching. The
yyFlexLexer
class provides a series of memberfunctions that can be used
for file switching purposes. The file-switching capability of a yyFlexLexer
object is founded on the struct yy_buffer_state
, containing the state of
the scan-buffer of the file that is currently scanned by the lexical scanner.
This buffer is pushed on a stack when an #include
is encountered, to
be replaced with the buffer of the file that is mentioned in the #include
directive.
The switching of the file to be scanned is realized in the following steps:
include
-nesting is inspected.
If the stackDetph
is reached, the stack is full, and the program
aborts with an appropriate message. For this the memberfunction
checkDepth()
is called.
fileName
stack is inspected, to avoid circular
inclusions. If nextSource
is encountered in the fileName
array, the inclusion is refused, and the program terminates with
an appropriate message. The memberfunction checkCircularity()
is called for this task.
ifstream
object is created, assigned to
nextSource
. If this fails, the program terminates with an
appropriate message.
yy_buffer_state
is created for the newly opened
stream, and the lexical scanner is instructed to switch to that
stream using yyFlexLexer
's memberfunction yy_switch_to_buffer
.
The sources for the memberfunctions performSwitch(), checkDepth()
, and
checkCircularity()
is given next:
The memberfunction popSource()
is called to pop the previously pushed
sourcefile from the stack, to continue its scan just beyond the just processed
#include
directive. The popSource()
function first inspects
stackTop
: if the variable is at least 0, then it's an index into the
yy_buffer_state
array, and thus the current buffer is deleted, to be
replaced by the state waiting on top of the stack. This is realized by
the yyFlexLexer
members yy_delete_buffer
and yy_switch_to_buffer
.
If a previous buffer waited on top of the stack, then 1 is returned, indicating a successful switch to the previously pushed file. If the stack was empty, 0 is returned, and the lexer will terminate.
Here is the source of the function popSource()
:
These functions complete the implementation of the complete lexical scanner:
the lexical scanner itself is stored in the yyFlexLexer
part of the
Scanner
object. The Scanner
object itself only has two public
memberfunctions: one to push a sourcefile on a stack when a switch to
the next sourcefile is requested, the other one restores the previously
pushed source.
Finally, the constructor will initialize the Scanner
object. Note that
the interface contains an overloaded assignment operator and a copy
constructor. By mentioning these two functions in the interface only,
without implementing them, they cannot be used in a program: the linking phase
of a program using such functions would fail. In this case this is intended
behavior: the Scanner
object does its own job, and there simply is no need
for the assignment of a Scanner
object to another one, or for
the duplication of a Scanner
object.
The constructor itself is a simple piece of code. Here is its source:
, but should not be used.
The main program is a very simple one. As the program expects a
filename to start the scanning process at, initially the number of
arguments is checked. If at least one argument was given, then a
ifstream
object is created. If this object can be created, then a
Scanner
object is created, receiving the address of the
ifstream
object as its argument. Then the yylex()
member
function of the Scanner
object is called. This function is
inherited from the Scanner
's base class yyFlexLexer
.
Here is the source-text of the main function:
15.3.1.4: Building the scanner-program
The final program is constructed in two steps. These steps are given
for a unix system, on which flex++
and the Gnu
C++
compiler g++
have been installed:
flex++
. For this the command
flex++ lexer
libfl.a
library. The appropriate command here is
g++ -o scanner *.cc -lfl
Starting point for a program using both a parser and a scanner is the grammar: the grammar is specified first. This results in a set of tokens which can be returned by the lexical scanner (commonly called the lexer. Finally, auxiliary code is provided to fill in the blanks: the actions which are performed by the parser and the lexer are not normally specified with the grammatical rules or lexical regular expressions, but are executed by functions, which are called from within the parser's rules or associated with the lexer's regular expressions.
In the previous section we've seen an example of a C++ class
generated by flex++
. In the current section the parser is our main
concern. The parser can be generated from a grammar specified for the
program bison++
. The specification of bison++
is similar to
the specifications required for bison
, but a class is generated,
rather than a single function. In the next sections we'll develop a
program converting infix expressions, in which binary operators
are written between their operands, to postfix expressions, in
which binary operators are written following their operands. A
comparable situation holds true for the unary operators -
and
+
: We can ignore the +
operator, but the -
is converted to
a unary minus.
Our calculator will recognize a minimal set of operators: multiplication, addition, parentheses, and the unary minus. We'll distinguish real numbers from integers, to illustrate a subtlety in the bison-like grammar specifications, but that's about it: the purpose of this section, after all, is to illustrate a C++ program, using a parser and a lexer, and not to construct a full-fledged calculator.
In the next few sections we'll start developing the grammar in a
bison++
specification file. Then, the regular expressions for the
scanner are specified according to the requirements of
flex++
. Finally the program is constructed.
15.3.2.1: The bison++ specification file
The bison specification file as used with bison
is comparable to the
specification file as used with bison++
. Differences are related to the
class nature of the resulting parser. The calculator will distinguish real
numbers from ints, and will support the basic set of arithmetic operators.
The bison++
specification file contains the following sections:
bison
. The difference being the
%header{
opening. In this section we'll encounter mainly declarations:
header files are included, and the yyFlexLexer
object is declared.
bison++
has several extra
items that can be declared here. They are important and warrant a section of
their own.
bison
program.
15.3.2.2: The bison++ token section
The token section contains all the tokens that are used in the grammar, as well as the priority rules as used for the mathematical operators. However, several extra items can be declared here:
%name ParserName
. The name ParserName
will be the name
of the parser's class. This entry should be the first entry of the
token-section. It is used in cases where multiple grammars are used,
to make sure that the different parser-classes use unique
identifiers. By default the name parse
is used.
%define name content
. The %define
has the same function
as the #define
statement for the C++
preprocessor. It can be
used to define, e.g., a macro. Internally, the defined symbol will be
the concatenation of YY_
, the parser's classname, and the name of
the macro. E.g.,
YY_ParserName_name
bison++
, and can be redefined in this section:
%define DEBUG 1
: if non-0 debugging code will be included
in the parser's source.
%define ERROR_VERBOSE
: if defined, the parser's stack
will be dumped when an error occurs.
%define LVAL yylval
: the default variable name is shown
here: the variable name containing the parser's semantic value is by
default yylval
, but its name may be redefined here.
%define INHERIT :public ClassA, public ClassB
: the
inheritance list for the parser's class. Note that it starts with the
':'
character. The define
should be left out if the parser's
class isn't derived from another class.
%define MEMBERS member-prototypes
: if the parser should
contain extra members, they must be declared here. Note that there is
only one %define MEMBERS
definition allowed. So, if multiple
members are to be declared, they must all be declared at this
point. To prevent very long lines in the specification file, the \ can
be used at the end of a line, to indicate that it continues on the
next line of the source-text. E.g.,
%define LEX_BODY inline-code
: here the body of the call
to the lexer is defined. It can be defined as = 0
for an abstract
parser-class, but otherwise it will contain the code representing
the call to the lexer. For example, if the lexer object generated by
flex++
is called lexer
, this declaration should be
%define LEX_BODY {return lexer.yylex();}
%define ERROR_BODY inline-code
: similarly, the body of
the code of the call to the error-function can be defined here. It can
be defined as = 0
, in which case the parser's class will again
become abstract. Otherwise, it can be used to specify the inner
workings of the error function. E.g.,
%define ERROR_BODY { cerr << "syntax Error\n"; }
%defines
can be used:
%define CONSTRUCTOR_PARAM (parameterlist)
: this
defines the parameterlist for the parser's constructor.
%define CONSTRUCTOR_INIT :initializer(s)
: this
defines the base-class and member initializers for the constructor.
%define CONSTRUCTOR_CODE { code }
: this
defines the code of the parser's constructor.
parse parser;
%union
. This starts the definition of the semantical value
union. It replaces the #define YYSTYPE
definition seen with
bison
. An example of a %union
declaration is
$$
or the generic returnvalues $1,
$2
, etc, that are associated with components of rules can be used,
rather than $$.i, $3.d
, etc. In order to associate a nonterminal
or a token with a unionfield, the <fieldname>
specification is
used. E.g.,
%union
discussion the %token
and %type
specifications should be noted. They are used for the specficiation of
the tokens (terminal symbols) that can be returned by the lexical
scanner, and for the specification of the returntypes of nonterminals.
Apart from %token
the token-indicators %left, %right
and
%nonassoc
may be used to specify the associativity of
operators. The token(s) mentioned at these indicators are interpreted
as tokens indicating operators, associating in the indicated
direction. The precedence of operators is given by their order: the
first specification has the lowest precedence. To overrule a certain
precedence in a certain context, %prec
can be used. As all this is
standard bison
practice, it isn't further discussed in this
context. The documentation provided with the bison
distribution
should be consulted for further reference.
15.3.2.3: The bison++ grammar rules
The rules and actions of the grammar are specified as usual. The grammar for our little calculator is given below. A lot of rules, but they illustrate the use of nonterminals associated with value-types.
doubleExpr
is
linked to real (double) values, intExpr
is linked to integer
values. Precedence and type association is defined in the token
section of the parser specification file, which is:
%type
specifiers,
connecting intExpr
to the i
-field of the semantic-value union,
and connecting doubleExpr
to the d
-field. At first sight it
looks a bit complex, since the expression rules must be included for
each individual returntype. On the other hand, if the union itself
would have been used, we would have had to specify somewhere in the
returned semantic values what field to use: less rules, but more
complex and error-prone code.
subsubsection(The flex++ specification file)
The flex-specification file to be used with our little calculator is
simple: blanks are skipped, single characters are returned, and
numerical values are returned as either Parser::INT
or
Parser::DOUBLE
values. Here is the complete flex++
specification file:
subsubsection(The generation of the code)
The code is generated in the same way as with bison
and
flex
. To order bison++
to generate the files parser.cc
and parser.h
, the command
bison++ -d -o parser.cc parser
Flex++
will thereupon generate code on lexer.cc
using the command
flex++ -I -olexer.cc lexer
flex++
expects no blanks between the -o
flag
and lexer.cc
.
On unix, linking and compiling the generated sources and the source for the main program (listed below) is realized with the following command:
g++ -o calc -Wall *.cc -lfl -s
libfl.a
library is mentioned here. If it's
not mentioned unresolved functions like yywrap()
emerge.
A source in which the main()
function, the lexical
scanner and the parser objects are defined is, finally: