1 ;;; Grammar compiler for the wisent LALR parser, integrating Wisi OpenToken output.
3 ;; Copyright (C) 2012, 2013 Free Software Foundation, Inc.
5 ;; Author: Stephen Leake <stephen_leake@member.fsf.org>
7 ;; This file is part of GNU Emacs.
9 ;; GNU Emacs is free software: you can redistribute it and/or modify
10 ;; it under the terms of the GNU General Public License as published by
11 ;; the Free Software Foundation, either version 3 of the License, or
12 ;; (at your option) any later version.
14 ;; GNU Emacs is distributed in the hope that it will be useful,
15 ;; but WITHOUT ANY WARRANTY; without even the implied warranty of
16 ;; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
17 ;; GNU General Public License for more details.
19 ;; You should have received a copy of the GNU General Public License
20 ;; along with GNU Emacs. If not, see <http://www.gnu.org/licenses/>.
22 ;;; History: first experimental version Jan 2013
26 ;; Semantic (info "(semantic)Top") provides an LALR(1) parser
27 ;; wisent-parse. The grammar used is defined by the functions
28 ;; semantic-grammar-create-package, which reads a bison-like source
29 ;; file and produces corresponding elisp source, and
30 ;; wisent-compile-grammar, which generates a parser table.
32 ;; However, the algorithm used in wisent-compile-grammar cannot cope
33 ;; with the grammar for the Ada language, because it is not
34 ;; LALR(1). So we provide a generalized LALR parser, which spawns
35 ;; parallel LALR parsers at each conflict. Instead of also rewriting
36 ;; the entire semantic grammar compiler, we use the OpenToken LALR
37 ;; parser generator, which is easier to modify (it is written in Ada,
40 ;; The Ada function Wisi.Generate reads the bison-like input and
41 ;; produces corresponding elisp source code, similar to that
42 ;; produced by semantic-grammar-create-package.
44 ;; wisi-compile-grammar (provided here) generate the automaton
45 ;; structure required by wisi-parse, using functions from
51 ;; can't just 'require'; `wisent-with-context' doesn't work.
52 ;; also can't load .elc; must load .el
53 (load (locate-library "semantic/wisent/comp.el")))
56 (require 'semantic/wisent/comp))
58 (defun wisi-compose-action (value symbol-array nonterms)
59 (let ((symbol (intern-soft (format "%s:%d" (car value) (cdr value)) symbol-array))
60 (prod (car (nth (cdr value) (cdr (assoc (car value) nonterms))))))
62 (list (car value) symbol (length prod))
63 (error "%s not in symbol-array" symbol))))
65 (defun wisi-replace-actions (action symbol-array nonterms)
66 "Replace semantic action symbol names in ACTION with list as defined in `wisi-compile-grammar'.
67 ACTION is the alist for one state from the grammar; NONTERMS is from the grammar.
68 Return the new alist."
69 ;; result is (nonterm index action-symbol token-count)
72 (setq item (pop action))
75 (memq (cdr item) '(error accept))
80 (let ((value (cdr item)))
82 ((symbolp (car value))
84 (push (cons (car item)
85 (wisi-compose-action value symbol-array nonterms))
88 ((integerp (car value))
89 ;; shift/reduce conflict
90 (push (cons (car item)
92 (wisi-compose-action (cadr value) symbol-array nonterms)))
95 ((integerp (cadr value))
96 ;; reduce/shift conflict
97 (push (cons (car item)
98 (list (wisi-compose-action (car value) symbol-array nonterms)
102 (t ;; reduce/reduce conflict
103 (push (cons (car item)
104 (list (wisi-compose-action (car value) symbol-array nonterms)
105 (wisi-compose-action (cadr value) symbol-array nonterms)))
110 (error "unexpected '%s'; expected 'error, 'accept, numberp, stringp, listp" (cdr item)))
115 (defun wisi-semantic-action (r rcode tags rlhs)
116 "Define an Elisp function for semantic action at rule R.
117 On entry RCODE[R] contains a vector [BODY N (NTERM I)] where BODY
118 is the body of the semantic action, N is the number of tokens in
119 the production, NTERM is the nonterminal the semantic action
120 belongs to, and I is the index of the production and associated
121 semantic action in the NTERM rule. Returns the semantic action
122 symbol, which is interned in RCODE[0].
124 The semantic action function accepts one argument, the list of
125 tokens to be reduced. It returns nil; it is called for the user
127 ;; based on comp.el wisent-semantic-action
128 (let* ((actn (aref rcode r))
129 (n (aref actn 1)) ; number of tokens in production
130 (name (apply 'format "%s:%d" (aref actn 2)))
132 (action-symbol (intern name (aref rcode 0))))
135 `(lambda (wisi-tokens)
136 (let* (($nterm ',(aref tags (aref rlhs r)))
137 ($1 nil));; wisent-parse-nonterminals defines a default body of $1 for empty actions
141 (list (car (aref actn 2)) action-symbol n)))
143 (defun wisi-compile-grammar (grammar)
144 "Compile the LALR(1) GRAMMAR; return the automaton for wisi-parse.
145 GRAMMAR is a list TERMINALS NONTERMS ACTIONS GOTOS, where:
147 TERMINALS is a list of terminal token symbols.
149 NONTERMS is a list of productions; each production is a
150 list (nonterm (tokens action) ...) where `action' is any lisp form.
152 ACTIONS is an array indexed by parser state, of alists indexed by
153 terminal tokens. The value of each item in the alists is one of:
159 integer - shift; gives new state
161 '(nonterm . index) - reduce by nonterm production index.
163 '(integer (nonterm . index)) - a shift/reduce conflict
164 '((nonterm . index) integer) - a reduce/shift conflict
165 '((nonterm . index) (nonterm . index)) - a reduce/reduce conflict
167 The first item in the alist must have the key 'default (not a
168 terminal token); it is used when no other item matches the
171 GOTOS is an array indexed by parser state, of alists giving the
172 new state after a reduce for each nonterminal legal in that
175 The automaton is an array with 3 elements:
177 parser-actions is a copy of the input ACTIONS, with reduction
178 actions replaced by a list (nonterm action-symbol token-count),
179 where `nonterm' is a symbol from NONTERMS, and is the
180 non-terminal to reduce to, token-count is the number of tokens in
181 the reduction, action-symbol is nil if there is no user action,
182 or a symbol from semantic-actions (below).
184 gotos is a copy of GOTOS.
186 semantic-actions is an obarray containing functions that
187 implement the user action for each nonterminal; the function
188 names have the format nonterm:index."
189 (wisent-with-context compile-grammar
190 (wisent-parse-grammar;; set global vars used by wisent-semantic-action
192 (nth 0 grammar);; TOKENS
194 (nth 1 grammar));; NONTERMS
197 (aset rcode 0 (make-vector 13 0));; obarray for semantic actions
199 ;; create semantic action functions, interned in rcode[0]
202 (wisi-semantic-action i rcode tags rlhs)
206 ;; replace semantic actions in ACTIONS with symbols from symbol-array
207 (let ((nactions (length (nth 2 grammar)))
208 (actions (nth 2 grammar))
209 (symbol-array (aref rcode 0))
211 (while (< i nactions)
213 (wisi-replace-actions (aref actions i) symbol-array (nth 1 grammar)))
221 (provide 'wisi-compile)