[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[elpa] externals/parser-generator 58e5806 129/434: Renamed plugin from p
|
From: |
ELPA Syncer |
|
Subject: |
[elpa] externals/parser-generator 58e5806 129/434: Renamed plugin from parser to parser-generator |
|
Date: |
Mon, 29 Nov 2021 15:59:25 -0500 (EST) |
branch: externals/parser-generator
commit 58e58068f5e1eebbba1548aede2956d34094a2f9
Author: Christian Johansson <christian@cvj.se>
Commit: Christian Johansson <christian@cvj.se>
Renamed plugin from parser to parser-generator
---
Makefile | 6 +-
README.md | 30 +-
parser-lr.el => parser-generator-lr.el | 190 +++----
parser.el => parser-generator.el | 338 ++++++-------
...rser-lr-test.el => parser-generator-lr-test.el} | 144 +++---
test/parser-generator-test.el | 543 +++++++++++++++++++++
test/parser-test.el | 543 ---------------------
7 files changed, 897 insertions(+), 897 deletions(-)
diff --git a/Makefile b/Makefile
index 951c98d..0cd694e 100644
--- a/Makefile
+++ b/Makefile
@@ -4,7 +4,7 @@ ifdef emacs
endif
EMACS_CMD := $(EMACS) -Q -batch -L . -L test/
-EL := parser.el test/parser-test.el
+EL := parser-generator.el parser-generator-lr.el
test/parser-generator-test.el test/parser-generator-lr-test.el
ELC := $(EL:.el=.elc)
.PHONY: clean
@@ -17,11 +17,11 @@ compile:
.PHONY: test
test:
- $(EMACS_CMD) -l test/parser-test.el -f "parser-test"
+ $(EMACS_CMD) -l test/parser-generator-test.el -f "parser-generator-test"
.PHONY: test-lr
test-lr:
- $(EMACS_CMD) -l test/parser-lr-test.el -f "parser-lr-test"
+ $(EMACS_CMD) -l test/parser-generator-lr-test.el -f
"parser-generator-lr-test"
.PHONY: tests
tests: test test-lr
diff --git a/README.md b/README.md
index 1a51a16..cbff6e6 100644
--- a/README.md
+++ b/README.md
@@ -46,12 +46,12 @@ Grammar consists of `N`, `T`, `P` and `S`, where `N` is
non-terminals, `T` is te
* S = `'S`
``` emacs-lisp
-(parser--set-grammar '((S A B C) (a b c) ((S (A B)) (A (B a) e) (B (C b) C) (C
c e)) S))
+(parser-generator--set-grammar '((S A B C) (a b c) ((S (A B)) (A (B a) e) (B
(C b) C) (C c e)) S))
```
### e
-The symbol defined in variable `parser--e-identifier`, with default-value:
'e`, symbolizes the e symbol. The symbol is allowed in some grammars and not in
others.
+The symbol defined in variable `parser-generator--e-identifier`, with
default-value: 'e`, symbolizes the e symbol. The symbol is allowed in some
grammars and not in others.
### Non-terminals
@@ -87,7 +87,7 @@ The start symbol is the entry-point of the grammar and should
be either a string
### Look-ahead number
-Is a simple integer above zero. You set it like this:
`(parser--set-look-ahead-number 1)` for `1` number look-ahead.
+Is a simple integer above zero. You set it like this:
`(parser-generator--set-look-ahead-number 1)` for `1` number look-ahead.
### Syntax-directed-translation (SDT)
@@ -106,14 +106,14 @@ Calculate the first look-ahead number of terminals of the
sentential-form `S`, e
``` emacs-lisp
(require 'ert)
-(parser--set-grammar '((S A B C) (a b c) ((S (A B)) (A (B a) e) (B (C b) C) (C
c e)) S))
-(parser--set-look-ahead-number 2)
-(parser--process-grammar)
+(parser-generator--set-grammar '((S A B C) (a b c) ((S (A B)) (A (B a) e) (B
(C b) C) (C c e)) S))
+(parser-generator--set-look-ahead-number 2)
+(parser-generator--process-grammar)
(should
(equal
'((a) (a c) (a b) (c a) (b a) (e) (c) (b) (c b))
- (parser--first 'S)))
+ (parser-generator--first 'S)))
```
### E-FREE-FIRST(S)
@@ -123,14 +123,14 @@ Calculate the e-free-first look-ahead number of terminals
of sentential-form `S`
``` emacs-lisp
(require 'ert)
-(parser--set-grammar '((S A B C) (a b c) ((S (A B)) (A (B a) e) (B (C b) C) (C
c e)) S))
-(parser--set-look-ahead-number 2)
-(parser--process-grammar)
+(parser-generator--set-grammar '((S A B C) (a b c) ((S (A B)) (A (B a) e) (B
(C b) C) (C c e)) S))
+(parser-generator--set-look-ahead-number 2)
+(parser-generator--process-grammar)
(should
(equal
'((c b) (c a))
- (parser--e-free-first 'S)))
+ (parser-generator--e-free-first 'S)))
```
### FOLLOW(S)
@@ -140,14 +140,14 @@ Calculate the look-ahead number of terminals possibly
following S.
``` emacs-lisp
(require 'ert)
-(parser--set-grammar '((S A B) (a c d f) ((S (A a)) (A B) (B (c f) d)) S))
-(parser--set-look-ahead-number 2)
-(parser--process-grammar)
+(parser-generator--set-grammar '((S A B) (a c d f) ((S (A a)) (A B) (B (c f)
d)) S))
+(parser-generator--set-look-ahead-number 2)
+(parser-generator--process-grammar)
(should
(equal
'((a))
- (parser--follow 'A)))
+ (parser-generator--follow 'A)))
```
## Test
diff --git a/parser-lr.el b/parser-generator-lr.el
similarity index 80%
rename from parser-lr.el
rename to parser-generator-lr.el
index 5a1b9f4..1b3b4c8 100644
--- a/parser-lr.el
+++ b/parser-generator-lr.el
@@ -1,4 +1,4 @@
-;;; parser-el.el --- LR(k) Parser -*- lexical-binding: t -*-
+;;; parser-generator-lr.el --- LR(k) Parser Generator -*- lexical-binding: t
-*-
;;; Commentary:
@@ -7,20 +7,21 @@
;;; Code:
-(require 'parser)
+(require 'parser-generator)
;;; Variables:
-(defvar parser-lr--action-tables
+
+(defvar parser-generator-lr--action-tables
nil
"Action-tables for grammar.")
-(defvar parser-lr--goto-tables
+(defvar parser-generator-lr--goto-tables
nil
"Goto-tables for grammar.")
-(defvar parser-lr--items
+(defvar parser-generator-lr--items
nil
"Hash-table for distinct LR-items in grammar.")
@@ -28,30 +29,29 @@
;; Helper Functions
-(defun parser-lr--reset ()
+(defun parser-generator-lr--reset ()
"Reset variables."
- (setq parser-lr--action-tables nil)
- (setq parser-lr--goto-tables nil)
- (setq parser-lr--items nil))
+ (setq parser-generator-lr--action-tables nil)
+ (setq parser-generator-lr--goto-tables nil)
+ (setq parser-generator-lr--items nil))
;; Main Algorithms
;; Algorithm 5.11, p. 393
-(defun parser-lr--generate-action-tables ()
+(defun parser-generator-lr--generate-action-tables ()
"Generate action-tables for lr-grammar."
- (unless parser-lr--action-tables
+ (unless parser-generator-lr--action-tables
(let ((action-tables)
(states '(shift reduce error))
(added-actions (make-hash-table :test 'equal))
- (goto-tables (parser--hash-to-list parser-lr--goto-tables)))
+ (goto-tables (parser-generator--hash-to-list
parser-generator-lr--goto-tables)))
(dolist (goto-table goto-tables)
(let ((goto-index (car goto-table))
- (gotos (car (cdr goto-table)))
(found-action nil)
(action-table))
- (let ((lr-items (gethash goto-index parser-lr--items)))
+ (let ((lr-items (gethash goto-index parser-generator-lr--items)))
(let ((lr-items-length (length lr-items)))
;; Where u is in (T U e)*k
(dolist (state states)
@@ -71,7 +71,7 @@
(v (nth 3 lr-item)))
(let ((Cv (append C v)))
(when Cv
- (let ((eff (parser--e-free-first Cv)))
+ (let ((eff (parser-generator--e-free-first Cv)))
(when eff
;; Go through eff-items and see if any item
is a valid look-ahead of grammar
;; in that case save in action table a shift
action here
@@ -83,7 +83,7 @@
searching-match
(< eff-index eff-length))
(setq eff-item (nth eff-index eff))
- (when (parser--valid-look-ahead-p
eff-item)
+ (when
(parser-generator--valid-look-ahead-p eff-item)
(let ((hash-key (format "%s-%s-%s"
goto-index state eff-item)))
(unless (gethash hash-key
added-actions)
(puthash hash-key t added-actions)
@@ -103,20 +103,20 @@
(B (nth 1 lr-item))
(u (nth 3 lr-item)))
(unless B
- (setq B (list parser--e-identifier)))
- (when (parser--valid-look-ahead-p u)
+ (setq B (list parser-generator--e-identifier)))
+ (when (parser-generator--valid-look-ahead-p u)
(let ((hash-key (format "%s-%s-%s" goto-index
state u)))
(unless (gethash hash-key added-actions)
(puthash hash-key t added-actions)
(let ((production (list A B)))
- (let ((production-number
(parser--get-grammar-production-number production)))
+ (let ((production-number
(parser-generator--get-grammar-production-number production)))
(unless production-number
(error "Expecting production number for
%s from LR-item %s!" production lr-item))
(if (and
(= production-number 0)
(= (length u) 1)
- (parser--valid-e-p (car u)))
+ (parser-generator--valid-e-p (car u)))
(progn
;; Reduction by first production
;; of empty look-ahead means grammar
has been accepted
@@ -132,33 +132,33 @@
(error (format "Failed to find any action in set %s"
lr-items)))
(setq continue-loop nil)))
(setq lr-item-index (1+ lr-item-index)))))))
- (parser--debug
+ (parser-generator--debug
(message "%s actions %s" goto-index action-table))
(when action-table
- (push (list goto-index (sort action-table 'parser--sort-list))
action-tables))))
+ (push (list goto-index (sort action-table
'parser-generator--sort-list)) action-tables))))
(setq action-tables (nreverse action-tables))
- (setq parser-lr--action-tables (make-hash-table :test 'equal))
+ (setq parser-generator-lr--action-tables (make-hash-table :test 'equal))
(let ((table-length (length action-tables))
(table-index 0))
(while (< table-index table-length)
- (puthash table-index (car (cdr (nth table-index action-tables)))
parser-lr--action-tables)
+ (puthash table-index (car (cdr (nth table-index action-tables)))
parser-generator-lr--action-tables)
(setq table-index (1+ table-index)))))))
;; Algorithm 5.9, p. 389
-(defun parser-lr--generate-goto-tables ()
+(defun parser-generator-lr--generate-goto-tables ()
"Calculate set of valid LR(k) items for grammar and a GOTO-table."
(unless (or
- parser-lr--goto-tables
- parser-lr--items)
- (setq parser-lr--goto-tables nil)
- (setq parser-lr--items (make-hash-table :test 'equal))
+ parser-generator-lr--goto-tables
+ parser-generator-lr--items)
+ (setq parser-generator-lr--goto-tables nil)
+ (setq parser-generator-lr--items (make-hash-table :test 'equal))
(let ((lr-item-set-new-index 0)
(goto-table)
(unmarked-lr-item-sets)
(marked-lr-item-sets (make-hash-table :test 'equal))
- (symbols (append (parser--get-grammar-non-terminals)
(parser--get-grammar-terminals))))
+ (symbols (append (parser-generator--get-grammar-non-terminals)
(parser-generator--get-grammar-terminals))))
- (let ((e-set (parser-lr--items-for-prefix parser--e-identifier)))
+ (let ((e-set (parser-generator-lr--items-for-prefix
parser-generator--e-identifier)))
;;(1) Place V(e) in S. The set V(e) is initially unmarked.
(push `(,lr-item-set-new-index ,e-set) unmarked-lr-item-sets)
(setq lr-item-set-new-index (1+ lr-item-set-new-index)))
@@ -174,7 +174,7 @@
(setq popped-item (pop unmarked-lr-item-sets))
(setq lr-item-set-index (car popped-item))
(setq lr-items (car (cdr popped-item)))
- (parser--debug
+ (parser-generator--debug
(message "lr-item-set-index: %s" lr-item-set-index)
(message "lr-items: %s" lr-items)
(message "popped-item: %s" popped-item))
@@ -182,32 +182,32 @@
;; (2) Mark a
(puthash lr-items lr-item-set-index marked-lr-item-sets)
- (puthash lr-item-set-index lr-items parser-lr--items)
+ (puthash lr-item-set-index lr-items parser-generator-lr--items)
(setq goto-table-table nil)
;; (2) By computing for each X in N u E, GOTO (a, X). (Algorithm 5.8
can be used here.)
;; V(X1,...,Xi) = GOTO(V(X1,...,Xi-1), Xi)
(dolist (symbol symbols)
- (parser--debug
+ (parser-generator--debug
(message "symbol: %s" symbol))
- (let ((prefix-lr-items (parser-lr--items-for-goto lr-items
symbol)))
+ (let ((prefix-lr-items (parser-generator-lr--items-for-goto
lr-items symbol)))
;; If a' = GOTO(a, X) is nonempty
(when prefix-lr-items
- (parser--debug
+ (parser-generator--debug
(message "GOTO(%s, %s) = %s" lr-items symbol prefix-lr-items))
;; and is not already in S
(let ((goto (gethash prefix-lr-items marked-lr-item-sets)))
(if goto
(progn
- (parser--debug
+ (parser-generator--debug
(message "Set already exists in: %s" goto))
(push `(,symbol ,goto) goto-table-table))
- (parser--debug
+ (parser-generator--debug
(message "Set is new"))
;; Note that GOTO(a, X) will always be empty if all items
in a
@@ -218,25 +218,25 @@
(push `(,lr-item-set-new-index ,prefix-lr-items)
unmarked-lr-item-sets)
(setq lr-item-set-new-index (1+
lr-item-set-new-index)))))))
- (setq goto-table-table (sort goto-table-table 'parser--sort-list))
+ (setq goto-table-table (sort goto-table-table
'parser-generator--sort-list))
(push `(,lr-item-set-index ,goto-table-table) goto-table)))
- (setq goto-table (sort goto-table 'parser--sort-list))
- (setq parser-lr--goto-tables (make-hash-table :test 'equal))
+ (setq goto-table (sort goto-table 'parser-generator--sort-list))
+ (setq parser-generator-lr--goto-tables (make-hash-table :test 'equal))
(let ((table-length (length goto-table))
(table-index 0))
(while (< table-index table-length)
- (puthash table-index (car (cdr (nth table-index goto-table)))
parser-lr--goto-tables)
+ (puthash table-index (car (cdr (nth table-index goto-table)))
parser-generator-lr--goto-tables)
(setq table-index (1+ table-index)))))
(unless
- (parser-lr--items-valid-p
- (parser--hash-values-to-list parser-lr--items t)) ;; TODO Should not
use this debug function
+ (parser-generator-lr--items-valid-p
+ (parser-generator--hash-values-to-list parser-generator-lr--items t))
;; TODO Should not use this debug function
(error "Inconsistent grammar!"))))
;; Algorithm 5.10, p. 391
-(defun parser-lr--items-valid-p (lr-item-sets)
+(defun parser-generator-lr--items-valid-p (lr-item-sets)
"Return whether the set collection LR-ITEM-SETS is valid or not."
- (parser--debug
+ (parser-generator--debug
(message "lr-item-sets: %s" lr-item-sets))
(let ((valid-p t)
(set-index 0)
@@ -259,7 +259,7 @@
valid-p
(< set-index sets-length))
(setq set (nth set-index lr-item-sets))
- (parser--debug
+ (parser-generator--debug
(message "set: %s" set))
;; Iterate each set
@@ -272,7 +272,7 @@
(setq a (nth a-index set))
(setq a-look-ahead (nth 2 a))
- (parser--debug
+ (parser-generator--debug
(message "a: %s" a)
(message "a-look-ahead: %s" a-look-ahead))
@@ -282,7 +282,7 @@
(not a-look-ahead))
(setq a-follow (nth 3 a))
- (parser--debug
+ (parser-generator--debug
(message "a-follow: %s" a-follow))
;; Iterate each set again
@@ -294,9 +294,9 @@
(setq b-suffix (nth 2 b))
(setq b-follow (nth 3 b))
(setq b-suffix-follow (append b-suffix b-follow))
- (setq b-suffix-follow-eff (parser--e-free-first b-suffix-follow))
+ (setq b-suffix-follow-eff (parser-generator--e-free-first
b-suffix-follow))
- (parser--debug
+ (parser-generator--debug
(message "b: %s" b)
(message "b-suffix: %s" b-suffix)
(message "b-follow: %s" b-follow)
@@ -305,7 +305,7 @@
(dolist (b-suffix-follow-eff-item b-suffix-follow-eff)
(when (equal a-follow b-suffix-follow-eff-item)
- (parser--debug
+ (parser-generator--debug
(message "Inconsistent grammar! %s conflicts with %s" a b))
(setq valid-p nil))))
(setq b-index (1+ b-index))))
@@ -315,12 +315,12 @@
valid-p))
;; Algorithm 5.8, p. 386
-(defun parser-lr--items-for-prefix (γ)
+(defun parser-generator-lr--items-for-prefix (γ)
"Calculate valid LR-items for the viable prefix Γ."
- (let ((start (parser--get-grammar-start)))
+ (let ((start (parser-generator--get-grammar-start)))
(unless (listp γ)
(setq γ (list γ)))
- (unless (parser--valid-sentential-form-p γ)
+ (unless (parser-generator--valid-sentential-form-p γ)
(error "Invalid sentential form γ!"))
(let ((lr-item-exists (make-hash-table :test 'equal)))
@@ -329,13 +329,13 @@
;; Iterate all productions in grammar
(let ((lr-items-e)
- (start-productions (parser--get-grammar-rhs start)))
+ (start-productions (parser-generator--get-grammar-rhs start)))
;; (a)
(dolist (rhs start-productions)
;; Add [S -> . α] to V(e)
(push `(,start nil ,rhs (e)) lr-items-e)
- (puthash `(,parser--e-identifier ,start nil ,rhs
(,parser--e-identifier)) t lr-item-exists))
+ (puthash `(,parser-generator--e-identifier ,start nil ,rhs
(,parser-generator--e-identifier)) t lr-item-exists))
;; (b) Iterate every item in v-set(e), if [A -> . Bα, u] is an item
and B -> β is in P
;; then for each x in FIRST(αu) add [B -> . β, x] to v-set(e),
provided it is not already there
@@ -356,17 +356,17 @@
;; Check if RHS starts with a non-terminal
(let ((rhs-first (car rhs)))
- (parser--debug
+ (parser-generator--debug
(message "rhs-first: %s" rhs-first))
- (when (parser--valid-non-terminal-p rhs-first)
+ (when (parser-generator--valid-non-terminal-p rhs-first)
(let ((rhs-rest (append (cdr rhs) suffix)))
- (let ((rhs-rest-first (parser--first rhs-rest)))
- (parser--debug
+ (let ((rhs-rest-first (parser-generator--first
rhs-rest)))
+ (parser-generator--debug
(message "rhs-rest-first: %s" rhs-rest-first))
(unless rhs-rest-first
- (setq rhs-rest-first `((,parser--e-identifier))))
- (let ((sub-production (parser--get-grammar-rhs
rhs-first)))
- (parser--debug
+ (setq rhs-rest-first
`((,parser-generator--e-identifier))))
+ (let ((sub-production
(parser-generator--get-grammar-rhs rhs-first)))
+ (parser-generator--debug
(message "sub-production: %s" sub-production))
;; For each production with B as LHS
@@ -375,15 +375,15 @@
;; Set follow to nil if it's the e-identifier
(when (and
(= (length sub-rhs) 1)
- (parser--valid-e-p (car sub-rhs)))
+ (parser-generator--valid-e-p (car
sub-rhs)))
(setq sub-rhs nil))
- (parser--debug
+ (parser-generator--debug
(message "sub-rhs: %s" sub-rhs))
;; For each x in FIRST(αu)
(dolist (f rhs-rest-first)
- (parser--debug
+ (parser-generator--debug
(message "f: %s" f))
;; Add [B -> . β, x] to V(e), provided it is
not already there
@@ -394,37 +394,37 @@
;; (c) Repeat (b) until no more items can be
added to V(e)
(setq found-new t))))))))))))))
- (parser--debug
+ (parser-generator--debug
(message "V(e) = %s" lr-items-e))
- (setq lr-items-e (sort lr-items-e 'parser--sort-list))
+ (setq lr-items-e (sort lr-items-e 'parser-generator--sort-list))
;; 2 Suppose that we have constructed V(X1,X2,...,Xi-1) we construct
V(X1,X2,...,Xi) as follows:
;; Only do this step if prefix is not the e-identifier
(let ((prefix-previous lr-items-e))
(unless (and
(= (length γ) 1)
- (parser--valid-e-p (car γ)))
+ (parser-generator--valid-e-p (car γ)))
(dolist (prefix γ)
(let ((lr-new-item))
- (setq lr-new-item (parser-lr--items-for-goto prefix-previous
prefix))
+ (setq lr-new-item (parser-generator-lr--items-for-goto
prefix-previous prefix))
- (parser--debug
+ (parser-generator--debug
(message "prefix: %s" prefix)
(message "prefix-previous: %s" prefix-previous)
(message "lr-new-item: %s" lr-new-item))
(setq prefix-previous lr-new-item))))
- (parser--debug
+ (parser-generator--debug
(message "γ: %s" γ))
prefix-previous)))))
-(defun parser-lr--items-for-goto (previous-lr-item x)
+(defun parser-generator-lr--items-for-goto (previous-lr-item x)
"Calculate LR-items for GOTO(PREVIOUS-LR-ITEM, X)."
(let ((lr-new-item)
(lr-item-exists (make-hash-table :test 'equal)))
- (parser--debug (message "x: %s" x))
+ (parser-generator--debug (message "x: %s" x))
(dolist (lr-item previous-lr-item)
(let ((lr-item-lhs (nth 0 lr-item))
@@ -439,7 +439,7 @@
;; Add [A -> aXi . B, u] to V(X1,...,Xi)
(let ((combined-prefix (append lr-item-prefix (list x))))
- (parser--debug
+ (parser-generator--debug
(message "lr-new-item-1: %s" `(,lr-item-lhs ,combined-prefix
,lr-item-suffix-rest ,lr-item-look-ahead)))
(push `(,lr-item-lhs ,combined-prefix ,lr-item-suffix-rest
,lr-item-look-ahead) lr-new-item))))))
@@ -454,12 +454,12 @@
;; (b) If [A -> a . Bb, u] has been placed in V(X1,...,Xi)
;; and B -> D is in P
- (when (parser--valid-non-terminal-p lr-item-suffix-first)
+ (when (parser-generator--valid-non-terminal-p
lr-item-suffix-first)
- (let ((lr-item-suffix-rest-first (parser--first
lr-item-suffix-rest)))
+ (let ((lr-item-suffix-rest-first (parser-generator--first
lr-item-suffix-rest)))
(unless lr-item-suffix-rest-first
(setq lr-item-suffix-rest-first (list nil)))
- (let ((sub-production (parser--get-grammar-rhs
lr-item-suffix-first)))
+ (let ((sub-production (parser-generator--get-grammar-rhs
lr-item-suffix-first)))
;; For each production with B as LHS
(dolist (sub-rhs sub-production)
@@ -467,7 +467,7 @@
;; Transform e-productions into nil
(when (and
(= (length sub-rhs) 1)
- (parser--valid-e-p (car sub-rhs)))
+ (parser-generator--valid-e-p (car sub-rhs)))
(setq sub-rhs nil))
;; For each x in FIRST(αu)
@@ -478,11 +478,11 @@
(let ((lr-item-to-add `(,lr-item-suffix-first nil
,sub-rhs ,f)))
(unless (gethash lr-item-to-add lr-item-exists)
(setq added-new t)
- (parser--debug (message "lr-item-to-add: %s"
lr-item-to-add))
+ (parser-generator--debug (message "lr-item-to-add:
%s" lr-item-to-add))
(puthash lr-item-to-add t lr-item-exists)
(push lr-item-to-add lr-new-item)))))))))))))
- (setq lr-new-item (sort lr-new-item 'parser--sort-list))
+ (setq lr-new-item (sort lr-new-item 'parser-generator--sort-list))
lr-new-item))
;; Algorithm 5.7, p. 375
@@ -490,7 +490,7 @@
;; TODO Add support for SDT
;; TODO Add support for semantic-actions
;; TODO Consider case with 2 character look-ahead
-(defun parser-lr--parse (input-tape &optional input-tape-index pushdown-list)
+(defun parser-generator-lr--parse (input-tape &optional input-tape-index
pushdown-list)
"Perform a LR-parse of INPUT-TAPE optionally at INPUT-TAPE-INDEX with
PUSHDOWN-LIST."
(unless input-tape-index
(setq input-tape-index 0))
@@ -498,8 +498,8 @@
(push 0 pushdown-list))
;; Make sure tables exists
- (parser-lr--generate-goto-tables)
- (parser-lr--generate-action-tables)
+ (parser-generator-lr--generate-goto-tables)
+ (parser-generator-lr--generate-action-tables)
(let ((accept nil)
(input-tape-length (length input-tape))
@@ -515,20 +515,20 @@
(while (and
(< look-ahead-input-tape-index input-tape-length)
- (< look-ahead-length parser--look-ahead-number))
+ (< look-ahead-length parser-generator--look-ahead-number))
(push (nth look-ahead-input-tape-index input-tape) look-ahead)
(setq look-ahead-length (1+ look-ahead-length))
(setq look-ahead-input-tape-index (1+ look-ahead-input-tape-index)))
;; If we reached end of input-tape and look-ahead is too small, append
e-identifiers
- (while (< look-ahead-length parser--look-ahead-number)
- (push parser--e-identifier look-ahead)
+ (while (< look-ahead-length parser-generator--look-ahead-number)
+ (push parser-generator--e-identifier look-ahead)
(setq look-ahead-length (1+ look-ahead-length)))
(setq look-ahead (nreverse look-ahead))
(let ((table-index (car pushdown-list)))
- (let ((action-table (gethash table-index parser-lr--action-tables)))
+ (let ((action-table (gethash table-index
parser-generator-lr--action-tables)))
(let ((action-match nil)
(action-table-length (length action-table))
@@ -568,7 +568,7 @@
;; and declare error.
(let ((a (car look-ahead)))
- (let ((goto-table (gethash table-index
parser-lr--goto-tables)))
+ (let ((goto-table (gethash table-index
parser-generator-lr--goto-tables)))
(let ((goto-table-length (length goto-table))
(goto-index 0)
(searching-match t)
@@ -608,10 +608,10 @@
;; the pushdown list and return to step (1)
(let ((production-number (car (cdr action-match))))
- (let ((production (parser--get-grammar-production-by-number
production-number)))
+ (let ((production
(parser-generator--get-grammar-production-by-number production-number)))
(let ((production-lhs (car production))
(production-rhs (car (cdr production))))
- (unless (equal production-rhs (list
parser--e-identifier))
+ (unless (equal production-rhs (list
parser-generator--e-identifier))
(let ((pop-items (* 2 (length production-rhs)))
(popped-items 0))
(while (< popped-items pop-items)
@@ -620,7 +620,7 @@
(push production-number output)
(let ((new-table-index (car pushdown-list)))
- (let ((goto-table (gethash new-table-index
parser-lr--goto-tables)))
+ (let ((goto-table (gethash new-table-index
parser-generator-lr--goto-tables)))
(let ((goto-table-length (length goto-table))
(goto-index 0)
(searching-match t)
@@ -655,6 +655,6 @@
(error "Parsed entire string without getting accepting!"))
(nreverse output)))
-(provide 'parser-lr)
+(provide 'parser-generator-lr)
-;;; parser-lr.el ends here
+;;; parser-generator-lr.el ends here
diff --git a/parser.el b/parser-generator.el
similarity index 72%
rename from parser.el
rename to parser-generator.el
index 90a73f2..3467008 100644
--- a/parser.el
+++ b/parser-generator.el
@@ -1,4 +1,4 @@
-;;; parser.el --- Parser library -*- lexical-binding: t -*-
+;;; parser-generator.el --- Parser Generator library -*- lexical-binding: t -*-
;;; Commentary:
@@ -9,59 +9,59 @@
;;; Variables:
-(defvar parser--allow-e-productions
+(defvar parser-generator--allow-e-productions
nil
"Flag whether e-productions is allowed or not.")
-(defvar parser--debug
+(defvar parser-generator--debug
nil
"Whether to print debug messages or not.")
-(defvar parser--e-identifier
+(defvar parser-generator--e-identifier
'e
"The identifier used for e-symbol. Default value 'e.")
-(defvar parser--grammar
+(defvar parser-generator--grammar
nil
"Current grammar used in parser.")
-(defvar parser--f-sets
+(defvar parser-generator--f-sets
nil
"Generated F-sets for grammar.")
-(defvar parser--f-free-sets
+(defvar parser-generator--f-free-sets
nil
"Generated e-free F-sets for grammar.")
-(defvar parser--lex-analyzer-function
+(defvar parser-generator--lex-analyzer-function
nil
"Function used as lex-analyzer.")
-(defvar parser--look-ahead-number
+(defvar parser-generator--look-ahead-number
nil
"Current look-ahead number used.")
-(defvar parser--table-look-aheads-p
+(defvar parser-generator--table-look-aheads-p
nil
"Hash-table of look-aheads for quick checking.")
-(defvar parser--table-non-terminal-p
+(defvar parser-generator--table-non-terminal-p
nil
"Hash-table of terminals for quick checking.")
-(defvar parser--table-productions-rhs
+(defvar parser-generator--table-productions-rhs
nil
"Hash-table of productions RHS indexed by LHS for quick retrieving.")
-(defvar parser--table-productions-number
+(defvar parser-generator--table-productions-number
nil
"Hash-table indexed by production and value is production-number.")
-(defvar parser--table-productions-number-reverse
+(defvar parser-generator--table-productions-number-reverse
nil
"Hash-table indexed by production-number and value is production.")
-(defvar parser--table-terminal-p
+(defvar parser-generator--table-terminal-p
nil
"Hash-table of non-terminals for quick checking.")
@@ -69,21 +69,21 @@
;; Macros
-(defmacro parser--debug (&rest message)
+(defmacro parser-generator--debug (&rest message)
"Output MESSAGE but only if debug is enabled."
- `(when parser--debug
+ `(when parser-generator--debug
,@message))
;; Helper Functions
-(defun parser--clear-cache ()
+(defun parser-generator--clear-cache ()
"Clear cache."
- (setq parser--f-sets nil)
- (setq parser--f-free-sets nil))
+ (setq parser-generator--f-sets nil)
+ (setq parser-generator--f-free-sets nil))
-(defun parser--distinct (elements)
+(defun parser-generator--distinct (elements)
"Return distinct of ELEMENTS."
(let ((processed (make-hash-table :test 'equal))
(new-elements))
@@ -93,13 +93,13 @@
(push element new-elements)))
(nreverse new-elements)))
-(defun parser--get-grammar-look-aheads ()
+(defun parser-generator--get-grammar-look-aheads ()
"Return all possible look-ahead set."
- (unless parser--look-ahead-number
+ (unless parser-generator--look-ahead-number
(error "No look-ahead number defined!"))
- (let ((terminals (parser--get-grammar-terminals))
+ (let ((terminals (parser-generator--get-grammar-terminals))
(look-aheads)
- (k parser--look-ahead-number)
+ (k parser-generator--look-ahead-number)
(stack '((0 0 nil)))
(marked-paths (make-hash-table :test 'equal))
(added-look-aheads (make-hash-table :test 'equal)))
@@ -137,70 +137,70 @@
(setq look-ahead-to-add (reverse look-ahead)))
(when (= look-ahead-length (1- k))
- (push parser--e-identifier look-ahead)
+ (push parser-generator--e-identifier look-ahead)
(setq look-ahead-to-add (reverse look-ahead))))
(when (= k 1)
- (setq look-ahead-to-add `(,parser--e-identifier))))
+ (setq look-ahead-to-add `(,parser-generator--e-identifier))))
(when (and look-ahead-to-add
(not (gethash look-ahead-to-add added-look-aheads)))
(puthash look-ahead-to-add t added-look-aheads)
(push look-ahead-to-add look-aheads))))))
- (sort look-aheads 'parser--sort-list)))
+ (sort look-aheads 'parser-generator--sort-list)))
-(defun parser--get-grammar-non-terminals (&optional G)
+(defun parser-generator--get-grammar-non-terminals (&optional G)
"Return non-terminals of grammar G."
(unless G
- (if parser--grammar
- (setq G parser--grammar)
+ (if parser-generator--grammar
+ (setq G parser-generator--grammar)
(error "No grammar G defined!")))
(nth 0 G))
-(defun parser--get-grammar-production-number (production)
+(defun parser-generator--get-grammar-production-number (production)
"If PRODUCTION exist, return it's number."
- (unless parser--table-productions-number
+ (unless parser-generator--table-productions-number
(error "Table for production-numbers is undefined!"))
- (gethash production parser--table-productions-number))
+ (gethash production parser-generator--table-productions-number))
-(defun parser--get-grammar-production-by-number (production-number)
+(defun parser-generator--get-grammar-production-by-number (production-number)
"If PRODUCTION-NUMBER exist, return it's production."
- (unless parser--table-productions-number-reverse
+ (unless parser-generator--table-productions-number-reverse
(error "Table for reverse production-numbers is undefined!"))
- (gethash production-number parser--table-productions-number-reverse))
+ (gethash production-number
parser-generator--table-productions-number-reverse))
-(defun parser--get-grammar-productions (&optional G)
+(defun parser-generator--get-grammar-productions (&optional G)
"Return productions of grammar G."
(unless G
- (if parser--grammar
- (setq G parser--grammar)
+ (if parser-generator--grammar
+ (setq G parser-generator--grammar)
(error "No grammar G defined!")))
(nth 2 G))
-(defun parser--get-grammar-rhs (lhs)
+(defun parser-generator--get-grammar-rhs (lhs)
"Return right hand sides of LHS if there is any."
- (unless parser--table-productions-rhs
+ (unless parser-generator--table-productions-rhs
(error "Table for productions RHS indexed by LHS is undefined!"))
- (gethash lhs parser--table-productions-rhs))
+ (gethash lhs parser-generator--table-productions-rhs))
-(defun parser--get-grammar-start (&optional G)
+(defun parser-generator--get-grammar-start (&optional G)
"Return start of grammar G."
(unless G
- (if parser--grammar
- (setq G parser--grammar)
+ (if parser-generator--grammar
+ (setq G parser-generator--grammar)
(error "No grammar G defined!")))
(nth 3 G))
-(defun parser--get-grammar-terminals (&optional G)
+(defun parser-generator--get-grammar-terminals (&optional G)
"Return terminals of grammar G."
(unless G
- (if parser--grammar
- (setq G parser--grammar)
+ (if parser-generator--grammar
+ (setq G parser-generator--grammar)
(error "No grammar G defined!")))
(nth 1 G))
-(defun parser--hash-to-list (hash-table &optional un-sorted)
+(defun parser-generator--hash-to-list (hash-table &optional un-sorted)
"Return a list that represent the HASH-TABLE. Each element is a list: (list
key value), optionally UN-SORTED."
(let (result)
(if (hash-table-p hash-table)
@@ -213,7 +213,7 @@
(sort (nreverse result) (lambda (a b) (< (car a) (car b))))))
nil)))
-(defun parser--hash-values-to-list (hash-table &optional un-sorted)
+(defun parser-generator--hash-values-to-list (hash-table &optional un-sorted)
"Return a list that represent the HASH-TABLE. Each element is a list: (list
key value), optionally UN-SORTED."
(let (result)
(if (hash-table-p hash-table)
@@ -226,32 +226,32 @@
(sort (nreverse result) (lambda (a b) (< (car a) (car b))))))
nil)))
-(defun parser--load-symbols ()
+(defun parser-generator--load-symbols ()
"Load terminals and non-terminals in grammar."
- (let ((terminals (parser--get-grammar-terminals)))
- (setq parser--table-terminal-p (make-hash-table :test 'equal))
+ (let ((terminals (parser-generator--get-grammar-terminals)))
+ (setq parser-generator--table-terminal-p (make-hash-table :test 'equal))
(dolist (terminal terminals)
- (puthash terminal t parser--table-terminal-p)))
+ (puthash terminal t parser-generator--table-terminal-p)))
- (let ((non-terminals (parser--get-grammar-non-terminals)))
- (setq parser--table-non-terminal-p (make-hash-table :test 'equal))
+ (let ((non-terminals (parser-generator--get-grammar-non-terminals)))
+ (setq parser-generator--table-non-terminal-p (make-hash-table :test
'equal))
(dolist (non-terminal non-terminals)
- (puthash non-terminal t parser--table-non-terminal-p)))
+ (puthash non-terminal t parser-generator--table-non-terminal-p)))
- (let ((productions (parser--get-grammar-productions)))
- (setq parser--table-productions-rhs (make-hash-table :test 'equal))
+ (let ((productions (parser-generator--get-grammar-productions)))
+ (setq parser-generator--table-productions-rhs (make-hash-table :test
'equal))
(dolist (p productions)
(let ((lhs (car p))
(rhs (cdr p)))
- (let ((new-value (gethash lhs parser--table-productions-rhs)))
+ (let ((new-value (gethash lhs
parser-generator--table-productions-rhs)))
(dolist (rhs-element rhs)
(unless (listp rhs-element)
(setq rhs-element (list rhs-element)))
(push rhs-element new-value))
- (puthash lhs (nreverse new-value) parser--table-productions-rhs))))
+ (puthash lhs (nreverse new-value)
parser-generator--table-productions-rhs))))
- (setq parser--table-productions-number (make-hash-table :test 'equal))
- (setq parser--table-productions-number-reverse (make-hash-table :test
'equal))
+ (setq parser-generator--table-productions-number (make-hash-table :test
'equal))
+ (setq parser-generator--table-productions-number-reverse (make-hash-table
:test 'equal))
(let ((production-index 0))
(dolist (p productions)
(let ((lhs (car p))
@@ -261,53 +261,53 @@
(unless (listp rhs-element)
(setq rhs-element (list rhs-element)))
(setq production (list lhs rhs-element))
- (parser--debug
+ (parser-generator--debug
(message "Production %s: %s" production-index production))
- (puthash production production-index
parser--table-productions-number)
- (puthash production-index production
parser--table-productions-number-reverse)
+ (puthash production production-index
parser-generator--table-productions-number)
+ (puthash production-index production
parser-generator--table-productions-number-reverse)
(setq production-index (1+ production-index)))))))
- (let ((look-aheads (parser--get-grammar-look-aheads)))
- (setq parser--table-look-aheads-p (make-hash-table :test 'equal))
+ (let ((look-aheads (parser-generator--get-grammar-look-aheads)))
+ (setq parser-generator--table-look-aheads-p (make-hash-table :test 'equal))
(dolist (look-ahead look-aheads)
- (puthash look-ahead t parser--table-look-aheads-p))))
+ (puthash look-ahead t parser-generator--table-look-aheads-p))))
-(defun parser--set-look-ahead-number (k)
+(defun parser-generator--set-look-ahead-number (k)
"Set look-ahead number K."
- (unless (parser--valid-look-ahead-number-p k)
+ (unless (parser-generator--valid-look-ahead-number-p k)
(error "Invalid look-ahead number k!"))
- (setq parser--look-ahead-number k))
+ (setq parser-generator--look-ahead-number k))
-(defun parser--set-allow-e-productions (flag)
+(defun parser-generator--set-allow-e-productions (flag)
"Set FLAG whether e-productions is allowed or not."
- (setq parser--allow-e-productions flag))
+ (setq parser-generator--allow-e-productions flag))
-(defun parser--set-grammar (G)
+(defun parser-generator--set-grammar (G)
"Set grammar G.."
- (unless (parser--valid-grammar-p G)
+ (unless (parser-generator--valid-grammar-p G)
(error "Invalid grammar G!"))
- (setq parser--grammar G))
+ (setq parser-generator--grammar G))
-(defun parser--process-grammar ()
+(defun parser-generator--process-grammar ()
"Process grammar."
- (parser--clear-cache)
- (parser--load-symbols))
+ (parser-generator--clear-cache)
+ (parser-generator--load-symbols))
-(defun parser--load-next-look-ahead ()
+(defun parser-generator--load-next-look-ahead ()
"Load next look-ahead number of tokens via lex-analyzer."
- (unless parser--lex-analyzer-function
+ (unless parser-generator--lex-analyzer-function
(error "Missing lex-analyzer function!"))
- (let ((left parser--look-ahead-number)
+ (let ((left parser-generator--look-ahead-number)
(look-ahead))
(while (> left 0)
- (let ((token (funcall parser--lex-analyzer-function)))
+ (let ((token (funcall parser-generator--lex-analyzer-function)))
(if token
(push token look-ahead)
- (push parser--e-identifier look-ahead)))
+ (push parser-generator--e-identifier look-ahead)))
(setq left (1- left)))
look-ahead))
-(defun parser--sort-list (a b)
+(defun parser-generator--sort-list (a b)
"Return non-nil if a element in A is greater than a element in B in
lexicographic order."
(let ((length (min (length a) (length b)))
(index 0)
@@ -349,11 +349,11 @@
(setq index (1+ index)))
response))
-(defun parser--valid-e-p (symbol)
+(defun parser-generator--valid-e-p (symbol)
"Return whether SYMBOL is the e identifier or not."
- (eq symbol parser--e-identifier))
+ (eq symbol parser-generator--e-identifier))
-(defun parser--valid-grammar-p (G)
+(defun parser-generator--valid-grammar-p (G)
"Return if grammar G is valid or not. Grammar should contain list with 4
elements: non-terminals (N), terminals (T), productions (P), start (S) where N,
T and P are lists containing symbols and/or strings and S is a symbol or
string."
(let ((valid-p t))
(unless (listp G)
@@ -410,7 +410,7 @@
valid-p
(< production-index production-count))
(let ((production (nth production-index productions)))
- (unless (parser--valid-production-p production)
+ (unless (parser-generator--valid-production-p production)
(setq valid-p nil)))
(setq production-index (1+ production-index)))))
@@ -422,27 +422,27 @@
(setq valid-p nil))))
valid-p))
-(defun parser--valid-look-ahead-p (symbol)
+(defun parser-generator--valid-look-ahead-p (symbol)
"Return whether SYMBOL is a look-ahead in grammar or not."
- (unless parser--table-look-aheads-p
+ (unless parser-generator--table-look-aheads-p
(error "Table for look-aheads is undefined!"))
(unless (listp symbol)
(setq symbol (list symbol)))
- (gethash symbol parser--table-look-aheads-p))
+ (gethash symbol parser-generator--table-look-aheads-p))
-(defun parser--valid-look-ahead-number-p (k)
+(defun parser-generator--valid-look-ahead-number-p (k)
"Return if look-ahead number K is valid or not."
(and
(integerp k)
(>= k 0)))
-(defun parser--valid-non-terminal-p (symbol)
+(defun parser-generator--valid-non-terminal-p (symbol)
"Return whether SYMBOL is a non-terminal in grammar or not."
- (unless parser--table-non-terminal-p
+ (unless parser-generator--table-non-terminal-p
(error "Table for non-terminals is undefined!"))
- (gethash symbol parser--table-non-terminal-p))
+ (gethash symbol parser-generator--table-non-terminal-p))
-(defun parser--valid-production-p (production)
+(defun parser-generator--valid-production-p (production)
"Return whether PRODUCTION is valid or not."
(let ((is-valid t))
(unless (listp production)
@@ -502,7 +502,7 @@
(setq rhs-index (1+ rhs-index)))))))
is-valid))
-(defun parser--valid-sentential-form-p (symbols)
+(defun parser-generator--valid-sentential-form-p (symbols)
"Return whether SYMBOLS is a valid sentential form in grammar or not."
(let ((is-valid t))
(let ((symbols-length (length symbols))
@@ -511,43 +511,43 @@
is-valid
(< symbol-index symbols-length))
(let ((symbol (nth symbol-index symbols)))
- (unless (parser--valid-symbol-p symbol)
+ (unless (parser-generator--valid-symbol-p symbol)
(setq is-valid nil)))
(setq symbol-index (1+ symbol-index))))
is-valid))
-(defun parser--valid-symbol-p (symbol)
+(defun parser-generator--valid-symbol-p (symbol)
"Return whether SYMBOL is valid or not."
(let ((is-valid t))
(unless (or
- (parser--valid-e-p symbol)
- (parser--valid-non-terminal-p symbol)
- (parser--valid-terminal-p symbol))
+ (parser-generator--valid-e-p symbol)
+ (parser-generator--valid-non-terminal-p symbol)
+ (parser-generator--valid-terminal-p symbol))
(setq is-valid nil))
is-valid))
-(defun parser--valid-terminal-p (symbol)
+(defun parser-generator--valid-terminal-p (symbol)
"Return whether SYMBOL is a terminal in grammar or not."
- (unless parser--table-terminal-p
+ (unless parser-generator--table-terminal-p
(error "Table for terminals is undefined!"))
- (gethash symbol parser--table-terminal-p))
+ (gethash symbol parser-generator--table-terminal-p))
;; Main Algorithms
;; p. 381
-(defun parser--e-free-first (α)
+(defun parser-generator--e-free-first (α)
"For sentential string Α, Calculate e-free-first k terminals in grammar."
- (parser--first α t))
+ (parser-generator--first α t))
;; p. 358
-(defun parser--f-set (input-tape state stack)
+(defun parser-generator--f-set (input-tape state stack)
"A deterministic push-down transducer (DPDT) for building F-sets from
INPUT-TAPE, STATE and STACK."
(unless (listp input-tape)
(setq input-tape (list input-tape)))
- (parser--debug
- (message "(parser--f-set)")
+ (parser-generator--debug
+ (message "(parser-generator--f-set)")
(message "input-tape: %s" input-tape)
(message "state: %s" state)
(message "stack: %s" stack))
@@ -558,58 +558,58 @@
(i (nth 1 state))
(f-sets (nth 2 state))
(disallow-e-first (nth 3 state)))
- (parser--debug
+ (parser-generator--debug
(message "disallow-e-first: %s" disallow-e-first)
(message "input-tape-length: %s" input-tape-length)
(message "k: %s" k)
(message "i: %s" i))
(while stack
(let ((stack-symbol (pop stack)))
- (parser--debug
+ (parser-generator--debug
(message "Stack-symbol: %s" stack-symbol))
(let ((leading-terminals (nth 0 stack-symbol))
(all-leading-terminals-p (nth 1 stack-symbol))
(input-tape-index (nth 2 stack-symbol))
(e-first-p))
- (parser--debug
+ (parser-generator--debug
(message "leading-terminals: %s" leading-terminals)
(message "all-leading-terminals-p: %s" all-leading-terminals-p)
(message "input-tape-index: %s" input-tape-index))
;; Flag whether leading-terminal is empty or not
- (when (parser--valid-e-p leading-terminals)
+ (when (parser-generator--valid-e-p leading-terminals)
(setq e-first-p t))
- (parser--debug (message "e-first-p: %s" e-first-p))
+ (parser-generator--debug (message "e-first-p: %s" e-first-p))
;; If leading terminal is empty and we have input-tape left,
disregard it
(when (and
(not disallow-e-first)
e-first-p
(< input-tape-index input-tape-length))
- (parser--debug (message "Disregarding empty first terminal"))
+ (parser-generator--debug (message "Disregarding empty first
terminal"))
(setq leading-terminals nil))
(let ((leading-terminals-count (length leading-terminals)))
- (parser--debug (message "leading-terminals-count: %s"
leading-terminals-count))
+ (parser-generator--debug (message "leading-terminals-count: %s"
leading-terminals-count))
(while (and
(< input-tape-index input-tape-length)
(< leading-terminals-count k)
all-leading-terminals-p)
(let ((rhs-element (nth input-tape-index input-tape))
(rhs-type))
- (parser--debug (message "rhs-element: %s" rhs-element))
+ (parser-generator--debug (message "rhs-element: %s"
rhs-element))
;; Determine symbol type
(cond
- ((parser--valid-non-terminal-p rhs-element)
+ ((parser-generator--valid-non-terminal-p rhs-element)
(setq rhs-type 'NON-TERMINAL))
- ((parser--valid-e-p rhs-element)
+ ((parser-generator--valid-e-p rhs-element)
(setq rhs-type 'EMPTY))
- ((parser--valid-terminal-p rhs-element)
+ ((parser-generator--valid-terminal-p rhs-element)
(setq rhs-type 'TERMINAL))
(t (error (format "Invalid symbol %s" rhs-element))))
- (parser--debug (message "rhs-type: %s" rhs-type))
+ (parser-generator--debug (message "rhs-type: %s" rhs-type))
(cond
@@ -618,7 +618,7 @@
(let ((sub-terminal-sets (gethash rhs-element (gethash
(1- i) f-sets))))
(if sub-terminal-sets
(progn
- (parser--debug
+ (parser-generator--debug
(message "Sub-terminal-sets F_%s_%s(%s) = %s
(%d)" (1- i) k rhs-element sub-terminal-sets (length sub-terminal-sets)))
(let ((sub-terminal-set (car sub-terminal-sets)))
@@ -629,11 +629,11 @@
(dolist (sub-terminal-alternative-set
sub-terminal-sets)
(unless (= sub-terminal-index 0)
(let
((alternative-all-leading-terminals-p all-leading-terminals-p))
- (parser--debug (message
"Sub-terminal-alternative-set: %s" sub-terminal-alternative-set))
+ (parser-generator--debug (message
"Sub-terminal-alternative-set: %s" sub-terminal-alternative-set))
;; When sub-set only contains the e
symbol
- (when (parser--valid-e-p (car
sub-terminal-alternative-set))
- (parser--debug (message
"alternative-set is e symbol"))
+ (when (parser-generator--valid-e-p
(car sub-terminal-alternative-set))
+ (parser-generator--debug (message
"alternative-set is e symbol"))
(if disallow-e-first
(when (=
leading-terminals-count 0)
(setq
alternative-all-leading-terminals-p nil))
@@ -641,25 +641,25 @@
(>
leading-terminals-count 0)
(< input-tape-index (1-
input-tape-length)))
(setq
sub-terminal-alternative-set nil)
- (parser--debug (message
"Cleared sub-terminal-alternative-set")))))
+ (parser-generator--debug
(message "Cleared sub-terminal-alternative-set")))))
(let ((sub-rhs-leading-terminals
(append leading-terminals sub-terminal-alternative-set)))
- (parser--debug (message
"sub-rhs-leading-terminals: %s" sub-rhs-leading-terminals))
+ (parser-generator--debug (message
"sub-rhs-leading-terminals: %s" sub-rhs-leading-terminals))
(when (> (length
sub-rhs-leading-terminals) k)
(setq sub-rhs-leading-terminals
(butlast sub-rhs-leading-terminals (- (length sub-rhs-leading-terminals) k))))
(push `(,sub-rhs-leading-terminals
,alternative-all-leading-terminals-p ,(1+ input-tape-index)) stack))))
(setq sub-terminal-index (1+
sub-terminal-index)))))
- (parser--debug (message "Sub-terminal-set: %s"
sub-terminal-set))
+ (parser-generator--debug (message
"Sub-terminal-set: %s" sub-terminal-set))
(when (or
- (not (parser--valid-e-p (car
sub-terminal-set)))
+ (not (parser-generator--valid-e-p (car
sub-terminal-set)))
(= input-tape-index (1-
input-tape-length)))
(setq leading-terminals (append
leading-terminals sub-terminal-set))
(setq leading-terminals-count (+
leading-terminals-count (length sub-terminal-set)))
(when (> leading-terminals-count k)
(setq leading-terminals (butlast
leading-terminals (- leading-terminals-count k)))
(setq leading-terminals-count k)))))
- (parser--debug
+ (parser-generator--debug
(message "Found no subsets for %s %s" rhs-element
(1- i)))
(setq all-leading-terminals-p nil)))
(setq all-leading-terminals-p nil)))
@@ -686,35 +686,35 @@
f-set))
;; Algorithm 5.5, p. 357
-(defun parser--first (β &optional disallow-e-first)
+(defun parser-generator--first (β &optional disallow-e-first)
"For sentential-form Β, calculate first terminals, optionally
DISALLOW-E-FIRST."
(unless (listp β)
(setq β (list β)))
- (unless (parser--valid-sentential-form-p β)
+ (unless (parser-generator--valid-sentential-form-p β)
(error "Invalid sentential form β!"))
- (let ((productions (parser--get-grammar-productions))
- (k parser--look-ahead-number))
+ (let ((productions (parser-generator--get-grammar-productions))
+ (k parser-generator--look-ahead-number))
(let ((i-max (length productions)))
;; Generate F-sets only once per grammar
(when (or
(and
(not disallow-e-first)
- (not parser--f-sets))
+ (not parser-generator--f-sets))
(and
disallow-e-first
- (not parser--f-free-sets)))
+ (not parser-generator--f-free-sets)))
(let ((f-sets (make-hash-table :test 'equal))
(i 0))
(while (< i i-max)
- (parser--debug (message "i = %s" i))
+ (parser-generator--debug (message "i = %s" i))
(let ((f-set (make-hash-table :test 'equal)))
;; Iterate all productions, set F_i
(dolist (p productions)
(let ((production-lhs (car p))
(production-rhs (cdr p)))
- (parser--debug
+ (parser-generator--debug
(message "Production: %s -> %s" production-lhs
production-rhs))
;; Iterate all blocks in RHS
@@ -722,8 +722,8 @@
(dolist (rhs-p production-rhs)
(let ((rhs-string rhs-p))
(let ((rhs-leading-terminals
- (parser--f-set rhs-string `(,k ,i ,f-sets
,disallow-e-first) '(("" t 0)))))
- (parser--debug
+ (parser-generator--f-set rhs-string `(,k ,i
,f-sets ,disallow-e-first) '(("" t 0)))))
+ (parser-generator--debug
(message "Leading %d terminals at index %s (%s) ->
%s = %s" k i production-lhs rhs-string rhs-leading-terminals))
(when rhs-leading-terminals
(when (and
@@ -733,17 +733,17 @@
(push rhs-leading-terminals-element
f-p-set)))))))
;; Make set distinct
- (setq f-p-set (parser--distinct f-p-set))
- (parser--debug
+ (setq f-p-set (parser-generator--distinct f-p-set))
+ (parser-generator--debug
(message "F_%s_%s(%s) = %s" i k production-lhs f-p-set))
(puthash production-lhs (nreverse f-p-set) f-set))))
(puthash i f-set f-sets)
(setq i (+ i 1))))
(if disallow-e-first
- (setq parser--f-free-sets f-sets)
- (setq parser--f-sets f-sets))))
+ (setq parser-generator--f-free-sets f-sets)
+ (setq parser-generator--f-sets f-sets))))
- (parser--debug
+ (parser-generator--debug
(message "Generated F-sets"))
(let ((first-list nil))
@@ -753,7 +753,7 @@
(stack '((0 0 nil))))
(while stack
(let ((stack-topmost (pop stack)))
- (parser--debug
+ (parser-generator--debug
(message "stack-topmost: %s" stack-topmost))
(let ((input-tape-index (car stack-topmost))
(first-length (car (cdr stack-topmost)))
@@ -764,25 +764,25 @@
(< input-tape-index input-tape-length)
(< first-length k))
(let ((symbol (nth input-tape-index input-tape)))
- (parser--debug
+ (parser-generator--debug
(message "symbol index: %s from %s is: %s"
input-tape-index input-tape symbol))
(cond
- ((parser--valid-terminal-p symbol)
+ ((parser-generator--valid-terminal-p symbol)
(setq first (append first (list symbol)))
(setq first-length (1+ first-length)))
- ((parser--valid-non-terminal-p symbol)
- (parser--debug
+ ((parser-generator--valid-non-terminal-p symbol)
+ (parser-generator--debug
(message "non-terminal symbol: %s" symbol))
(let ((symbol-f-set))
(if disallow-e-first
- (setq symbol-f-set (gethash symbol (gethash (1-
i-max) parser--f-free-sets)))
- (setq symbol-f-set (gethash symbol (gethash (1-
i-max) parser--f-sets))))
- (parser--debug
+ (setq symbol-f-set (gethash symbol (gethash (1-
i-max) parser-generator--f-free-sets)))
+ (setq symbol-f-set (gethash symbol (gethash (1-
i-max) parser-generator--f-sets))))
+ (parser-generator--debug
(message "symbol-f-set: %s" symbol-f-set))
(if (not symbol-f-set)
(progn
- (parser--debug
+ (parser-generator--debug
(message "empty symbol-f-set, so stop looking"))
(setq keep-looking nil))
@@ -795,26 +795,26 @@
(let ((alternative-first-length (+
first-length (length symbol-f-set-element)))
(alternative-first (append first
symbol-f-set-element))
(alternative-tape-index (1+
input-tape-index)))
- (parser--debug
+ (parser-generator--debug
(message "alternative-first: %s"
alternative-first))
(push `(,alternative-tape-index
,alternative-first-length ,alternative-first) stack)))
(setq symbol-f-set-index (1+
symbol-f-set-index)))))
- (parser--debug
+ (parser-generator--debug
(message "main-symbol-f-set: %s" (car
symbol-f-set)))
(setq first-length (+ first-length (length (car
symbol-f-set))))
(setq first (append first (car symbol-f-set))))))))
(setq input-tape-index (1+ input-tape-index)))
(when (> first-length 0)
- (parser--debug
+ (parser-generator--debug
(message "push to first-list: %s to %s" first first-list))
(push first first-list))))))
- (setq first-list (sort first-list 'parser--sort-list))
+ (setq first-list (sort first-list 'parser-generator--sort-list))
first-list))))
;; Definition at p. 343
-(defun parser--follow (β)
+(defun parser-generator--follow (β)
"Calculate follow-set of Β. FOLLOW(β) = w, w is the set {w | S =>* αβγ and
w is in FIRST(γ)}."
;; Make sure argument is a list
(unless (listp β)
@@ -822,7 +822,7 @@
(let ((follow-set nil)
(match-length (length β)))
;; Iterate all productions in grammar
- (let ((productions (parser--get-grammar-productions)))
+ (let ((productions (parser-generator--get-grammar-productions)))
(dolist (p productions)
;; Iterate all RHS of every production
(let ((production-rhs (cdr p))
@@ -847,19 +847,19 @@
(when (= match-index match-length)
(if (= rhs-index (1- rhs-count))
;; If rest of RHS is empty add e in follow-set
- (push `(,parser--e-identifier) follow-set)
+ (push `(,parser-generator--e-identifier)
follow-set)
;; Otherwise add FOLLOW(rest) to follow-set
(let ((rest (nthcdr (1+ rhs-index) rhs)))
- (let ((first-set (parser--first rest)))
+ (let ((first-set (parser-generator--first rest)))
(setq follow-set (append first-set
follow-set)))))
(setq match-index 0)))
(when (> match-index 0)
(setq match-index 0))))
(setq rhs-index (1+ rhs-index))))))))
(when (> (length follow-set) 0)
- (setq follow-set (parser--distinct follow-set)))
+ (setq follow-set (parser-generator--distinct follow-set)))
follow-set))
-(provide 'parser)
+(provide 'parser-generator)
-;;; parser.el ends here
+;;; parser-generator.el ends here
diff --git a/test/parser-lr-test.el b/test/parser-generator-lr-test.el
similarity index 51%
rename from test/parser-lr-test.el
rename to test/parser-generator-lr-test.el
index 79f8a49..37b4de8 100644
--- a/test/parser-lr-test.el
+++ b/test/parser-generator-lr-test.el
@@ -1,4 +1,4 @@
-;;; parser-lr-test.el --- Tests for LR(k) Parser -*- lexical-binding: t -*-
+;;; parser-generator-lr-test.el --- Tests for LR(k) Parser Generator -*-
lexical-binding: t -*-
;;; Commentary:
@@ -6,21 +6,21 @@
;;; Code:
-(require 'parser-lr)
+(require 'parser-generator-lr)
(require 'ert)
-(defun parser-lr-test--generate-action-tables ()
- "Test `parser-lr--generate-action-tables'."
- (message "Starting tests for (parser-lr--generate-action-tables)")
+(defun parser-generator-lr-test--generate-action-tables ()
+ "Test `parser-generator-lr--generate-action-tables'."
+ (message "Starting tests for (parser-generator-lr--generate-action-tables)")
;; Example 5.32 p. 393
- (parser--set-grammar '((Sp S) (a b) ((Sp S) (S (S a S b)) (S e)) Sp))
- (parser--set-look-ahead-number 1)
- (parser--process-grammar)
+ (parser-generator--set-grammar '((Sp S) (a b) ((Sp S) (S (S a S b)) (S e))
Sp))
+ (parser-generator--set-look-ahead-number 1)
+ (parser-generator--process-grammar)
- (parser-lr--reset)
- (parser-lr--generate-goto-tables)
- (parser-lr--generate-action-tables)
+ (parser-generator-lr--reset)
+ (parser-generator-lr--generate-goto-tables)
+ (parser-generator-lr--generate-action-tables)
(should
(equal
@@ -32,7 +32,7 @@
(5 nil)
(6 ((a 4) (b 7)))
(7 nil))
- (parser--hash-to-list parser-lr--goto-tables)))
+ (parser-generator--hash-to-list parser-generator-lr--goto-tables)))
(should
(equal
@@ -44,7 +44,7 @@
(5 ((S (S a S b) nil (a)) (S (S a S b) nil (e))))
(6 ((S (S) (a S b) (a)) (S (S) (a S b) (b)) (S (S a S) (b) (a)) (S (S a
S) (b) (b))))
(7 ((S (S a S b) nil (a)) (S (S a S b) nil (b)))))
- (parser--hash-to-list parser-lr--items)))
+ (parser-generator--hash-to-list parser-generator-lr--items)))
;; Fig. 5.9 p. 374
(should
@@ -57,24 +57,24 @@
(5 (((a) reduce 1) ((e) reduce 1)))
(6 (((a) shift) ((b) shift)))
(7 (((a) reduce 1) ((b) reduce 1))))
- (parser--hash-to-list parser-lr--action-tables)))
+ (parser-generator--hash-to-list parser-generator-lr--action-tables)))
- (message "Ended tests for (parser-lr--generate-action-tables)"))
+ (message "Ended tests for (parser-generator-lr--generate-action-tables)"))
-(defun parser-lr-test--generate-goto-tables ()
- "Test `parser-lr--generate-goto-tables'."
- (message "Starting tests for (parser-lr--generate-goto-tables)")
+(defun parser-generator-lr-test--generate-goto-tables ()
+ "Test `parser-generator-lr--generate-goto-tables'."
+ (message "Starting tests for (parser-generator-lr--generate-goto-tables)")
;; Example 5.30, p. 389
- (parser--set-grammar '((Sp S) (a b) ((Sp S) (S (S a S b)) (S e)) Sp))
- (parser--set-look-ahead-number 1)
- (parser--process-grammar)
+ (parser-generator--set-grammar '((Sp S) (a b) ((Sp S) (S (S a S b)) (S e))
Sp))
+ (parser-generator--set-look-ahead-number 1)
+ (parser-generator--process-grammar)
- (parser-lr--reset)
- (parser-lr--generate-goto-tables)
+ (parser-generator-lr--reset)
+ (parser-generator-lr--generate-goto-tables)
- ;; (message "GOTO-table: %s" parser-lr--goto-tables)
- ;; (message "LR-items: %s" (parser--hash-to-list parser-lr--items))
+ ;; (message "GOTO-table: %s" parser-generator-lr--goto-tables)
+ ;; (message "LR-items: %s" (parser-generator--hash-to-list
parser-generator-lr--items))
(should
(equal
@@ -86,7 +86,7 @@
(5 nil)
(6 ((a 4) (b 7)))
(7 nil))
- (parser--hash-to-list parser-lr--goto-tables)))
+ (parser-generator--hash-to-list parser-generator-lr--goto-tables)))
(should
(equal
@@ -98,22 +98,22 @@
(5 ((S (S a S b) nil (a)) (S (S a S b) nil (e))))
(6 ((S (S) (a S b) (a)) (S (S) (a S b) (b)) (S (S a S) (b) (a)) (S (S a
S) (b) (b))))
(7 ((S (S a S b) nil (a)) (S (S a S b) nil (b)))))
- (parser--hash-to-list parser-lr--items)))
+ (parser-generator--hash-to-list parser-generator-lr--items)))
(message "Passed LR-items for example 5.30")
(message "Passed tests for (parser-r--generate-goto-tables)"))
-(defun parser-lr-test--items-for-prefix ()
- "Test `parser-lr--items-for-prefix'."
- (message "Starting tests for (parser-lr--items-for-prefix)")
+(defun parser-generator-lr-test--items-for-prefix ()
+ "Test `parser-generator-lr--items-for-prefix'."
+ (message "Starting tests for (parser-generator-lr--items-for-prefix)")
;; Example 5.29 p 387
- (parser--set-grammar '((Sp S) (a b) ((Sp S) (S (S a S b)) (S e)) Sp))
- (parser--set-look-ahead-number 1)
- (parser--process-grammar)
+ (parser-generator--set-grammar '((Sp S) (a b) ((Sp S) (S (S a S b)) (S e))
Sp))
+ (parser-generator--set-look-ahead-number 1)
+ (parser-generator--process-grammar)
- (parser-lr--reset)
+ (parser-generator-lr--reset)
(should
(equal
@@ -122,7 +122,7 @@
(S nil nil (a))
(S nil nil (e))
(Sp nil (S) (e)))
- (parser-lr--items-for-prefix 'e)))
+ (parser-generator-lr--items-for-prefix 'e)))
(message "Passed V(e)")
(should
@@ -130,19 +130,19 @@
'((S (S) (a S b) (a))
(S (S) (a S b) (e))
(Sp (S) nil (e)))
- (parser-lr--items-for-prefix 'S)))
+ (parser-generator-lr--items-for-prefix 'S)))
(message "Passed V(S)")
(should
(equal
nil
- (parser-lr--items-for-prefix 'a)))
+ (parser-generator-lr--items-for-prefix 'a)))
(message "Passed V(a)")
(should
(equal
nil
- (parser-lr--items-for-prefix 'b)))
+ (parser-generator-lr--items-for-prefix 'b)))
(message "Passed V(b)")
(should
@@ -153,19 +153,19 @@
(S nil (S a S b) (b))
(S nil nil (a))
(S nil nil (b)))
- (parser-lr--items-for-prefix '(S a))))
+ (parser-generator-lr--items-for-prefix '(S a))))
(message "Passed V(Sa)")
(should
(equal
nil
- (parser-lr--items-for-prefix '(S S))))
+ (parser-generator-lr--items-for-prefix '(S S))))
(message "Passed V(SS)")
(should
(equal
nil
- (parser-lr--items-for-prefix '(S b))))
+ (parser-generator-lr--items-for-prefix '(S b))))
(message "Passed V(Sb)")
;; a3 p. 390
@@ -175,72 +175,72 @@
(S (S) (a S b) (b))
(S (S a S) (b) (a))
(S (S a S) (b) (e)))
- (parser-lr--items-for-prefix '(S a S))))
+ (parser-generator-lr--items-for-prefix '(S a S))))
(message "Passed V(SaS)")
(should
(equal
nil
- (parser-lr--items-for-prefix '(S a a))))
+ (parser-generator-lr--items-for-prefix '(S a a))))
(message "Passed V(Saa)")
(should
(equal
nil
- (parser-lr--items-for-prefix '(S a b))))
+ (parser-generator-lr--items-for-prefix '(S a b))))
(message "Passed V(Sab)")
- (message "Passed tests for (parser-lr--items-for-prefix)"))
+ (message "Passed tests for (parser-generator-lr--items-for-prefix)"))
-(defun parser-lr-test--items-valid-p ()
- "Test `parser-lr--items-valid-p'."
- (message "Started tests for (parser-lr--items-valid-p)")
+(defun parser-generator-lr-test--items-valid-p ()
+ "Test `parser-generator-lr--items-valid-p'."
+ (message "Started tests for (parser-generator-lr--items-valid-p)")
- (parser--set-grammar '((Sp S) (a b) ((Sp S) (S (S a S b)) (S e)) Sp))
- (parser--set-look-ahead-number 1)
- (parser--process-grammar)
+ (parser-generator--set-grammar '((Sp S) (a b) ((Sp S) (S (S a S b)) (S e))
Sp))
+ (parser-generator--set-look-ahead-number 1)
+ (parser-generator--process-grammar)
- (parser-lr--reset)
- (parser-lr--generate-goto-tables)
+ (parser-generator-lr--reset)
+ (parser-generator-lr--generate-goto-tables)
(should
(equal
t
- (parser-lr--items-valid-p (parser--hash-values-to-list parser-lr--items
t))))
+ (parser-generator-lr--items-valid-p (parser-generator--hash-values-to-list
parser-generator-lr--items t))))
(message "Passed first")
(should
(equal
nil
- (parser-lr--items-valid-p
+ (parser-generator-lr--items-valid-p
'(((S nil (S a S b) (a)) (S nil (S a S b) (e)) (S nil nil (a)) (S nil nil
(e)) (Sp nil (S) (e))) ((S (S) (a S b) (a)) (S (S) (a S b) (e)) (Sp (S) nil
(e))) ((S (S a) (S b) (a)) (S (S a) (S b) (e)) (S nil (S a S b) (a)) (S nil (S
a S b) (b)) (S nil nil (a)) (S nil nil (b))) ((S (S) (a S b) (a)) (S (S) (a S
b) (b)) (S (S a S) (b) (a)) (S (S a S) (b) (e))) ((S (S a S b) nil (a)) (S (S a
S b) (a) (a)) (S (S a S b) nil (e))) ((S (S a) (S b) (a)) (S (S a) (S b) (b))
(S nil (S a S b) (a)) [...]
- (message "Passed tests for (parser-lr--items-valid-p)"))
+ (message "Passed tests for (parser-generator-lr--items-valid-p)"))
-(defun parser-lr-test--parse ()
- "Test `parser-lr--parse'."
- (message "Started tests for (parser-lr--parse)")
+(defun parser-generator-lr-test--parse ()
+ "Test `parser-generator-lr--parse'."
+ (message "Started tests for (parser-generator-lr--parse)")
- (parser--set-grammar '((Sp S) (a b) ((Sp S) (S (S a S b)) (S e)) Sp))
- (parser--set-look-ahead-number 1)
- (parser--process-grammar)
+ (parser-generator--set-grammar '((Sp S) (a b) ((Sp S) (S (S a S b)) (S e))
Sp))
+ (parser-generator--set-look-ahead-number 1)
+ (parser-generator--process-grammar)
(should
(equal
'(2 2 2 1 1)
- (parser-lr--parse '(a a b b))))
+ (parser-generator-lr--parse '(a a b b))))
- (message "Passed tests for (parser-lr--parse)"))
+ (message "Passed tests for (parser-generator-lr--parse)"))
-(defun parser-lr-test ()
+(defun parser-generator-lr-test ()
"Run test."
;; (setq debug-on-error t)
- (parser-lr-test--items-for-prefix)
- (parser-lr-test--items-valid-p)
- (parser-lr-test--generate-goto-tables)
- (parser-lr-test--generate-action-tables)
- (parser-lr-test--parse))
+ (parser-generator-lr-test--items-for-prefix)
+ (parser-generator-lr-test--items-valid-p)
+ (parser-generator-lr-test--generate-goto-tables)
+ (parser-generator-lr-test--generate-action-tables)
+ (parser-generator-lr-test--parse))
-(provide 'parser-lr-test)
+(provide 'parser-generator-lr-test)
-;;; parser-lr-test.el ends here
+;;; parser-generator-lr-test.el ends here
diff --git a/test/parser-generator-test.el b/test/parser-generator-test.el
new file mode 100644
index 0000000..824bced
--- /dev/null
+++ b/test/parser-generator-test.el
@@ -0,0 +1,543 @@
+;;; parser-generator-test.el --- Tests for Parser Generator -*-
lexical-binding: t -*-
+
+
+;;; Commentary:
+
+
+;;; Code:
+
+(require 'parser-generator)
+(require 'ert)
+
+(defun parser-generator-test--valid-look-ahead-p ()
+ "Test `parser-generator--valid-look-ahead-p'."
+ (message "Starting tests for (parser-generator--valid-look-ahead-p)")
+
+ (parser-generator--set-look-ahead-number 1)
+ (parser-generator--set-grammar '((S A) ("a" "b") ((S A) (A ("b" "a"))) S))
+ (parser-generator--process-grammar)
+
+ (should
+ (equal
+ t
+ (parser-generator--valid-look-ahead-p "a")))
+ (should
+ (equal
+ t
+ (parser-generator--valid-look-ahead-p "b")))
+ (should
+ (equal
+ nil
+ (parser-generator--valid-look-ahead-p "c")))
+ (should
+ (equal
+ nil
+ (parser-generator--valid-look-ahead-p "d")))
+ (should
+ (equal
+ t
+ (parser-generator--valid-look-ahead-p 'e)))
+
+ (message "Passed tests for (parser-generator--valid-look-ahead-p)"))
+
+(defun parser-generator-test--get-grammar-look-aheads ()
+ "Test `parser-generator--get-look-aheads'."
+ (message "Starting tests for (parser-generator--get-grammar-look-aheads)")
+
+ (parser-generator--set-look-ahead-number 1)
+ (parser-generator--set-grammar '((S A) ("a" "b") ((S A) (A ("b" "a"))) S))
+ (parser-generator--process-grammar)
+
+ (should
+ (equal
+ '(("a") ("b") (e))
+ (parser-generator--get-grammar-look-aheads)))
+ (message "Passed ((a) (b) (e))")
+
+ (parser-generator--set-look-ahead-number 2)
+
+ (should
+ (equal
+ '(("a" "a") ("a" "b") ("a" e) ("b" "a") ("b" "b") ("b" e))
+ (parser-generator--get-grammar-look-aheads)))
+
+ (message "Passed tests for (parser-generator--get-grammar-look-aheads)"))
+
+(defun parser-generator-test--sort-list ()
+ "Test `parser-generator--sort-list'."
+ (message "Starting tests for (parser-generator-test--sort-list)")
+
+ (should
+ (equal
+ '((a b c) (b c d) (c e f))
+ (sort '((a b c) (c e f) (b c d)) 'parser-generator--sort-list)))
+
+ (should
+ (equal
+ '((a b c) (a c c) (c e f))
+ (sort '((a c c) (a b c) (c e f)) 'parser-generator--sort-list)))
+
+ (should
+ (equal
+ '((a b) (a c c) (c e f g h))
+ (sort '((a c c) (a b) (c e f g h)) 'parser-generator--sort-list)))
+
+ (should
+ (equal
+ '((a) (b) (c))
+ (sort '((a) (c) (b)) 'parser-generator--sort-list)))
+
+ (message "Passed tests for (parser-generator--distinct)"))
+
+(defun parser-generator-test--distinct ()
+ "Test `parser-generator--distinct'."
+ (message "Starting tests for (parser-generator--distinct)")
+
+ (should
+ (equal
+ '(a b c)
+ (parser-generator--distinct '(a a b c))))
+
+ (should
+ (equal
+ '("aa" "b" "cc" "c" "a")
+ (parser-generator--distinct '("aa" "b" "cc" "c" "b" "a" "aa"))))
+ (message "Passed tests for (parser-generator--distinct)"))
+
+(defun parser-generator-test--follow ()
+ "Test `parser-generator--follow'."
+ (message "Starting tests for (parser-generator--follow)")
+
+ (parser-generator--set-grammar '((S A) (b) ((S A) (A b)) S))
+ (parser-generator--set-look-ahead-number 2)
+ (parser-generator--process-grammar)
+
+ (should
+ (equal
+ '((e))
+ (parser-generator--follow 'A)))
+ (message "Passed follow 1 with intermediate grammar")
+
+ (parser-generator--set-grammar '((S A B) (a c d f) ((S (A a)) (A B) (B (c f)
d)) S))
+ (parser-generator--set-look-ahead-number 2)
+ (parser-generator--process-grammar)
+
+ (should
+ (equal
+ '((a))
+ (parser-generator--follow 'A)))
+ (message "Passed follow 2 with intermediate grammar")
+
+ (parser-generator--set-grammar '((S A B) (a c d f) ((S (A a)) (A (B c d)) (B
(c f) d)) S))
+ (parser-generator--set-look-ahead-number 2)
+ (parser-generator--process-grammar)
+
+ (should
+ (equal
+ '((c d))
+ (parser-generator--follow 'B)))
+ (message "Passed follow 3 with intermediate grammar")
+
+ (message "Passed tests for (parser-generator--follow)"))
+
+(defun parser-generator-test--first ()
+ "Test `parser-generator--first'."
+ (message "Starting tests for (parser-generator--first)")
+
+ (parser-generator--set-grammar '((S) (a) ((S a)) S))
+ (parser-generator--set-look-ahead-number 1)
+ (parser-generator--process-grammar)
+
+ (should
+ (equal
+ '((a))
+ (parser-generator--first 'S)))
+ (message "Passed first 1 with rudimentary grammar")
+
+ (parser-generator--set-grammar '((S) (a) ((S a)) S))
+ (parser-generator--set-look-ahead-number 1)
+ (parser-generator--process-grammar)
+
+ (should
+ (equal
+ '((a))
+ (parser-generator--first '(S a))))
+ (message "Passed first 1b with rudimentary grammar")
+
+ (parser-generator--set-grammar '((S) (a) ((S a)) S))
+ (parser-generator--set-look-ahead-number 2)
+ (parser-generator--process-grammar)
+
+ (should
+ (equal
+ '((a a))
+ (parser-generator--first '(S a))))
+ (message "Passed first 1c with rudimentary grammar")
+
+ (parser-generator--set-grammar '((S) (a) ((S a)) S))
+ (parser-generator--set-look-ahead-number 2)
+ (parser-generator--process-grammar)
+
+ (should
+ (equal
+ '((a))
+ (parser-generator--first '(a))))
+ (message "Passed first 1d with rudimentary grammar")
+
+ (parser-generator--set-grammar '((S) ("a" "b" "c") ((S ("a" "b" "c"))) S))
+ (parser-generator--set-look-ahead-number 2)
+ (parser-generator--process-grammar)
+
+ (should
+ (equal
+ '(("a" "b"))
+ (parser-generator--first 'S)))
+ (message "Passed first 2 with rudimentary grammar")
+
+ (parser-generator--set-grammar '((S) ("a" b "c") ((S ("a" b "c"))) S))
+ (parser-generator--set-look-ahead-number 3)
+ (parser-generator--process-grammar)
+
+ (should
+ (equal
+ '(("a" b "c"))
+ (parser-generator--first 'S)))
+ (message "Passed first 3 with rudimentary grammar")
+
+ (parser-generator--set-grammar '((S A) (b) ((S A) (A b)) S))
+ (parser-generator--set-look-ahead-number 2)
+ (parser-generator--process-grammar)
+
+ (should
+ (equal
+ '((b))
+ (parser-generator--first 'S)))
+ (message "Passed first 1 with intermediate grammar")
+
+ (parser-generator--set-grammar '((S A) ("a" "b") ((S A) (A ("b" "a"))) S))
+ (parser-generator--set-look-ahead-number 2)
+ (parser-generator--process-grammar)
+
+ (should
+ (equal
+ '(("b" "a"))
+ (parser-generator--first 'S)))
+ (message "Passed first 2 with intermediate grammar")
+
+ (parser-generator--set-grammar '((S A) ("a" "b" "c" "d") ((S A) (A ("b" "a"
"c" "d"))) S))
+ (parser-generator--set-look-ahead-number 3)
+ (parser-generator--process-grammar)
+
+ (should
+ (equal
+ '(("b" "a" "c"))
+ (parser-generator--first 'S)))
+ (message "Passed first 3 with intermediate grammar")
+
+ (parser-generator--set-grammar '((S A B) ("c" "d") ((S A) (A B) (B "c" "d"))
S))
+ (parser-generator--set-look-ahead-number 1)
+ (parser-generator--process-grammar)
+
+ (should
+ (equal
+ '(("c") ("d"))
+ (parser-generator--first 'S)))
+ (message "Passed first 1 with semi-complex grammar")
+
+ (parser-generator--set-grammar '((S A B) (a c d f) ((S (A a)) (A B) (B (c f)
d)) S))
+ (parser-generator--set-look-ahead-number 2)
+ (parser-generator--process-grammar)
+
+ (should
+ (equal
+ '((c f) (d a))
+ (parser-generator--first 'S)))
+ (message "Passed first 2 with semi-complex grammar")
+
+ (parser-generator--set-grammar '((S A B) ("a" "c" "d" "m") ((S A) (A (B "a"
"m")) (B "c" "d")) S))
+ (parser-generator--set-look-ahead-number 3)
+ (parser-generator--process-grammar)
+
+ (should
+ (equal
+ '(("c" "a" "m") ("d" "a" "m"))
+ (parser-generator--first 'S)))
+ (message "Passed first 3 with semi-complex grammar")
+
+ (parser-generator--set-grammar '((S A B C) (a b c) ((S A B) (A (B a) e) (B
(C b) C) (C c e)) S))
+ (parser-generator--set-look-ahead-number 1)
+ (parser-generator--process-grammar)
+
+ (should
+ (equal
+ '((a) (b) (c) (e))
+ (parser-generator--first 'S)))
+ (message "Passed first 1 with complex grammar")
+
+ ;; Example 5.28 p 382
+ (parser-generator--set-grammar '((S A B C) (a b c) ((S (A B)) (A (B a) e) (B
(C b) C) (C c e)) S))
+ (parser-generator--set-look-ahead-number 2)
+ (parser-generator--process-grammar)
+
+ (should
+ (equal
+ '((a b) (a c) (a) (b a) (b) (c a) (c) (c b) (e))
+ (parser-generator--first 'S)))
+ (message "Passed first 2 with complex grammar")
+
+ (parser-generator--set-grammar '((S A B C) (a b c) ((S (A B)) (A (B a) e) (B
(C b) C) (C c e)) S))
+ (parser-generator--set-look-ahead-number 3)
+ (parser-generator--process-grammar)
+
+ (should
+ (equal
+ '((a) (a b) (a c) (a c b) (b a) (b a b) (b a c) (b) (c a) (c a b) (c a c)
(c b) (c) (c b a) (e))
+ (parser-generator--first 'S)))
+ (message "Passed first 3 with complex grammar")
+
+ (message "Passed tests for (parser-generator--first)"))
+
+;; Example 5.28 page 402
+(defun parser-generator-test--e-free-first ()
+ "Test `parser-generator--e-free-first'."
+ (message "Starting tests for (parser-generator--e-free-first)")
+
+ ;; Example 5.28 p 402
+ (parser-generator--set-grammar '((S A B C) (a b c) ((S (A B)) (A (B a) e) (B
(C b) C) (C c e)) S))
+ (parser-generator--set-look-ahead-number 2)
+ (parser-generator--process-grammar)
+
+ (should
+ (equal
+ '((c a) (c b))
+ (parser-generator--e-free-first 'S)))
+ (message "Passed empty-free-first 2 with complex grammar")
+
+ (parser-generator--set-look-ahead-number 1)
+ (parser-generator--process-grammar)
+ (should
+ (equal
+ '((c))
+ (parser-generator--e-free-first '(S b a))))
+ (message "Passed empty-free-first 1 with complex grammar")
+
+ (parser-generator--set-grammar '((Sp S) (a b) ((Sp S) (S (S a S b)) (S e))
Sp))
+ (parser-generator--set-look-ahead-number 1)
+ (parser-generator--process-grammar)
+ (should
+ (equal
+ nil
+ (parser-generator--e-free-first '(S b a))))
+ (message "Passed empty-free-first 1 with complex grammar 2")
+
+ (message "Passed tests for (parser-generator--empty-free-first)"))
+
+(defun parser-generator-test--valid-grammar-p ()
+ "Test function `parser-generator--valid-grammar-p'."
+ (message "Starting tests for (parser-generator--valid-grammar-p)")
+
+ (should (equal
+ t
+ (parser-generator--valid-grammar-p '((A B C) ("a" "b" "c") ((A
"a")) A))))
+
+ (should (equal
+ nil
+ (parser-generator--valid-grammar-p '((A B C) ("a" "b" "c") ((A
"a")) (A)))))
+
+ (should (equal
+ nil
+ (parser-generator--valid-grammar-p '((A B C) (("a" "b") "c") ((A
"a")) A))))
+
+ (should (equal
+ nil
+ (parser-generator--valid-grammar-p '(((A B) C) ("a" "b" "c") ((A
"a")) A))))
+
+ (should (equal
+ nil
+ (parser-generator--valid-grammar-p '(((A B) C) ("a" "b" "c") ((A))
A))))
+
+ (should (equal
+ nil
+ (parser-generator--valid-grammar-p "A")))
+
+ (should (equal
+ nil
+ (parser-generator--valid-grammar-p '(A B C))))
+
+ (should (equal
+ nil
+ (parser-generator--valid-grammar-p '((A B)))))
+
+ (should (equal
+ nil
+ (parser-generator--valid-grammar-p '((A B C) (a (b c) "c") (A ("a"
"b") (a b)) (B b) (C "c")))))
+
+ (message "Passed tests for (parser-generator--valid-grammar-p)"))
+
+(defun parser-generator-test--valid-look-ahead-number-p ()
+ "Test function `parser-generator--valid-look-ahead-number-p'."
+ (message "Starting tests for (parser-generator--valid-look-ahead-number-p)")
+
+ (should (equal
+ nil
+ (parser-generator--valid-look-ahead-number-p 'A)))
+
+ (should (equal
+ nil
+ (parser-generator--valid-look-ahead-number-p "A")))
+
+ (should (equal
+ nil
+ (parser-generator--valid-look-ahead-number-p -2)))
+
+ (should (equal
+ nil
+ (parser-generator--valid-look-ahead-number-p 3.3)))
+
+ (should (equal
+ t
+ (parser-generator--valid-look-ahead-number-p 2)))
+
+ (should (equal
+ t
+ (parser-generator--valid-look-ahead-number-p 1)))
+
+ (message "Passed tests for (parser-generator--valid-look-ahead-number-p)"))
+
+(defun parser-generator-test--valid-sentential-form-p ()
+ "Test `parser-generator--valid-sentential-form-p'."
+ (message "Starting tests for (parser-generator--valid-sentential-form-p)")
+
+ ;; TODO Add tests for this
+
+ (message "Passed tests for (parser-generator--valid-sentential-form-p)"))
+
+(defun parser-generator-test--valid-production-p ()
+ "Test `parser-generator--valid-production-p'."
+ (message "Starting tests for (parser-generator--valid-production-p)")
+
+ (should (equal
+ t
+ (parser-generator--valid-production-p '(A a))))
+
+ (should (equal
+ nil
+ (parser-generator--valid-production-p "A")))
+
+ (should (equal
+ nil
+ (parser-generator--valid-production-p '((A a)))))
+
+ (message "Passed tests for (parser-generator--valid-production-p)"))
+
+(defun parser-generator-test--get-grammar-rhs ()
+ "Test `parser-generator--get-grammar-rhs'."
+ (message "Started tests for (parser-generator--get-grammar-rhs)")
+
+ (parser-generator--set-grammar '((S A) ("a" "b") ((S A) (A ("b" "a"))) S))
+ (parser-generator--process-grammar)
+
+ (should (equal
+ '((A))
+ (parser-generator--get-grammar-rhs 'S)))
+ (should (equal
+ '(("b" "a"))
+ (parser-generator--get-grammar-rhs 'A)))
+
+ (parser-generator--set-grammar '((S A B) ("a" "b") ((S A) (S (B)) (B "a") (A
"a") (A ("b" "a"))) S))
+ (parser-generator--process-grammar)
+
+ (should (equal
+ '((A) (B))
+ (parser-generator--get-grammar-rhs 'S)))
+ (should (equal
+ '(("a") ("b" "a"))
+ (parser-generator--get-grammar-rhs 'A)))
+
+ (message "Passed tests for (parser-generator--get-grammar-rhs)"))
+
+(defun parser-generator-test--valid-non-terminal-p ()
+ "Test `parser-generator--valid-non-terminal-p'."
+ (message "Starting tests for (parser-generator--valid-non-terminal-p)")
+
+ (parser-generator--set-grammar '((S A B) ("a" "b") ((S A) (S (B)) (B "a") (A
"a") (A ("b" "a"))) S))
+ (parser-generator--process-grammar)
+
+ (should
+ (equal
+ t
+ (parser-generator--valid-non-terminal-p 'S)))
+ (should
+ (equal
+ t
+ (parser-generator--valid-non-terminal-p 'A)))
+ (should
+ (equal
+ t
+ (parser-generator--valid-non-terminal-p 'B)))
+ (should
+ (equal
+ nil
+ (parser-generator--valid-non-terminal-p 'C)))
+ (should
+ (equal
+ nil
+ (parser-generator--valid-non-terminal-p "a")))
+
+ (message "Passed tests for (parser-generator--valid-non-terminal-p)"))
+
+(defun parser-generator-test--valid-terminal-p ()
+ "Test `parser-generator--valid-terminal-p'."
+ (message "Starting tests for (parser-generator--valid-terminal-p)")
+
+ (parser-generator--set-grammar '((S A B) ("a" "b") ((S A) (S (B)) (B "a") (A
"a") (A ("b" "a"))) S))
+ (parser-generator--process-grammar)
+
+ (should
+ (equal
+ t
+ (parser-generator--valid-terminal-p "a")))
+ (should
+ (equal
+ t
+ (parser-generator--valid-terminal-p "b")))
+ (should
+ (equal
+ t
+ (parser-generator--valid-terminal-p "a")))
+ (should
+ (equal
+ nil
+ (parser-generator--valid-terminal-p 'S)))
+ (should
+ (equal
+ nil
+ (parser-generator--valid-terminal-p 'A)))
+
+ (message "Passed tests for (parser-generator--valid-terminal-p)"))
+
+(defun parser-generator-test ()
+ "Run test."
+ ;; (setq debug-on-error t)
+
+ ;; Helpers
+ (parser-generator-test--valid-look-ahead-p)
+ (parser-generator-test--valid-look-ahead-number-p)
+ (parser-generator-test--valid-production-p)
+ (parser-generator-test--valid-grammar-p)
+ (parser-generator-test--valid-non-terminal-p)
+ (parser-generator-test--valid-sentential-form-p)
+ (parser-generator-test--valid-terminal-p)
+ (parser-generator-test--distinct)
+ (parser-generator-test--sort-list)
+ (parser-generator-test--get-grammar-rhs)
+ (parser-generator-test--get-grammar-look-aheads)
+
+ ;; Algorithms
+ (parser-generator-test--first)
+ (parser-generator-test--e-free-first)
+ (parser-generator-test--follow))
+
+(provide 'parser-generator-test)
+
+;;; parser-generator-test.el ends here
diff --git a/test/parser-test.el b/test/parser-test.el
deleted file mode 100644
index 1ebe13b..0000000
--- a/test/parser-test.el
+++ /dev/null
@@ -1,543 +0,0 @@
-;;; parser-test.el --- Tests for Parser -*- lexical-binding: t -*-
-
-
-;;; Commentary:
-
-
-;;; Code:
-
-(require 'parser)
-(require 'ert)
-
-(defun parser-test--valid-look-ahead-p ()
- "Test `parser--valid-look-ahead-p'."
- (message "Starting tests for (parser--valid-look-ahead-p)")
-
- (parser--set-look-ahead-number 1)
- (parser--set-grammar '((S A) ("a" "b") ((S A) (A ("b" "a"))) S))
- (parser--process-grammar)
-
- (should
- (equal
- t
- (parser--valid-look-ahead-p "a")))
- (should
- (equal
- t
- (parser--valid-look-ahead-p "b")))
- (should
- (equal
- nil
- (parser--valid-look-ahead-p "c")))
- (should
- (equal
- nil
- (parser--valid-look-ahead-p "d")))
- (should
- (equal
- t
- (parser--valid-look-ahead-p 'e)))
-
- (message "Passed tests for (parser--valid-look-ahead-p)"))
-
-(defun parser-test--get-grammar-look-aheads ()
- "Test `parser--get-look-aheads'."
- (message "Starting tests for (parser--get-grammar-look-aheads)")
-
- (parser--set-look-ahead-number 1)
- (parser--set-grammar '((S A) ("a" "b") ((S A) (A ("b" "a"))) S))
- (parser--process-grammar)
-
- (should
- (equal
- '(("a") ("b") (e))
- (parser--get-grammar-look-aheads)))
- (message "Passed ((a) (b) (e))")
-
- (parser--set-look-ahead-number 2)
-
- (should
- (equal
- '(("a" "a") ("a" "b") ("a" e) ("b" "a") ("b" "b") ("b" e))
- (parser--get-grammar-look-aheads)))
-
- (message "Passed tests for (parser--get-grammar-look-aheads)"))
-
-(defun parser-test--sort-list ()
- "Test `parser--sort-list'."
- (message "Starting tests for (parser-test--sort-list)")
-
- (should
- (equal
- '((a b c) (b c d) (c e f))
- (sort '((a b c) (c e f) (b c d)) 'parser--sort-list)))
-
- (should
- (equal
- '((a b c) (a c c) (c e f))
- (sort '((a c c) (a b c) (c e f)) 'parser--sort-list)))
-
- (should
- (equal
- '((a b) (a c c) (c e f g h))
- (sort '((a c c) (a b) (c e f g h)) 'parser--sort-list)))
-
- (should
- (equal
- '((a) (b) (c))
- (sort '((a) (c) (b)) 'parser--sort-list)))
-
- (message "Passed tests for (parser--distinct)"))
-
-(defun parser-test--distinct ()
- "Test `parser--distinct'."
- (message "Starting tests for (parser--distinct)")
-
- (should
- (equal
- '(a b c)
- (parser--distinct '(a a b c))))
-
- (should
- (equal
- '("aa" "b" "cc" "c" "a")
- (parser--distinct '("aa" "b" "cc" "c" "b" "a" "aa"))))
- (message "Passed tests for (parser--distinct)"))
-
-(defun parser-test--follow ()
- "Test `parser--follow'."
- (message "Starting tests for (parser--follow)")
-
- (parser--set-grammar '((S A) (b) ((S A) (A b)) S))
- (parser--set-look-ahead-number 2)
- (parser--process-grammar)
-
- (should
- (equal
- '((e))
- (parser--follow 'A)))
- (message "Passed follow 1 with intermediate grammar")
-
- (parser--set-grammar '((S A B) (a c d f) ((S (A a)) (A B) (B (c f) d)) S))
- (parser--set-look-ahead-number 2)
- (parser--process-grammar)
-
- (should
- (equal
- '((a))
- (parser--follow 'A)))
- (message "Passed follow 2 with intermediate grammar")
-
- (parser--set-grammar '((S A B) (a c d f) ((S (A a)) (A (B c d)) (B (c f) d))
S))
- (parser--set-look-ahead-number 2)
- (parser--process-grammar)
-
- (should
- (equal
- '((c d))
- (parser--follow 'B)))
- (message "Passed follow 3 with intermediate grammar")
-
- (message "Passed tests for (parser--follow)"))
-
-(defun parser-test--first ()
- "Test `parser--first'."
- (message "Starting tests for (parser--first)")
-
- (parser--set-grammar '((S) (a) ((S a)) S))
- (parser--set-look-ahead-number 1)
- (parser--process-grammar)
-
- (should
- (equal
- '((a))
- (parser--first 'S)))
- (message "Passed first 1 with rudimentary grammar")
-
- (parser--set-grammar '((S) (a) ((S a)) S))
- (parser--set-look-ahead-number 1)
- (parser--process-grammar)
-
- (should
- (equal
- '((a))
- (parser--first '(S a))))
- (message "Passed first 1b with rudimentary grammar")
-
- (parser--set-grammar '((S) (a) ((S a)) S))
- (parser--set-look-ahead-number 2)
- (parser--process-grammar)
-
- (should
- (equal
- '((a a))
- (parser--first '(S a))))
- (message "Passed first 1c with rudimentary grammar")
-
- (parser--set-grammar '((S) (a) ((S a)) S))
- (parser--set-look-ahead-number 2)
- (parser--process-grammar)
-
- (should
- (equal
- '((a))
- (parser--first '(a))))
- (message "Passed first 1d with rudimentary grammar")
-
- (parser--set-grammar '((S) ("a" "b" "c") ((S ("a" "b" "c"))) S))
- (parser--set-look-ahead-number 2)
- (parser--process-grammar)
-
- (should
- (equal
- '(("a" "b"))
- (parser--first 'S)))
- (message "Passed first 2 with rudimentary grammar")
-
- (parser--set-grammar '((S) ("a" b "c") ((S ("a" b "c"))) S))
- (parser--set-look-ahead-number 3)
- (parser--process-grammar)
-
- (should
- (equal
- '(("a" b "c"))
- (parser--first 'S)))
- (message "Passed first 3 with rudimentary grammar")
-
- (parser--set-grammar '((S A) (b) ((S A) (A b)) S))
- (parser--set-look-ahead-number 2)
- (parser--process-grammar)
-
- (should
- (equal
- '((b))
- (parser--first 'S)))
- (message "Passed first 1 with intermediate grammar")
-
- (parser--set-grammar '((S A) ("a" "b") ((S A) (A ("b" "a"))) S))
- (parser--set-look-ahead-number 2)
- (parser--process-grammar)
-
- (should
- (equal
- '(("b" "a"))
- (parser--first 'S)))
- (message "Passed first 2 with intermediate grammar")
-
- (parser--set-grammar '((S A) ("a" "b" "c" "d") ((S A) (A ("b" "a" "c" "d")))
S))
- (parser--set-look-ahead-number 3)
- (parser--process-grammar)
-
- (should
- (equal
- '(("b" "a" "c"))
- (parser--first 'S)))
- (message "Passed first 3 with intermediate grammar")
-
- (parser--set-grammar '((S A B) ("c" "d") ((S A) (A B) (B "c" "d")) S))
- (parser--set-look-ahead-number 1)
- (parser--process-grammar)
-
- (should
- (equal
- '(("c") ("d"))
- (parser--first 'S)))
- (message "Passed first 1 with semi-complex grammar")
-
- (parser--set-grammar '((S A B) (a c d f) ((S (A a)) (A B) (B (c f) d)) S))
- (parser--set-look-ahead-number 2)
- (parser--process-grammar)
-
- (should
- (equal
- '((c f) (d a))
- (parser--first 'S)))
- (message "Passed first 2 with semi-complex grammar")
-
- (parser--set-grammar '((S A B) ("a" "c" "d" "m") ((S A) (A (B "a" "m")) (B
"c" "d")) S))
- (parser--set-look-ahead-number 3)
- (parser--process-grammar)
-
- (should
- (equal
- '(("c" "a" "m") ("d" "a" "m"))
- (parser--first 'S)))
- (message "Passed first 3 with semi-complex grammar")
-
- (parser--set-grammar '((S A B C) (a b c) ((S A B) (A (B a) e) (B (C b) C) (C
c e)) S))
- (parser--set-look-ahead-number 1)
- (parser--process-grammar)
-
- (should
- (equal
- '((a) (b) (c) (e))
- (parser--first 'S)))
- (message "Passed first 1 with complex grammar")
-
- ;; Example 5.28 p 382
- (parser--set-grammar '((S A B C) (a b c) ((S (A B)) (A (B a) e) (B (C b) C)
(C c e)) S))
- (parser--set-look-ahead-number 2)
- (parser--process-grammar)
-
- (should
- (equal
- '((a b) (a c) (a) (b a) (b) (c a) (c) (c b) (e))
- (parser--first 'S)))
- (message "Passed first 2 with complex grammar")
-
- (parser--set-grammar '((S A B C) (a b c) ((S (A B)) (A (B a) e) (B (C b) C)
(C c e)) S))
- (parser--set-look-ahead-number 3)
- (parser--process-grammar)
-
- (should
- (equal
- '((a) (a b) (a c) (a c b) (b a) (b a b) (b a c) (b) (c a) (c a b) (c a c)
(c b) (c) (c b a) (e))
- (parser--first 'S)))
- (message "Passed first 3 with complex grammar")
-
- (message "Passed tests for (parser--first)"))
-
-;; Example 5.28 page 402
-(defun parser-test--e-free-first ()
- "Test `parser--e-free-first'."
- (message "Starting tests for (parser--e-free-first)")
-
- ;; Example 5.28 p 402
- (parser--set-grammar '((S A B C) (a b c) ((S (A B)) (A (B a) e) (B (C b) C)
(C c e)) S))
- (parser--set-look-ahead-number 2)
- (parser--process-grammar)
-
- (should
- (equal
- '((c a) (c b))
- (parser--e-free-first 'S)))
- (message "Passed empty-free-first 2 with complex grammar")
-
- (parser--set-look-ahead-number 1)
- (parser--process-grammar)
- (should
- (equal
- '((c))
- (parser--e-free-first '(S b a))))
- (message "Passed empty-free-first 1 with complex grammar")
-
- (parser--set-grammar '((Sp S) (a b) ((Sp S) (S (S a S b)) (S e)) Sp))
- (parser--set-look-ahead-number 1)
- (parser--process-grammar)
- (should
- (equal
- nil
- (parser--e-free-first '(S b a))))
- (message "Passed empty-free-first 1 with complex grammar 2")
-
- (message "Passed tests for (parser--empty-free-first)"))
-
-(defun parser-test--valid-grammar-p ()
- "Test function `parser--valid-grammar-p'."
- (message "Starting tests for (parser--valid-grammar-p)")
-
- (should (equal
- t
- (parser--valid-grammar-p '((A B C) ("a" "b" "c") ((A "a")) A))))
-
- (should (equal
- nil
- (parser--valid-grammar-p '((A B C) ("a" "b" "c") ((A "a")) (A)))))
-
- (should (equal
- nil
- (parser--valid-grammar-p '((A B C) (("a" "b") "c") ((A "a")) A))))
-
- (should (equal
- nil
- (parser--valid-grammar-p '(((A B) C) ("a" "b" "c") ((A "a")) A))))
-
- (should (equal
- nil
- (parser--valid-grammar-p '(((A B) C) ("a" "b" "c") ((A)) A))))
-
- (should (equal
- nil
- (parser--valid-grammar-p "A")))
-
- (should (equal
- nil
- (parser--valid-grammar-p '(A B C))))
-
- (should (equal
- nil
- (parser--valid-grammar-p '((A B)))))
-
- (should (equal
- nil
- (parser--valid-grammar-p '((A B C) (a (b c) "c") (A ("a" "b") (a
b)) (B b) (C "c")))))
-
- (message "Passed tests for (parser--valid-grammar-p)"))
-
-(defun parser-test--valid-look-ahead-number-p ()
- "Test function `parser--valid-look-ahead-number-p'."
- (message "Starting tests for (parser--valid-look-ahead-number-p)")
-
- (should (equal
- nil
- (parser--valid-look-ahead-number-p 'A)))
-
- (should (equal
- nil
- (parser--valid-look-ahead-number-p "A")))
-
- (should (equal
- nil
- (parser--valid-look-ahead-number-p -2)))
-
- (should (equal
- nil
- (parser--valid-look-ahead-number-p 3.3)))
-
- (should (equal
- t
- (parser--valid-look-ahead-number-p 2)))
-
- (should (equal
- t
- (parser--valid-look-ahead-number-p 1)))
-
- (message "Passed tests for (parser--valid-look-ahead-number-p)"))
-
-(defun parser-test--valid-sentential-form-p ()
- "Test `parser--valid-sentential-form-p'."
- (message "Starting tests for (parser--valid-sentential-form-p)")
-
- ;; TODO Add tests for this
-
- (message "Passed tests for (parser--valid-sentential-form-p)"))
-
-(defun parser-test--valid-production-p ()
- "Test `parser--valid-production-p'."
- (message "Starting tests for (parser--valid-production-p)")
-
- (should (equal
- t
- (parser--valid-production-p '(A a))))
-
- (should (equal
- nil
- (parser--valid-production-p "A")))
-
- (should (equal
- nil
- (parser--valid-production-p '((A a)))))
-
- (message "Passed tests for (parser--valid-production-p)"))
-
-(defun parser-test--get-grammar-rhs ()
- "Test `parser--get-grammar-rhs'."
- (message "Started tests for (parser--get-grammar-rhs)")
-
- (parser--set-grammar '((S A) ("a" "b") ((S A) (A ("b" "a"))) S))
- (parser--process-grammar)
-
- (should (equal
- '((A))
- (parser--get-grammar-rhs 'S)))
- (should (equal
- '(("b" "a"))
- (parser--get-grammar-rhs 'A)))
-
- (parser--set-grammar '((S A B) ("a" "b") ((S A) (S (B)) (B "a") (A "a") (A
("b" "a"))) S))
- (parser--process-grammar)
-
- (should (equal
- '((A) (B))
- (parser--get-grammar-rhs 'S)))
- (should (equal
- '(("a") ("b" "a"))
- (parser--get-grammar-rhs 'A)))
-
- (message "Passed tests for (parser--get-grammar-rhs)"))
-
-(defun parser-test--valid-non-terminal-p ()
- "Test `parser--valid-non-terminal-p'."
- (message "Starting tests for (parser--valid-non-terminal-p)")
-
- (parser--set-grammar '((S A B) ("a" "b") ((S A) (S (B)) (B "a") (A "a") (A
("b" "a"))) S))
- (parser--process-grammar)
-
- (should
- (equal
- t
- (parser--valid-non-terminal-p 'S)))
- (should
- (equal
- t
- (parser--valid-non-terminal-p 'A)))
- (should
- (equal
- t
- (parser--valid-non-terminal-p 'B)))
- (should
- (equal
- nil
- (parser--valid-non-terminal-p 'C)))
- (should
- (equal
- nil
- (parser--valid-non-terminal-p "a")))
-
- (message "Passed tests for (parser--valid-non-terminal-p)"))
-
-(defun parser-test--valid-terminal-p ()
- "Test `parser--valid-terminal-p'."
- (message "Starting tests for (parser--valid-terminal-p)")
-
- (parser--set-grammar '((S A B) ("a" "b") ((S A) (S (B)) (B "a") (A "a") (A
("b" "a"))) S))
- (parser--process-grammar)
-
- (should
- (equal
- t
- (parser--valid-terminal-p "a")))
- (should
- (equal
- t
- (parser--valid-terminal-p "b")))
- (should
- (equal
- t
- (parser--valid-terminal-p "a")))
- (should
- (equal
- nil
- (parser--valid-terminal-p 'S)))
- (should
- (equal
- nil
- (parser--valid-terminal-p 'A)))
-
- (message "Passed tests for (parser--valid-terminal-p)"))
-
-(defun parser-test ()
- "Run test."
- ;; (setq debug-on-error t)
-
- ;; Helpers
- (parser-test--valid-look-ahead-p)
- (parser-test--valid-look-ahead-number-p)
- (parser-test--valid-production-p)
- (parser-test--valid-grammar-p)
- (parser-test--valid-non-terminal-p)
- (parser-test--valid-sentential-form-p)
- (parser-test--valid-terminal-p)
- (parser-test--distinct)
- (parser-test--sort-list)
- (parser-test--get-grammar-rhs)
- (parser-test--get-grammar-look-aheads)
-
- ;; Algorithms
- (parser-test--first)
- (parser-test--e-free-first)
- (parser-test--follow))
-
-(provide 'parser-test)
-
-;;; parser-test.el ends here
- [elpa] externals/parser-generator 1b8f025 016/434: More work on validating a grammar structure, (continued)
- [elpa] externals/parser-generator 1b8f025 016/434: More work on validating a grammar structure, ELPA Syncer, 2021/11/29
- [elpa] externals/parser-generator 1ae36fc 029/434: Added support for calculating first of a sentential form, ELPA Syncer, 2021/11/29
- [elpa] externals/parser-generator 38c2040 032/434: Improved markdown code examples, ELPA Syncer, 2021/11/29
- [elpa] externals/parser-generator e463bae 041/434: Passing tests for sorting lists, ELPA Syncer, 2021/11/29
- [elpa] externals/parser-generator 840c418 044/434: Improved comment about follow function, ELPA Syncer, 2021/11/29
- [elpa] externals/parser-generator 2a3a02d 083/434: Removed cache for LR-items for prefixes, ELPA Syncer, 2021/11/29
- [elpa] externals/parser-generator 3ba5250 090/434: Removed debugging stuff, ELPA Syncer, 2021/11/29
- [elpa] externals/parser-generator 83298fe 099/434: Passing test for function that generates possible look-ahead permutations, ELPA Syncer, 2021/11/29
- [elpa] externals/parser-generator e9697ea 100/434: Added function that tests if a look-ahead is valid or not, ELPA Syncer, 2021/11/29
- [elpa] externals/parser-generator 53c09f7 119/434: Added hash-table for productions indexed by production-number, ELPA Syncer, 2021/11/29
- [elpa] externals/parser-generator 58e5806 129/434: Renamed plugin from parser to parser-generator,
ELPA Syncer <=
- [elpa] externals/parser-generator 0695275 143/434: More updates to docs, ELPA Syncer, 2021/11/29
- [elpa] externals/parser-generator 1b17ef8 159/434: Added another unit tests for translations, ELPA Syncer, 2021/11/29
- [elpa] externals/parser-generator 04fdc96 167/434: Added unit-test for incremental translations, ELPA Syncer, 2021/11/29
- [elpa] externals/parser-generator fa6237a 170/434: Added TODO items, ELPA Syncer, 2021/11/29
- [elpa] externals/parser-generator 71f03cc 171/434: Updated example, ELPA Syncer, 2021/11/29
- [elpa] externals/parser-generator 0b72792 177/434: Added failing unit tests for FIRST, ELPA Syncer, 2021/11/29
- [elpa] externals/parser-generator 181b499 178/434: Fixed bug in FIRST generation where multiple equal LHS:s, ELPA Syncer, 2021/11/29
- [elpa] externals/parser-generator c4455db 179/434: Added TODO-item, ELPA Syncer, 2021/11/29
- [elpa] externals/parser-generator 84ffb4e 181/434: f-set max index is now set depending on if all non-terminals have been expanded or not, ELPA Syncer, 2021/11/29
- [elpa] externals/parser-generator 4aeed22 191/434: Passed tests for e-free first function, ELPA Syncer, 2021/11/29