-;;; Grammar compiler for the wisent LALR parser, integrating Wisi OpenToken output. -*- lexical-binding:t -*-
+;; wisi-compile.el --- Grammar compiler for the wisi parser, integrating Wisi OpenToken output. -*- lexical-binding:t -*-
;;
-;; Copyright (C) 2012, 2013, 2015 Free Software Foundation, Inc.
+;; Copyright (C) 2012, 2013, 2015, 2016 Free Software Foundation, Inc.
;;
;; Author: Stephen Leake <stephen_leake@member.fsf.org>
;;
;; You should have received a copy of the GNU General Public License
;; along with GNU Emacs. If not, see <http://www.gnu.org/licenses/>.
;;
-;;; History: first experimental version Jan 2013
+
+;;; Commentary:
+;;
+
+;;;; History: first experimental version Jan 2013
;;
-;;; Context
+;;;; Context
;;
;; Semantic (info "(semantic)Top") provides an LALR(1) parser
-;; wisent-parse. The grammar used is defined by the functions
+;; wisent-parse. The grammar used is defined by the functions
;; semantic-grammar-create-package, which reads a bison-like source
;; file and produces corresponding elisp source, and
;; wisent-compile-grammar, which generates a parser table.
;;
;; However, the algorithm used in wisent-compile-grammar cannot cope
;; with the grammar for the Ada language, because it is not
-;; LALR(1). So we provide a generalized LALR parser, which spawns
-;; parallel LALR parsers at each conflict. Instead of also rewriting
+;; LALR(1). So we provide a generalized LALR parser, which spawns
+;; parallel LALR parsers at each conflict. Instead of also rewriting
;; the entire semantic grammar compiler, we use the OpenToken LALR
;; parser generator, which is easier to modify (it is written in Ada,
;; not Lisp).
;; produces corresponding elisp source code, similar to that
;; produced by semantic-grammar-create-package.
;;
-;; wisi-compile-grammar (provided here) generate the automaton
-;; structure required by wisi-parse, using functions from
-;; wisent/comp.el
+;; wisi-compile-grammar (provided here) generates the automaton
+;; structure required by wisi-parse
;;
;;;;
-(require 'semantic/wisent/comp)
-
-(defun wisi-compose-action (value symbol-array nonterms)
- (let ((symbol (intern-soft (format "%s:%d" (car value) (cdr value)) symbol-array))
- (prod (car (nth (cdr value) (cdr (assoc (car value) nonterms))))))
- (if symbol
- (list (car value) symbol (length prod))
- (error "%s not in symbol-array" symbol))))
+(defun wisi-compose-action (value symbol-obarray nonterms)
+ (let* ((nonterm (car value))
+ (index (cdr value))
+ (symbol (intern-soft (format "%s:%d" nonterm index) symbol-obarray))
+ (rhs (car (nth index (cdr (assoc nonterm nonterms))))))
+ (list nonterm symbol (length rhs))
+ ))
-(defun wisi-replace-actions (action symbol-array nonterms)
+(defun wisi-replace-actions (action symbol-obarray nonterms)
"Replace semantic action symbol names in ACTION with list as defined in `wisi-compile-grammar'.
-ACTION is the alist for one state from the grammar; NONTERMS is from the grammar.
-Return the new alist."
- ;; result is (nonterm index action-symbol token-count)
+ACTION is the alist for one state from the grammar, with the form:
+ ((default . error) ITEM ... )
+ITEM is one of:
+reduction (TOKEN . (NONTERM . INDEX)) where NONTERM . INDEX gives the action symbol name.
+shift (TOKEN . STATE)
+shift/reduce conflict (STATE (NONTERM . INDEX))
+reduce/shift conflict ((NONTERM . INDEX) (NONTERM . INDEX))
+
+SYMBOL-OBARRAY contains the action symbols.
+NONTERMS is from the grammar.
+Return the new action alist."
+ ;; result is list of (nonterm index action-symbol token-count)
(let (result item)
(while action
(setq item (pop action))
(cond
((or
(memq (cdr item) '(error accept))
- (numberp (cdr item)))
+ (numberp (cdr item))) ;; shift
(push item result))
((listp (cdr item))
((symbolp (car value))
;; reduction
(push (cons (car item)
- (wisi-compose-action value symbol-array nonterms))
+ (wisi-compose-action value symbol-obarray nonterms))
result))
((integerp (car value))
;; shift/reduce conflict
(push (cons (car item)
(list (car value)
- (wisi-compose-action (cadr value) symbol-array nonterms)))
- result))
-
- ((integerp (cadr value))
- ;; reduce/shift conflict
- (push (cons (car item)
- (list (wisi-compose-action (car value) symbol-array nonterms)
- (cadr value)))
+ (wisi-compose-action (cadr value) symbol-obarray nonterms)))
result))
(t ;; reduce/reduce conflict
(push (cons (car item)
- (list (wisi-compose-action (car value) symbol-array nonterms)
- (wisi-compose-action (cadr value) symbol-array nonterms)))
+ (list (wisi-compose-action (car value) symbol-obarray nonterms)
+ (wisi-compose-action (cadr value) symbol-obarray nonterms)))
result))
)))
(reverse result)))
-(defun wisi-semantic-action (r rcode tags rlhs)
- "Define an Elisp function for semantic action at rule R.
-On entry RCODE[R] contains a vector [BODY N (NTERM I)] where BODY
-is the body of the semantic action, N is the number of tokens in
-the production, NTERM is the nonterminal the semantic action
-belongs to, and I is the index of the production and associated
-semantic action in the NTERM rule. Returns the semantic action
-symbol, which is interned in RCODE[0].
-
-The semantic action function accepts one argument, the list of
-tokens to be reduced. It returns nil; it is called for the user
-side-effects only."
+(defun wisi-semantic-action (form nonterm iactn symbol-obarray)
+ "Define an Elisp semantic action function for a production, interned in SYMBOL-OBARRAY.
+FORM is the body of the semantic action.
+NONTERM is the nonterminal left hand side.
+IACTN is the index of the production in the NTERM rule.
+
+The semantic action function accepts two arguments;
+- $nterm : the nonterminal
+- wisi-tokens : the list of tokens to be reduced.
+
+It returns nil; it is called for the semantic side-effects only."
;; based on comp.el wisent-semantic-action
- (let* ((actn (aref rcode r))
- (n (aref actn 1)) ; number of tokens in production
- (name (apply 'format "%s:%d" (aref actn 2)))
- (form (aref actn 0))
- (action-symbol (intern name (aref rcode 0))))
+ (let* ((name (format "%s:%d" nonterm iactn))
+ (action-symbol (intern name symbol-obarray)))
(fset action-symbol
- `(lambda (wisi-tokens)
- (let* (($nterm ',(aref tags (aref rlhs r)))
- ($1 nil));; wisent-parse-nonterminals defines a default body of $1 for empty actions
- ,form
- nil)))
-
- (list (car (aref actn 2)) action-symbol n)))
+ `(lambda ($nterm wisi-tokens)
+ ,form
+ nil))))
(defun wisi-compile-grammar (grammar)
- ;; FIXME: This docstring is full of ambiguities making it unclear whether
- ;; we're talking for example about data that includes the symbol `nonterm' as
- ;; opposed to data that includes some non terminal object we denote
- ;; with the meta-variable "nonterm".
- ;; The convention in Elisp's docstrings is to use all-caps for metavariables
- ;; (and `...' quoting as opposed to the '... quoting used below in a few
- ;; spots).
"Compile the LALR(1) GRAMMAR; return the automaton for wisi-parse.
GRAMMAR is a list TERMINALS NONTERMS ACTIONS GOTOS, where:
TERMINALS is a list of terminal token symbols.
NONTERMS is a list of productions; each production is a
-list (nonterm (tokens action) ...) where `action' is any lisp form.
+list (nonterm (tokens semantic-action) ...) where `semantic-action' is
+any lisp form. The set of (tokens semantic-action) are the right hand
+sides; nonterm is the left hand side.
ACTIONS is an array indexed by parser state, of alists indexed by
terminal tokens. The value of each item in the alists is one of:
-'error
+`error'
-'accept
+`accept'
integer - shift; gives new state
-'(nonterm . index) - reduce by nonterm production index.
+(nonterm . index) - reduce by nonterm production index.
-'(integer (nonterm . index)) - a shift/reduce conflict
-'((nonterm . index) integer) - a reduce/shift conflict
-'((nonterm . index) (nonterm . index)) - a reduce/reduce conflict
+(integer (nonterm . index)) - a shift/reduce conflict
+((nonterm . index) (nonterm . index)) - a reduce/reduce conflict
-The first item in the alist must have the key 'default (not a
+The first item in the alist must have the key `default' (not a
terminal token); it is used when no other item matches the
current token.
new state after a reduce for each nonterminal legal in that
state.
-The automaton is an array with 3 elements:
+The automaton is an array [parser-actions gotos symbol-obarray]:
-parser-actions is a copy of the input ACTIONS, with reduction
-actions replaced by a list (NONTERM ACTION-SYMBOL TOKEN-COUNT),
-where NONTERM is a symbol from NONTERMS, and is the
-non-terminal to reduce to, TOKEN-COUNT is the number of tokens in
-the reduction, ACTION-SYMBOL is nil if there is no user action,
-or a symbol from semantic-actions (below).
+- parser-actions is a copy of the input ACTIONS, with semantic
+actions replaced by a list (nonterm action-symbol token-count),
+where:
-gotos is a copy of GOTOS.
+-- nonterm is a symbol from NONTERMS, and is the non-terminal to
+reduce to
-semantic-actions is an obarray containing functions that
-implement the user action for each nonterminal; the function
-names have the format nonterm:index."
- (defvar nrules) (defvar ptable) (defvar rcode) (defvar rlhs) (defvar tags)
- (defvar token-list) (defvar var-list)
- (let (nrules ptable rcode rlhs tags token-list var-list)
- (wisent-parse-grammar;; set global vars used by wisent-semantic-action
- (cons
- (nth 0 grammar);; TOKENS
- (cons nil ;; ASSOCS
- (nth 1 grammar));; NONTERMS
- ))
-
- (aset rcode 0 (make-vector 13 0));; obarray for semantic actions
-
- ;; create semantic action functions, interned in rcode[0]
- (let* ((i 1))
- (while (<= i nrules)
- (wisi-semantic-action i rcode tags rlhs)
- (setq i (1+ i)))
- )
+-- token-count is the number of tokens in the reduction,
- ;; replace semantic actions in ACTIONS with symbols from symbol-array
+-- action-symbol is nil if there is no semantic action, or a
+symbol interned in symbol-obarray
+
+- gotos is a copy of GOTOS.
+
+- symbol-obarray is an obarray containing functions that
+implement the semantic action for each nonterminal; the function
+names have the format nonterm:index."
+ ;; We store named symbols for semantic actions, not just lambda
+ ;; functions, so we have a name for debug trace.
+ ;;
+ ;; FIXME: TERMINALS is not used. Eliminating it requires decoupling
+ ;; from OpenToken; we'll do that in the move to FastToken.
+ ;;
+ ;; FIXME: eliminate use of semantic-lex-* in *-wy.el. Similarly
+ ;; requires decoupling from OpenToken
+ ;;
+ ;; FIXME: can eliminate obarray? We don't need the obarray to
+ ;; avoid garbage collection of the symbols; they are all referenced in the compiled grammar.
+ ;; But each semantic action function has to be defined (and byte-compiled?) somewhere?
+ ;; currently actions are _not_ byte-compiled; wisi-compile-grammar is run at load time
+ ;; need 'eval-when-compile' to byte-compile them?
+ ;; can't byte-compile obarray?
+
+ (let ((defs (nth 1 grammar))
+ (symbol-obarray (make-vector 13 0));; for parse actions
+ def nonterm rhs-list rule
+ semantic-action index)
+
+ (while defs
+ (setq def (car defs)
+ defs (cdr defs)
+ nonterm (car def)
+ rhs-list (cdr def)
+ index 0)
+ (while rhs-list
+ (setq rule (car rhs-list)
+ rhs-list (cdr rhs-list)
+ semantic-action (cadr rule))
+
+ (when semantic-action
+ (wisi-semantic-action semantic-action nonterm index symbol-obarray))
+
+ (setq index (1+ index))
+ ))
+
+ ;; replace semantic actions in ACTIONS with symbols from symbol-obarray
(let ((nactions (length (nth 2 grammar)))
(actions (nth 2 grammar))
- (symbol-array (aref rcode 0))
(i 0))
(while (< i nactions)
(aset actions i
- (wisi-replace-actions (aref actions i) symbol-array (nth 1 grammar)))
+ (wisi-replace-actions (aref actions i) symbol-obarray (nth 1 grammar)))
(setq i (1+ i)))
(vector
actions
(nth 3 grammar)
- symbol-array)
+ symbol-obarray)
)))
(provide 'wisi-compile)
-
;;; wisi-compile.el ends here