In this assignment will you will construct some core portions of a scanner and demonstrate your implementation's correctness. The name of your application must be NFAMATCH (case sensitive).

Input

NFAMATCH will accept two or more arguments:

NFAMATCH should:

1. read the NFA definition file,
2. convert the NFA to a DFA,
3. optimize the DFA (including dead state and unreachable state pruning),
4. output the optimized DFA transition table ($T$) to the path name of the command line second argument.

5. and finally test the remaining tokens on the command line to determine if they are an element of the DFA's regular set

   If a token is part of the DFA's regular set, your NFAMATCH should emit an (:M:), otherwise NFAMATCH should emit the first character position ($1,2,3,\ldots$, not an index!) that fails the DFA. If the token is not long enough to match the DFA, emit one more than the length of the token. If the token is an empty string which does not match the DFA, then a 0 should be emitted. These last few "special cases" are consistent with reporting the character position of match failure.

NFA Definition File

An NFA definition file is line oriented, all fields are white space delimited. The first line contains three or more fields:

Subsequent lines represent transitions between two states; these lines contain 3 or more fields. State $0$ is implicitely the starting state.

There is only one transition line permitted between any two states. Empty lines in an NFA definition file should be ignored, there is no commentary symbols or syntax. All transition lines must have at least 3 fields.

NFA Definition Example

If we let P be $\Pi=\Sigma - \{ / \ast \}$, then this is an NFA definition file for the C/C++ block comment RE RE we've discussed in lecture:

13 # * / P
- 0 1 /
- 1 2 *
- 2 3 #
- 2 5 #
- 2 7 #
- 2 10 #
- 3 4 /
- 4 10 #
- 5 6 P
- 6 10 #
- 7 8 *
- 8 8 *
- 8 9 P
- 9 10 #
- 10 2 #
- 10 11 *
- 11 11 *
- 11 12 /
+ 12 12

Tokens

A token will be a sequence of non-whitespace containing characters from the NFA's alphabet ($\Sigma$). All the characters of a token must be matched in order for it to be considered a successful match against the DFA.

Output

You will report the following values from your application NFAMATCH on the process stdout (in this order, and according to the course submission requirements):

1. The match results (non-negative integers) for command line provided arguments 3, 4, $\ldots$

An example of a successful run of your NFAMATCH might look like this at a Linux console (the … represents arbitrary console messages that will be ignored by the grader script):

$ ls
NFAMATCH  cblock.nfa
$ ./NFAMATCH cblock.nfa _ttable.dat  '/*PPPPPP*/'  '*/**/'  ""  '/*******/'  '/*P/*/'  '/*PP'
…
OUTPUT :M:
…
OUTPUT 1
…
OUTPUT 0
… 
OUTPUT :M:
… 
OUTPUT :M:
… 
OUTPUT 5
…
$ cat _ttable.dat
- 0 E 1 E
- 1 2 E E
- 2 3 2 2
- 3 3 4 2
+ 4 E E E

The match results could also be written on one line:

OUTPUT :M: 1 0 :M: :M: 5

(And merely for completeness sake)

Examples

Data file tarballs of this C/C++ block comment (group question) and other examples (three underscored identifiers, floating points) that have been part of previous LGAs and we may have discussed in lecture are available.

grader.sh

I am providing to students the same tarball the grader will use for testing your NFAMATCH. is how to use it (a video is posted here):

First, download this tarball to your Mines Linux account ("alamode" machines!) and unroll it in a temporary directory.

$ ls nfamatch-student.*
nfamatch-student.tar.bz2
$ mkdir ~/tmp
$ cd ~/tmp
$ tar xjf ../nfamatch-student.tar.bz2
:
$ ls
nfamatch/

Second, set the COMPGRADING environmental variable with:

$ source ~khellman/COMPGRADING/setup.sh ~khellman/COMPGRADING

Now go to the directory holding your NFAMATCH and execute the grader.sh script from the nfamatch-student.tar.bz2 resource.

$ cd ~/compilers/nfaMatch
$ ls NFAMATCH
NFAMATCH
$ ~/tmp/nfamatch/grader.sh
:
:
:

You will need to read any messages from the script carefully, and hit ENTER several times throughout its course. This script checks for:

1. missing data files
2. truncated data files

3. and the difference between your NFAMATCH results and expected results.

The latter test results are displayed on the terminal screen, but they whip by pretty quickly so you may need to scroll up and make sure you see them all.

When there is a discrepancy in expected results the script either:

• points you to a data file along side your NFAMATCH where more failure details are available,

• or all the details are displayed on screen.

Before the grader.sh terminates, it will show a summary of some specific rubric line results for the programming project.

Submit Your Work

Rubric

This work is worth 60 points. See assignments/nfamatch/.AddRubricSubcats.sh