J

Useful Links

Installing the interpreter

The J interpreter is not installed for you already. On a *nix machine, run the two commands:

  wget http://jsoftware.com/download/j602a_linux32.sh
  /bin/sh j602a_linux32.sh
from your home directory. Then the commands you will need are in the directory ~/j602/bin/. I will use the jconsole command to test your code, but you are encouraged to use the GUI, jwd, for development.

Note: we are using the J602 version. This is also available for other platforms, from this page.

How I will run your code

You should create an argument-free function main to run your program at the top level. Save your program in a file called proj.ijs in folders called proj1 and proj2 respectively for phases 1 and 2 of your project.

I will test your code in the same environment as the lab machines in MI 302, using the command

  echo "main" | ~/j602/bin/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

Phase 2 Assignment

For phase 2 of your project, you will write a program to generate PREDICT and FOLLOW sets for a given grammar. You should submit your program in a folder called proj2, and be sure that it runs as described above.

Specification

Your program will read the grammar specification from a file called spec.txt. 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 spec.txt file 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 in the spec.txt file, for the above grammar, is a bunch of lines with integers. An example file for the grammar above is written out below.

To be precise, each line of the spec.txt file is a single production rule in the grammar, without anything fancy like | or *. 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 right-hand side. 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.

Tips

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.

  1. Start by just reading in the spec.txt file and storing the rules in an array of integers. The J primer page on reading files will probably be helpful for this.
  2. The PREDICT and FOLLOW sets should just be stored in two arrays, with each row corresponding to the PREDICT or FOLLOW set for the non-terminal corresponding to the row index. Initialize these arrays (initially all sets are empty) according to the number of non-terminals in the grammar, and then have your program do nothing and just print out the empty sets for each non-terminal.
  3. Now start adding in rules. The first might be to automatically add 0 to the FOLLOW set of the start symbol, and to add any non-terminal with an empty right-hand side to EPS.
  4. Code up the more complicated rules for PREDICT and FOLLOW as actual J functions. These functions should take a single production rule from the grammar (list of integers), and whatever the current sets are, and return modified sets (arrays) based on the information in that production rule. So for instance one function will just check if the right-hand side of the rule starts with a token, and if so add this token to the PREDICT set of the left-hand side. Try to make these functions simple; they should just examine the single production rule and look for one case of things to add to PREDICT or FOLLOW.
  5. The next step is just to apply your functions to the rules. First try just applying each function once and printing the results. Then augment this functionality to apply functions repeatedly until the sets (arrays) are no longer changed by any function. Then you're done!

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.

Example

Here is a sample spec.txt file corresponding to the grammar above:

-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!).