CS 5010: Problem Set 11

Out: Monday, 3 April 2017
Due: Monday, 10 April 2017 at 6pm
Corrected: Monday, 3 April 2017
Corrected: Tuesday, 4 April 2017:

This is a pair programming assignment. You are required to complete this problem set in collaboration with your assigned partner, but neither of you are allowed to discuss this problem set with any other person. You are also not allowed to search for or to view any solutions to similar problems that may be available on the World-Wide Web or in other resources that might otherwise have been available to you.

We have created a repository for you and your partner to use.

In those repositories, we have created files named ID1-log.txt and ID2-log.txt for you to use when filing work session reports, as in previous problem sets. You and your partner are required to push your files at the end of every work session. (You may push your files several times during a work session, but we do not require you to do so.)

At the end of every work session, you are required to update your log file to record the time you spent in that work session. (Please do not include the time you spent in any previous work sessions, as those times will already have been recorded in previous versions of your log file.) If both of you work together during a work session, both of you must update your log files, recording only the time you spent working. Do not include your partner's time in your log file, but be sure to push the updated versions of both log files.

In the first part of this problem set, you will define a Programs.main method that reads a ps11 program from a file specified on the command line, parses that program, and runs it on one or more inputs specified on the command line, printing the result computed by the program. That should make it easier for you to finish debugging the interpreter you wrote in Problem Set 10.

In the second part of this problem set, you will implement a simple static analysis: given the name of a file containing a ps11 program, return a set containing the names of all undefined variables that are referenced anywhere in the program.

You must use Java 8 for this assignment. All of your code must reside within the default package. You may use/import anything in the java.lang and java.util packages, and you may import the specific things imported by the Java files we are giving you as a hint, but you are not allowed to use any other packages.

Problem Specification

In Problem Set 10, you wrote an interpreter for a simple functional programming language.

For Problem Set 11, we are going to change the concrete syntax by making semicolon a separator rather than a terminator, and by eliminating the fi token that terminated if expressions in the concrete syntax given in Problem Set 10. For Problem Set 11, the concrete syntax is:

    <pgm>     ::=  <defn>
              ::=  <defn> ; <pgm>
    <defn>    ::=  <id> = <const>
              ::=  <id> (<formals>) <expr>
    <const>   ::=  true 
              ::=  false
              ::=  <int>
    <lambda>  ::=  (λ ( <formals> ) <expr>)
    <expr>    ::=  <const>
              ::=  <id>
              ::=  <lambda>
              ::=  <arith>
              ::=  <call>
              ::=  <if>
              ::=  ( <expr> )
    <arith>   ::=  <expr> <op> <expr>
    <call>    ::=  <expr> (<exprs>)
    <if>      ::=  if <expr> then <expr> else <expr>
    <op>      ::=  < | = | > | + | - | *
    <formals>  ::=  <id>
               ::=  <id> , <formals>
    <exprs>    ::=  <expr>
               ::=  <expr> , <exprs>
    <int> and <id> are described by regular expressions:
        digit digit*
        letter (letter | digit)*

That change to the concrete syntax should not affect any code code you wrote for Problem Set 10, because your interpreter used abstract syntax, which remains the same in Problem Set 11.

The concrete syntax we use will also allow comments, which start with the # character and extend through the end of the line.

The context-free grammar shown above is ambiguous, but it can be converted into an unambiguous grammar that generates the same set of programs. The unambiguous grammar we will use as the official concrete syntax is the LL(1) grammar given in the cfg.pg file within the set11parser directory we are giving you as a hint for part 1 of this problem set. That directory contains a README file that describes the files in that directory. You should read that README file before you start to work on this problem set.

If you did a good job on Problem Set 10, this problem set will be easy. If the interpreter you wrote for Problem Set 10 had problems, this problem set will give you a chance to fix those problems.

  1. Copy the program you wrote for Problem Set 11 into a directory named set11. Add a definition of the following public static method to the Programs class defined in your Programs.java file:
            // Runs the ps11 program found in the file named on the command line
            // on the integer inputs that follow its name on the command line,
            // printing the result computed by the program.
            // Example:
            //     % java Programs sieve.ps11 2 100
            //     25
            public static void main (String[] args) { ... }

    Hint: We are giving you a directory of Java code that contains a recursive descent parser for ps11 programs. The Scanner class defined in Scanner.java defines several public static methods you may find helpful.

  2. Add a definition of the following public static method to the Programs class defined in your Programs.java file:
            // Reads the ps11 program found in the file named by the given string
            // and returns the set of all variable names that occur free within
            // the program.
            // Examples:
            //     Programs.undefined ("church.ps11")    // returns an empty set
            //     Programs.undefined ("bad.ps11")       // returns { "x", "z" }
            //   where bad.ps11 is a file containing:
            //     f (x, y) g (x, y) (y, z);
            //     g (z, y) if 3 > 4 then x else f
            public static Set<String> undefined (String filename) { ... }

For debugging: Click here to validate.