Flex/Bison based compiler and interpreter written in C++ (using Boost)

\chapter{Overview}
\texttt{vyp08} is compiler and interpreter of \texttt{VYP08}
language\footnote{\texttt{VYP08} language definition can be
found in the task description, nowadays available at
\href{https://www.fit.vutbr.cz/study/courses/VYP/private/projekt/vyp2008.pdf}{
https://www.fit.vutbr.cz/study/courses/VYP/private/projekt/vyp2008.pdf}}
developed as a school project
for~\href{https://www.fit.vutbr.cz/study/courses/VYP/public/}{VYP course}. Its
input is a program in \texttt{VYP08} language. There is no equivalent output
program written to file and the compiled program is given directly to the
interpreter instead (in an internal representation based on \texttt{vyp08}
object model).
 
The compiler part of this program is heavily based on \textit{FLEX/Bison}
equipment. FLEX is used to generate the core part of \texttt{scanner} module and
Bison is used to generate the core part of \texttt{parser} module. FLEX/Bison
utilities have been used for decades in many successful projects and they can
significantly speedup the development of projects like this.
 
The main goal of this project was development of generic and reusable compiler
modules which can be used later again in similar projects. The key part of
design is therefore object model based on modern programming techniques like
design patterns \cite{Gamma}. As the components are intended to be reusable, all
public classes are well documented in API documentation (generated by
Doxygen\footnote{source code documentation generator tool, available at
\href{http://www.stack.nl/~dimitri/doxygen/}{
http://www.stack.nl/$\sim$dimitri/doxygen/}}).
 
In the following chapter are briefly described utilities FLEX and Bison.
In~the~chapter~\ref{design} is the object model explained step by step. In
the chapter \ref{implementation} are a few hints about implementation, build
and testing. And finally in~the~chapter~\ref{conclusion} is summarized the
contribution of this work.
 
% \vfill\hfill {\footnotesize This document was typed by typesetting system
% \LaTeX.}
 
 
\chapter{Theoretical part}\label{theory}
In this chapter are briefly described utilities FLEX and Bison. The goal is
to explain why are these utilities useful for development of compiler like
\texttt{vyp08}. Huge amount of documentation, tutorials and FAQs can be found
in referred (mostly on web published) materials. 
 
\section{FLEX}
FLEX (\textit{Fast LEXical analyzer generator}) is a tool for generating
scanners \cite{flex-tutor}. On its input is an program in the FLEX language,
roughly speaking a set of regular expressions defining desired lexical units.
Output of FLEX is a program in C/C++ which can read these lexical units.
 
The generated scanner is based on FSM (\textit{Finite State Machine}). The
family of languages accepted by regular expressions is equivalent to family of
languages accepted by FSM \cite{TIN}. Each regular expression can be converted
to equivalent non-deterministic FSM, each non-deterministic FSM can be converted
to deterministic FSM and each deterministic FSM can be converted to minimal
FSM. In this way is the scanner generated by FLEX from a set of regular
expressions on its input.
 
FLEX manual which includes a lot of examples and FAQs, can be found\\at
\href{http://flex.sourceforge.net/manual/}{http://flex.sourceforge.net/manual/}.
 
\section{Bison}
As FLEX is generator of scanner, Bison\footnote{Bison is based on YACC
(\textit{Yeat Another Compiler-Compiler}, its predecessor) and is backward
compatible with it.} is generator of parser. On its input is an program in the
Bison language, roughly speaking an CFG (\textit{Context-Free Grammar}) which
defines the language accepted by parser being generated. Output of Bison is an
program in C/C++ which can read the language defined by the CFG.
 
In the default configuration the \textit{LALR(1)} parser is generated. LALR1 is
a kind of very strong LR-parser, which can read any language acceptable by
deterministic PDA (\textit{PushDown Automata}) \cite{vyp6}. It is possible to
generate GLR (\textit{Generalized LR}) parser by Bison. This kind of parser can
read languages defined by general CFG, but it is more complex to use and even
more complex to run.
 
Bison manual which includes a lot of examples and FAQs, can be found\\at
\href{http://www.gnu.org/software/bison/manual/html_mono/bison.html}
{http://www.gnu.org/software/bison/manual/html\_mono/bison.html}.
 
 
\chapter{Solution design}\label{design}
In this chapter is presented the object model of \texttt{vyp08}. The program
consists of a few separated design modules (which partly corresponds to C++
modules being built). The~modules are intended to be independent on each other
as much as possible. Each module has simple and generic interface which hides
its implementation. This good manner makes it possible to take one module and
replace it by another one with completely different implementation.
 
\section{Scanner interface}
As it has been already told, the core part of scanner is generated by FLEX
utility. But this is not reason to make scanner interface dependent on FLEX.
Therefore the FLEX is used only to generate part of implementation of this
module. The public interface is much more generic. We can take (already
compiled) \texttt{vyp08} project and replace scanner module by~another
implementation of scanner, which does not know anything about FLEX. Moreover we
do not have to recompile the rest of \texttt{vyp08} project -- link target
binary is the only thing we have to do\footnote{It is also recommended to run
the test suite which is distributed with compiler, to check if compiler works.}.
 
The interface of \texttt{scanner} module is pretty simple -- there are two
value types, two interfaces (pure virtual classes in C++ terminology
\cite{Stroustrup}) and one static-only factory \cite{Gamma}. Enumeration type
\texttt{EToken} represents scanner token type (e.g. \texttt{T\_ID} or
\texttt{T\_ELSE}). Value type \texttt{Token} couples token type with its value
(which makes sense only for tokens holding a value).
 
The root level interface \texttt{IErrorSensitive} defines simple method
\texttt{hasError}. This interface is used as base class for all fundamental
compiler parts which are sensitive to errors. The interface \texttt{IScanner}
(based on \texttt{IErrorSensitive}) defines one more method to read the tokens
from input program. Static-only class \texttt{ScannerFactory} is responsible
for scanner object creation. The whole scanner interface is well documented in
the API documentation mentioned above.
 
\section{Scanner implementation}
The implementation of scanner consists of two modules, one is generated by FLEX
and one is written manually as a sort of wrapper around the code generated by
FLEX. Scanner generated by FLEX is used to read all tokens except keywords (and
keyword-like operators). The keywords are read as identifiers by FLEX scanner
and handled later on.
 
FLEX can generate a legacy code for old program written in C language, but
newly \cite{flexcpp} it can generate a C++ compatible code\footnote{The C++
support in FLEX has been not declared stable yet. Its future modification can
break even the source code level compatibility.} as well. Then the Flex scanner
is generated as an ordinary C++ class and this approach was chosen for
\texttt{vyp08}.
 
The class generated by Flex is used as a base class for
\texttt{PrivateFlexLexer} which implements \textit{NVI} (Non-Virtual Interface
\cite{Sutter}) over the FLEX scanner. Classes \texttt{FlexScanner} and
\texttt{KwScanner} stand for a \textit{decorator} \cite{Gamma} chain based on
\texttt{IScanner} interface. The first one checks literals read by FLEX scanner
and converts them to value. The second one converts identifiers representing a
keyword, to tokens representing the keyword.
 
\section{Parser}
Analogous to previous module, parser's interface is not dependent on its
implementation. The interface is based on callback as the compilation process
is syntax-directed. Pure virtual class \texttt{IBuilder} defines the callback
and it separates parser and builder modules. The parser does not know anything
about builder and the builder does not know anything about parser. This pure
virtual class is the only thing which is common for both modules.
 
Similar to scanner, the implementation of parser has two parts. The first one is
generated by Bison and the second one is written manually as something like
wrapper around the code generated by Bison. Both parts are connected by
\texttt{IBisonListener} interface.
 
In the Bison input is only the \texttt{VYP08} grammar defined, there
is almost no code inside. The action code consists only of invocation of
appropriate \texttt{IBisonListener} method. Class \texttt{BisonListener}
implements the \texttt{IBisonListener} interface and acts as bridge between
parser generated by Bison and the builder.
 
\section{Virtual machine}
As the parser module stands for the core of compiler, the core of interpreter
is a module called \textit{virtual machine} (shortly \textit{vm}). Each basic
abstraction defined by \texttt{VYP08} language has its equivalent in the
virtual machine. There is a whole hierarchy of run-time objects. On~the~low
level there are simple value types and on the topmost level is the class
\texttt{Vm} which represents the whole virtual machine. Class \texttt{VmRunner}
acts as servant class \cite{Pecin} used to run virtual machine (to run an
abstraction of compiled \texttt{VYP08} program). On the collaboration diagram
\ref{cgVmRunner} is visualized the situation from runner's perspective.
\begin{figure}[h]
  \begin{center}\includegraphics[scale=0.5]{img/cgVmRunner.png}\end{center}
  \caption{Collaboration graph of class \tt{VmRunner}}\label{cgVmRunner}
\end{figure}
 
Value type \texttt{Value} stands for a generic data type defined by virtual
machine. Universal variable for global/local variables, function arguments and
function return value is defined by value type \texttt{Var}. A smart container
for such variables is the class \texttt{VarSet}. Declaration of~function is
represented by value type \texttt{FncDeclaration}. Function definition (value
type \texttt{FncDefinition}) is directly inherited from type
\texttt{FncDeclaration}. This inheritance makes comparison of two declarations
or definition with declaration much more easy. Container \texttt{FncSet} acts
as a common storage for \texttt{FncDeclaration} and \texttt{FncDefinition}
objects.
 
All actions performed by the \texttt{VYP08} code are abstractly defined by
interface \texttt{ICmd} (design pattern \textit{command} \cite{Gamma}). A
sequence of actions is therefore a container of objects which implements
\texttt{ICmd} interface. This container (class \texttt{CmdList}) implements
\texttt{ICmd} interface as well (design pattern \textit{composite} \cite{Gamma}).
Particular \texttt{ICmd} implementations are placed in separate module called
\textit{cmd}. The vm module does not know (and does not need to know) about
these implementations.
 
The running \texttt{VYP08} program (strictly speaking its abstraction) needs
some workspace -- amount of memory to store temporary results etc. A stack was
considered a suitable data structure for such purposes. Class
\texttt{ValueStack} stands for a stack of \texttt{Value} objects used by
particular \texttt{ICmd} implementations. The whole virtual machine is
represented by value type (structure\footnote{The only difference between class
and structure is the default visibility from the C++ compiler's perspective.
Therefore it has been called as class first to not frighten the reader.} in C++
terminology) \texttt{Vm}. Its fundamental members are:
\begin{itemize}
 \item \texttt{glVars} - container for global variables
 \item \texttt{fncSet} - container for function declaration and definitions
 \item \texttt{vmStack} - object of type \texttt{ValueStack} (mentioned above)
\end{itemize}
 
\section{Builder}
Up to now it has been explained how does virtual machine works. There has been
nothing told about construction of virtual machine equivalent to interpreted
\texttt{VYP08} program yet. This is builder's responsibility.
 
Instance of builder is created by factory \texttt{BuilderFactory}. Builder
implements the \texttt{IBuilder} interface (mentioned above) defined by parser.
Each particular method implementing \texttt{IBuilder} interface builds a part
of virtual machine corresponding to the event fired by parser. In the builder's
public interface is one more factory class -- \texttt{FncFactory} which creates
the built-in function's declarations/definitions during virtual machine
initialization.
 
\begin{figure}[p]
  \begin{center}\includegraphics[scale=0.5]{img/cgParser.png}\end{center}
  \caption{Collaboration graph of class \tt{Parser}}\label{cgParser}
\end{figure}
Collaboration diagram \ref{cgParser} of class \texttt{Parser} shows the object
model being used during the build of virtual machine. Parser uses instance of
scanner object to read input and instance of builder object to build virtual
machine equivalent to input program in \texttt{VYP08} language.
 
Factory class \texttt{CmdFactory} belongs to module cmd mentioned above and is
used by~builder to obtain \texttt{ICmd} implementations which perform requested
action in the run time. The \texttt{ICmd} objects are put to appropriate
\texttt{CmdList} object which represents a block of commands in the input
\texttt{VYP08} program -- either function body or part of
\texttt{if}/\texttt{while} statement. The appropriate \texttt{CmdList} object is
always the top of \textit{block stack} which is maintained by builder. The
static type checking is based on \textit{type stack} which is maintained by
builder as well.
 
\newpage
\section{Summary}
Diagram \ref{md} shows relations between modules. Note these dependencies are
between mo\-dule's implementations. Looking at module's public interfaces there
are almost no dependencies between them.
\begin{figure}[h]
  \begin{center}\includegraphics[scale=0.5]{img/modules.png}\end{center}
  \caption{Modules dependency graph}\label{md}
\end{figure}
 
 
\chapter{Implementation}\label{implementation}
\texttt{vyp08} is written in the C++ language. Not counting FLEX/Bison it
depends on \textit{Boost}\footnote{available at \href{http://www.boost.org/}{
http://www.boost.org/ } } libra\-ries. The library called \texttt{smart\_ptr}
provides various types of smart pointers \cite{boost-smart-ptr}. Template
\texttt{shared\_ptr} from this library is used instead of native C++ pointer in
certain places in the \texttt{vyp08} code. \texttt{shared\_ptr} behaves as
native C++ pointer, but in addition it counts references to pointed object and
destroy the object automatically when the references count became zero.
 
Each module includes header \texttt{config.h} which consolidates various
compile-time configu\-ration options. Some diagnostic messages can be turned
on/off within this file. In the \texttt{config.h} are also defined conditional
macros as wrappers around some STL and Boost containers to work better with
Doxygen.
 
\section{Build from sources}
Build of \texttt{vyp08} from sources is based on
\textit{CMake}\footnote{available at
\href{http://www.cmake.org/}{http://www.cmake.org/}} (the cross-platform,
open-source build system). CMake checks availability of Flex/Bison utilities and
required Boost libraries. It can also scan dependencies of compiled
modules and automatically generate Makefile for the project.
 
By default \texttt{vyp08} uses colorized console output for \texttt{stderr}.
You can switch it off by changing value of \texttt{CONSOLE\_COLOR\_OUTPUT} macro
to zero in \texttt{config.h} (mentioned above) before build -- this is an
compile-time\footnote{Implementing this as run-time option is a trivial change
but it violates with task description as there can be no more command-line
arguments.} option.
 
For successful build you need Flex, Bison, Boost and CMake. To build project
from sources just type \texttt{make} in the project directory. You can also
build this documentation (requires \LaTeX) and API documentation (requires
Doxygen). To do so, type \texttt{make doc}.
 
\section{Test suite}
After successful build it is recommended to run the test suit distributed with
compiler. It checks if \texttt{vyp08} works as expected. This is very useful in
case of some future changes (e.g. bug fixes) to avoid regression. The test suit
consists of 40 tests.
 
The first two are unit tests for scanner and parser
modules. Both of them can be run in manual mode in case of debugging. The manual
mode can be initiated by passing `\texttt{-}' as the command-line argument to
the test binary. Then it reads the \texttt{VYP08} code from standard input and
writes corresponding lexical (in case of scanner) or syntactical (in case of
parser) units to standard output.
 
Remaining 38 tests work with the \texttt{vyp08} binary. Each test gives a
piece of \texttt{VYP08} (valid or invalid) code to \texttt{vyp08} to execute.
If the test requires some input, the test gives it to compiler's input. Then
the test checks the exit code of \texttt{vyp08} and (optionally) its
output with the expected one.
 
To run this test suite type \texttt{make check} in the project directory. If it
succeeds, exit code is zero. If not, there are some additional information in
the build directory.
 
\chapter{Conclusion}\label{conclusion}
Implemented compiler and interpreter \texttt{vyp08} works as it was requested.
You can test it on the test suite distributed with the project or you can try
the compiler with your own programs in \texttt{VYP08} language. The task was
accomplished.
 
There is no doubt that \texttt{VYP08} language is completely useless. The goal
of this project is not to define a new revolutionary programming language.
Instead of that, the work shows benefits of Flex/Bison usage for development
of compilers like \texttt{vyp08}.
 
In chapter \ref{design} are presented generic and reusable compiler modules as
the main goal of the project. This main goal has been reached and these modules
can be used (with minimal modifications) in development of similar compilers.
For example the module of scanner has been already used in another
project\footnote{The scanner module was used in a robot simulator which is
coming soon...}, even before the first release of \texttt{vyp08}. Source codes
of \texttt{vyp08} are covered by a free license -- hopefully it will help to use
these modules somewhere.
 
% ----------------------------------------------
% Bibliography
\bibliographystyle{abbrv} % FIXME
\begin{flushleft}
\bibliography{vyp08}
\end{flushleft}
 
%\appendix
%\chapter{Example of VYP08 code}
\end{document}