<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
<html><head><meta http-equiv="Content-Type" content="text/html;charset=UTF-8">
<title>Flex Bison C++ Example: Main Page</title>
<link href="tabs.css" rel="stylesheet" type="text/css">
<link href="doxygen.css" rel="stylesheet" type="text/css">
</head><body>
<!-- Generated by Doxygen 1.5.9 -->
<div class="navigation" id="top">
<div class="tabs">
<ul>
<li class="current"><a href="index.html"><span>Main Page</span></a></li>
<li><a href="namespaces.html"><span>Namespaces</span></a></li>
<li><a href="annotated.html"><span>Classes</span></a></li>
<li><a href="files.html"><span>Files</span></a></li>
</ul>
</div>
</div>
<div class="contents">
<h1>Flex Bison C++ Example Documentation</h1>
<p>
<h3 align="center">0.1.4 </h3><h2><a class="anchor" name="sec_summary">
Summary</a></h2>
This example shows how to use both <a href="http://flex.sourceforge.net/">Flex</a> and <a href="http://www.gnu.org/software/bison/">Bison</a> in C++ mode. This way both lexer and parser code and data is encapsulated into classes. Thus the lexer and parser are fully re-entrant, because all state variables are contained in the class objects. Furthermore multiple different lexer-parser pairs can easily be linked into one binary, because they have different class names and/or are located in a different namespace.<h2><a class="anchor" name="sec_website_license">
Website / License</a></h2>
The current example package can be downloaded from <a href="http://idlebox.net/2007/flex-bison-cpp-example/">http://idlebox.net/2007/flex-bison-cpp-example/</a><p>
The following just mean you can copy the example code into your program or use it for whatever purpose without crediting me (though I would really like it if you did):<p>
The parts of the example code written by myself are released into the public domain or, at your option, under the <a href="http://sam.zoy.org/wtfpl/">Do What The Fuck You Want To Public License (WTFPL)</a>, which can be found in the file COPYING. There are some special GPL license exceptions for the included source files from the Bison and Flex distributions.<p>
The idea and method of this example is based on code from <a href="http://ioctl.org/jan/bison/">http://ioctl.org/jan/bison/</a><h2><a class="anchor" name="sec_whyuse">
Why Use These Old Tools?</a></h2>
Well, they are here to stay and they work well. These days there are much more sophisticated C++ parser generation frameworks around:<p>
<ul>
<li>Most well-known is the <a href="http://spirit.sourceforge.net">Boost.Spirit parser framework</a> </li>
<li>and the <a href="http://www.antlr.org">ANTLR parser generator</a>. </li>
<li>Less well known is the <a href="http://cttl.sourceforge.net/">Common Text Transformation Library</a>.</li>
</ul>
All these libraries do good jobs when you need to generate parsers for more difficult grammars.<p>
However if you write a program with one of the frameworks above, then your users need that parser framework installed to compile your program. But <b>Flex and Bison require no compile-time dependencies</b>, because they generate fully autonomous source code. (And Flex and Bison are installed almost everywhere.) So far I have not found any modern parser generator which outputs independent code.<p>
It is even possible to compile the generated source with Visual C++ on Windows (worked with 8.0 aka 2005). Flex and Bison need not be installed on the windows machine. The source package includes a VC++ solution and two project files.<h2><a class="anchor" name="sec_source_files">
Source and Generated Files</a></h2>
The src directory contains the following source files. Note that some of them are automatically generated from others.<p>
<ul>
<li><a class="el" href="scanner_8ll.html" title="Define the example Flex lexical scanner.">scanner.ll</a> contains the Flex source for the C++ lexical scanner. </li>
<li><a class="el" href="scanner_8cc.html">scanner.cc</a> is generated from <a class="el" href="scanner_8ll.html" title="Define the example Flex lexical scanner.">scanner.ll</a> by Flex. </li>
<li><a class="el" href="scanner_8h.html">scanner.h</a> defines the lexer class <a class="el" href="classexample_1_1Scanner.html" title="Scanner is a derived class to add some extra function to the scanner class.">example::Scanner</a>. </li>
<li><a class="el" href="FlexLexer_8h.html">FlexLexer.h</a> copied from Flex distribution. Defines the abstract lexer class.</li>
</ul>
<ul>
<li><a class="el" href="parser_8yy.html" title="Contains the example Bison parser source.">parser.yy</a> is the example Bison parser grammar. </li>
<li><a class="el" href="parser_8cc.html">parser.cc</a> generated from <a class="el" href="parser_8yy.html" title="Contains the example Bison parser source.">parser.yy</a> by Bison. </li>
<li><a class="el" href="parser_8h.html">parser.h</a> generated from <a class="el" href="parser_8yy.html" title="Contains the example Bison parser source.">parser.yy</a> by Bison. </li>
<li><a class="el" href="y_8tab_8h.html" title="Forwarding include file to parser.h (actually by including scanner.h).">y.tab.h</a> contains nothing. Just forwards to <a class="el" href="parser_8h.html">parser.h</a></li>
</ul>
<ul>
<li><a class="el" href="location_8hh.html" title="Define the example::location class.">location.hh</a> installed by Bison. Contains something required by the parser class. </li>
<li><a class="el" href="position_8hh.html" title="Define the example::position class.">position.hh</a> same. </li>
<li><a class="el" href="stack_8hh.html">stack.hh</a> same.</li>
</ul>
<ul>
<li><a class="el" href="driver_8h.html" title="Declaration of the example::Driver class.">driver.h</a> defines the <a class="el" href="classexample_1_1Driver.html" title="The Driver class brings together all components.">example::Driver</a> class, which puts together lexer and parser. </li>
<li><a class="el" href="driver_8cc.html" title="Implementation of the example::Driver class.">driver.cc</a> implementation for <a class="el" href="driver_8h.html" title="Declaration of the example::Driver class.">driver.h</a></li>
</ul>
<ul>
<li><a class="el" href="expression_8h.html" title="Implements an example calculator class group.">expression.h</a> defines the example's calculator node classes. </li>
<li><a class="el" href="exprtest_8cc.html">exprtest.cc</a> contains a main function to run the example calculator.</li>
</ul>
<ul>
<li><a class="el" href="readme_8dox.html" title="Contains main doxygen example explanation page.">readme.dox</a> doxygen explanation text, which you are reading right now.</li>
</ul>
So if you wish to create a program using a C++ Flex lexer and Bison parser, you need to copy the following files: <ul>
<li><a class="el" href="scanner_8ll.html" title="Define the example Flex lexical scanner.">scanner.ll</a>, <a class="el" href="scanner_8h.html">scanner.h</a>, <a class="el" href="FlexLexer_8h.html">FlexLexer.h</a> </li>
<li><a class="el" href="parser_8yy.html" title="Contains the example Bison parser source.">parser.yy</a>, <a class="el" href="y_8tab_8h.html" title="Forwarding include file to parser.h (actually by including scanner.h).">y.tab.h</a> </li>
<li><a class="el" href="location_8hh.html" title="Define the example::location class.">location.hh</a>, <a class="el" href="position_8hh.html" title="Define the example::position class.">position.hh</a>, <a class="el" href="stack_8hh.html">stack.hh</a> (are created by Bison when run on the grammar) </li>
<li><a class="el" href="driver_8h.html" title="Declaration of the example::Driver class.">driver.h</a>, <a class="el" href="driver_8cc.html" title="Implementation of the example::Driver class.">driver.cc</a></li>
</ul>
<h3><a class="anchor" name="subsec_namespacelibrary">
Namespace and Library</a></h3>
The scanner, parser and driver classes are located within the <a class="el" href="namespaceexample.html" title="The example namespace is used to encapsulate the three parser classes example::Parser...">example</a> namespace. When coding a larger program, I believe it is most convenient to put all scanner/parser source files into a separate directory and build a static library. Then all parts of the parser are located in a separate namespace and directory.<h2><a class="anchor" name="sec_overview">
Code Overview</a></h2>
This is a brief overview of the code's structure. Further detailed information is contained in the doxygen documentation, comments in the source and ultimately in the code itself.<h3><a class="anchor" name="subsec_overview_scanner">
Scanner</a></h3>
The input stream is first converted by the lexical scanner into tokens. The scanner is defined by the list of regular expressions in <a class="el" href="scanner_8ll.html" title="Define the example Flex lexical scanner.">scanner.ll</a> . From this file Flex generates the file <a class="el" href="scanner_8cc.html">scanner.cc</a>, which mainly contains a function called <a class="el" href="parser_8cc.html#5611300548b2030d86b6ab9168132b88">yylex()</a>. This function returns the next token for the parser. For a C++ scanner the <a class="el" href="parser_8cc.html#5611300548b2030d86b6ab9168132b88">yylex()</a> function is contained in a class, which is named yyFlexLexer by default. It is declared in the <a class="el" href="FlexLexer_8h.html">FlexLexer.h</a> and is derived from the abstract <a class="el" href="classFlexLexer.html">FlexLexer</a> class.<p>
By defining the macro yyFlexLexer => <a class="el" href="classExampleFlexLexer.html">ExampleFlexLexer</a> in <a class="el" href="scanner_8h.html">scanner.h</a>, the default name of the scanner class is changed. Furthermore to extend <a class="el" href="parser_8cc.html#5611300548b2030d86b6ab9168132b88">yylex()</a>'s parameter list, the class <a class="el" href="classexample_1_1Scanner.html" title="Scanner is a derived class to add some extra function to the scanner class.">example::Scanner</a> is derived from the <a class="el" href="classExampleFlexLexer.html">ExampleFlexLexer</a> class. It is mainly a forwarding class. By defining the macro YY_DECL, the <a class="el" href="parser_8cc.html#5611300548b2030d86b6ab9168132b88">yylex()</a> function generated by Flex is renamed to <a class="el" href="classexample_1_1Scanner.html#60e1b0f8a420164e464823b8578d6d7d" title="This is the main lexing function.">example::Scanner::lex()</a>.<p>
Another change to the default Flex code is that the token type is changed from <code>int</code> to the enum <a class="el" href="structexample_1_1Parser_1_1token.html" title="Tokens.">example::Parser::token</a> defined by parser.<h3><a class="anchor" name="subsec_overview_parser">
Parser</a></h3>
Bison's support for C++ is much more sophisticated. In C++ mode it generates a class named <a class="el" href="classexample_1_1Parser.html" title="A Bison parser.">example::Parser</a>, which is located in <a class="el" href="parser_8cc.html">parser.cc</a> and declared in <a class="el" href="parser_8h.html">parser.h</a> . The header file also defines the scanner tokens, which must be returned by the Flex scanner's regular expression rules. Bison's C++ skeleton also installs the three .hh files, which contain utility classes required by the parser.<p>
In the example calculator the Bison code constructs a calculation node tree. The tree's nodes are derived from <a class="el" href="classCalcNode.html" title="CalcNode is the abstract base class for calculation nodes.">CalcNode</a> and are evaluated to output the parsed expression's result.<h3><a class="anchor" name="subsec_overview_driver">
Driver</a></h3>
The <a class="el" href="classexample_1_1Driver.html" title="The Driver class brings together all components.">example::Driver</a> class brings the two components scanner and parser classes together. It is the context parameter of the parser class. The hook between scanner object and parser object is done by defining the <a class="el" href="parser_8cc.html#5611300548b2030d86b6ab9168132b88">yylex()</a> macro to be "driver.lexer->lex". This way the Bison parser requests the next token from the scanner object contained within the driver.<p>
The <a class="el" href="classexample_1_1Driver.html" title="The Driver class brings together all components.">example::Driver</a> object can be accessed by the Bison actions. Therefore it will contain a reference to the data classes filled by the parser's rules. In the example it contains a reference to the <a class="el" href="classCalcContext.html" title="Calculator context used to save the parsed expressions.">CalcContext</a>. Thus a refernce to a <a class="el" href="classCalcContext.html" title="Calculator context used to save the parsed expressions.">CalcContext</a> must be given to the constructor of <a class="el" href="classexample_1_1Driver.html" title="The Driver class brings together all components.">example::Driver</a>. This <a class="el" href="classCalcContext.html" title="Calculator context used to save the parsed expressions.">CalcContext</a> object will be filled with the parsed data.<p>
To initiate parsing the <a class="el" href="classexample_1_1Driver.html" title="The Driver class brings together all components.">example::Driver</a> class contains the three functions <a class="el" href="classexample_1_1Driver.html#a02195b250993e74acceb0fdd5e04414" title="Invoke the scanner and parser for a stream.">example::Driver::parse_stream()</a>, <a class="el" href="classexample_1_1Driver.html#ffea06783586d2253a4231e89cfd1ff7" title="Invoke the scanner and parser on a file.">example::Driver::parse_file()</a> and <a class="el" href="classexample_1_1Driver.html#34d3f98359759bd7dbec2ae9cf14ca6f" title="Invoke the scanner and parser on an input string.">example::Driver::parse_string()</a>.<h2><a class="anchor" name="sec_example">
Example Calculator</a></h2>
The example lexer and grammar is a simple floating point arithmetic calculator. It follows the usual operator precedence rules (sometimes called BODMAS or PEMDAS): Parentheses, Exponentation, Multiplication/Division, Addition/Subtraction.<p>
Besides these simple arithmetic operators, the program also supports variables. These can be assigned a value and used in subsequent expressions.<p>
It can be started interactively and will process expressions entered on the console. The expression's parse tree is printed and then evaluated. Here some examples:<p>
<pre class="fragment">
$ <span class="keywordflow">./exprtest</span>
Reading expressions from stdin
input: <span class="keywordflow">4 * 1.5 + 3 * (2 ^ 4 - 4)</span>
tree:
+ add
* multiply
4
1.5
* multiply
3
- subtract
^ power
2
4
4
evaluated: 42
input: <span class="keywordflow">v = (2 ^ 4 - 4)</span>
Setting variable v = 12
input: <span class="keywordflow">3.5 * a</span>
input:1.6: Unknown variable "a"
input: <span class="keywordflow">3.5 * v</span>
tree:
* multiply
3.5
12
evaluated: 42
input: <span class="keywordflow">5 + * 6</span>
input:1.4: syntax error, unexpected '*'
input: <span class="keywordflow">5 + (4 * 4</span>
input:1.10-9: syntax error, unexpected end of file, expecting ')'
</pre><p>
The exprtest can also be used to process text files containing expressions. Within the file each line is parsed as an expression. Multiple expressions can be put into one line by terminating them with a semicolon '<code>;</code>'. The exprtest outputs a parse tree for each parsed non-assignment line.<p>
<div class="fragment"><pre class="fragment">
v = (2 ^ 4 - 4); e = 2.71828
4 * 1.5 + 3 * v
6 * (2 * 2) ^ 2 / 2
</pre></div><p>
The above example file (included as <code>exprtest.txt</code>) can be processed by calling <code>./exprtest exprtest.txt</code>. The program outputs the following evaluation:<p>
<div class="fragment"><pre class="fragment">
Setting variable v = 12
Setting variable e = 2.71828
Expressions:
[0]:
tree:
+ add
* multiply
4
1.5
* multiply
3
12
evaluated: 42
[1]:
tree:
/ divide
* multiply
6
^ power
* multiply
2
2
2
2
evaluated: 48
</pre></div><p>
<dl class="author" compact><dt><b>Author:</b></dt><dd>Timo Bingmann </dd></dl>
<dl class="date" compact><dt><b>Date:</b></dt><dd>2007-08-20 </dd></dl>
</div>
<hr size="1"><address style="text-align: right;"><small>Generated on Sat Sep 5 10:26:25 2009 for Flex Bison C++ Example by
<a href="http://www.doxygen.org/index.html">
<img src="doxygen.png" alt="doxygen" align="middle" border="0"></a> 1.5.9 </small></address>
</body>
</html>
