**nacc** was a program I worked on in my spare time, many years ago (early
1980's?); I never completed it. The name is a take-off on **yacc(1)** (Yet
Another Compiler-Compiler). An article, "A LALR(1) Grammar For '82 Ada" by
Philippe Charles and Gerald Fisher (ACM Ada Letters, Volume II,
Number 2, Sept-Oct 1982), was the inspiration for **nacc**: I wanted to
build an Ada syntax checker. If memory serves, **nacc** was intended to
generate LALR parse tables which I would feed into a yet-to-be-written parser.

**nacc** (what there was of it) was written in FORTRAN. Before you
roll on the floor laughing, remember that this was the early or mid 1980's.
We were a VMS shop (an excellent one, by the way) - no Ada, no UNIX, no C,
no YACC, no Internet, etc. And, face it, FORTRAN 77 blows C away in the
string handling department. From the looks of the output, it looks like
I got as far as generating the LR(0) sets of items; I remember studying
the dragon book trying to figure out the algorithm for going from LR(0)
to LALR. (The meanings of these compiler terms are pretty hazy now!)

The structure chart for the program, as built:

NOT_ANOTHER_COMPILER_COMPILER NCDISPLAY CURSOR_EDIT READ_GRAMMAR ADD_SYMBOL * NCERROR GETSTRING ADD_RIGHT_SIDE ADD_ACTION ADD_RIGHT_SIDE_SYMBOL ADD_SYMBOL * OUTPUT_GRAMMAR_FILE WRITEVBLK * PRINT_GRAMMAR GENERATE_LR0_SETS_OF_ITEMS INPUT_GRAMMAR_FILE READVBLK ADD_ITEM * COMPUTE_CLOSURE * ADD_ITEM * ADD_STATE SETS_EQUAL MAKE_LIST COMPUTE_GOTO ADD_ITEM * COMPUTE_CLOSURE * ADD_GOTO OUTPUT_LR0_FILE WRITEVBLK * PRINT_LR0_SETS_OF_ITEMS BUILD_PRODUCTION GENERATE_LALR_SETS_OF_ITEMS GENERATE_PARSE_TABLE

My test grammar (the input is free format):

%START %IS E %SYMBOL E %IS E + T %OR T %SYMBOL T %IS T * F %OR F %SYMBOL F %IS ( E ) %OR id

And the LR(0) sets of items:

** State 1 ** Set of Items (Left, Right, Dot): %START => E Dot = 0 E => E + T Dot = 0 E => T Dot = 0 T => T * F Dot = 0 T => F Dot = 0 F => ( E ) Dot = 0 F => ID Dot = 0 Goto Transitions (Symbol, State): E => 2 T => 3 F => 4 ( => 5 ID => 6 ** State 2 ** Set of Items (Left, Right, Dot): %START => E Dot = 1 E => E + T Dot = 1 Goto Transitions (Symbol, State): + => 7 ** State 3 ** Set of Items (Left, Right, Dot): E => T Dot = 1 T => T * F Dot = 1 Goto Transitions (Symbol, State): * => 8 ** State 4 ** Set of Items (Left, Right, Dot): T => F Dot = 1 ** State 5 ** Set of Items (Left, Right, Dot): E => E + T Dot = 0 E => T Dot = 0 T => T * F Dot = 0 T => F Dot = 0 F => ( E ) Dot = 0 F => ID Dot = 0 F => ( E ) Dot = 1 Goto Transitions (Symbol, State): E => 9 T => 3 F => 4 ( => 5 ID => 6 ** State 6 ** Set of Items (Left, Right, Dot): F => ID Dot = 1 ** State 7 ** Set of Items (Left, Right, Dot): T => T * F Dot = 0 T => F Dot = 0 F => ( E ) Dot = 0 F => ID Dot = 0 E => E + T Dot = 2 Goto Transitions (Symbol, State): T => 10 F => 4 ( => 5 ID => 6 ** State 8 ** Set of Items (Left, Right, Dot): F => ( E ) Dot = 0 F => ID Dot = 0 T => T * F Dot = 2 Goto Transitions (Symbol, State): ( => 5 ID => 6 F => 11 ** State 9 ** Set of Items (Left, Right, Dot): E => E + T Dot = 1 F => ( E ) Dot = 2 Goto Transitions (Symbol, State): + => 7 ) => 12 ** State 10 ** Set of Items (Left, Right, Dot): T => T * F Dot = 1 E => E + T Dot = 3 Goto Transitions (Symbol, State): * => 8 ** State 11 ** Set of Items (Left, Right, Dot): T => T * F Dot = 3 ** State 12 ** Set of Items (Left, Right, Dot): F => ( E ) Dot = 3

Pretty cool stuff, huh?!