Homework #8

Assigned: December 1
Due: December 10, 11:59pm


(32+32+7=71 points) Build an interpreter and compiler to C++ for the language BOOLexp.

BOOLexp programs are defined by the following BNF (not EBNF) grammar:

    <sentence> ::= (<declarations>, <expr>)
<declarations> ::= []
<declarations> ::= [<varlist>]
     <varlist> ::= <var>
     <varlist> ::= <var>, <varlist>
        <expr> ::= <expr> & <expr>
        <expr> ::= <expr> | <expr>
        <expr> ::= ~ <expr>
        <expr> ::= <literal>
     <literal> ::= t
     <literal> ::= f
        <expr> ::= <var>
         <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 a the variable list is assumed to be false. 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. 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. All input expressions will be syntactically valid.


  1. Use flex and bison to develop your system (interpreter and compiler).
  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.
  3. 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 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. The C++ programs you compile to must compile on our system with g++ without errros or warnings.
  5. Develop a Makefile which builds your system (interpreter and compiler). Your Makefile must include target directives for every derived file produced during the compilation process (i.e., each program, each object file, and any other intermediate files produced during code generation and compilation). Make sure that each directive also lists all files on which the derived file depends in its dependency list. Also, your Makefile must be written so carries out only the commands necessary to bring any produced file up-to-date. Your Makefile must do just enough, but no extra, work to bring the final executable for your system up-to-date every time make is invoked. In addition, it must have an all directive and a clean directive to remove all generated files. Use variables where appropriate in your Makefile to improve its readability.
  6. Your Makefile must bring everything up-to-date, using only flex, bison, and gcc without any warnings or errors, when make is invoked on our system.

Sample test data

Sample standard input and standard output. A sample test session is available here. These test cases are not exhaustive.

How to submit

Note: All directory and filenames below are case-sensitive. You must use the directory and filenames exactly as shown below (i.e., all lower case).

Prepare your submission file as /home/<logname>/homeworks/hw8/hw8.tar, where <logname> is your login name (e.g., cps444-n1.19). This archive must contain only the most minimal set of files necessary to build your system from scratch. Only the file /home/<logname>/homeworks/hw8/hw8.tar will be electronically collected from your account on the deadline.

Failure to follow these submission requirements will result in a 10% penalty.


Ninety percent of your score will come from correctness and 10% of your score will come from following our programming style guide. Applicable submission penalties will then be applied.

Return Home