branch: externals/parser-generator
commit 01173e2caffeb8c6efef107b762ba65191fed411
Author: Christian Johansson <christ...@cvj.se>
Commit: Christian Johansson <christ...@cvj.se>
Added EOF identifier, passing all unit tests
---
parser-generator-lex-analyzer.el | 2 +-
parser-generator-lr.el | 38 +-
parser-generator.el | 38 +-
test/parser-generator-lex-analyzer-test.el | 2 +-
test/parser-generator-lr-test.el | 1061 ++++++++++++++--------------
test/parser-generator-test.el | 14 +-
6 files changed, 572 insertions(+), 583 deletions(-)
diff --git a/parser-generator-lex-analyzer.el b/parser-generator-lex-analyzer.el
index 16d4714..634079b 100644
--- a/parser-generator-lex-analyzer.el
+++ b/parser-generator-lex-analyzer.el
@@ -83,7 +83,7 @@
(push next-look-ahead-item look-ahead)
(setq look-ahead-length (1+ look-ahead-length))
(setq index (cdr (cdr next-look-ahead-item))))))
- (push (list parser-generator--e-identifier) look-ahead)
+ (push (list parser-generator--eof-identifier) look-ahead)
(setq look-ahead-length (1+ look-ahead-length))
(setq index (1+ index)))))
(error (error
diff --git a/parser-generator-lr.el b/parser-generator-lr.el
index 369b4eb..1129844 100644
--- a/parser-generator-lr.el
+++ b/parser-generator-lr.el
@@ -53,6 +53,7 @@
(let ((lr-items
(gethash goto-index table-lr-items)))
(let ((lr-items-length (length lr-items)))
+
;; Where u is in (T U e)*k
(dolist (state states)
(let ((lr-item)
@@ -136,7 +137,7 @@
(if (and
(= production-number 0)
(>= (length u) 1)
- (parser-generator--valid-e-p
+ (parser-generator--valid-eof-p
(nth (1- (length u)) u)))
(progn
;; Reduction by first production
@@ -406,13 +407,21 @@
(parser-generator--get-grammar-rhs start))
(e-list (parser-generator--generate-list-of-symbol
parser-generator--look-ahead-number
- parser-generator--e-identifier)))
+ parser-generator--e-identifier))
+ (eof-list (parser-generator--generate-list-of-symbol
+ parser-generator--look-ahead-number
+ parser-generator--eof-identifier)))
;; (a)
(dolist (rhs start-productions)
;; Add [S -> . α] to V(e)
- (push `(,(list start) nil ,rhs ,e-list) lr-items-e)
- (puthash `(,e-list ,(list start) nil ,rhs ,e-list) t lr-item-exists))
+ (push
+ `(,(list start) nil ,rhs ,eof-list)
+ lr-items-e)
+ (puthash
+ `(,e-list ,(list start) nil ,rhs ,eof-list)
+ 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
@@ -439,11 +448,12 @@
(parser-generator--valid-non-terminal-p
rhs-first)
(let ((rhs-rest (append (cdr rhs) suffix)))
- (let ((rhs-rest-first (parser-generator--first
rhs-rest)))
+ (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 `(,e-list)))
+ (setq rhs-rest-first `(,eof-list)))
(let ((sub-production
(parser-generator--get-grammar-rhs
rhs-first)))
@@ -470,10 +480,10 @@
;; Add [B -> . β, x] to V(e), provided it is
not already there
(unless
(gethash
- `(e ,(list rhs-first) nil ,sub-rhs ,f)
+ `(,e-list ,(list rhs-first) nil ,sub-rhs
,f)
lr-item-exists)
(puthash
- `(e ,(list rhs-first) nil ,sub-rhs ,f)
+ `(,e-list ,(list rhs-first) nil ,sub-rhs ,f)
t
lr-item-exists)
(push
@@ -488,7 +498,9 @@
(setq
lr-items-e
- (sort lr-items-e 'parser-generator--sort-list))
+ (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
@@ -717,13 +729,7 @@
(error "Missing GOTO-tables for grammar!"))
(let ((accept)
- (pre-index 0)
- (e-list
- (parser-generator--generate-list-of-symbol
- parser-generator--look-ahead-number
- parser-generator--e-identifier)))
- (parser-generator--debug
- (message "e-list: %s" e-list))
+ (pre-index 0))
(while (not accept)
diff --git a/parser-generator.el b/parser-generator.el
index 37152f7..a6de4c8 100644
--- a/parser-generator.el
+++ b/parser-generator.el
@@ -18,6 +18,10 @@
'e
"The identifier used for e-symbol. Default value 'e.")
+(defvar parser-generator--eof-identifier
+ '$
+ "The identifier used for end of file identifier. Default value is '$.")
+
(defvar parser-generator--grammar
nil
"Current grammar used in parser.")
@@ -113,13 +117,17 @@
(terminal-index)
(look-ahead-length)
(look-ahead)
- (e-list))
-
- (let ((e-list-index 0)
- (e-list-length parser-generator--look-ahead-number))
- (while (< e-list-index e-list-length)
- (push parser-generator--e-identifier e-list)
- (setq e-list-index (1+ e-list-index))))
+ (eof-list))
+
+ (let ((eof-list-index 0)
+ (eof-list-length parser-generator--look-ahead-number))
+ (while (< eof-list-index eof-list-length)
+ (push
+ parser-generator--eof-identifier
+ eof-list)
+ (setq
+ eof-list-index
+ (1+ eof-list-index))))
(while stack
(let ((item (pop stack)))
@@ -147,12 +155,17 @@
(if look-ahead
(progn
+ ;; If length of look-ahead is below k, append EOF identifiers
(while (< look-ahead-length k)
- (push parser-generator--e-identifier look-ahead)
- (setq look-ahead-length (1+ look-ahead-length)))
+ (push
+ parser-generator--eof-identifier
+ look-ahead)
+ (setq
+ look-ahead-length
+ (1+ look-ahead-length)))
(setq look-ahead-to-add (reverse look-ahead)))
- (setq look-ahead-to-add e-list))
+ (setq look-ahead-to-add eof-list))
(when (and look-ahead-to-add
(not (gethash look-ahead-to-add added-look-aheads)))
@@ -448,6 +461,10 @@
"Return whether SYMBOL is the e identifier or not."
(eq symbol parser-generator--e-identifier))
+(defun parser-generator--valid-eof-p (symbol)
+ "Return whether SYMBOL is the EOF identifier or not."
+ (eq symbol parser-generator--eof-identifier))
+
(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))
@@ -636,6 +653,7 @@
(let ((is-valid t))
(unless (or
(parser-generator--valid-e-p symbol)
+ (parser-generator--valid-eof-p symbol)
(parser-generator--valid-non-terminal-p symbol)
(parser-generator--valid-terminal-p symbol))
(setq is-valid nil))
diff --git a/test/parser-generator-lex-analyzer-test.el
b/test/parser-generator-lex-analyzer-test.el
index e86f8f8..ea93b8f 100644
--- a/test/parser-generator-lex-analyzer-test.el
+++ b/test/parser-generator-lex-analyzer-test.el
@@ -58,7 +58,7 @@
(setq parser-generator--look-ahead-number 10)
(should
(equal
- '(("a" 1 . 2) ("b" 2 . 3) ("c" 3 . 4) ("d" 4 . 5) (e) (e) (e) (e) (e) (e))
+ '(("a" 1 . 2) ("b" 2 . 3) ("c" 3 . 4) ("d" 4 . 5) ($) ($) ($) ($) ($) ($))
(parser-generator-lex-analyzer--peek-next-look-ahead)))
(setq
diff --git a/test/parser-generator-lr-test.el b/test/parser-generator-lr-test.el
index 79b537a..46f203c 100644
--- a/test/parser-generator-lr-test.el
+++ b/test/parser-generator-lr-test.el
@@ -61,45 +61,17 @@
(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)
- (let ((table-lr-items (parser-generator-lr-generate-parser-tables)))
-
- (should
- (equal
- '((0 (((S) 1)))
- (1 (((a) 2)))
- (2 (((S) 3)))
- (3 (((a) 4) ((b) 5)))
- (4 (((S) 6)))
- (5 nil)
- (6 (((a) 4) ((b) 7)))
- (7 nil))
- (parser-generator--hash-to-list
- parser-generator-lr--goto-tables)))
- (message "Passed GOTO-tables")
-
- (should
- (equal
- '((0 (((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))))
- (1 (((S) (S) (a S b) (a)) ((S) (S) (a S b) (e)) ((Sp) (S) nil (e))))
- (2 (((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))))
- (3 (((S) (S) (a S b) (a)) ((S) (S) (a S b) (b)) ((S) (S a S) (b) (a))
((S) (S a S) (b) (e))))
- (4 (((S) (S a) (S b) (a)) ((S) (S a) (S b) (b)) ((S) nil (S a S b)
(a)) ((S) nil (S a S b) (b)) ((S) nil nil (a)) ((S) nil nil (b))))
- (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-generator--hash-to-list
- table-lr-items)))
- (message "Passed LR-items"))
+ (parser-generator-lr-generate-parser-tables)
- ;; Fig. 5.9 p. 374
+ ;; Fig. 5.9 p. 374, replaced e with $
(should
(equal
- '((0 (((a) reduce 2) ((e) reduce 2)))
- (1 (((a) shift) ((e) accept)))
+ '((0 ((($) reduce 2) ((a) reduce 2)))
+ (1 ((($) accept) ((a) shift)))
(2 (((a) reduce 2) ((b) reduce 2)))
(3 (((a) shift) ((b) shift)))
(4 (((a) reduce 2) ((b) reduce 2)))
- (5 (((a) reduce 1) ((e) reduce 1)))
+ (5 ((($) reduce 1) ((a) reduce 1)))
(6 (((a) shift) ((b) shift)))
(7 (((a) reduce 1) ((b) reduce 1))))
(parser-generator--hash-to-list
@@ -118,595 +90,590 @@
'((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)
- (let ((table-lr-items (parser-generator-lr--generate-goto-tables)))
+ (let ((table-lr-items
+ (parser-generator-lr--generate-goto-tables)))
(parser-generator--debug
(message
"GOTO-table: %s"
(parser-generator--hash-to-list
parser-generator-lr--goto-tables))
+ (should
+ (equal
+ '((0 (((S) 1)))
+ (1 (((a) 2)))
+ (2 (((S) 3)))
+ (3 (((a) 4) ((b) 5)))
+ (4 (((S) 6)))
+ (5 nil)
+ (6 (((a) 4) ((b) 7)))
+ (7 nil))
+ (parser-generator--hash-to-list
+ parser-generator-lr--goto-tables)))
+ (message "Passed GOTO-tables")
+
(message
"LR-items: %s"
(parser-generator--hash-to-list
table-lr-items)))
-
- (parser-generator-lr--generate-action-tables
- table-lr-items)
- (parser-generator--debug
- (message
- "ACTION-tables: %s"
- (parser-generator--hash-to-list
- parser-generator-lr--action-tables)))
-
- (should
- (equal
- '((0 (((S) 1)))
- (1 (((a) 2)))
- (2 (((S) 3)))
- (3 (((a) 4) ((b) 5)))
- (4 (((S) 6)))
- (5 nil)
- (6 (((a) 4) ((b) 7)))
- (7 nil))
- (parser-generator--hash-to-list
- parser-generator-lr--goto-tables)))
- (message "Passed GOTO-tables")
-
(should
(equal
- '((0 (((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))))
- (1 (((S) (S) (a S b) (a)) ((S) (S) (a S b) (e)) ((Sp) (S) nil (e))))
- (2 (((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))))
- (3 (((S) (S) (a S b) (a)) ((S) (S) (a S b) (b)) ((S) (S a S) (b) (a))
((S) (S a S) (b) (e))))
+ '((0 (((S) nil (S a S b) ($)) ((S) nil (S a S b) (a)) ((S) nil nil ($))
((S) nil nil (a)) ((Sp) nil (S) ($))))
+ (1 (((S) (S) (a S b) ($)) ((S) (S) (a S b) (a)) ((Sp) (S) nil ($))))
+ (2 (((S) (S a) (S b) ($)) ((S) (S a) (S b) (a)) ((S) nil (S a S b)
(a)) ((S) nil (S a S b) (b)) ((S) nil nil (a)) ((S) nil nil (b))))
+ (3 (((S) (S) (a S b) (a)) ((S) (S) (a S b) (b)) ((S) (S a S) (b) ($))
((S) (S a S) (b) (a))))
(4 (((S) (S a) (S b) (a)) ((S) (S a) (S b) (b)) ((S) nil (S a S b)
(a)) ((S) nil (S a S b) (b)) ((S) nil nil (a)) ((S) nil nil (b))))
- (5 (((S) (S a S b) nil (a)) ((S) (S a S b) nil (e))))
+ (5 (((S) (S a S b) nil ($)) ((S) (S a S b) nil (a))))
(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-generator--hash-to-list
- table-lr-items))))
- (message "Passed LR-items")
+ table-lr-items)))
+ (message "Passed LR-items"))
- (message "Passed LR-items for example 5.30")
+ (message "Passed LR-items for example 5.30")
- ;; Example 5.30, p. 389 but with terminals as strings
- (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)
-
- (let ((table-lr-items
- (parser-generator-lr-generate-parser-tables)))
+ ;; Example 5.30, p. 389 but with terminals as strings
+ (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)
- ;; (message "GOTO-table: %s" (parser-generator--hash-to-list
parser-generator-lr--goto-tables))
- ;; (message "LR-items: %s" (parser-generator--hash-to-list
parser-generator-lr--items))
+ (let ((table-lr-items
+ (parser-generator-lr--generate-goto-tables)))
+
+ ;; (message "GOTO-table: %s" (parser-generator--hash-to-list
parser-generator-lr--goto-tables))
+ ;; (message "LR-items: %s" (parser-generator--hash-to-list
parser-generator-lr--items))
+
+ (should
+ (equal
+ '((0 (((S) 1)))
+ (1 ((("a") 2)))
+ (2 (((S) 3)))
+ (3 ((("a") 4) (("b") 5)))
+ (4 (((S) 6)))
+ (5 nil)
+ (6 ((("a") 4) (("b") 7)))
+ (7 nil))
+ (parser-generator--hash-to-list
+ parser-generator-lr--goto-tables)))
+ (message "Passed GOTO-tables with tokens as strings")
+
+ (should
+ (equal
+ '((0 (((S) nil (S "a" S "b") ($)) ((S) nil (S "a" S "b") ("a")) ((S)
nil nil ($)) ((S) nil nil ("a")) ((Sp) nil (S) ($))))
+ (1 (((S) (S) ("a" S "b") ($)) ((S) (S) ("a" S "b") ("a")) ((Sp) (S)
nil ($))))
+ (2 (((S) (S "a") (S "b") ($)) ((S) (S "a") (S "b") ("a")) ((S) nil
(S "a" S "b") ("a")) ((S) nil (S "a" S "b") ("b")) ((S) nil nil ("a")) ((S) nil
nil ("b"))))
+ (3 (((S) (S) ("a" S "b") ("a")) ((S) (S) ("a" S "b") ("b")) ((S) (S
"a" S) ("b") ($)) ((S) (S "a" S) ("b") ("a"))))
+ (4 (((S) (S "a") (S "b") ("a")) ((S) (S "a") (S "b") ("b")) ((S) nil
(S "a" S "b") ("a")) ((S) nil (S "a" S "b") ("b")) ((S) nil nil ("a")) ((S) nil
nil ("b"))))
+ (5 (((S) (S "a" S "b") nil ($)) ((S) (S "a" S "b") nil ("a"))))
+ (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-generator--hash-to-list table-lr-items)))
+ (message "Passed LR-items with tokens as strings"))
+
+ (message "Passed LR-items for example 5.30 but with tokens as strings")
+
+ ;; TODO Test with look-ahead number > 1 he
+
+ (message "Passed tests for (parser-r--generate-goto-tables)"))
+
+ (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-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
- '((0 (((S) 1)))
- (1 ((("a") 2)))
- (2 (((S) 3)))
- (3 ((("a") 4) (("b") 5)))
- (4 (((S) 6)))
- (5 nil)
- (6 ((("a") 4) (("b") 7)))
- (7 nil))
- (parser-generator--hash-to-list parser-generator-lr--goto-tables)))
- (message "Passed GOTO-tables with tokens as strings")
+ '(((S) nil (S a S b) ($))
+ ((S) nil (S a S b) (a))
+ ((S) nil nil ($))
+ ((S) nil nil (a))
+ ((Sp) nil (S) ($)))
+ (parser-generator-lr--items-for-prefix 'e)))
+ (message "Passed V(e)")
(should
(equal
- '((0 (((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))))
- (1 (((S) (S) ("a" S "b") ("a")) ((S) (S) ("a" S "b") (e)) ((Sp) (S)
nil (e))))
- (2 (((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"))))
- (3 (((S) (S) ("a" S "b") ("a")) ((S) (S) ("a" S "b") ("b")) ((S) (S
"a" S) ("b") ("a")) ((S) (S "a" S) ("b") (e))))
- (4 (((S) (S "a") (S "b") ("a")) ((S) (S "a") (S "b") ("b")) ((S) nil
(S "a" S "b") ("a")) ((S) nil (S "a" S "b") ("b")) ((S) nil nil ("a")) ((S) nil
nil ("b"))))
- (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-generator--hash-to-list table-lr-items)))
- (message "Passed LR-items with tokens as strings"))
-
- (message "Passed LR-items for example 5.30 but with tokens as strings")
-
- (message "Passed tests for (parser-r--generate-goto-tables)"))
-
-(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-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
- '(((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)))
- (parser-generator-lr--items-for-prefix 'e)))
- (message "Passed V(e)")
-
- (should
- (equal
- '(((S) (S) (a S b) (a))
- ((S) (S) (a S b) (e))
- ((Sp) (S) nil (e)))
- (parser-generator-lr--items-for-prefix 'S)))
- (message "Passed V(S)")
-
- (should
- (equal
- nil
- (parser-generator-lr--items-for-prefix 'a)))
- (message "Passed V(a)")
+ '(((S) (S) (a S b) ($))
+ ((S) (S) (a S b) (a))
+ ((Sp) (S) nil ($)))
+ (parser-generator-lr--items-for-prefix 'S)))
+ (message "Passed V(S)")
- (should
- (equal
- nil
- (parser-generator-lr--items-for-prefix 'b)))
- (message "Passed V(b)")
-
- (should
- (equal
- '(((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)))
- (parser-generator-lr--items-for-prefix '(S a))))
- (message "Passed V(Sa)")
-
- (should
- (equal
- nil
- (parser-generator-lr--items-for-prefix '(S S))))
- (message "Passed V(SS)")
-
- (should
- (equal
- nil
- (parser-generator-lr--items-for-prefix '(S b))))
- (message "Passed V(Sb)")
-
- ;; a3 p. 390
- (should
- (equal
- '(((S) (S) (a S b) (a))
- ((S) (S) (a S b) (b))
- ((S) (S a S) (b) (a))
- ((S) (S a S) (b) (e)))
- (parser-generator-lr--items-for-prefix '(S a S))))
- (message "Passed V(SaS)")
-
- (should
- (equal
- nil
- (parser-generator-lr--items-for-prefix '(S a a))))
- (message "Passed V(Saa)")
-
- (should
- (equal
- nil
- (parser-generator-lr--items-for-prefix '(S a b))))
- (message "Passed V(Sab)")
-
- (message "Passed tests for (parser-generator-lr--items-for-prefix)"))
+ (should
+ (equal
+ nil
+ (parser-generator-lr--items-for-prefix 'a)))
+ (message "Passed V(a)")
-(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)")
+ (should
+ (equal
+ nil
+ (parser-generator-lr--items-for-prefix 'b)))
+ (message "Passed V(b)")
- (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)
-
+ (should
+ (equal
+ '(((S) (S a) (S b) ($))
+ ((S) (S a) (S b) (a))
+ ((S) nil (S a S b) (a))
+ ((S) nil (S a S b) (b))
+ ((S) nil nil (a))
+ ((S) nil nil (b)))
+ (parser-generator-lr--items-for-prefix '(S a))))
+ (message "Passed V(Sa)")
- (let ((table-lr-items (parser-generator-process-grammar)))
+ (should
+ (equal
+ nil
+ (parser-generator-lr--items-for-prefix '(S S))))
+ (message "Passed V(SS)")
(should
(equal
- t
- (parser-generator-lr--items-valid-p
(parser-generator--hash-values-to-list table-lr-items t))))
+ nil
+ (parser-generator-lr--items-for-prefix '(S b))))
+ (message "Passed V(Sb)")
- (message "Passed first"))
+ ;; a3 p. 390
+ (should
+ (equal
+ '(((S) (S) (a S b) (a))
+ ((S) (S) (a S b) (b))
+ ((S) (S a S) (b) ($))
+ ((S) (S a S) (b) (a)))
+ (parser-generator-lr--items-for-prefix '(S a S))))
+ (message "Passed V(SaS)")
- (should
- (equal
- nil
- (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)) [...]
+ (should
+ (equal
+ nil
+ (parser-generator-lr--items-for-prefix '(S a a))))
+ (message "Passed V(Saa)")
- (message "Passed tests for (parser-generator-lr--items-valid-p)"))
+ (should
+ (equal
+ nil
+ (parser-generator-lr--items-for-prefix '(S a b))))
+ (message "Passed V(Sab)")
-(defun parser-generator-lr-test-parse ()
- "Test `parser-generator-lr-parse'."
- (message "Started tests for (parser-generator-lr-parse)")
+ (message "Passed tests for (parser-generator-lr--items-for-prefix)"))
- (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-generator-lr-generate-parser-tables)
- (setq
- parser-generator-lex-analyzer--function
- (lambda (index)
- (let* ((string '((a 1 . 2) (a 2 . 3) (b 3 . 4) (b 4 . 5)))
- (string-length (length string))
- (max-index index)
- (tokens))
- (while (and
- (< (1- index) string-length)
- (< (1- index) max-index))
- (push (nth (1- index) string) tokens)
- (setq index (1+ index)))
- (nreverse tokens))))
- (should
- (equal
- '(2 2 2 1 1)
- (parser-generator-lr-parse)))
- (message "Passed test with terminals as symbols")
-
- (setq
- parser-generator-lex-analyzer--function
- (lambda (index)
- (let* ((string '((a 1 . 2) (a 2 . 3) (b 3 . 4) (b 4 . 5) (b 5 . 6)))
- (string-length (length string))
- (max-index index)
- (tokens))
- (while (and
- (< (1- index) string-length)
- (< (1- index) max-index))
- (push (nth (1- index) string) tokens)
- (setq index (1+ index)))
- (nreverse tokens))))
- (should-error
- (parser-generator-lr--parse))
- (message "Passed test with terminals as symbols, invalid syntax")
-
- (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)
- (let ((lr-items (parser-generator-lr-generate-parser-tables)))
- (parser-generator--debug
- (message "lr-items: %s" (parser-generator--hash-values-to-list lr-items
t)))
- )
- (parser-generator--debug
- (message "goto-tables: %s" (parser-generator--hash-values-to-list
parser-generator-lr--goto-tables t))
- (message "action-tables: %s" (parser-generator--hash-values-to-list
parser-generator-lr--action-tables t)))
- (setq
- parser-generator-lex-analyzer--function
- (lambda (index)
- (let* ((string '(("a" 1 . 2) ("a" 2 . 3) ("b" 3 . 4) ("b" 4 . 5)))
- (string-length (length string))
- (max-index index)
- (tokens))
- (while (and
- (< (1- index) string-length)
- (< (1- index) max-index))
- (push (nth (1- index) string) tokens)
- (setq index (1+ index)))
- (nreverse tokens))))
- (should
- (equal
- '(2 2 2 1 1)
- (parser-generator-lr-parse)))
- (message "Passed test with terminals as string")
-
- (setq
- parser-generator-lex-analyzer--function
- (lambda (index)
- (let* ((string '(("a" 1 . 2) ("a" 2 . 3) ("b" 3 . 4) ("b" 4 . 5) ("b" 5 .
6)))
- (string-length (length string))
- (max-index index)
- (tokens))
- (while (and
- (< (1- index) string-length)
- (< (1- index) max-index))
- (push (nth (1- index) string) tokens)
- (setq index (1+ index)))
- (nreverse tokens))))
- (should-error
- (parser-generator-lr--parse))
- (message "Passed test with terminals as string, invalid syntax")
-
- (setq
- parser-generator-lex-analyzer--function
- (lambda (index)
- (let* ((string '(("a" 1 . 2) ("a" 2 . 3) ("b" 3 . 4) ("b" 4 . 5)))
- (string-length (length string))
- (max-index index)
- (tokens))
- (while (and
- (< (1- index) string-length)
- (< (1- index) max-index))
- (push (nth (1- index) string) tokens)
- (setq index (1+ index)))
- (nreverse tokens))))
-
- (parser-generator-lr-test--parse-incremental-vs-regular)
- (message "Passed incremental-tests")
-
- (message "Passed tests for (parser-generator-lr--parse)"))
-
-(defun parser-generator-lr-test-parse-k-2 ()
- "Test `parser-generator-lr-parse' with k = 2."
- (message "Started tests for (parser-generator-lr-parse) k = 2")
-
- (parser-generator-set-grammar '((Sp S) ("a" "b") ((Sp S) (S (S "a" S "b"))
(S e)) Sp))
- (parser-generator-set-look-ahead-number 2)
- (parser-generator-process-grammar)
+ (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)")
- (let ((lr-items (parser-generator-lr--generate-goto-tables)))
- (parser-generator--debug
- (message "all lr-items: %s" (parser-generator--hash-values-to-list
lr-items t)))
-
- ;; (should
- ;; (equal
- ;; '((0 ((S 1)))
- ;; (1 (("a" 2)))
- ;; (2 ((S 3)))
- ;; (3 (("a" 4) ("b" 5)))
- ;; (4 ((S 6)))
- ;; (5 nil)
- ;; (6 (("a" 4) ("b" 7)))
- ;; (7 nil))
- ;; (parser-generator--hash-to-list
- ;; parser-generator-lr--goto-tables)))
- ;; (message "Passed GOTO-tables k = 2")
-
- ;; TODO Validate lr-items here
-
- ;; (should
- ;; (equal
- ;; '((0 (((S) nil (S "a" S "b") ("a" e)) ((S) nil (S "a" S "b") ("a"
"a")) ((S) nil (S "a" S "b") (e e)) ((S) nil nil ("a" e)) ((S) nil nil ("a"
"a")) ((S) nil nil (e e)) ((Sp) nil (S) (e e))))
- ;; (1 (((S) (S) ("a" S "b") ("a" "a")) ((S) (S) ("a" S "b") ("a" e))
((S) (S) ("a" S "b") (e e)) ((Sp) (S) nil (e e))))
- ;; (2 (((S) (S "a") (S "b") ("a" e)) ((S) (S "a") (S "b") ("a" "a"))
((S) (S "a") (S "b") (e e)) ((S) nil (S "a" S "b") ("a" e)) ((S) nil (S "a" S
"b") ("a" "a")) ((S) nil (S "a" S "b") ("b" e)) ((S) nil nil ("a" e)) ((S) nil
nil ("a" "a")) ((S) nil nil ("b" e))))
- ;; (3 (((S) (S) ("a" S "b") ("a" "a")) ((S) (S) ("a" S "b") ("a" e))
((S) (S) ("a" S "b") ("b" e)) ((S) (S "a" S) ("b") ("a" "a")) ((S) (S "a" S)
("b") ("a" e)) ((S) (S "a" S) ("b") (e e))))
- ;; (4 (((S) (S "a") (S "b") ("a" e)) ((S) (S "a") (S "b") ("a" "a"))
((S) (S "a") (S "b") ("b" e)) ((S) nil (S "a" S "b") ("a" e)) ((S) nil (S "a" S
"b") ("a" "a")) ((S) nil (S "a" S "b") ("b" e)) ((S) nil nil ("a" e)) ((S) nil
nil ("a" "a")) ((S) nil nil ("b" e))))
- ;; (5 (((S) (S "a" S "b") nil ("a" e)) ((S) (S "a" S "b") nil ("a"
"a")) ((S) (S "a" S "b") nil (e e))))
- ;; (6 (((S) (S) ("a" S "b") ("a" "a")) ((S) (S) ("a" S "b") ("a" e))
((S) (S) ("a" S "b") ("b" e)) ((S) (S "a" S) ("b") ("a" "a")) ((S) (S "a" S)
("b") ("a" e)) ((S) (S "a" S) ("b") ("b" e))))
- ;; (7 (((S) (S "a" S "b") nil ("a" e)) ((S) (S "a" S "b") nil ("a"
"a")) ((S) (S "a" S "b") nil ("b" e)))))
- ;; (parser-generator--hash-to-list
- ;; lr-items)))
- ;; (message "Passed LR-items k = 2")
-
- (parser-generator-lr--generate-action-tables lr-items)
- (parser-generator--debug
- (message "action-tables: %s" (parser-generator--hash-values-to-list
parser-generator-lr--action-tables t)))
+ (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)
+
- ;; TODO Validate action-table here, should be able to reduce at look-ahead
("a" "b") as well
-
- ;; (should
- ;; (equal
- ;; '((0 ((("a" "a") reduce 2) (("a" e) reduce 2) ((e e) reduce 2)))
- ;; (1 ((("a" "b") shift) ((e e) accept)))
- ;; (2 ((("a" "a") reduce 2) (("a" e) reduce 2) (("b" e) reduce 2)))
- ;; (3 ((("a" "b") shift) (("b" e) shift) (("b" "a") shift)))
- ;; (4 ((("a" "a") reduce 2) (("a" e) reduce 2) (("b" e) reduce 2)))
- ;; (5 ((("a" "a") reduce 1) (("a" e) reduce 1) ((e e) reduce 1)))
- ;; (6 ((("a" "b") shift) (("b" "b") shift) (("b" "a") shift)))
- ;; (7 ((("a" "a") reduce 1) (("a" e) reduce 1) (("b" e) reduce 1))))
- ;; (parser-generator--hash-to-list
- ;; parser-generator-lr--action-tables)))
- ;; (message "Passed ACTION-tables k = 2")
+ (let ((table-lr-items (parser-generator-process-grammar)))
- )
- (setq
- parser-generator-lex-analyzer--function
- (lambda (index)
- (let* ((string '(("a" 1 . 2) ("b" 2 . 3)))
- (string-length (length string))
- (max-index index)
- (tokens))
- (while (and
- (< (1- index) string-length)
- (< (1- index) max-index))
- (push (nth (1- index) string) tokens)
- (setq index (1+ index)))
- (nreverse tokens))))
- (should
- (equal
- '(2 2 2 1 1)
- (parser-generator-lr-parse)))
- (message "Passed test with terminals as string with look-ahead-number 2")
+ (should
+ (equal
+ t
+ (parser-generator-lr--items-valid-p
(parser-generator--hash-values-to-list table-lr-items t))))
- (message "Passed tests for (parser-generator-lr--parse-k-2)"))
+ (message "Passed first"))
-(defun parser-generator-lr-test-translate ()
- "Test `parser-generator-lr-translate'."
- (message "Started tests for (parser-generator-lr-translate)")
+ (should
+ (equal
+ nil
+ (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) [...]
- ;; Test translation with terminals as strings here
+ (message "Passed tests for (parser-generator-lr--items-valid-p)"))
- (let ((buffer (generate-new-buffer "*a*")))
- (switch-to-buffer buffer)
- (insert "aabb")
+ (defun parser-generator-lr-test-parse ()
+ "Test `parser-generator-lr-parse'."
+ (message "Started tests for (parser-generator-lr-parse)")
- (parser-generator-set-grammar '((Sp S) ("a" "b") ((Sp S) (S (S "a" S "b"
(lambda(args) (let ((list "")) (dolist (item args) (when item (setq list
(format "%s%s" item list)))) list)))) (S e)) Sp))
+ (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-generator-lr-generate-parser-tables)
-
(setq
parser-generator-lex-analyzer--function
(lambda (index)
- (with-current-buffer buffer
- (when (<= (+ index 1) (point-max))
- (let ((start index)
- (end (+ index 1)))
- (let ((token (buffer-substring-no-properties start end)))
- `(,token ,start . ,end)))))))
-
- (setq
- parser-generator-lex-analyzer--get-function
- (lambda (token)
- (with-current-buffer buffer
- (let ((start (car (cdr token)))
- (end (cdr (cdr token))))
- (when (<= end (point-max))
- (buffer-substring-no-properties start end))))))
-
+ (let* ((string '((a 1 . 2) (a 2 . 3) (b 3 . 4) (b 4 . 5)))
+ (string-length (length string))
+ (max-index index)
+ (tokens))
+ (while (and
+ (< (1- index) string-length)
+ (< (1- index) max-index))
+ (push (nth (1- index) string) tokens)
+ (setq index (1+ index)))
+ (nreverse tokens))))
(should
(equal
- "bbaaba"
- (parser-generator-lr-translate)))
-
- (kill-buffer buffer))
- (message "Passed test with translation 1")
-
- (let ((buffer (generate-new-buffer "*a*")))
- (switch-to-buffer buffer)
- (insert "if (a) { b; }")
-
- (parser-generator-set-grammar '((Sp S) (";" OPEN_ROUND_BRACKET
CLOSE_ROUND_BRACKET ECHO IF OPEN_CURLY_BRACKET CLOSE_CURLY_BRACKET VARIABLE)
((Sp S) (S (IF OPEN_ROUND_BRACKET VARIABLE CLOSE_ROUND_BRACKET
OPEN_CURLY_BRACKET VARIABLE ";" CLOSE_CURLY_BRACKET (lambda(args) (format
"(when %s %s)" (nth 2 args) (nth 5 args)))))) Sp))
- (parser-generator-set-look-ahead-number 1)
- (parser-generator-process-grammar)
- (parser-generator-lr-generate-parser-tables)
+ '(2 2 2 1 1)
+ (parser-generator-lr-parse)))
+ (message "Passed test with terminals as symbols")
(setq
parser-generator-lex-analyzer--function
(lambda (index)
- (with-current-buffer buffer
- (unless (>= index (point-max))
- (goto-char index)
- (unless (looking-at "[^ \n\t]")
- (search-forward-regexp "[^ \n\t]" nil t nil)
- (forward-char -1))
- (let ((token))
- (cond
- ((looking-at "if")
- (setq token `(IF ,(match-beginning 0) . ,(match-end 0))))
- ((looking-at "echo")
- (setq token `(ECHO ,(match-beginning 0) . ,(match-end 0))))
- ((looking-at "(")
- (setq token `(OPEN_ROUND_BRACKET ,(match-beginning 0) .
,(match-end 0))))
- ((looking-at ")")
- (setq token `(CLOSE_ROUND_BRACKET ,(match-beginning 0) .
,(match-end 0))))
- ((looking-at "{")
- (setq token `(OPEN_CURLY_BRACKET ,(match-beginning 0) .
,(match-end 0))))
- ((looking-at "}")
- (setq token `(CLOSE_CURLY_BRACKET ,(match-beginning 0) .
,(match-end 0))))
- ((looking-at ";")
- (setq token `(";" ,(match-beginning 0) . ,(match-end 0))))
- ((looking-at "[a-zA-Z]+")
- (setq token `(VARIABLE ,(match-beginning 0) . ,(match-end 0))))
- (t (error "Invalid syntax! Could not lex-analyze at %s!"
(point))))
- token)))))
-
- (setq
- parser-generator-lex-analyzer--get-function
- (lambda (token)
- (with-current-buffer buffer
- (let ((start (car (cdr token)))
- (end (cdr (cdr token))))
- (when (<= end (point-max))
- (buffer-substring-no-properties start end))))))
-
- (should
- (equal
- "(when a b)"
- (parser-generator-lr-translate)))
- (message "Passed test with non-nested translation")
-
- (switch-to-buffer buffer)
- (kill-region (point-min) (point-max))
+ (let* ((string '((a 1 . 2) (a 2 . 3) (b 3 . 4) (b 4 . 5) (b 5 . 6)))
+ (string-length (length string))
+ (max-index index)
+ (tokens))
+ (while (and
+ (< (1- index) string-length)
+ (< (1- index) max-index))
+ (push (nth (1- index) string) tokens)
+ (setq index (1+ index)))
+ (nreverse tokens))))
+ (should-error
+ (parser-generator-lr--parse))
+ (message "Passed test with terminals as symbols, invalid syntax")
- (parser-generator-set-grammar '((Sp S T) (";" OPEN_ROUND_BRACKET
CLOSE_ROUND_BRACKET ECHO IF OPEN_CURLY_BRACKET CLOSE_CURLY_BRACKET VARIABLE)
((Sp S) (S (IF OPEN_ROUND_BRACKET VARIABLE CLOSE_ROUND_BRACKET
OPEN_CURLY_BRACKET T CLOSE_CURLY_BRACKET (lambda(args) (format "(when %s %s)"
(nth 2 args) (nth 5 args))))) (T (ECHO VARIABLE ";" (lambda(args) (format
"(message %s)" (nth 1 args)))) (VARIABLE ";" (lambda(args) (format "%s" (nth 0
args)))))) Sp))
+ (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-generator-lr-generate-parser-tables)
-
- (insert "if (a) { echo b; }")
-
+ (let ((lr-items (parser-generator-lr-generate-parser-tables)))
+ (parser-generator--debug
+ (message "lr-items: %s" (parser-generator--hash-values-to-list lr-items
t)))
+ )
+ (parser-generator--debug
+ (message "goto-tables: %s" (parser-generator--hash-values-to-list
parser-generator-lr--goto-tables t))
+ (message "action-tables: %s" (parser-generator--hash-values-to-list
parser-generator-lr--action-tables t)))
+ (setq
+ parser-generator-lex-analyzer--function
+ (lambda (index)
+ (let* ((string '(("a" 1 . 2) ("a" 2 . 3) ("b" 3 . 4) ("b" 4 . 5)))
+ (string-length (length string))
+ (max-index index)
+ (tokens))
+ (while (and
+ (< (1- index) string-length)
+ (< (1- index) max-index))
+ (push (nth (1- index) string) tokens)
+ (setq index (1+ index)))
+ (nreverse tokens))))
(should
(equal
- "(when a (message b))"
- (parser-generator-lr-translate)))
-
- (message "Passed test with nested-translation with depth 2")
-
- (switch-to-buffer buffer)
- (kill-region (point-min) (point-max))
- (goto-char 1)
- (insert "if (a) { echo b }")
-
- (should-error
- (parser-generator-lr-parse))
-
- (kill-buffer buffer))
- (message "Passed test with translation 2")
-
- (let ((buffer (generate-new-buffer "*a*")))
- (switch-to-buffer buffer)
- (insert "if (a) { b; }")
-
- (parser-generator-set-grammar '((Sp S) (";" OPEN_ROUND_BRACKET
CLOSE_ROUND_BRACKET IF OPEN_CURLY_BRACKET CLOSE_CURLY_BRACKET VARIABLE) ((Sp S)
(S (IF OPEN_ROUND_BRACKET VARIABLE CLOSE_ROUND_BRACKET OPEN_CURLY_BRACKET
VARIABLE ";" CLOSE_CURLY_BRACKET (lambda(args) (format "(when %s %s)" (nth 2
args) (nth 5 args)))))) Sp))
- (parser-generator-set-look-ahead-number 1)
- (parser-generator-process-grammar)
- (parser-generator-lr-generate-parser-tables)
+ '(2 2 2 1 1)
+ (parser-generator-lr-parse)))
+ (message "Passed test with terminals as string")
(setq
parser-generator-lex-analyzer--function
(lambda (index)
- (with-current-buffer "*a*"
- (unless (>= index (point-max))
- (goto-char index)
- (unless (looking-at "[^ \n\t]")
- (search-forward-regexp "[^ \n\t]" nil t nil)
- (forward-char -1))
- (let ((token))
- (cond
- ((looking-at "if")
- (setq token `(IF ,(match-beginning 0) . ,(match-end 0))))
- ((looking-at "(")
- (setq token `(OPEN_ROUND_BRACKET ,(match-beginning 0) .
,(match-end 0))))
- ((looking-at ")")
- (setq token `(CLOSE_ROUND_BRACKET ,(match-beginning 0) .
,(match-end 0))))
- ((looking-at "{")
- (setq token `(OPEN_CURLY_BRACKET ,(match-beginning 0) .
,(match-end 0))))
- ((looking-at "}")
- (setq token `(CLOSE_CURLY_BRACKET ,(match-beginning 0) .
,(match-end 0))))
- ((looking-at ";")
- (setq token `(";" ,(match-beginning 0) . ,(match-end 0))))
- ((looking-at "[a-zA-Z]+")
- (setq token `(VARIABLE ,(match-beginning 0) . ,(match-end 0))))
- (t (error "Invalid syntax! Could not lex-analyze at %s!"
(point))))
- token)))))
+ (let* ((string '(("a" 1 . 2) ("a" 2 . 3) ("b" 3 . 4) ("b" 4 . 5) ("b" 5
. 6)))
+ (string-length (length string))
+ (max-index index)
+ (tokens))
+ (while (and
+ (< (1- index) string-length)
+ (< (1- index) max-index))
+ (push (nth (1- index) string) tokens)
+ (setq index (1+ index)))
+ (nreverse tokens))))
+ (should-error
+ (parser-generator-lr--parse))
+ (message "Passed test with terminals as string, invalid syntax")
(setq
- parser-generator-lex-analyzer--get-function
- (lambda (token)
- (with-current-buffer "*a*"
- (let ((start (car (cdr token)))
- (end (cdr (cdr token))))
- (when (<= end (point-max))
- (buffer-substring-no-properties start end))))))
+ parser-generator-lex-analyzer--function
+ (lambda (index)
+ (let* ((string '(("a" 1 . 2) ("a" 2 . 3) ("b" 3 . 4) ("b" 4 . 5)))
+ (string-length (length string))
+ (max-index index)
+ (tokens))
+ (while (and
+ (< (1- index) string-length)
+ (< (1- index) max-index))
+ (push (nth (1- index) string) tokens)
+ (setq index (1+ index)))
+ (nreverse tokens))))
(parser-generator-lr-test--parse-incremental-vs-regular)
- (kill-buffer buffer))
+ (message "Passed incremental-tests")
- (message "Passed incremental tests")
+ (message "Passed tests for (parser-generator-lr--parse)"))
- (message "Passed tests for (parser-generator-lr-translate)"))
+ (defun parser-generator-lr-test-parse-k-2 ()
+ "Test `parser-generator-lr-parse' with k = 2."
+ (message "Started tests for (parser-generator-lr-parse) k = 2")
-(defun parser-generator-lr-test ()
- "Run test."
- ;; (setq debug-on-error t)
+ (parser-generator-set-grammar '((Sp S) ("a" "b") ((Sp S) (S (S "a" S "b"))
(S e)) Sp))
+ (parser-generator-set-look-ahead-number 2)
+ (parser-generator-process-grammar)
- (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)
- (parser-generator-lr-test-translate)
- ;; (parser-generator-lr-test-parse-k-2)
- )
+ (let ((lr-items (parser-generator-lr--generate-goto-tables)))
+ (parser-generator--debug
+ (message "all lr-items: %s" (parser-generator--hash-values-to-list
lr-items t)))
+
+ ;; (should
+ ;; (equal
+ ;; '((0 ((S 1)))
+ ;; (1 (("a" 2)))
+ ;; (2 ((S 3)))
+ ;; (3 (("a" 4) ("b" 5)))
+ ;; (4 ((S 6)))
+ ;; (5 nil)
+ ;; (6 (("a" 4) ("b" 7)))
+ ;; (7 nil))
+ ;; (parser-generator--hash-to-list
+ ;; parser-generator-lr--goto-tables)))
+ ;; (message "Passed GOTO-tables k = 2")
+
+ ;; TODO Validate lr-items here
+
+ ;; (should
+ ;; (equal
+ ;; '((0 (((S) nil (S "a" S "b") ("a" e)) ((S) nil (S "a" S "b") ("a"
"a")) ((S) nil (S "a" S "b") (e e)) ((S) nil nil ("a" e)) ((S) nil nil ("a"
"a")) ((S) nil nil (e e)) ((Sp) nil (S) (e e))))
+ ;; (1 (((S) (S) ("a" S "b") ("a" "a")) ((S) (S) ("a" S "b") ("a" e))
((S) (S) ("a" S "b") (e e)) ((Sp) (S) nil (e e))))
+ ;; (2 (((S) (S "a") (S "b") ("a" e)) ((S) (S "a") (S "b") ("a" "a"))
((S) (S "a") (S "b") (e e)) ((S) nil (S "a" S "b") ("a" e)) ((S) nil (S "a" S
"b") ("a" "a")) ((S) nil (S "a" S "b") ("b" e)) ((S) nil nil ("a" e)) ((S) nil
nil ("a" "a")) ((S) nil nil ("b" e))))
+ ;; (3 (((S) (S) ("a" S "b") ("a" "a")) ((S) (S) ("a" S "b") ("a" e))
((S) (S) ("a" S "b") ("b" e)) ((S) (S "a" S) ("b") ("a" "a")) ((S) (S "a" S)
("b") ("a" e)) ((S) (S "a" S) ("b") (e e))))
+ ;; (4 (((S) (S "a") (S "b") ("a" e)) ((S) (S "a") (S "b") ("a" "a"))
((S) (S "a") (S "b") ("b" e)) ((S) nil (S "a" S "b") ("a" e)) ((S) nil (S "a" S
"b") ("a" "a")) ((S) nil (S "a" S "b") ("b" e)) ((S) nil nil ("a" e)) ((S) nil
nil ("a" "a")) ((S) nil nil ("b" e))))
+ ;; (5 (((S) (S "a" S "b") nil ("a" e)) ((S) (S "a" S "b") nil ("a"
"a")) ((S) (S "a" S "b") nil (e e))))
+ ;; (6 (((S) (S) ("a" S "b") ("a" "a")) ((S) (S) ("a" S "b") ("a" e))
((S) (S) ("a" S "b") ("b" e)) ((S) (S "a" S) ("b") ("a" "a")) ((S) (S "a" S)
("b") ("a" e)) ((S) (S "a" S) ("b") ("b" e))))
+ ;; (7 (((S) (S "a" S "b") nil ("a" e)) ((S) (S "a" S "b") nil ("a"
"a")) ((S) (S "a" S "b") nil ("b" e)))))
+ ;; (parser-generator--hash-to-list
+ ;; lr-items)))
+ ;; (message "Passed LR-items k = 2")
+
+ (parser-generator-lr--generate-action-tables lr-items)
+ (parser-generator--debug
+ (message "action-tables: %s" (parser-generator--hash-values-to-list
parser-generator-lr--action-tables t)))
+
+ ;; TODO Validate action-table here, should be able to reduce at
look-ahead ("a" "b") as well
+
+ ;; (should
+ ;; (equal
+ ;; '((0 ((("a" "a") reduce 2) (("a" e) reduce 2) ((e e) reduce 2)))
+ ;; (1 ((("a" "b") shift) ((e e) accept)))
+ ;; (2 ((("a" "a") reduce 2) (("a" e) reduce 2) (("b" e) reduce 2)))
+ ;; (3 ((("a" "b") shift) (("b" e) shift) (("b" "a") shift)))
+ ;; (4 ((("a" "a") reduce 2) (("a" e) reduce 2) (("b" e) reduce 2)))
+ ;; (5 ((("a" "a") reduce 1) (("a" e) reduce 1) ((e e) reduce 1)))
+ ;; (6 ((("a" "b") shift) (("b" "b") shift) (("b" "a") shift)))
+ ;; (7 ((("a" "a") reduce 1) (("a" e) reduce 1) (("b" e) reduce 1))))
+ ;; (parser-generator--hash-to-list
+ ;; parser-generator-lr--action-tables)))
+ ;; (message "Passed ACTION-tables k = 2")
+
+ )
+ (setq
+ parser-generator-lex-analyzer--function
+ (lambda (index)
+ (let* ((string '(("a" 1 . 2) ("b" 2 . 3)))
+ (string-length (length string))
+ (max-index index)
+ (tokens))
+ (while (and
+ (< (1- index) string-length)
+ (< (1- index) max-index))
+ (push (nth (1- index) string) tokens)
+ (setq index (1+ index)))
+ (nreverse tokens))))
+ (should
+ (equal
+ '(2 2 2 1 1)
+ (parser-generator-lr-parse)))
+ (message "Passed test with terminals as string with look-ahead-number 2")
+
+ (message "Passed tests for (parser-generator-lr--parse-k-2)"))
+
+ (defun parser-generator-lr-test-translate ()
+ "Test `parser-generator-lr-translate'."
+ (message "Started tests for (parser-generator-lr-translate)")
+
+ ;; Test translation with terminals as strings here
+
+ (let ((buffer (generate-new-buffer "*a*")))
+ (switch-to-buffer buffer)
+ (insert "aabb")
+
+ (parser-generator-set-grammar '((Sp S) ("a" "b") ((Sp S) (S (S "a" S "b"
(lambda(args) (let ((list "")) (dolist (item args) (when item (setq list
(format "%s%s" item list)))) list)))) (S e)) Sp))
+ (parser-generator-set-look-ahead-number 1)
+ (parser-generator-process-grammar)
+ (parser-generator-lr-generate-parser-tables)
+
+ (setq
+ parser-generator-lex-analyzer--function
+ (lambda (index)
+ (with-current-buffer buffer
+ (when (<= (+ index 1) (point-max))
+ (let ((start index)
+ (end (+ index 1)))
+ (let ((token (buffer-substring-no-properties start end)))
+ `(,token ,start . ,end)))))))
+
+ (setq
+ parser-generator-lex-analyzer--get-function
+ (lambda (token)
+ (with-current-buffer buffer
+ (let ((start (car (cdr token)))
+ (end (cdr (cdr token))))
+ (when (<= end (point-max))
+ (buffer-substring-no-properties start end))))))
+
+ (should
+ (equal
+ "bbaaba"
+ (parser-generator-lr-translate)))
+
+ (kill-buffer buffer))
+ (message "Passed test with translation 1")
+
+ (let ((buffer (generate-new-buffer "*a*")))
+ (switch-to-buffer buffer)
+ (insert "if (a) { b; }")
+
+ (parser-generator-set-grammar '((Sp S) (";" OPEN_ROUND_BRACKET
CLOSE_ROUND_BRACKET ECHO IF OPEN_CURLY_BRACKET CLOSE_CURLY_BRACKET VARIABLE)
((Sp S) (S (IF OPEN_ROUND_BRACKET VARIABLE CLOSE_ROUND_BRACKET
OPEN_CURLY_BRACKET VARIABLE ";" CLOSE_CURLY_BRACKET (lambda(args) (format
"(when %s %s)" (nth 2 args) (nth 5 args)))))) Sp))
+ (parser-generator-set-look-ahead-number 1)
+ (parser-generator-process-grammar)
+ (parser-generator-lr-generate-parser-tables)
+
+ (setq
+ parser-generator-lex-analyzer--function
+ (lambda (index)
+ (with-current-buffer buffer
+ (unless (>= index (point-max))
+ (goto-char index)
+ (unless (looking-at "[^ \n\t]")
+ (search-forward-regexp "[^ \n\t]" nil t nil)
+ (forward-char -1))
+ (let ((token))
+ (cond
+ ((looking-at "if")
+ (setq token `(IF ,(match-beginning 0) . ,(match-end 0))))
+ ((looking-at "echo")
+ (setq token `(ECHO ,(match-beginning 0) . ,(match-end 0))))
+ ((looking-at "(")
+ (setq token `(OPEN_ROUND_BRACKET ,(match-beginning 0) .
,(match-end 0))))
+ ((looking-at ")")
+ (setq token `(CLOSE_ROUND_BRACKET ,(match-beginning 0) .
,(match-end 0))))
+ ((looking-at "{")
+ (setq token `(OPEN_CURLY_BRACKET ,(match-beginning 0) .
,(match-end 0))))
+ ((looking-at "}")
+ (setq token `(CLOSE_CURLY_BRACKET ,(match-beginning 0) .
,(match-end 0))))
+ ((looking-at ";")
+ (setq token `(";" ,(match-beginning 0) . ,(match-end 0))))
+ ((looking-at "[a-zA-Z]+")
+ (setq token `(VARIABLE ,(match-beginning 0) . ,(match-end
0))))
+ (t (error "Invalid syntax! Could not lex-analyze at %s!"
(point))))
+ token)))))
+
+ (setq
+ parser-generator-lex-analyzer--get-function
+ (lambda (token)
+ (with-current-buffer buffer
+ (let ((start (car (cdr token)))
+ (end (cdr (cdr token))))
+ (when (<= end (point-max))
+ (buffer-substring-no-properties start end))))))
+
+ (should
+ (equal
+ "(when a b)"
+ (parser-generator-lr-translate)))
+ (message "Passed test with non-nested translation")
+
+ (switch-to-buffer buffer)
+ (kill-region (point-min) (point-max))
+
+ (parser-generator-set-grammar '((Sp S T) (";" OPEN_ROUND_BRACKET
CLOSE_ROUND_BRACKET ECHO IF OPEN_CURLY_BRACKET CLOSE_CURLY_BRACKET VARIABLE)
((Sp S) (S (IF OPEN_ROUND_BRACKET VARIABLE CLOSE_ROUND_BRACKET
OPEN_CURLY_BRACKET T CLOSE_CURLY_BRACKET (lambda(args) (format "(when %s %s)"
(nth 2 args) (nth 5 args))))) (T (ECHO VARIABLE ";" (lambda(args) (format
"(message %s)" (nth 1 args)))) (VARIABLE ";" (lambda(args) (format "%s" (nth 0
args)))))) Sp))
+ (parser-generator-set-look-ahead-number 1)
+ (parser-generator-process-grammar)
+ (parser-generator-lr-generate-parser-tables)
+
+ (insert "if (a) { echo b; }")
+
+ (should
+ (equal
+ "(when a (message b))"
+ (parser-generator-lr-translate)))
+
+ (message "Passed test with nested-translation with depth 2")
+
+ (switch-to-buffer buffer)
+ (kill-region (point-min) (point-max))
+ (goto-char 1)
+ (insert "if (a) { echo b }")
+
+ (should-error
+ (parser-generator-lr-parse))
+
+ (kill-buffer buffer))
+ (message "Passed test with translation 2")
+
+ (let ((buffer (generate-new-buffer "*a*")))
+ (switch-to-buffer buffer)
+ (insert "if (a) { b; }")
+
+ (parser-generator-set-grammar '((Sp S) (";" OPEN_ROUND_BRACKET
CLOSE_ROUND_BRACKET IF OPEN_CURLY_BRACKET CLOSE_CURLY_BRACKET VARIABLE) ((Sp S)
(S (IF OPEN_ROUND_BRACKET VARIABLE CLOSE_ROUND_BRACKET OPEN_CURLY_BRACKET
VARIABLE ";" CLOSE_CURLY_BRACKET (lambda(args) (format "(when %s %s)" (nth 2
args) (nth 5 args)))))) Sp))
+ (parser-generator-set-look-ahead-number 1)
+ (parser-generator-process-grammar)
+ (parser-generator-lr-generate-parser-tables)
+
+ (setq
+ parser-generator-lex-analyzer--function
+ (lambda (index)
+ (with-current-buffer "*a*"
+ (unless (>= index (point-max))
+ (goto-char index)
+ (unless (looking-at "[^ \n\t]")
+ (search-forward-regexp "[^ \n\t]" nil t nil)
+ (forward-char -1))
+ (let ((token))
+ (cond
+ ((looking-at "if")
+ (setq token `(IF ,(match-beginning 0) . ,(match-end 0))))
+ ((looking-at "(")
+ (setq token `(OPEN_ROUND_BRACKET ,(match-beginning 0) .
,(match-end 0))))
+ ((looking-at ")")
+ (setq token `(CLOSE_ROUND_BRACKET ,(match-beginning 0) .
,(match-end 0))))
+ ((looking-at "{")
+ (setq token `(OPEN_CURLY_BRACKET ,(match-beginning 0) .
,(match-end 0))))
+ ((looking-at "}")
+ (setq token `(CLOSE_CURLY_BRACKET ,(match-beginning 0) .
,(match-end 0))))
+ ((looking-at ";")
+ (setq token `(";" ,(match-beginning 0) . ,(match-end 0))))
+ ((looking-at "[a-zA-Z]+")
+ (setq token `(VARIABLE ,(match-beginning 0) . ,(match-end
0))))
+ (t (error "Invalid syntax! Could not lex-analyze at %s!"
(point))))
+ token)))))
+
+ (setq
+ parser-generator-lex-analyzer--get-function
+ (lambda (token)
+ (with-current-buffer "*a*"
+ (let ((start (car (cdr token)))
+ (end (cdr (cdr token))))
+ (when (<= end (point-max))
+ (buffer-substring-no-properties start end))))))
+
+ (parser-generator-lr-test--parse-incremental-vs-regular)
+ (kill-buffer buffer))
+
+ (message "Passed incremental tests")
+
+ (message "Passed tests for (parser-generator-lr-translate)"))
+
+ (defun parser-generator-lr-test ()
+ "Run test."
+ ;; (setq debug-on-error t)
+
+ (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)
+ (parser-generator-lr-test-translate)
+ ;; (parser-generator-lr-test-parse-k-2)
+ )
-(provide 'parser-generator-lr-test)
+ (provide 'parser-generator-lr-test)
;;; parser-generator-lr-test.el ends here
diff --git a/test/parser-generator-test.el b/test/parser-generator-test.el
index f8b24c3..7ee76af 100644
--- a/test/parser-generator-test.el
+++ b/test/parser-generator-test.el
@@ -49,12 +49,10 @@
(should
(equal
t
- (parser-generator--valid-look-ahead-p 'e)))
+ (parser-generator--valid-look-ahead-p '$)))
(message "Passed with look-ahead number is 1")
- ;; TODO Test with look-ahead number = 2 here
-
(parser-generator-set-look-ahead-number 2)
(parser-generator-set-grammar '((S A) ("a" "b") ((S A) (A ("b" "a"))) S))
(parser-generator-process-grammar)
@@ -81,11 +79,11 @@
(should
(equal
nil
- (parser-generator--valid-look-ahead-p '(f e))))
+ (parser-generator--valid-look-ahead-p '(f $))))
(should
(equal
t
- (parser-generator--valid-look-ahead-p '(e e))))
+ (parser-generator--valid-look-ahead-p '($ $))))
(message "Passed with look-ahead number is 2")
@@ -101,15 +99,15 @@
(should
(equal
- '(("a") ("b") (e))
+ '(($) ("a") ("b"))
(parser-generator--get-grammar-look-aheads)))
- (message "Passed ((a) (b) (e))")
+ (message "Passed ((a) (b) ($))")
(parser-generator-set-look-ahead-number 2)
(should
(equal
- '(("a" "a") ("a" "b") ("a" e) ("b" "a") ("b" "b") ("b" e) (e e))
+ '(($ $) ("a" $) ("a" "a") ("a" "b") ("b" $) ("b" "a") ("b" "b"))
(parser-generator--get-grammar-look-aheads)))
(message "Passed tests for (parser-generator--get-grammar-look-aheads)"))
