branch: externals/parser-generator
commit 6e91a4b498e87106222a419789044e61498158d2
Author: Christian Johansson <christ...@cvj.se>
Commit: Christian Johansson <christ...@cvj.se>
More work on helper functions
---
parser-generator-ll.el | 16 +++++++++-------
parser-generator.el | 29 ++++++++++++++++++++++-------
test/parser-generator-test.el | 17 ++++++++++++-----
3 files changed, 43 insertions(+), 19 deletions(-)
diff --git a/parser-generator-ll.el b/parser-generator-ll.el
index 5345ec0724..973571e575 100644
--- a/parser-generator-ll.el
+++ b/parser-generator-ll.el
@@ -85,41 +85,43 @@
(parser-generator--debug
(message "\nproduction-lhs: %S" production-lhs)
(message "production-rhs: %S" production-rhs)
- (message "parent-follow: %S" parent-follow))
+ (message "parent-follow: %S" parent-follow)
+ (message "first-rhs: %S" first-rhs)
+ (message "satured-first-rhs: %S" satured-first-rhs))
;; TODO Remove items in first-rhs that ends with the e-identifier
;; TODO but only if it has other items that does not end with the
e-identifier
;; F('((a e) (a a))) = ((a a))
(cond
- ((and first-rhs
+ ((and satured-first-rhs
(not first-parent-follow))
(setq
look-aheads
(parser-generator--merge-max-terminal-sets
- first-rhs
+ satured-first-rhs
nil)))
((and first-parent-follow
- (not first-rhs))
+ (not satured-first-rhs))
(setq
look-aheads
(parser-generator--merge-max-terminal-sets
nil
first-parent-follow)))
- ((and first-rhs
+ ((and satured-first-rhs
first-parent-follow)
(setq
look-aheads
(parser-generator--merge-max-terminal-sets
- first-rhs
+ satured-first-rhs
first-parent-follow)))
(t (error
"Unexpected empty FIRST for production: %S and parent-follow: %S"
production
parent-follow)))
+
(parser-generator--debug
(message "look-aheads: %S" look-aheads))
- ;; TODO merge-max-terminal-sets should do the right thing
;; For each non-terminal in the production right-hand side
;; push a new item to stack with a local-follow
diff --git a/parser-generator.el b/parser-generator.el
index 28be004d80..e956ffc033 100644
--- a/parser-generator.el
+++ b/parser-generator.el
@@ -2101,20 +2101,27 @@
(defun parser-generator-generate-sets-of-terminals (sets count)
"Generate set of terminals in sequence from SETS with COUNT."
- (let ((sets-of-terminals))
+ (let ((sets-of-terminals)
+ (terminal-set-exists-p (make-hash-table :test 'equal)))
(dolist (set sets)
(let ((item-count (length set))
(item-index 0)
(only-terminals t)
- (terminal-count 0))
+ (terminal-count 0)
+ (terminals))
(while (and
only-terminals
+ (< terminal-count count)
(< item-index item-count))
(let ((item (nth item-index set)))
(if (parser-generator--valid-terminal-p item)
- (setq
- terminal-count
- (1+ terminal-count))
+ (progn
+ (push
+ item
+ terminals)
+ (setq
+ terminal-count
+ (1+ terminal-count)))
(setq
only-terminals
nil)))
@@ -2123,9 +2130,17 @@
(1+ item-index)))
(when (and
only-terminals
- (= terminal-count count))
+ (= terminal-count count)
+ (not
+ (gethash
+ terminals
+ terminal-set-exists-p)))
+ (puthash
+ terminals
+ t
+ terminal-set-exists-p)
(push
- set
+ (reverse terminals)
sets-of-terminals))))
(reverse sets-of-terminals)))
diff --git a/test/parser-generator-test.el b/test/parser-generator-test.el
index e159585bf5..a7d415abc3 100644
--- a/test/parser-generator-test.el
+++ b/test/parser-generator-test.el
@@ -1085,20 +1085,19 @@
(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)
- ;; TODO Test here
(should
(equal
(parser-generator-generate-sets-of-terminals
'(("a" "a") ("b") ("b" "a") ("a" "b" "a") ("a" e S "b" "a") ("b" "b" A))
2)
- '(("a" "a") ("b" "a"))))
+ '(("a" "a") ("b" "a") ("a" "b") ("b" "b"))))
(should
(equal
(parser-generator-generate-sets-of-terminals
'(("a" "a") ("b") ("b" "a") ("a" "b" "a") ("a" e S "b" "a") ("b" "b" A))
1)
- '(("b"))))
+ '(("a") ("b"))))
(should
(equal
@@ -1107,6 +1106,13 @@
3)
'(("a" "b" "a"))))
+ (should
+ (equal
+ (parser-generator-generate-sets-of-terminals
+ '(("a" e) ("b") ("b" "a") ("a" "b" "a") ("a" e S "b" "a") ("b" "b" A))
+ 1)
+ '(("a") ("b"))))
+
(message "Passed tests for (parser-generator--generate-sets-of-terminals)"))
(defun parser-generator-test--generate-terminal-saturated-first-set ()
@@ -1121,12 +1127,13 @@
(equal
(parser-generator-generate-terminal-saturated-first-set
'(("a" "b") ("a" "a" e) ("b") ("a" e)))
- '(("a" "b"))))
+ '(("a" "b") ("a" "a"))))
+
(should
(equal
(parser-generator-generate-terminal-saturated-first-set
'(("a" "b") ("a" "a" e) ("b" "b") ("a" e)))
- '(("a" "b") ("b" "b"))))
+ '(("a" "b") ("a" "a") ("b" "b"))))
(message "Passed tests for
(parser-generator-generate-terminal-saturated-first-set)"))
