Mercurial > emacs
annotate lisp/progmodes/ebnf-otz.el @ 38512:c9de551dd922
(server-visit-files): Fix variable name typo.
author | Stefan Monnier <monnier@iro.umontreal.ca> |
---|---|
date | Fri, 20 Jul 2001 22:45:11 +0000 |
parents | b174db545cfd |
children | ad17cb15119e |
rev | line source |
---|---|
38436
b174db545cfd
Some fixes to follow coding conventions.
Pavel Janík <Pavel@Janik.cz>
parents:
34806
diff
changeset
|
1 ;;; ebnf-otz.el --- syntatic chart OpTimiZer |
27451 | 2 |
27539 | 3 ;; Copyright (C) 1999, 2000 Free Software Foundation, Inc. |
27451 | 4 |
5 ;; Author: Vinicius Jose Latorre <vinicius@cpqd.com.br> | |
6 ;; Maintainer: Vinicius Jose Latorre <vinicius@cpqd.com.br> | |
7 ;; Keywords: wp, ebnf, PostScript | |
38436
b174db545cfd
Some fixes to follow coding conventions.
Pavel Janík <Pavel@Janik.cz>
parents:
34806
diff
changeset
|
8 ;; Time-stamp: <2001-07-15 01:03:33 pavel> |
27451 | 9 ;; Version: 1.0 |
10 | |
27539 | 11 ;; This file is part of GNU Emacs. |
27451 | 12 |
27539 | 13 ;; GNU Emacs is free software; you can redistribute it and/or modify |
27451 | 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. | |
17 | |
27539 | 18 ;; GNU Emacs is distributed in the hope that it will be useful, |
27451 | 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. | |
22 | |
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. | |
27 | |
28 ;;; Commentary: | |
29 | |
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 ;; ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; | |
41 | |
38436
b174db545cfd
Some fixes to follow coding conventions.
Pavel Janík <Pavel@Janik.cz>
parents:
34806
diff
changeset
|
42 ;;; Code: |
27451 | 43 |
44 | |
45 (require 'ebnf2ps) | |
46 | |
47 | |
48 ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; | |
49 | |
50 | |
51 (defvar ebnf-empty-rule-list nil | |
52 "List of empty rule name.") | |
53 | |
54 | |
55 (defun ebnf-add-empty-rule-list (rule) | |
56 "Add empty RULE in `ebnf-empty-rule-list'." | |
57 (and ebnf-ignore-empty-rule | |
58 (eq (ebnf-node-kind (ebnf-node-production rule)) | |
59 'ebnf-generate-empty) | |
60 (setq ebnf-empty-rule-list (cons (ebnf-node-name rule) | |
61 ebnf-empty-rule-list)))) | |
62 | |
63 | |
64 (defun ebnf-otz-initialize () | |
65 "Initialize optimizer." | |
66 (setq ebnf-empty-rule-list nil)) | |
67 | |
68 | |
69 ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; | |
70 ;; Eliminate empty rules | |
71 | |
72 | |
73 (defun ebnf-eliminate-empty-rules (syntax-list) | |
74 "Eliminate empty rules." | |
75 (while ebnf-empty-rule-list | |
76 (let ((ebnf-total (length syntax-list)) | |
77 (ebnf-nprod 0) | |
78 (prod-list syntax-list) | |
79 new-list before) | |
80 (while prod-list | |
81 (ebnf-message-info "Eliminating empty rules") | |
82 (let ((rule (car prod-list))) | |
83 ;; if any non-terminal pertains to ebnf-empty-rule-list | |
84 ;; then eliminate non-terminal from rule | |
85 (if (ebnf-eliminate-empty rule) | |
86 (setq before prod-list) | |
87 ;; eliminate empty rule from syntax-list | |
88 (setq new-list (cons (ebnf-node-name rule) new-list)) | |
89 (if before | |
90 (setcdr before (cdr prod-list)) | |
91 (setq syntax-list (cdr syntax-list))))) | |
92 (setq prod-list (cdr prod-list))) | |
93 (setq ebnf-empty-rule-list new-list))) | |
94 syntax-list) | |
95 | |
96 | |
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] | |
104 | |
105 (defun ebnf-eliminate-empty (rule) | |
106 (let ((kind (ebnf-node-kind rule))) | |
107 (cond | |
108 ;; non-terminal | |
109 ((eq kind 'ebnf-generate-non-terminal) | |
110 (if (member (ebnf-node-name rule) ebnf-empty-rule-list) | |
111 nil | |
112 rule)) | |
113 ;; sequence | |
114 ((eq kind 'ebnf-generate-sequence) | |
115 (let ((seq (ebnf-node-list rule)) | |
116 (header (ebnf-node-list rule)) | |
117 before elt) | |
118 (while seq | |
119 (setq elt (car seq)) | |
120 (if (ebnf-eliminate-empty elt) | |
121 (setq before seq) | |
122 (if before | |
123 (setcdr before (cdr seq)) | |
124 (setq header (cdr header)))) | |
125 (setq seq (cdr seq))) | |
126 (when header | |
127 (ebnf-node-list rule header) | |
128 rule))) | |
129 ;; alternative | |
130 ((eq kind 'ebnf-generate-alternative) | |
131 (let ((seq (ebnf-node-list rule)) | |
132 (header (ebnf-node-list rule)) | |
133 before elt) | |
134 (while seq | |
135 (setq elt (car seq)) | |
136 (if (ebnf-eliminate-empty elt) | |
137 (setq before seq) | |
138 (if before | |
139 (setcdr before (cdr seq)) | |
140 (setq header (cdr header)))) | |
141 (setq seq (cdr seq))) | |
142 (when header | |
143 (if (= (length header) 1) | |
144 (car header) | |
145 (ebnf-node-list rule header) | |
146 rule)))) | |
147 ;; production | |
148 ((eq kind 'ebnf-generate-production) | |
149 (let ((prod (ebnf-eliminate-empty (ebnf-node-production rule)))) | |
150 (when prod | |
151 (ebnf-node-production rule prod) | |
152 rule))) | |
153 ;; terminal, special and empty | |
154 (t | |
155 rule) | |
156 ))) | |
157 | |
158 | |
159 ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; | |
160 ;; Optimizations | |
161 | |
162 | |
163 ;; *To be implemented*: | |
164 ;; left recursion: | |
165 ;; A = B | A C B | A C D. ==> A = B {C (B | D)}*. | |
166 | |
167 ;; right recursion: | |
168 ;; A = B | C A. ==> A = {C}* B. | |
169 ;; A = B | D | C A | E A. ==> A = { C | E }* ( B | D ). | |
170 | |
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. | |
175 | |
176 | |
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 }*. | |
184 | |
185 ;; optional: | |
186 ;; A = B | . ==> A = [B]. | |
187 ;; A = | B . ==> A = [B]. | |
188 | |
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. | |
193 | |
194 ;; none: | |
195 ;; A = B | C | . ==> A = B | C | . | |
196 ;; A = B | C A D. ==> A = B | C A D. | |
197 | |
198 (defun ebnf-optimize (syntax-list) | |
199 "Syntatic chart optimizer." | |
200 (if (not ebnf-optimize) | |
201 syntax-list | |
202 (let ((ebnf-total (length syntax-list)) | |
203 (ebnf-nprod 0) | |
204 new) | |
205 (while syntax-list | |
206 (setq new (cons (ebnf-optimize1 (car syntax-list)) new) | |
207 syntax-list (cdr syntax-list))) | |
208 (nreverse new)))) | |
209 | |
210 | |
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 }*. | |
217 | |
218 ;; optional: | |
219 ;; 6. A = B | . ==> A = [B]. | |
220 ;; 7. A = | B . ==> A = [B]. | |
221 | |
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. | |
226 | |
227 (defun ebnf-optimize1 (prod) | |
228 (ebnf-message-info "Optimizing syntatic chart") | |
229 (let ((production (ebnf-node-production prod))) | |
230 (and (eq (ebnf-node-kind production) 'ebnf-generate-alternative) | |
231 (let* ((hlist (ebnf-split-header-prefix | |
232 (ebnf-node-list production) | |
233 (ebnf-node-name prod))) | |
234 (nlist (car hlist)) | |
235 (zlist (cdr hlist)) | |
236 (elist (ebnf-split-header-suffix nlist zlist))) | |
237 (ebnf-node-production | |
238 prod | |
239 (cond | |
240 ;; cases 2., 4. | |
241 (elist | |
242 (and (eq elist t) | |
243 (setq elist nil)) | |
244 (setq elist (or (ebnf-prefix-suffix elist) | |
245 elist)) | |
246 (let* ((nl (ebnf-extract-empty nlist)) | |
247 (el (or (ebnf-prefix-suffix (cdr nl)) | |
248 (ebnf-create-alternative (cdr nl))))) | |
249 (if (car nl) | |
250 (ebnf-make-zero-or-more el elist) | |
251 (ebnf-make-one-or-more el elist)))) | |
252 ;; cases 1., 3., 5. | |
253 (zlist | |
254 (let* ((xlist (cdr (ebnf-extract-empty zlist))) | |
255 (znode (ebnf-make-zero-or-more | |
256 (or (ebnf-prefix-suffix xlist) | |
257 (ebnf-create-alternative xlist)))) | |
258 (nnode (ebnf-map-list-to-optional nlist))) | |
259 (and nnode | |
260 (setq nlist (list nnode))) | |
261 (if (or (null nlist) | |
262 (and (= (length nlist) 1) | |
263 (eq (ebnf-node-kind (car nlist)) | |
264 'ebnf-generate-empty))) | |
265 znode | |
266 (ebnf-make-sequence | |
267 (list (or (ebnf-prefix-suffix nlist) | |
268 (ebnf-create-alternative nlist)) | |
269 znode))))) | |
270 ;; cases 6., 7. | |
271 ((ebnf-map-node-to-optional production) | |
272 ) | |
273 ;; cases 8., 9., 10. | |
274 ((ebnf-prefix-suffix nlist) | |
275 ) | |
276 ;; none | |
277 (t | |
278 production) | |
279 )))) | |
280 prod)) | |
281 | |
282 | |
283 (defun ebnf-split-header-prefix (node-list header) | |
284 (let* ((hlist (ebnf-split-header-prefix1 node-list header)) | |
285 (nlist (car hlist)) | |
286 zlist empty-p) | |
287 (while (setq hlist (cdr hlist)) | |
288 (let ((elt (car hlist))) | |
289 (if (eq (ebnf-node-kind elt) 'ebnf-generate-sequence) | |
290 (setq zlist (cons | |
291 (let ((seq (cdr (ebnf-node-list elt)))) | |
292 (if (= (length seq) 1) | |
293 (car seq) | |
294 (ebnf-node-list elt seq) | |
295 elt)) | |
296 zlist)) | |
297 (setq empty-p t)))) | |
298 (and empty-p | |
299 (setq zlist (cons (ebnf-make-empty) | |
300 zlist))) | |
301 (cons nlist (nreverse zlist)))) | |
302 | |
303 | |
304 (defun ebnf-split-header-prefix1 (node-list header) | |
305 (let (hlist nlist) | |
306 (while node-list | |
307 (if (ebnf-node-equal-header (car node-list) header) | |
308 (setq hlist (cons (car node-list) hlist)) | |
309 (setq nlist (cons (car node-list) nlist))) | |
310 (setq node-list (cdr node-list))) | |
311 (cons (nreverse nlist) (nreverse hlist)))) | |
312 | |
313 | |
314 (defun ebnf-node-equal-header (node header) | |
315 (let ((kind (ebnf-node-kind node))) | |
316 (cond | |
317 ((eq kind 'ebnf-generate-sequence) | |
318 (ebnf-node-equal-header (car (ebnf-node-list node)) header)) | |
319 ((eq kind 'ebnf-generate-non-terminal) | |
320 (string= (ebnf-node-name node) header)) | |
321 (t | |
322 nil) | |
323 ))) | |
324 | |
325 | |
326 (defun ebnf-map-node-to-optional (node) | |
327 (and (eq (ebnf-node-kind node) 'ebnf-generate-alternative) | |
328 (ebnf-map-list-to-optional (ebnf-node-list node)))) | |
329 | |
330 | |
331 (defun ebnf-map-list-to-optional (nlist) | |
332 (and (= (length nlist) 2) | |
333 (let ((first (nth 0 nlist)) | |
334 (second (nth 1 nlist))) | |
335 (cond | |
336 ;; empty second | |
337 ((eq (ebnf-node-kind first) 'ebnf-generate-empty) | |
338 (ebnf-make-optional second)) | |
339 ;; first empty | |
340 ((eq (ebnf-node-kind second) 'ebnf-generate-empty) | |
341 (ebnf-make-optional first)) | |
342 ;; first second | |
343 (t | |
344 nil) | |
345 )))) | |
346 | |
347 | |
348 (defun ebnf-extract-empty (elist) | |
349 (let ((now elist) | |
350 before empty-p) | |
351 (while now | |
352 (if (not (eq (ebnf-node-kind (car now)) 'ebnf-generate-empty)) | |
353 (setq before now) | |
354 (setq empty-p t) | |
355 (if before | |
356 (setcdr before (cdr now)) | |
357 (setq elist (cdr elist)))) | |
358 (setq now (cdr now))) | |
359 (cons empty-p elist))) | |
360 | |
361 | |
362 (defun ebnf-split-header-suffix (nlist zlist) | |
363 (let (new empty-p) | |
364 (and (cond | |
365 ((= (length nlist) 1) | |
366 (let ((ok t) | |
367 (elt (car nlist))) | |
368 (while (and ok zlist) | |
369 (setq ok (ebnf-split-header-suffix1 elt (car zlist)) | |
370 zlist (cdr zlist)) | |
371 (if (eq ok t) | |
372 (setq empty-p t) | |
373 (setq new (cons ok new)))) | |
374 ok)) | |
375 ((= (length nlist) (length zlist)) | |
376 (let ((ok t)) | |
377 (while (and ok zlist) | |
378 (setq ok (ebnf-split-header-suffix1 (car nlist) (car zlist)) | |
379 nlist (cdr nlist) | |
380 zlist (cdr zlist)) | |
381 (if (eq ok t) | |
382 (setq empty-p t) | |
383 (setq new (cons ok new)))) | |
384 ok)) | |
385 (t | |
386 nil) | |
387 ) | |
388 (let* ((lis (ebnf-unique-list new)) | |
389 (len (length lis))) | |
390 (cond | |
391 ((zerop len) | |
392 t) | |
393 ((= len 1) | |
394 (setq lis (car lis)) | |
395 (if empty-p | |
396 (ebnf-make-optional lis) | |
397 lis)) | |
398 (t | |
399 (and empty-p | |
400 (setq lis (cons (ebnf-make-empty) lis))) | |
401 (ebnf-create-alternative (nreverse lis))) | |
402 ))))) | |
403 | |
404 | |
405 (defun ebnf-split-header-suffix1 (ne ze) | |
406 (cond | |
407 ((eq (ebnf-node-kind ne) 'ebnf-generate-sequence) | |
408 (and (eq (ebnf-node-kind ze) 'ebnf-generate-sequence) | |
409 (let ((nl (ebnf-node-list ne)) | |
410 (zl (ebnf-node-list ze)) | |
411 len z) | |
412 (and (>= (length zl) (length nl)) | |
413 (let ((ok t)) | |
414 (setq len (- (length zl) (length nl)) | |
415 z (nthcdr len zl)) | |
416 (while (and ok z) | |
417 (setq ok (ebnf-node-equal (car z) (car nl)) | |
418 z (cdr z) | |
419 nl (cdr nl))) | |
420 ok) | |
421 (if (zerop len) | |
422 t | |
423 (setcdr (nthcdr (1- len) zl) nil) | |
424 ze))))) | |
425 ((eq (ebnf-node-kind ze) 'ebnf-generate-sequence) | |
426 (let* ((zl (ebnf-node-list ze)) | |
427 (len (length zl))) | |
428 (and (ebnf-node-equal ne (car (nthcdr (1- len) zl))) | |
429 (cond | |
430 ((= len 1) | |
431 t) | |
432 ((= len 2) | |
433 (car zl)) | |
434 (t | |
435 (setcdr (nthcdr (- len 2) zl) nil) | |
436 ze) | |
437 )))) | |
438 (t | |
439 (ebnf-node-equal ne ze)) | |
440 )) | |
441 | |
442 | |
443 (defun ebnf-prefix-suffix (lis) | |
444 (and lis (listp lis) | |
445 (let* ((prefix (ebnf-split-prefix lis)) | |
446 (suffix (ebnf-split-suffix (cdr prefix))) | |
447 (middle (cdr suffix))) | |
448 (setq prefix (car prefix) | |
449 suffix (car suffix)) | |
450 (and (or prefix suffix) | |
451 (ebnf-make-sequence | |
452 (nconc prefix | |
453 (and middle | |
454 (list (or (ebnf-map-list-to-optional middle) | |
455 (ebnf-create-alternative middle)))) | |
456 suffix)))))) | |
457 | |
458 | |
459 (defun ebnf-split-prefix (lis) | |
460 (let* ((len (length lis)) | |
461 (tail lis) | |
462 (head (if (eq (ebnf-node-kind (car lis)) 'ebnf-generate-sequence) | |
463 (ebnf-node-list (car lis)) | |
464 (list (car lis)))) | |
465 (ipre (1+ len))) | |
466 ;; determine prefix length | |
467 (while (and (> ipre 0) (setq tail (cdr tail))) | |
468 (let ((cur head) | |
469 (this (if (eq (ebnf-node-kind (car tail)) 'ebnf-generate-sequence) | |
470 (ebnf-node-list (car tail)) | |
471 (list (car tail)))) | |
472 (i 0)) | |
473 (while (and cur this | |
474 (ebnf-node-equal (car cur) (car this))) | |
475 (setq cur (cdr cur) | |
476 this (cdr this) | |
477 i (1+ i))) | |
478 (setq ipre (min ipre i)))) | |
479 (if (or (zerop ipre) (> ipre len)) | |
480 ;; no prefix at all | |
481 (cons nil lis) | |
482 (let* ((tail (nthcdr ipre head)) | |
483 ;; get prefix | |
484 (prefix (progn | |
485 (and tail | |
486 (setcdr (nthcdr (1- ipre) head) nil)) | |
487 head)) | |
488 empty-p before) | |
489 ;; adjust first element | |
490 (if (or (not (eq (ebnf-node-kind (car lis)) 'ebnf-generate-sequence)) | |
491 (null tail)) | |
492 (setq lis (cdr lis) | |
493 tail lis | |
494 empty-p t) | |
495 (if (= (length tail) 1) | |
496 (setcar lis (car tail)) | |
497 (ebnf-node-list (car lis) tail)) | |
498 (setq tail (cdr lis))) | |
499 ;; eliminate prefix from lis based on ipre | |
500 (while tail | |
501 (let ((elt (car tail)) | |
502 rest) | |
503 (if (and (eq (ebnf-node-kind elt) 'ebnf-generate-sequence) | |
504 (setq rest (nthcdr ipre (ebnf-node-list elt)))) | |
505 (progn | |
506 (if (= (length rest) 1) | |
507 (setcar tail (car rest)) | |
508 (ebnf-node-list elt rest)) | |
509 (setq before tail)) | |
510 (setq empty-p t) | |
511 (if before | |
512 (setcdr before (cdr tail)) | |
513 (setq lis (cdr lis)))) | |
514 (setq tail (cdr tail)))) | |
515 (cons prefix (ebnf-unique-list | |
516 (if empty-p | |
517 (nconc lis (list (ebnf-make-empty))) | |
518 lis))))))) | |
519 | |
520 | |
521 (defun ebnf-split-suffix (lis) | |
522 (let* ((len (length lis)) | |
523 (tail lis) | |
524 (head (nreverse | |
525 (if (eq (ebnf-node-kind (car lis)) 'ebnf-generate-sequence) | |
526 (ebnf-node-list (car lis)) | |
527 (list (car lis))))) | |
528 (isuf (1+ len))) | |
529 ;; determine suffix length | |
530 (while (and (> isuf 0) (setq tail (cdr tail))) | |
531 (let* ((cur head) | |
532 (tlis (nreverse | |
533 (if (eq (ebnf-node-kind (car tail)) 'ebnf-generate-sequence) | |
534 (ebnf-node-list (car tail)) | |
535 (list (car tail))))) | |
536 (this tlis) | |
537 (i 0)) | |
538 (while (and cur this | |
539 (ebnf-node-equal (car cur) (car this))) | |
540 (setq cur (cdr cur) | |
541 this (cdr this) | |
542 i (1+ i))) | |
543 (nreverse tlis) | |
544 (setq isuf (min isuf i)))) | |
545 (setq head (nreverse head)) | |
546 (if (or (zerop isuf) (> isuf len)) | |
547 ;; no suffix at all | |
548 (cons nil lis) | |
549 (let* ((n (- (length head) isuf)) | |
550 ;; get suffix | |
551 (suffix (nthcdr n head)) | |
552 (tail (and (> n 0) | |
553 (progn | |
554 (setcdr (nthcdr (1- n) head) nil) | |
555 head))) | |
556 before empty-p) | |
557 ;; adjust first element | |
558 (if (or (not (eq (ebnf-node-kind (car lis)) 'ebnf-generate-sequence)) | |
559 (null tail)) | |
560 (setq lis (cdr lis) | |
561 tail lis | |
562 empty-p t) | |
563 (if (= (length tail) 1) | |
564 (setcar lis (car tail)) | |
565 (ebnf-node-list (car lis) tail)) | |
566 (setq tail (cdr lis))) | |
567 ;; eliminate suffix from lis based on isuf | |
568 (while tail | |
569 (let ((elt (car tail)) | |
570 rest) | |
571 (if (and (eq (ebnf-node-kind elt) 'ebnf-generate-sequence) | |
572 (setq rest (ebnf-node-list elt) | |
573 n (- (length rest) isuf)) | |
574 (> n 0)) | |
575 (progn | |
576 (if (= n 1) | |
577 (setcar tail (car rest)) | |
578 (setcdr (nthcdr (1- n) rest) nil) | |
579 (ebnf-node-list elt rest)) | |
580 (setq before tail)) | |
581 (setq empty-p t) | |
582 (if before | |
583 (setcdr before (cdr tail)) | |
584 (setq lis (cdr lis)))) | |
585 (setq tail (cdr tail)))) | |
586 (cons suffix (ebnf-unique-list | |
587 (if empty-p | |
588 (nconc lis (list (ebnf-make-empty))) | |
589 lis))))))) | |
590 | |
591 | |
592 (defun ebnf-unique-list (nlist) | |
593 (let ((current nlist) | |
594 before) | |
595 (while current | |
596 (let ((tail (cdr current)) | |
597 (head (car current)) | |
598 remove-p) | |
599 (while tail | |
600 (if (not (ebnf-node-equal head (car tail))) | |
601 (setq tail (cdr tail)) | |
602 (setq remove-p t | |
603 tail nil) | |
604 (if before | |
605 (setcdr before (cdr current)) | |
606 (setq nlist (cdr nlist))))) | |
607 (or remove-p | |
608 (setq before current)) | |
609 (setq current (cdr current)))) | |
610 nlist)) | |
611 | |
612 | |
613 (defun ebnf-node-equal (A B) | |
614 (let ((kindA (ebnf-node-kind A)) | |
615 (kindB (ebnf-node-kind B))) | |
616 (and (eq kindA kindB) | |
617 (cond | |
618 ;; empty | |
619 ((eq kindA 'ebnf-generate-empty) | |
620 t) | |
621 ;; non-terminal, terminal, special | |
622 ((memq kindA '(ebnf-generate-non-terminal | |
623 ebnf-generate-terminal | |
624 ebnf-generate-special)) | |
625 (string= (ebnf-node-name A) (ebnf-node-name B))) | |
626 ;; alternative, sequence | |
627 ((memq kindA '(ebnf-generate-alternative ; any order | |
628 ebnf-generate-sequence)) ; order is important | |
629 (let ((listA (ebnf-node-list A)) | |
630 (listB (ebnf-node-list B))) | |
631 (and (= (length listA) (length listB)) | |
632 (let ((ok t)) | |
633 (while (and ok listA) | |
634 (setq ok (ebnf-node-equal (car listA) (car listB)) | |
635 listA (cdr listA) | |
636 listB (cdr listB))) | |
637 ok)))) | |
638 ;; production | |
639 ((eq kindA 'ebnf-generate-production) | |
640 (and (string= (ebnf-node-name A) (ebnf-node-name B)) | |
641 (ebnf-node-equal (ebnf-node-production A) | |
642 (ebnf-node-production B)))) | |
643 ;; otherwise | |
644 (t | |
645 nil) | |
646 )))) | |
647 | |
648 | |
649 (defun ebnf-create-alternative (alt) | |
650 (if (> (length alt) 1) | |
651 (ebnf-make-alternative alt) | |
652 (car alt))) | |
653 | |
654 | |
655 ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; | |
656 | |
657 | |
658 (provide 'ebnf-otz) | |
659 | |
660 | |
661 ;;; ebnf-otz.el ends here |