Homework IX

BNF Processing (100 points)

For this project you will modify and extend the Prolog program in the file Prolog/exprCompiler in our class directory, and discussed in class. You are to extend the BNF in conjunction with modifications to the parse and compile predicates in the expression compiler. These changes should accomplish the following extension:

* Add BNF for conditional expressions of the form (Java syntax)

E1 ? E2 : E3

where E2, and E3 are other (unrestricted) expressions, possibly including conditional expressions, and E1 is an unconditional (but possibly compound) expression. Conditional expressions should be allowed at any point if they are parenthesized. The evaluation result of a conditional expression is the value of either E2 or E3, depending on whether the value of E1 is non-zero or zero, respectively (i.e., non-zero means true, zero means false). The expression connectors '?' and ':' should have precedence lower than all other operations, so that, for instance, a?b:c+d "means" a?b:(c+d), not (a?b:c)+d.

* Add/modify the code for parse and compile predicates to correctly process these additional forms of expression.

This project utilizes a simple single-register (virtual) computer with the following single-address instructions (which for convenience we write in Prolog term notation):

ld(addr) -- load the contents of memory location addr into the arithmetic register (or accumulator)

sto(addr) -- store the contents of the arithmetic register into the memory location addr

add(addr) -- add the contents of the memory location addr to that of the arithmetic register

sub(addr) -- subtract the contents of the memory location addr from that of the arithmetic register

mul(addr) -- multiply the contents of the arithmetic register by the contents of the memory location addr

div(addr) -- divide the contents of the arithmetic register by the contents of the memory location addr

noop -- no-op operation, the computation continues without change

br(index) -- transfer control to the instruction 'index'(an integer) steps forward from this one

brz(index) -- if the content of the arithmetic register is zero, transfer control to the instruction 'index'(an integer) steps forward from this one; otherwise execute the next sequential instruction .

For memory "addresses" or locations, we allow symbolic identifiers from the expression grammar (i.e., variable identifiers), plus "internal" identifiers temp1, temp2, ... for temporary working storage locations generated in compilation, or positive integers in the branch instructions. The above instructions are all already implemented in the virtual machine defined by the 'execute' predicate which should require no changes.

In order to 'execute' the compiled pseudo-code for an expression (i.e., evaluate it), values must be provided for each of the variables that occur in the expression. These are supplied separately in an "environment" argument -- simply a list of pairs associating a numerical value with each identifier; this is the RAM for our virtual machine. For instance,

?- evaluate("a+b?a*b:c-b", [(a,2), (b,-2), (c,3)], Ans).

should succeed with Ans=5.

Submission instructions

Clearly identify the code and BNF additions and changes that you make. You need to justify that the BNF you devise for the new expressions is suitable. Then justify that your code revisions accomplish the required processing.

Solutions must include documentation (comments/write-up) that makes it clear both what your strategy is, and how the details of the program accomplish that strategy. You need to run test cases that exercise every component of your code. You should illustrate expressions using the conditional construction in diverse contexts. You may use any other predicates that are pre-defined, included in our class directory, or auxiliary predicates you define yourself (you are responsible for testing only the code you create).

It is not the grader’s responsibility to figure out your code and whether it is correct — it is your responsibility to explain your code and convince the grader it is completely tested and correct. Include documentation that justifies that your test data meets these conditions. Full credit will not be awarded, even for (apparently) correct programs, without completing all these requirements.

In addition to submitting a printout showing documentation, source code, and test outcomes, you should use the 'submit' command to provide an electronic copy of your source code. Send it to the directory Hwk9 (for course c111).