;; Generation Instructions}

;; In order to generate a table for the parsing skeleton one must go
;; to a bit of trouble, as the first and follow calculation 
;; could not be expressed in NQTHM.
;; A non-left-recursive context-free grammar is needed as input to
;; the table generator. The following is a list of the instructions in the
;; order they need to be done.

;; Bootstrap NQTHM and make sure that all files in the init.lsp are loaded.
(boot-strap NQTHM)

;; Start (R-LOOP)
(R-LOOP)

;; Submit the grammar in this form: 
;; (mk-grammar nonterms terms prods axiom)

(setq grammar
      (mk-grammar
       '(PROG BLK PROC PDECLLIST PDECL DECL SPROCLIST 
	      PDECLREST SPROCREST GCREST 
	      SPROC GCLIST GC EXP LITERAL SIMPLE 
	      DOP MOP VAR)		; non-terminals
       '(MINUS NOT PLUS TIMES DIV REM EQ LT GT NE LE GE AND OR
	       QUEST EXCLAIM
	       INT TRUE FALSE SKIP STOP COLONEQ INPUT OUTPUT SEQ IF WHILE CALL
	       IDENT COLON LP RP LB RB REC INTEGER ni si bi PROCKW) ; terminals
	(list
	 (mk-prod 0 '(PROG)	'(BLK))
	 (mk-prod 1 '(BLK)	'(DECL COLON si BLK))
	 (mk-prod 2 '(BLK)	'(PROC))
	 (mk-prod 3 '(DECL)	'(INT IDENT))
	 (mk-prod 4 '(DECL)	'(LB INTEGER RB INT IDENT))
	 (mk-prod 5 '(PDECL)	'(PROCKW IDENT LP RP ni SPROC bi COLON))
	 (mk-prod 6 '(PDECLLIST) '(PDECL si PDECLREST))
	 (mk-prod 7 '(PDECLLIST) '(PDECL))
	 (mk-prod 8 '(PDECLLIST) '())
	 (mk-prod 9 '(PDECLREST) '(PDECL))
	 (mk-prod 10 '(PDECLREST) '(PDECL si PDECLREST))
	 (mk-prod 11 '(PROC)	'(REC ni PDECLLIST bi COLON si PROC))
	 (mk-prod 12 '(PROC)	'(SPROC))
	 (mk-prod 13 '(SPROC)	'(SKIP))
	 (mk-prod 14 '(SPROC)	'(STOP))
	 (mk-prod 15 '(SPROC)	'(VAR COLONEQ EXP))
	 (mk-prod 16 '(SPROC)	'(INPUT QUEST IDENT))
	 (mk-prod 17 '(SPROC)	'(OUTPUT EXCLAIM EXP))
	 (mk-prod 18 '(SPROC)	'(CALL IDENT LP RP))
	 (mk-prod 19 '(SPROC)	'(SEQ ni SPROCLIST bi))
	 (mk-prod 20 '(SPROC)	'(IF ni GCLIST bi))
	 (mk-prod 21 '(SPROC)	'(WHILE EXP ni SPROC bi))
	 (mk-prod 22 '(SPROCLIST) '(SPROC si SPROCREST))	
	 (mk-prod 23 '(SPROCLIST) '(SPROC))
	 (mk-prod 24 '(SPROCLIST) '())
	 (mk-prod 25 '(SPROCREST) '(SPROC))
	 (mk-prod 26 '(SPROCREST) '(SPROC si SPROCREST))	
	 (mk-prod 27 '(GCLIST)	'(GC si GCREST))
	 (mk-prod 28 '(GCLIST)	'(GC))
	 (mk-prod 29 '(GCLIST)	'())
	 (mk-prod 30 '(GCREST)	'(GC si GCREST))
	 (mk-prod 31 '(GCREST)	'(GC))
	 (mk-prod 32 '(GC)	'(EXP ni SPROC bi))
	 (mk-prod 33 '(EXP) 	'(SIMPLE))
	 (mk-prod 34 '(EXP)    '(MOP SIMPLE))
	 (mk-prod 35 '(EXP) 	'(SIMPLE DOP SIMPLE))
	 (mk-prod 36 '(SIMPLE) '(VAR))
	 (mk-prod 37 '(SIMPLE) '(LITERAL))
	 (mk-prod 38 '(SIMPLE) '(LP EXP RP))
	 (mk-prod 39 '(LITERAL) '(INTEGER))
	 (mk-prod 40 '(LITERAL) '(TRUE))
	 (mk-prod 41 '(LITERAL) '(FALSE))
	 (mk-prod 42 '(VAR)     '(IDENT))
	 (mk-prod 43 '(VAR)     '(IDENT LB EXP RB))
	 (mk-prod 44 '(DOP)  	'(PLUS))
	 (mk-prod 45 '(DOP)	'(MINUS))
	 (mk-prod 46 '(DOP)	'(TIMES))
	 (mk-prod 47 '(DOP)	'(DIV))
	 (mk-prod 48 '(DOP)	'(REM))
	 (mk-prod 49 '(DOP)	'(EQ))
	 (mk-prod 50 '(DOP)	'(LT))
	 (mk-prod 51 '(DOP)	'(GT))
	 (mk-prod 52 '(DOP)	'(NE))
	 (mk-prod 53 '(DOP)	'(LE))
	 (mk-prod 54 '(DOP)	'(GE))
	 (mk-prod 55 '(DOP)	'(AND))
	 (mk-prod 56 '(DOP)	'(OR))
	 (mk-prod 57 '(MOP)  	'(MINUS))
	 (mk-prod 58 '(MOP)	'(NOT))
	 )
       0))

;; Pull out the non-terminals

(setq nts     (sel-nonterminals grammar))

;; The terminals need the end-of-file marker

(setq terms   (append (sel-terminals grammar) (list (end-of-file))))


;; Calculate the set of LR(0) items for \plor\ 
;; in (R-LOOP). The result contains 178 items.

(setq fis (LR-0-items grammar))

;; Create the follow set
(setq follows (all-follows grammar))

;; Quit (R-LOOP)
ok

;; Start the LISP-Timer with

(get-decoded-time)

;; Reenter (R-LOOP) and calculate the canonical collection. For
;; \plor\ it consists of 112 sets of items, each determining a
;; state in the deterministic automaton.

(R-LOOP)

(setq cc  (canonical-collection grammar))

;; Construct the action and goto tables. 
;; There are 511 entries in
;; the action table and 87 in the goto table for \plor.

(setq tables (construct-tables1 cc nts terms fis follows))

;; How long does the calculation take?
ok
(get-decoded-time)

;; Don't forget to save a copy of the tables for future reference!