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:
- you may use imports seen in Java files we give you
- corrected concrete syntax (semicolon is separator, not terminator)
-
set11parserV2
replacesset11parser
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.
-
Copy the program you wrote for Problem Set 11 into a
directory named
set11
. Add a definition of the following public static method to thePrograms
class defined in yourPrograms.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. TheScanner
class defined inScanner.java
defines several public static methods you may find helpful. -
Add a definition of the following public static method to
the
Programs
class defined in yourPrograms.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) { ... }