Home

GEONius.com
23-Dec-2015
E-mail

nacc - Not Another Compiler-Compiler

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


Alex Measday  /  E-mail