This is the archived website of SI 413 from the Fall 2013 semester. Feel free to browse around; you may also find more recent offerings at my teaching page.
J was designed in 1990 by Iverson and Hui. This is direct descendant of APL (A Programming Language), which uses a paradigm called array programming in which every operation is applied by default in parallel to an entire array of data. These languages are usually very terse and well-suited to mathematical and financial applications.
The J interpreter, version 602, is installed for you on the CS Linux
environment. This is also available for other platforms, from
I will use the
command to test your code, but you are encouraged to use the GUI,
jwd, for development.
You should create an argument-free function
to run your program at the top level.
Save your program in a file called
I will test your code in the same environment as the lab
machines in MI 316, using the command
echo "main" | jconsole proj.ijs
So for example, the 99 bottles of beer program, for my purposes, would be written as
bob =: ": , ' bottles of beer'"_ -. 1&= # 's'"_ bobw=: bob , ' on the wall'"_ beer=: bobw , ', '"_ , bob , '; take one down and pass it around, '"_ , bobw@<: main=: beer"0 (- i.) 99
For phase 2 of your project,
you will write a program to generate PREDICT and FOLLOW sets for a given
You should submit your program in a folder
proj2, and be sure that it runs as described above.
Your program will read the grammar specification from a file called
Because J likes working with numbers, every token and non-terminal in the
language is represented by a single integer. Tokens are positive integers,
starting from 1 and counting up, and non-terminals are negative integers,
starting from -1 and counting down. The
will just contain lines that are lists of integers. Each list corresponds
to a single production rule in the grammar.
So for instance if we have the grammar
start → BOO foo BAR baz
foo → baz
foo → BAR BAR BOO
baz → ε
baz → BOO foo BOO
Then the non-terminals start, foo,
and baz might be assigned -1, -2, -3, respectively. And the
tokens BOO and BAR
might be assigned 1 and 2, respectively. By convention, -1 will always be the
start symbol, and 0 will represent the EOF token (which we usually write as
All the names above will never be seen by your J program. All it will see
spec.txt file, for the above grammar, is a bunch of lines
with integers. An example file for the grammar above is written out
To be precise, each line of the
spec.txt file is a single
production rule in the grammar, without anything fancy like
Each rule is simply a list of integers, starting with the left-hand side
non-terminal symbol, and followed by each token or non-terminal on the
Epsilon productions don't explicitly write "epsilon", they just have an
empty right-hand side.
Your program should apply the rules for computing EPS, PREDICT, and FOLLOW sets according to this handout, repeatedly applying each rule until nothing more can be added to the sets. Next you should print the word PREDICT on a single line, followed by lines with lists of integers indicating the PREDICT set for every non-terminal. Then all the FOLLOW sets should be printed in the same way. The ordering that the sets are printed in does not matter.
I suggest you write your program in the following steps. Of course you are free to develop however you wish. In any case, I strongly recommend that you start with a small, working program, and then try to add more functionality in very small increments. As always, feel free to submit every time you complete some small step.
spec.txtfile and storing the rules in an array of integers. The J primer page on reading files will probably be helpful for this.
For full credit, your program should be well-documented and (relatively) easy to follow. J programming encourages very terse lines that do a whole lot at once. Feel free to program accordingly. But you still need to tell me (in comments) everything that that line is doing.
Here is a sample
spec.txt file corresponding to the
-1 1 -2 2 -3 -2 -3 -2 2 2 1 -3 -3 1 -2 1
Given this grammar, your program might print out something like
PREDICT -1 1 -2 2 1 0 -3 1 2 0 FOLLOW -1 0 -2 2 1 -3 0 2 1
Again, the ordering that the sets are printed in does not matter. But no sets should contain any duplicates (then they aren't sets!).