Files

No distribution for this project. You'll need to build your own JFlex file, along with your parser class and a test driver class.

Set Up

Use Eclipse for this if you must, but unlike the previous assignment (and all of the ones after this), I recommend that you run JFlex to generate your lexer class from the command line (otherwise, you'll also have to write your own build.xml file and figure out Ant task syntax!). Let's assume that your JFlex file is called exp.flex, and that you have JFlex installed in the directory ~/developer. From the src directory of your project, you can generate your lexer file with the command

java -jar ~/developer/jflex-1.6.1.jar exp.flex 

Your Job

We begin by considering our grammar for simple arithmetic expressions, now with an additional exponentiation operator, ^. This operator has higher precedence than any of *, /, +., or -, and it is right associative: for example, 2 ^ 3 ^ 4 should be read as 234 = 281, rather than (23)4 = 212. The other four operators are left associative, with multiplication and division having higher precedence than addition and subtraction.

    E   -->  <int_const> | E + E | E - E | E * E | E / E | E ^ E | (E)

Factoring this to express both precedence and associativity (and eliminate ambiguity), we get

    E   -->   E + T | E - T | T
    T   -->   T * F | T / F | F
    F   -->   F2 ^ F | F2
    F2  -->   <int_const> | (E)

Sadly, this still gives us a grammar that cannot be implement by recursive descent, since it is left recursive. After transforming once more to remove all left recursion, we get

    E      -->   T ERest
    ERest  -->  + T ERest | - T ERest | <empty>
    T      -->   F TRest
    TRest  --> * F TRest | / F  TRest | <empty>
    F      -->   F2 ^ F | F2
    F2     -->   <int_const> | (E)

Implement a recursive descent parser for arithmetic expressions, according to this grammar (after one more repair: see below). To do this, you'll construct four files:

  1. A JFlex file, which defines the tokens for this language. This is fairly easy, as you can follow much of the structure of your work in Lab 1. You'll want to include a peek() method, in order to implement token matching in the parser. You can use this:

        public Symbol peek() throws java.io.IOException {
            Symbol sym = this.next_token();
    
            yypushback(yylength());
            return sym;
        }
    
  2. A Symbol class, containing symbolic constants for all 9 possible tokens (counting the EOF marker).
  3. The parser class.

  4. A test driver, with a main method that prompts for expressions, parses them, and reprots whether or not they are syntactically valid. Note that you do not need to calculate the values of these expressions, transform them to postfix form, or any other semantic manipulation.

One caveat: The final grammar given above is free of left recursion, but it is still not enough for a recursive descent parser. Explain why not, and repair the grammar appropriately (this will be discussed in Friday's class).

Turn In:

John H. E. Lasseter