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> )

<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 terminals 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 evaluates the expression as it walks the tree (the interpreter component) and

CHAPTER 10. AUTOMATIC PROGRAM GENERATION

the other generates C++ code as it walks the tree (the compiler component).

The following is sample input and output for the interpreter (i.e., expression 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 evaluate 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:

1. Use flex and bison to develop the front end of your system (i.e., scanner and parser, respectively).
2. Implement a -i option indicating to only interpret and a -c option indicating to only compile. If no command line options are given, then interpret and compile. Alternatively, generate two seperate executables: one for the interpreter and one for the compiler. Only the first approach is demonstrated below.
3. Your program must read from standard input and write to standardoutput. Specifically, your program must read a set of expressions from standard input (one per line) and write the corresponding parenthesized expressions (also one per line, in the format used above) to standard output. When compiling, the compiled programs are written to files, rather than standard output.
4. Free all memory that you explicitly allocated from the heap. Specifi-cally, free the entire parse tree which means you must free each node,

10.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.

1. The C++ programs you compile to must compile with g++ without errors or warnings.
2. 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)

> ^D

$

preter and compiler): $ ./boolexp

> ([] , t & f

^D

$

$ cat 1.cpp #include<iostream> using namespace std; main() {

bool p = true; bool q = true;

bool e = false; bool r = false; if (result) cout << true;

else

cout << . << endl;

}

$

$ cat 4.cpp #include<iostream> using namespace std; main() { if (result) cout << true;

else

cout << . << endl;

}

$

$ ./boolexp

> ([

^D

$

$ ./boolexp -c

$

^D

$

$ cat 1.cpp #include<iostream> using namespace std; main() { if (result) cout << true;

else

cout << . << endl;

}

10.6

10.7

10.8

10.9