Build an interpreter and a compiler to C ++ for the language BOOLexp using flex and bison
vic
final.pdf
C O
N F ID
E N
T IA
L D
R A
F T10.5. PROGRAMMING PROJECT FOR CHAPTER 10 333
10.5 Programming Project for Chapter 10
Putting It All Together
Build an interpreter and a compiler to C++ for the language BOOLexp. BOOLexp programs are defined by the following context-free grammar in BNF (not EBNF):
<sentence> ::= ( <declarations> , <expr> )
<declarations> ::= [] <declarations> ::= [ <varlist> ]
<varlist> ::= <var>
<varlist> ::= <var> , <varlist> <expr> ::= <expr> & <expr>
<expr> ::= <expr> | <expr> <expr> ::= ∼ <expr>
<expr> ::= <literal> <expr> ::= <var>
<literal> ::= t
<literal> ::= f <var> ::= a . . . e <var> ::= g . . . s <var> ::= u . . . z
where t, f, |, &, and ∼ are terminals which represent true, false, or, and, and not, respectively, and all lower case letters except for f and t are ter- minals each representing a variable. Each variable in the variable list is bound to true in the expression. Any variable used in any expression not contained in the variable list is assumed to be false.
Factor your system into the following three components:
• Front End (i.e., a shift-reduce parser, automatically generated with flex and bison, which produces a parse tree)
• Interpreter (i.e., expression evaluator)
• Compiler (i.e., translator)
The general approach to this problem is to build a parse tree for each sentence and then implement two traversals of the tree: one traversal eval- uates the expression as it walks the tree (the interpreter component) and
C O
N F ID
E N
T IA
L D
R A
F T334 CHAPTER 10. AUTOMATIC PROGRAM GENERATION
the other generates C++ code as it walks the tree (the compiler compo- nent).
The following is sample input and output for the interpreter (i.e., ex- pression evaluator) (> is simply the prompt for input and will be the empty string in your system).
> ([], f | t & f | ~t)
((f | (t & f)) | (~t)) is false.
> ([p,q], ~t | p | ~e & ~f & t & ~q | r)
((((~t) | p) | ((((~e) & (~f)) & t) & (~q))) | r) is true.
Notice that when interpreting a BOOLexp program you must not only eval- uate the logical expression (the first element of the program pair) but also determine the order in which operators of it are evaluated and illustrate that order in the diagrammed output. Normal precedence rules hold: ∼ has the highest, & has the second highest, and | has the lowest. Assume left-to-right associativity. When compiling a BOOLexp program to C++ you must generate a C++ program with equivalent semantics as the BOOLexp program.
Requirements:
a) Use flex and bison to develop the front end of your system (i.e., scan- ner and parser, respectively).
b) Implement a -i option indicating to only interpret and a -c option in- dicating to only compile. If no command line options are given, then in- terpret and compile. Alternatively, generate two seperate executables: one for the interpreter and one for the compiler. Only the first approach is demonstrated below.
c) Your program must read from standard input and write to standard output. Specifically, your program must read a set of expressions from standard input (one per line) and write the corresponding parenthe- sized expressions (also one per line, in the format used above) to stan- dard output. When compiling, the compiled programs are written to files, rather than standard output.
d) Free all memory that you explicitly allocated from the heap. Specifi- cally, free the entire parse tree which means you must free each node,
C O
N F ID
E N
T IA
L D
R A
F T10.5. PROGRAMMING PROJECT FOR CHAPTER 10 335
and for internal (operator) nodes you must free the buffer which stores the pointers to its children, if used.
e) The C++ programs you compile to must compile with g++ without er- rors or warnings.
f) Write a Makefile that builds your system (interpreter and compiler) as indicated in Programming Exercise 10.5.18,
Sample Test Data
Sample standard input is available at http://perugini. cps.udayton.edu/teaching/books/SPUC/www/files/
boolexpstdin.txt and sample standard output is available at http://perugini.cps.udayton.edu/teaching/books/SPUC/
www/files/boolexpstdout.txt. A sample test session with boolexp on that data is available at http://perugini.cps.udayton.edu/ teaching/books/SPUC/www/files/boolexptestsession.txt. These test cases are not exhaustive. There is also a reference boolexp executable solution for this system available at http://perugini.cps. udayton.edu/teaching/books/SPUC/www/files/boolexp. This sample test data with the reference executable is bundled and available at http://perugini.cps.udayton.edu/teaching/books/SPUC/ www/files/boolexpdata.tar.
The following is sample input and output for the interpreter (only) (> is simply the prompt for input and will be the empty string in your system).
$ ./boolexp -i
> ([] , f | t & f | ~ t)
((f | (t & f)) | (~t)) is false.
> ([p], f | t & f | ~p)
((f | (t & f)) | (~p)) is false.
> ([] , f | t | f & t | f | t & t & t | ~ t)
(((((f | t) | (f & t)) | f) | ((t & t) & t)) | (~t)) is true.
> ([p, q], ~t | p | ~e & ~f & t & ~q | r)
((((~t) | p) | ((((~e) & (~f)) & t) & (~q))) | r) is true.
> ([] , t & f & t | ~ t & ~ f & ~ f | f & t & ~ t)
((((t & f) & t) | (((~t) & (~f)) & (~f))) | ((f & t) & (~t))) is false.
> ([] , t & f | t & f | t & f | f & ~ t | f)
(((((t & f) | (t & f)) | (t & f)) | (f & (~t))) | f) is false.
> ([], t & t & ~ f | f & ~ t | ~ t & f)
((((t & t) & (~f)) | (f & (~t))) | ((~t) & f)) is true.
> ([ ], t & t | ~ f & ~ f | t & f | ~ t)
C O
N F ID
E N
T IA
L D
R A
F T336 CHAPTER 10. AUTOMATIC PROGRAM GENERATION
((((t & t) | ((~f) & (~f))) | (t & f)) | (~t)) is true.
> ([a,b,c], a & ~ f & ~ f & b | ~ t | c)
(((((a & (~f)) & (~f)) & b) | (~t)) | c) is true.
> ([], t & ~ f & ~ t | ~ f & ~ t & t)
(((t & (~f)) & (~t)) | (((~f) & (~t)) & t)) is false.
> ([], t & ~ f | t & ~ f)
((t & (~f)) | (t & (~f))) is true.
> ([], t | f | t & f | t | ~ t & t | f)
(((((t | f) | (t & f)) | t) | ((~t) & t)) | f) is true.
> ([], ~ f & t & ~ t | ~ f | t & ~ f)
(((((~f) & t) & (~t)) | (~f)) | (t & (~f))) is true.
> ([],~ t | ~ f | ~ t & ~ f & f & ~ t)
(((~t) | (~f)) | ((((~t) & (~f)) & f) & (~t))) is true.
> ([x,y], ~x | t | ~z & ~f & y & ~y | f)
((((~x) | t) | ((((~z) & (~f)) & y) & (~y))) | f) is true.
> ([],~t|~f&~t|~t&~f|~t&~t)
((((~t) | ((~f) & (~t))) | ((~t) & (~f))) | ((~t) & (~t))) is false.
> ^D
$
The following is a sample interactive test session for the system (inter- preter and compiler):
$ ./boolexp
> ([p, q], ~t | p | ~e & ~f & t & ~q | r)
((((~t) | p) | ((((~e) & (~f)) & t) & (~q))) | r) is true.
> ([] , t & f & t | ~ t & ~ f & ~ f | f & t & ~ t)
((((t & f) & t) | (((~t) & (~f)) & (~f))) | ((f & t) & (~t))) is false.
> ([] , t & f | t & f | t & f | f & ~ t | f)
(((((t & f) | (t & f)) | (t & f)) | (f & (~t))) | f) is false.
> ([], t & t & ~ f | f & ~ t | ~ t & f)
((((t & t) & (~f)) | (f & (~t))) | ((~t) & f)) is true.
^D
$
$ cat 1.cpp
#include<iostream>
using namespace std;
main() {
bool p = true;
bool q = true;
bool e = false;
bool r = false;
C O
N F ID
E N
T IA
L D
R A
F T10.5. PROGRAMMING PROJECT FOR CHAPTER 10 337
bool result = !true || p || !e && !false & true && !q || r;
cout << "The result is ";
if (result)
cout << "true";
else
cout << "false";
cout << "." << endl;
}
$
$ cat 4.cpp
#include<iostream>
using namespace std;
main() {
bool result = true && true && !false || false && !true || !true & false;
cout << "The result is ";
if (result)
cout << "true";
else
cout << "false";
cout << "." << endl;
}
$
$ ./boolexp
> ([ ], t & t | ~ f & ~ f | t & f | ~ t)
((((t & t) | ((~f) & (~f))) | (t & f)) | (~t)) is true.
> ([a,b,c], a & ~ f & ~ f & b | ~ t | c)
(((((a & (~f)) & (~f)) & b) | (~t)) | c) is true.
> ([], t & ~ f & ~ t | ~ f & ~ t & t)
(((t & (~f)) & (~t)) | (((~f) & (~t)) & t)) is false.
> ([], t & ~ f | t & ~ f)
((t & (~f)) | (t & (~f))) is true.
> ([], t | f | t & f | t | ~ t & t | f)
(((((t | f) | (t & f)) | t) | ((~t) & t)) | f) is true.
> ([], ~ f & t & ~ t | ~ f | t & ~ f)
(((((~f) & t) & (~t)) | (~f)) | (t & (~f))) is true.
> ([],~ t | ~ f | ~ t & ~ f & f & ~ t)
C O
N F ID
E N
T IA
L D
R A
F T338 CHAPTER 10. AUTOMATIC PROGRAM GENERATION
(((~t) | (~f)) | ((((~t) & (~f)) & f) & (~t))) is true.
^D
$
$ ./boolexp -c
> ([x,y], ~x | t | ~z & ~f & y & ~y | f)
$
$ ./boolexp -ci
> ([],~t|~f&~t|~t&~f|~t&~t)
((((~t) | ((~f) & (~t))) | ((~t) & (~f))) | ((~t) & (~t))) is false.
^D
$
$ cat 1.cpp
#include<iostream>
using namespace std;
main() {
bool result = !true || !false && !true || !true && !false || !true && !true;
cout << "The result is ";
if (result)
cout << "true";
else
cout << "false";
cout << "." << endl;
}
10.6 Thematic Take-Aways
10.7 Chapter Summary
10.8 Key Terms
10.9 Bibliographic Notes
