| blob | 224ce9f64338b645a127560933fa673ec172c6cb |
1 ;;; ebnf-otz --- Syntatic chart OpTimiZer
3 ;; Copyright (C) 1999, 2000 Free Software Foundation, Inc.
5 ;; Author: Vinicius Jose Latorre <vinicius@cpqd.com.br>
6 ;; Maintainer: Vinicius Jose Latorre <vinicius@cpqd.com.br>
7 ;; Keywords: wp, ebnf, PostScript
8 ;; Time-stamp: <2000/12/19 14:54:41 vinicius>
9 ;; Version: 1.0
11 ;; This file is part of GNU Emacs.
13 ;; GNU Emacs is free software; you can redistribute it and/or modify
14 ;; it under the terms of the GNU General Public License as published by
15 ;; the Free Software Foundation; either version 2, or (at your option)
16 ;; any later version.
18 ;; GNU Emacs is distributed in the hope that it will be useful,
19 ;; but WITHOUT ANY WARRANTY; without even the implied warranty of
20 ;; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
21 ;; GNU General Public License for more details.
23 ;; You should have received a copy of the GNU General Public License
24 ;; along with GNU Emacs; see the file COPYING. If not, write to the
25 ;; Free Software Foundation, Inc., 59 Temple Place - Suite 330,
26 ;; Boston, MA 02111-1307, USA.
28 ;;; Commentary:
30 ;; ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
31 ;;
32 ;;
33 ;; This is part of ebnf2ps package.
34 ;;
35 ;; This package defines an optimizer for ebnf2ps.
36 ;;
37 ;; See ebnf2ps.el for documentation.
38 ;;
39 ;;
40 ;; ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
42 ;;; code:
47 \f
48 ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
56 "Add empty RULE in `ebnf-empty-rule-list'."
61 ebnf-empty-rule-list))))
65 "Initialize optimizer."
68 \f
69 ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
70 ;; Eliminate empty rules
74 "Eliminate empty rules."
79 new-list before)
83 ;; if any non-terminal pertains to ebnf-empty-rule-list
84 ;; then eliminate non-terminal from rule
87 ;; eliminate empty rule from syntax-list
94 syntax-list)
97 ;; [production width-func entry height width name production action]
98 ;; [sequence width-func entry height width list]
99 ;; [alternative width-func entry height width list]
100 ;; [non-terminal width-func entry height width name default]
101 ;; [empty width-func entry height width]
102 ;; [terminal width-func entry height width name default]
103 ;; [special width-func entry height width name default]
108 ;; non-terminal
111 nil
112 rule))
113 ;; sequence
117 before elt)
128 rule)))
129 ;; alternative
133 before elt)
146 rule))))
147 ;; production
152 rule)))
153 ;; terminal, special and empty
155 rule)
156 )))
158 \f
159 ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
160 ;; Optimizations
163 ;; *To be implemented*:
164 ;; left recursion:
165 ;; A = B | A C B | A C D. ==> A = B {C (B | D)}*.
167 ;; right recursion:
168 ;; A = B | C A. ==> A = {C}* B.
169 ;; A = B | D | C A | E A. ==> A = { C | E }* ( B | D ).
171 ;; optional:
172 ;; A = B | C B. ==> A = [C] B.
173 ;; A = B | B C. ==> A = B [C].
174 ;; A = D | B D | B C D. ==> A = [B [C]] D.
177 ;; *Already implemented*:
178 ;; left recursion:
179 ;; A = B | A C. ==> A = B {C}*.
180 ;; A = B | A B. ==> A = {B}+.
181 ;; A = | A B. ==> A = {B}*.
182 ;; A = B | A C B. ==> A = {B || C}+.
183 ;; A = B | D | A C | A E. ==> A = ( B | D ) { C | E }*.
185 ;; optional:
186 ;; A = B | . ==> A = [B].
187 ;; A = | B . ==> A = [B].
189 ;; factoration:
190 ;; A = B C | B D. ==> A = B (C | D).
191 ;; A = C B | D B. ==> A = (C | D) B.
192 ;; A = B C E | B D E. ==> A = B (C | D) E.
194 ;; none:
195 ;; A = B | C | . ==> A = B | C | .
196 ;; A = B | C A D. ==> A = B | C A D.
199 "Syntatic chart optimizer."
201 syntax-list
204 new)
211 ;; left recursion:
212 ;; 1. A = B | A C. ==> A = B {C}*.
213 ;; 2. A = B | A B. ==> A = {B}+.
214 ;; 3. A = | A B. ==> A = {B}*.
215 ;; 4. A = B | A C B. ==> A = {B || C}+.
216 ;; 5. A = B | D | A C | A E. ==> A = ( B | D ) { C | E }*.
218 ;; optional:
219 ;; 6. A = B | . ==> A = [B].
220 ;; 7. A = | B . ==> A = [B].
222 ;; factoration:
223 ;; 8. A = B C | B D. ==> A = B (C | D).
224 ;; 9. A = C B | D B. ==> A = (C | D) B.
225 ;; 10. A = B C E | B D E. ==> A = B (C | D) E.
238 prod
240 ;; cases 2., 4.
245 elist))
252 ;; cases 1., 3., 5.
265 znode
269 znode)))))
270 ;; cases 6., 7.
272 )
273 ;; cases 8., 9., 10.
275 )
276 ;; none
278 production)
279 ))))
280 prod))
286 zlist empty-p)
295 elt))
296 zlist))
300 zlist)))
322 nil)
323 )))
336 ;; empty second
339 ;; first empty
342 ;; first second
344 nil)
345 ))))
350 before empty-p)
374 ok))
384 ok))
386 nil)
387 )
392 t)
397 lis))
402 )))))
411 len z)
420 ok)
422 t
424 ze)))))
431 t)
436 ze)
437 ))))
440 ))
456 suffix))))))
466 ;; determine prefix length
480 ;; no prefix at all
483 ;; get prefix
487 head))
488 empty-p before)
489 ;; adjust first element
493 tail lis
494 empty-p t)
499 ;; eliminate prefix from lis based on ipre
502 rest)
518 lis)))))))
529 ;; determine suffix length
547 ;; no suffix at all
550 ;; get suffix
555 head)))
556 before empty-p)
557 ;; adjust first element
561 tail lis
562 empty-p t)
567 ;; eliminate suffix from lis based on isuf
570 rest)
589 lis)))))))
594 before)
598 remove-p)
603 tail nil)
610 nlist))
618 ;; empty
620 t)
621 ;; non-terminal, terminal, special
623 ebnf-generate-terminal
624 ebnf-generate-special))
626 ;; alternative, sequence
637 ok))))
638 ;; production
643 ;; otherwise
645 nil)
646 ))))
654 \f
655 ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
661 ;;; ebnf-otz.el ends here