Homework Assignment 3

  1. Explain the difference between the task performed by a lexical analyzer and the task performed by a parser.

  2. Consider the following grammar discussed in class:
    Exp -> Exp + Exp | Exp * Exp | ( Exp ) 
        |  - Exp | id | num
    Using this grammar (a) write a derivation for the string "(A + C) * (8 + B + -(B + C))", and (b) show the parse tree for your derivation. Assume that * has precedence over + and that all operators are left associative.

  3. Write a context free grammar that specifies the syntax for C functions. For the statements that go into the function body it is fine to go no deeper than individual statements. In other words, you may assume that stmt is a terminal symbol that does not have to be expanded further into assignment statements, function calls, control constructs, etc. You do have to specify that it is ok to have zero or more statements in the function body and that a statement may be a block of statements enclosed in {}'s. For this assignment allowable return and parameter types are int, char, float, pointer versions of these three types, struct id, and struct id *. C functions have the form:
    type name (type param1, type param2, ..., type param n) body

  4. Scott #2.10 a

  5. Write a JCup and JLex specification for the following grammar. You will need to modify your JLex specification from the previous homework but you should not need to modify it too much. An id is any string of one or more upper/lowercase letters and a num is any string of 1 or more digits. In other words, all nums are non-negative integers. You should recognize this grammar as roughly corresponding to the strings recognized by the expression tree problem in previous homeworks:
         Pgm -> (Stmt | Exp)*
         Stmt -> = id Exp
         Exp -> + Exp Exp | - Exp Exp | * Exp Exp | / Exp Exp
                id | num
    When your JCup specification recognizes a production it should print out the production. If you have a question about whether or not a string is valid or how your program should print productions, you can run the parser that I have written which is in ~cs365/www-home/hw/hw3. You will need to type the following two commands:
        setenv CLASSPATH .:..:/usr/local/lib/jar:/home/cs365/www-home/hw/
        java hw3.parser < inputfile
    where inputfile is the name of the file containing your strings. You can also run the parser interactively but be aware that it will not always completely parse the previous expression/statement until you type another one.

    Name your two files exp.cup and exp.lex and place these two files in a package named expparser.

What to Submit

Submit a jar file named hw3.jar. The jar file should contain the following files:

  1. hw3.txt: An ascii file that contains the answers to questions 1-3.
  2. exp.cup
  3. exp.lex
  4. the .class files for your lexer and parser.
  5. manifest.txt: It should list the Main-Class as expparser.parser.
Michael should be able to test your answer to question 4 by typing:
java -cp .:..:hw3.jar:/usr/local/lib/jar expparser.parser < inputfile