Построить множество follow(1) на основе заданной ll-грамматики - Lisp

;; computing First and Follow sets
 
;;Here is a sample grammar
 
;; We need a way to represent a grammar in Lisp. We could do it in a
;; variety of different ways, for example setting up a data structure
;; of some kind of collection for the rules (list, hashtable, array),
;; some kind of indexing or selection so we can step through the
;; rules, some kind of constructors so we can construct the grammar
;; and its rules in the first place, some selectors on rule parts so
;; we can get the left-hand and right-hand sides, a selector so that
;; we can step through components in the right-hand side, etc.  It
;; turns out that if we use lisp lists as shown below, we can make
;; very neat use of built-in lisp programs to manipulate
;; grammars... like car, cdr, mapc, list, union. Programs to print
;; grammars are also free; and formatted output is also pretty
;; standard.  If we constructed a grammar data-type (and in some
;; languages we could mention we would have to do so), it would take
;; us a page of code, and all of our programs would have to use these
;; structures.  It would make the programs relatively opaque: you
;; would have to be fully educated in what we had done to make sense
;; of them.
 
;; If this appears to you to constitute an argument against abstract
;; data types, you are right.  It is not a mathematical, legal, or ethical
;; argument. In fact it is an argument based on TASTE, and reasonable
;; people can disagree with me about what I've done.  I might even
;; change my mind about some of the issues, but at the moment I think
;; I'm right.  ( :) .
 
;; 
 
;; Here is what we do to define a grammar.  The 2nd element in each
;; rule is the symbol "->".  This is just for visual appearance.  We
;; do not allow any of the extended notations like | or *.  If we did,
;; we could write an extended-grammar to vanilla-grammar translator.
 
(defparameter  ; grammar 3.12
    g
    '((Z -> d)
      (Z -> X Y Z)
      (Y -> )
      (Y -> c)
      (X -> Y)
      (X -> a)))
 
(defparameter lect7
    '((E -> T X)
      (T -> \( E \) )
      (T -> int Y)
      (X -> + T)
      (X -> )
      (Y -> * T)
      (Y -> )))
      
 
 
;; selecting stuff from a rule
 
(defun rhs(rule)(cddr rule))        ;right hand side
(defun lhs(rule)(car rule))     ;left hand side
 
;; Return a list of the non-terminal symbols of g by making a list of
;; all the symbols on the lhs. Remove duplicates from that list.
 
(defun non-terminals(g) (remove-duplicates (mapcar #'lhs g)))
 
;; Return a list of the terminal symbols of the grammar g by computing
;; the union of all the symbols on the rhs of all the rules of g.
;; Eliminate the non-terminal symbols.
 
(defun terminals(g)
  (set-difference (reduce #'union (mapcar #'rhs g))
          (non-terminals g) ))
 
;; a diversion to discuss MACROS.
 
;; We repeatedly need to do (setf foo (union foo z)). No big deal,
;; except that foo is sometimes a big expression, and we don't really
;; want to write it out twice. We might make a mistake and write it
;; differently the second time. Let's extend lisp with a macro,
;; addinto, so that we can write (addinto foo z). Like foo+=z in C
;; except we are using union instead of +.  We want to take a place
;; and stuff and produce a new expression that looks like (setf place
;; (union place stuff)).  But of course we must do sometime to make
;; place and stuff parameters.
;;
;; (defun addinto(p s)(setf p (union p s))) 
;;  -- will not work. (addinto x y) sets p to (union x y).
 
;; (defun addinto (p s) (list 'setf p (list 'union p s)))
;; --- will not work.  (addinto x y) returns the list (setf x (union x y))
 
;; this second definition is closer, because if we 
;; evaluate the returned list, we win. In fact
;; (defmacro addinto (p s) (list 'setf p (list 'union p s)))
;; does what we want.
 
;; The experienced lisp macro-writer is more likely to
;; use the "backquote" syntax, for the IDENTICAL result:
 
(defmacro addinto(place stuff) 
  `(setf ,place (union ,place ,stuff)))
 
;; note that backquote is just like quote except that items with a
;; comma in front of them are replaced by their values.
;; There are other tricks, including ,@ which works like this:
 
;; (setf x '(a b c)) 
;; `(x ,x)   ==> (x (a b c))
;; `(x ,@ x) ==> (x a b c)    ;,@ works by appending 
 
;; Back to MACROS.
 
;; In fact, what we want to say is written in the textbook as
;; something like Follow[x] := Follow[x] U First[y].  where Follow might
;; be First or some other set associated with the symbol x. 
 
;; We have chosen to represent First etc. as hashtables, which means
;; that to get First[X] we could write (gethash X Follow).  But maybe
;; we will weigh in on the side of abstraction this time, and vote
;; against explicitly writing gethash all over. Why? 
;; That commits us to always using the hashtable mechanism.  Maybe we
;; will come up with another idea for the table datatype that
;; associates a symbol like X with several properties like First[X]
;; and Follow[X], and we would like to substitute our implementation
;; for this one, simply.
 
;; Here's a useful Macro trick, then, that abstracts out the gethash:
 
;; Like First[x] in textbook, where x is a symbol, we allow (First x)
 
(defmacro First (x)
  `(gethash ,x First))
 
;; Like Follow[x] in textbook, where x is a symbol.
 
(defmacro Follow(x)
  `(gethash ,x Follow))
 
;; We can now write (Follow x) instead of (gethash x Follow).
 
;; Lisp note: More significantly, using a macro allows us to write
;; (setf (Follow x) ...), which would not be possible if we merely
;; defined functions: (defun Follow(x)(gethash x Follow)).  
;; Also, we expand this macro in the lexical environment of
;; the program. Thus the names First and Follow are the local
;; names, used in the program where the macros are used.
 
;; Combining these macros allows us to write things like 
;;(addinto (Follow x) (First y))
 
;;; end of MACRO discussion