CS 4980 CC: Assignment 1

The goal of this assignment is to give you experience writing a simple recursive descent parser and expression evaluator.

The C++ program simple-expr-recognizer.cpp reads integer expressions over + and * from standard input and prints whether or not it is acceptable to standard output. A slightly more sophisticated version is expr.cpp; this version accepts its input as command-line arguments and prints the result to standard output.

Your task is to rewrite simple-expr-recognizer.cpp in Java so it supports simple boolean expressions. In particular

1. Rewrite simple-expr-recognizer.cpp (as is) in Java. You can introduce a class for your tokenizer if you find it convenient, or you can just have an array and index as done in the C++ version. Use your login name as the package name (with no "org" or "msoe" stuff).
2. Revise your code to handle boolean expressions over &&, ||, and ! with ! having the highest precedence and && having higher precedence than ||.
3. Use true and false as your constants (no numbers).
4. That is, the grammar you support will be

           OrExpr → AndExpr
           OrExpr → AndExpr '||' OrExpr
           AndExpr → NotExpr
           AndExpr → NotExpr '&&' AndExpr
           NotExpr → SimpleExpr
           NotExpr → '!' SimpleExpr
           SimpleExpr → 'true'
           SimpleExpr → 'false'
           SimpleExpr → '(' OrExpr ')'
   

   where the start symbol is OrExpr.
5. Your solution must read the expression from standard input (System.in) and write the result to standard output (System.out).
6. The output will be one of the following:
   • legal, meaning the input is legal according to the above grammar
   • illegal token xxx, meaning there is an illegal token in the input such as & (since only double &'s are legal) or +
   • expecting xxx when the parser is given one token but expecting another

Some sample runs:

        $ java BoolExpr.java
        expression: true && false || true
        accepted
        $ java BoolExpr.java
        expression: true && ( ! false || true
        expected )
        $ java BoolExpr.java
        expression: true && ! ( false || true )
        accepted

A key to this assignment is to not get mired down in details about breaking the input into separate tokens. Assume every token is separated by some whitespace from the other tokens. You can assume all input is on a single line (and maybe use .split to break it into separate tokens) or just read word by word until you reach end of file. This assignment is about the recursive descent parser, not fancy footwork recognizing tokens. The test data will be on a single line with one or more spaces between each token.

Submission

Check that your implementation meets the coding standards in the syllabus. Key things to watch for are not using hard tabs and making sure your name is in the source file. Then submit your solution to https://esubmit.msoe.edu/. Brief notes on using esubmit:

• Log in using your campus username (email without the @msoe.edu part) and standard password.
• Click on as1rd for the course, cs4980cc-h.
• You can have more than one file. Use Browse... to navigate to whatever file contains your main.
• You can click Add file once for each other file, or you can click Add file just one time and then use shift-select to select all files (including your "main" file - esubmit will work it out).
• Click on Submit to get esubmit to compile and run your code on the test cases. If the Test Results section shows errors, correct your code. For this lab I will ignore extraneous output, but you should print "accepted" or the specified error message as appropriate. You can click on individual tests to see the input; all tests are available in as1-tests.zip.