|
|
|
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?!