1 ;;; ebnf-abn.el --- parser for ABNF (Augmented BNF)
3 ;; Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006
4 ;; Free Sofware Foundation, Inc.
6 ;; Author: Vinicius Jose Latorre <viniciusjl@ig.com.br>
7 ;; Maintainer: Vinicius Jose Latorre <viniciusjl@ig.com.br>
8 ;; Time-stamp: <2004/04/03 16:43:57 vinicius>
9 ;; Keywords: wp, ebnf, PostScript
12 ;; This file is part of GNU Emacs.
14 ;; GNU Emacs is free software; you can redistribute it and/or modify
15 ;; it under the terms of the GNU General Public License as published by
16 ;; the Free Software Foundation; either version 2, or (at your option)
19 ;; GNU Emacs is distributed in the hope that it will be useful,
20 ;; but WITHOUT ANY WARRANTY; without even the implied warranty of
21 ;; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
22 ;; GNU General Public License for more details.
24 ;; You should have received a copy of the GNU General Public License
25 ;; along with GNU Emacs; see the file COPYING. If not, write to the
26 ;; Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
27 ;; Boston, MA 02110-1301, USA.
31 ;; ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
34 ;; This is part of ebnf2ps package.
36 ;; This package defines a parser for ABNF (Augmented BNF).
38 ;; See ebnf2ps.el for documentation.
45 ;; `http://www.ietf.org/rfc/rfc2234.txt'
47 ;; `http://www.faqs.org/rfcs/rfc2234.html'
49 ;; `http://www.rnp.br/ietf/rfc/rfc2234.txt'
50 ;; ("Augmented BNF for Syntax Specifications: ABNF").
53 ;; rulelist = 1*( rule / (*c-wsp c-nl) )
55 ;; rule = rulename defined-as elements c-nl
56 ;; ; continues if next line starts with white space
58 ;; rulename = ALPHA *(ALPHA / DIGIT / "-")
60 ;; defined-as = *c-wsp ("=" / "=/") *c-wsp
61 ;; ; basic rules definition and incremental
64 ;; elements = alternation *c-wsp
66 ;; c-wsp = WSP / (c-nl WSP)
68 ;; c-nl = comment / CRLF
69 ;; ; comment or newline
71 ;; comment = ";" *(WSP / VCHAR) CRLF
73 ;; alternation = concatenation
74 ;; *(*c-wsp "/" *c-wsp concatenation)
76 ;; concatenation = repetition *(1*c-wsp repetition)
78 ;; repetition = [repeat] element
80 ;; repeat = 1*DIGIT / (*DIGIT "*" *DIGIT)
82 ;; element = rulename / group / option /
83 ;; char-val / num-val / prose-val
85 ;; group = "(" *c-wsp alternation *c-wsp ")"
87 ;; option = "[" *c-wsp alternation *c-wsp "]"
89 ;; char-val = DQUOTE *(%x20-21 / %x23-7E) DQUOTE
90 ;; ; quoted string of SP and VCHAR without DQUOTE
92 ;; num-val = "%" (bin-val / dec-val / hex-val)
94 ;; bin-val = "b" 1*BIT
95 ;; [ 1*("." 1*BIT) / ("-" 1*BIT) ]
96 ;; ; series of concatenated bit values
97 ;; ; or single ONEOF range
99 ;; dec-val = "d" 1*DIGIT
100 ;; [ 1*("." 1*DIGIT) / ("-" 1*DIGIT) ]
102 ;; hex-val = "x" 1*HEXDIG
103 ;; [ 1*("." 1*HEXDIG) / ("-" 1*HEXDIG) ]
105 ;; prose-val = "<" *(%x20-3D / %x3F-7E) ">"
106 ;; ; bracketed string of SP and VCHAR without
108 ;; ; prose description, to be used as last resort
110 ;; ; Core rules -- the coding depends on the system, here is used 7-bit ASCII
112 ;; ALPHA = %x41-5A / %x61-7A
118 ;; ; any 7-bit US-ASCII character, excluding NUL
124 ;; ; Internet standard newline
126 ;; CTL = %x00-1F / %x7F
133 ;; ; " (Double Quote)
135 ;; HEXDIG = DIGIT / "A" / "B" / "C" / "D" / "E" / "F"
143 ;; LWSP = *(WSP / CRLF WSP)
144 ;; ; linear white space (past newline)
153 ;; ; visible (printing) characters
161 ;; 1. Rules name and terminal strings are case INSENSITIVE.
162 ;; So, the following rule names are all equals:
163 ;; Rule-name, rule-Name, rule-name, RULE-NAME
164 ;; Also, the following strings are equals:
165 ;; "abc", "ABC", "aBc", "Abc", "aBC", etc.
167 ;; 2. To have a case SENSITIVE string, use the character notation.
168 ;; For example, to specify the lowercase string "abc", use:
171 ;; 3. There are no implicit spaces between elements, for example, the
178 ;; mumble = foo bar foo
180 ;; Are equivalent to the following rule:
182 ;; mumble = %x61.62.61
184 ;; If spaces are needed, it should be explicit specified, like:
186 ;; spaces = 1*(%x20 / %x09) ; one or more spaces or tabs
188 ;; mumble = foo spaces bar spaces foo
190 ;; 4. Lines starting with space or tab are considered a continuation line.
191 ;; For example, the rule:
201 ;; Differences Between ABNF And ebnf2ps ABNF
202 ;; -----------------------------------------
204 ;; Besides the characters that ABNF accepts, ebnf2ps ABNF accepts also the
205 ;; underscore (_) for rule name and european 8-bit accentuated characters (from
206 ;; \240 to \377) for rule name, string and comment.
209 ;; ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
217 (defvar ebnf-abn-lex nil
218 "Value returned by `ebnf-abn-lex' function.")
221 ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
222 ;; Syntactic analyzer
225 ;;; rulelist = 1*( rule / (*c-wsp c-nl) )
227 (defun ebnf-abn-parser (start)
229 (let ((total (+ (- ebnf-limit start
) 1))
232 rule-list token rule
)
234 (setq token
(ebnf-abn-lex))
235 (and (eq token
'end-of-input
)
236 (error "Invalid ABNF file format"))
237 (and (eq token
'end-of-rule
)
238 (setq token
(ebnf-abn-lex)))
239 (while (not (eq token
'end-of-input
))
242 (/ (* (- (point) bias
) 100.0) total
))
243 (setq token
(ebnf-abn-rule token
)
246 (or (ebnf-add-empty-rule-list rule
)
247 (setq rule-list
(cons rule rule-list
))))
252 ;;; rule = rulename defined-as elements c-nl
253 ;;; ; continues if next line starts with white space
255 ;;; rulename = ALPHA *(ALPHA / DIGIT / "-")
257 ;;; defined-as = *c-wsp ("=" / "=/") *c-wsp
258 ;;; ; basic rules definition and incremental
261 ;;; elements = alternation *c-wsp
263 ;;; c-wsp = WSP / (c-nl WSP)
265 ;;; c-nl = comment / CRLF
266 ;;; ; comment or newline
268 ;;; comment = ";" *(WSP / VCHAR) CRLF
271 (defun ebnf-abn-rule (token)
272 (let ((name ebnf-abn-lex
)
275 (setq ebnf-action nil
)
276 (or (eq token
'non-terminal
)
277 (error "Invalid rule name"))
278 (setq token
(ebnf-abn-lex))
279 (or (memq token
'(equal incremental-alternative
))
280 (error "Invalid rule: missing `=' or `=/'"))
281 (and (eq token
'incremental-alternative
)
282 (setq name
(concat name
" =/")))
283 (setq elements
(ebnf-abn-alternation))
284 (or (memq (car elements
) '(end-of-rule end-of-input
))
285 (error "Invalid rule: there is no end of rule"))
286 (setq elements
(cdr elements
))
287 (ebnf-eps-add-production name
)
289 (ebnf-make-production name elements action
))))
292 ;;; alternation = concatenation
293 ;;; *(*c-wsp "/" *c-wsp concatenation)
296 (defun ebnf-abn-alternation ()
297 (let (body concatenation
)
298 (while (eq (car (setq concatenation
299 (ebnf-abn-concatenation (ebnf-abn-lex))))
301 (setq body
(cons (cdr concatenation
) body
)))
302 (ebnf-token-alternative body concatenation
)))
305 ;;; concatenation = repetition *(1*c-wsp repetition)
308 (defun ebnf-abn-concatenation (token)
309 (let ((term (ebnf-abn-repetition token
))
311 (or (setq token
(car term
)
313 (error "Empty element"))
314 (setq seq
(cons term seq
))
315 (while (setq term
(ebnf-abn-repetition token
)
318 (setq seq
(cons term seq
)))
320 (ebnf-token-sequence seq
))))
323 ;;; repetition = [repeat] element
325 ;;; repeat = 1*DIGIT / (*DIGIT "*" *DIGIT)
328 (defun ebnf-abn-repetition (token)
330 ;; INTEGER [ "*" [ INTEGER ] ]
331 (when (eq token
'integer
)
332 (setq lower ebnf-abn-lex
333 token
(ebnf-abn-lex))
334 (or (eq token
'repeat
)
337 (when (eq token
'repeat
)
338 ;; only * ==> lower & upper are empty string
342 (when (eq (setq token
(ebnf-abn-lex)) 'integer
)
343 (setq upper ebnf-abn-lex
344 token
(ebnf-abn-lex))))
345 (let ((element (ebnf-abn-element token
)))
347 ;; there is a repetition
350 (error "Missing element repetition"))
351 (setq token
(ebnf-abn-lex))
354 ((and (string= lower
"1") (null upper
))
355 (cons token
(ebnf-make-one-or-more element
)))
357 ((or (and (string= lower
"0") (null upper
))
358 (and (string= lower
"") (string= upper
"")))
359 (cons token
(ebnf-make-zero-or-more element
)))
362 (ebnf-token-repeat lower
(cons token element
) upper
))))
363 ;; there is an element
365 (cons (ebnf-abn-lex) element
))
366 ;; something that caller has to deal
368 (cons token nil
))))))
371 ;;; element = rulename / group / option /
372 ;;; char-val / num-val / prose-val
374 ;;; group = "(" *c-wsp alternation *c-wsp ")"
376 ;;; option = "[" *c-wsp alternation *c-wsp "]"
378 ;;; char-val = DQUOTE *(%x20-21 / %x23-7E) DQUOTE
379 ;;; ; quoted string of SP and VCHAR without DQUOTE
381 ;;; num-val = "%" (bin-val / dec-val / hex-val)
383 ;;; bin-val = "b" 1*BIT
384 ;;; [ 1*("." 1*BIT) / ("-" 1*BIT) ]
385 ;;; ; series of concatenated bit values
386 ;;; ; or single ONEOF range
388 ;;; dec-val = "d" 1*DIGIT
389 ;;; [ 1*("." 1*DIGIT) / ("-" 1*DIGIT) ]
391 ;;; hex-val = "x" 1*HEXDIG
392 ;;; [ 1*("." 1*HEXDIG) / ("-" 1*HEXDIG) ]
394 ;;; prose-val = "<" *(%x20-3D / %x3F-7E) ">"
395 ;;; ; bracketed string of SP and VCHAR without
397 ;;; ; prose description, to be used as last resort
400 (defun ebnf-abn-element (token)
403 ((eq token
'terminal
)
404 (ebnf-make-terminal ebnf-abn-lex
))
406 ((eq token
'non-terminal
)
407 (ebnf-make-non-terminal ebnf-abn-lex
))
409 ((eq token
'begin-group
)
410 (let ((body (ebnf-abn-alternation)))
411 (or (eq (car body
) 'end-group
)
412 (error "Missing `)'"))
415 ((eq token
'begin-optional
)
416 (let ((body (ebnf-abn-alternation)))
417 (or (eq (car body
) 'end-optional
)
418 (error "Missing `]'"))
419 (ebnf-token-optional (cdr body
))))
426 ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
430 (defconst ebnf-abn-token-table
(make-vector 256 'error
)
431 "Vector used to map characters to a lexical token.")
434 (defun ebnf-abn-initialize ()
435 "Initialize EBNF token table."
436 ;; control character & control 8-bit character are set to `error'
439 (while (< char ?
\072)
440 (aset ebnf-abn-token-table char
'integer
)
441 (setq char
(1+ char
)))
442 ;; printable character: A-Z
444 (while (< char ?
\133)
445 (aset ebnf-abn-token-table char
'non-terminal
)
446 (setq char
(1+ char
)))
447 ;; printable character: a-z
449 (while (< char ?
\173)
450 (aset ebnf-abn-token-table char
'non-terminal
)
451 (setq char
(1+ char
)))
452 ;; European 8-bit accentuated characters:
454 (while (< char ?
\400)
455 (aset ebnf-abn-token-table char
'non-terminal
)
456 (setq char
(1+ char
)))
457 ;; Override end of line characters:
458 (aset ebnf-abn-token-table ?
\n 'end-of-rule
) ; [NL] linefeed
459 (aset ebnf-abn-token-table ?
\r 'end-of-rule
) ; [CR] carriage return
460 ;; Override space characters:
461 (aset ebnf-abn-token-table ?
\013 'space
) ; [VT] vertical tab
462 (aset ebnf-abn-token-table ?
\t 'space
) ; [HT] horizontal tab
463 (aset ebnf-abn-token-table ?\
'space
) ; [SP] space
464 ;; Override form feed character:
465 (aset ebnf-abn-token-table ?
\f 'form-feed
) ; [FF] form feed
466 ;; Override other lexical characters:
467 (aset ebnf-abn-token-table ?
< 'non-terminal
)
468 (aset ebnf-abn-token-table ?%
'terminal
)
469 (aset ebnf-abn-token-table ?
\" 'terminal
)
470 (aset ebnf-abn-token-table ?\
( 'begin-group
)
471 (aset ebnf-abn-token-table ?\
) 'end-group
)
472 (aset ebnf-abn-token-table ?
* 'repeat
)
473 (aset ebnf-abn-token-table ?
= 'equal
)
474 (aset ebnf-abn-token-table ?\
[ 'begin-optional
)
475 (aset ebnf-abn-token-table ?\
] 'end-optional
)
476 (aset ebnf-abn-token-table ?
/ 'alternative
)
477 ;; Override comment character:
478 (aset ebnf-abn-token-table ?\
; 'comment)))
481 ;; replace the range "\240-\377" (see `ebnf-range-regexp').
482 (defconst ebnf-abn-non-terminal-chars
483 (ebnf-range-regexp "-_0-9A-Za-z" ?
\240 ?
\377))
484 (defconst ebnf-abn-non-terminal-letter-chars
485 (ebnf-range-regexp "A-Za-z" ?
\240 ?
\377))
488 (defun ebnf-abn-lex ()
489 "Lexical analyzer for ABNF.
491 Return a lexical token.
493 See documentation for variable `ebnf-abn-lex'."
494 (if (>= (point) ebnf-limit
)
497 ;; skip spaces and comments
498 (while (if (> (following-char) 255)
502 (setq token
(aref ebnf-abn-token-table
(following-char)))
505 (skip-chars-forward " \013\t" ebnf-limit
)
506 (< (point) ebnf-limit
))
508 (ebnf-abn-skip-comment))
509 ((eq token
'form-feed
)
511 (setq ebnf-action
'form-feed
))
512 ((eq token
'end-of-rule
)
513 (ebnf-abn-skip-end-of-rule))
518 ((>= (point) ebnf-limit
)
522 (error "Invalid character"))
524 ((eq token
'end-of-rule
)
528 (setq ebnf-abn-lex
(ebnf-buffer-substring "0-9"))
530 ;; terminal: "string" or %[bdx]NNN((.NNN)+|-NNN)?
531 ((eq token
'terminal
)
533 (if (= (following-char) ?
\")
535 (ebnf-abn-character)))
537 ;; non-terminal: NAME or <NAME>
538 ((eq token
'non-terminal
)
539 (let ((prose-p (= (following-char) ?
<)))
542 (or (looking-at ebnf-abn-non-terminal-letter-chars
)
543 (error "Invalid prose value")))
545 (ebnf-buffer-substring ebnf-abn-non-terminal-chars
))
547 (or (= (following-char) ?
>)
548 (error "Invalid prose value"))
549 (setq ebnf-abn-lex
(concat "<" ebnf-abn-lex
">"))))
554 (if (/= (following-char) ?
/)
557 'incremental-alternative
))
558 ;; miscellaneous: (, ), [, ], /, *
565 (defun ebnf-abn-skip-end-of-rule ()
568 ;; end of rule ==> 2 or more consecutive end of lines
569 (setq eor-p
(or (> (skip-chars-forward "\r\n" ebnf-limit
) 1)
572 (skip-chars-forward " \013\t" ebnf-limit
)
574 (and (= (following-char) ?\
;)
575 (ebnf-abn-skip-comment))))
579 ;; replace the range "\177-\237" (see `ebnf-range-regexp').
580 (defconst ebnf-abn-comment-chars
581 (ebnf-range-regexp "^\n\000-\010\016-\037" ?
\177 ?
\237))
584 (defun ebnf-abn-skip-comment ()
588 ((and ebnf-eps-executing
(= (following-char) ?\
[))
589 (ebnf-eps-add-context (ebnf-abn-eps-filename)))
591 ((and ebnf-eps-executing
(= (following-char) ?\
]))
592 (ebnf-eps-remove-context (ebnf-abn-eps-filename)))
593 ;; any other action in comment
595 (setq ebnf-action
(aref ebnf-comment-table
(following-char)))
596 (skip-chars-forward ebnf-abn-comment-chars ebnf-limit
))
598 ;; check for a valid end of comment
599 (cond ((>= (point) ebnf-limit
)
601 ((= (following-char) ?
\n)
604 (error "Invalid character"))
608 (defun ebnf-abn-eps-filename ()
610 (ebnf-buffer-substring ebnf-abn-comment-chars
))
613 ;; replace the range "\240-\377" (see `ebnf-range-regexp').
614 (defconst ebnf-abn-string-chars
615 (ebnf-range-regexp " -!#-~" ?
\240 ?
\377))
618 (defun ebnf-abn-string ()
619 (buffer-substring-no-properties
624 (skip-chars-forward ebnf-abn-string-chars ebnf-limit
)
625 (or (= (following-char) ?
\")
626 (error "Missing `\"'"))
632 (defun ebnf-abn-character ()
633 ;; %[bdx]NNN((-NNN)|(.NNN)+)?
634 (buffer-substring-no-properties
638 (let* ((char (following-char))
639 (chars (cond ((or (= char ?B
) (= char ?b
)) "01")
640 ((or (= char ?D
) (= char ?d
)) "0-9")
641 ((or (= char ?X
) (= char ?x
)) "0-9A-Fa-f")
642 (t (error "Invalid terminal value")))))
644 (or (> (skip-chars-forward chars ebnf-limit
) 0)
645 (error "Invalid terminal value"))
646 (if (= (following-char) ?-
)
649 (or (> (skip-chars-forward chars ebnf-limit
) 0)
650 (error "Invalid terminal value range")))
651 (while (= (following-char) ?.
)
653 (or (> (skip-chars-forward chars ebnf-limit
) 0)
654 (error "Invalid terminal value")))))
658 ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
663 ;;; arch-tag: 8d1b3c4d-4226-4393-b9ae-b7ccf07cf779
664 ;;; ebnf-abn.el ends here