branch: externals/parser-generator
commit 6ce0dd9429fbc0c4178eb34df4f4c072693d9199
Author: Christian Johansson <christ...@cvj.se>
Commit: Christian Johansson <christ...@cvj.se>
Improved function to calculate merge max terminal sets
---
parser-generator-ll.el | 67 ++++----------------------------
parser-generator.el | 88 ++++++++++++++++++++++++++++++++-----------
test/parser-generator-test.el | 30 ++++++---------
3 files changed, 85 insertions(+), 100 deletions(-)
diff --git a/parser-generator-ll.el b/parser-generator-ll.el
index 2b2a22ff7d..bdbc0ca76a 100644
--- a/parser-generator-ll.el
+++ b/parser-generator-ll.el
@@ -66,74 +66,21 @@
look-aheads
(parser-generator--merge-max-terminals
first-production
- nil
- k)))
+ nil)))
((and first-dot-look-ahead
(not first-production))
(setq
look-aheads
(parser-generator--merge-max-terminals
nil
- first-dot-look-ahead
- k)))
+ first-dot-look-ahead)))
((and first-production
first-dot-look-ahead)
- ;; Generate a new list of all permutations
- ;; of first-production
- ;; and first-dot-look-ahead
- ;; with maximum length k
- (let ((first-production-length
- (length first-production))
- (first-production-index 0)
- (first-dot-look-ahead-length
- (length first-dot-look-ahead))
- (merged-look-aheds))
- (while
- (<
- first-production-index
- first-production-length)
- (let ((first-production-element
- (nth
- first-production-index
- first-production))
- (first-dot-look-ahead-index 0))
- (while
- (<
- first-dot-look-ahead-index
- first-dot-look-ahead-length)
- (let ((first-dot-look-ahead-element
- (nth
- first-dot-look-ahead-index
- first-dot-look-ahead)))
- (let ((merged-first-element
- (parser-generator--merge-max-terminals
- first-production-element
- first-dot-look-ahead-element)))
- (if merged-look-aheads
- (setq
- merged-look-aheads
- (append
- merged-look-aheads
- merged-first-element))
- (setq
- merged-look-aheads
- merged-first-element))))
- (setq
- first-dot-look-ahead-index
- (1+ first-dot-look-ahead-index)))
- (setq
- first-production-index
- (1+ first-production-index))))
- (setq
- merged-look-aheads
- (parser-generator--distinct
- merged-look-aheads))
- (setq
- look-aheads
- merged-look-aheads))
-
-
- )
+ (setq
+ look-aheads
+ (parser-generator--merge-max-terminal-sets
+ first-production
+ first-dot-look-ahead))))
(t (error
"Unexpected empty FIRST for production: %S and dot-look-ahead: %S"
production
diff --git a/parser-generator.el b/parser-generator.el
index 9bd2035a62..5cf4d9374f 100644
--- a/parser-generator.el
+++ b/parser-generator.el
@@ -1230,35 +1230,79 @@
look-ahead)))
(nreverse look-ahead)))
-(defun parser-generator--merge-max-terminals (a b k)
- "Merge terminals from A and B to a maximum length of K."
- (let ((merged)
+(defun parser-generator--merge-max-terminal-sets (a b)
+ "Calculate list of all lists of L1 (+) L2 which is a merge of all terminals
in lists A combined with all terminals in lists B but with maximum length of
the set look-ahead number."
+ (let ((a-length
+ (length a))
+ (a-index 0)
+ (b-length
+ (length b))
+ (merged-lists))
+ (while (< a-index a-length)
+ (let ((a-element (nth a-index a))
+ (b-index 0))
+ (while (< b-index b-length)
+ (let ((b-element (nth b-index b)))
+ (let ((merged-element
+ (parser-generator--merge-max-terminals
+ a-element
+ b-element)))
+ (if merged-lists
+ (setq
+ merged-lists
+ (append
+ merged-lists
+ (list merged-element)))
+ (setq
+ merged-lists
+ (list merged-element)))))
+ (setq b-index (1+ b-index)))
+ (setq a-index (1+ a-index))))
+ (setq
+ merged-lists
+ (parser-generator--distinct
+ merged-lists))
+ (setq
+ merged-lists
+ (sort
+ merged-lists
+ 'parser-generator--sort-list))
+ merged-lists))
+
+;; Lemma 5.1 p. 348
+(defun parser-generator--merge-max-terminals (a b)
+ "Calculate L1 (+) L2 which is a merge of all terminals in A and B but with
maximum length of the set look-ahead number."
+ (let ((k (max 1 parser-generator--look-ahead-number))
+ (merged)
(merge-count 0)
- (continue t)
(a-element)
(a-index 0)
(a-length (length a))
(b-element)
(b-index 0)
(b-length (length b)))
- (while (and
- (< a-index a-length)
- (< merge-count k)
- continue)
- (setq a-element (nth a-index a))
- (when (parser-generator--valid-e-p a-element)
- (setq continue nil))
- (push a-element merged)
- (setq a-index (1+ a-index)))
- (while (and
- (< b-index b-length)
- (< merge-count k)
- continue)
- (setq b-element (nth b-index b))
- (when (parser-generator--valid-e-p b-element)
- (setq continue nil))
- (push b-element merged)
- (setq b-index (1+ b-index)))
+ (let ((continue t))
+ (while (and
+ (< a-index a-length)
+ (< merge-count k)
+ continue)
+ (setq a-element (nth a-index a))
+ (if (parser-generator--valid-e-p a-element)
+ (setq continue nil)
+ (push a-element merged)
+ (setq a-index (1+ a-index))
+ (setq merge-count (1+ merge-count)))))
+ (let ((continue t))
+ (while (and
+ (< b-index b-length)
+ (< merge-count k)
+ continue)
+ (setq b-element (nth b-index b))
+ (if (parser-generator--valid-e-p b-element)
+ (setq continue nil)
+ (push b-element merged)
+ (setq b-index (1+ b-index))
+ (setq merge-count (1+ merge-count)))))
(nreverse merged)))
;; p. 357
diff --git a/test/parser-generator-test.el b/test/parser-generator-test.el
index 1fab673dc2..c6165fd311 100644
--- a/test/parser-generator-test.el
+++ b/test/parser-generator-test.el
@@ -967,27 +967,21 @@
(message "Passed tests for (parser-generator--valid-terminal-p)"))
-(defun parser-generator-test--merge-max-terminals ()
- "Test `parser-generator--merge-max-terminals'."
- (message "Starting tests for (parser-generator--merge-max-terminals)")
-
- (should
- (equal
- '(a b e)
- (parser-generator--merge-max-terminals
- '(a)
- '(b e)
- 3)))
+(defun parser-generator-test--merge-max-terminal-sets ()
+ "Test `parser-generator--merge-max-terminal-sets'."
+ (message "Starting tests for (parser-generator--merge-max-terminal-sets)")
+ ;; Example 5.13 p. 348
+ (parser-generator-set-e-identifier 'e)
+ (parser-generator-set-look-ahead-number 2)
(should
(equal
- '(a e)
- (parser-generator--merge-max-terminals
- '(a e)
- '(b e)
- 3)))
+ '((a b) (b) (b a))
+ (parser-generator--merge-max-terminal-sets
+ '((a b b) (e))
+ '((b) (b a b)))))
- (message "Passed tests for (parser-generator--merge-max-terminals)"))
+ (message "Passed tests for (parser-generator--merge-max-terminal-sets)"))
(defun parser-generator-test--get-list-permutations ()
"Test `parser-generator--get-list-permutations'."
@@ -1061,7 +1055,7 @@
(parser-generator-test--get-grammar-look-aheads)
(parser-generator-test--get-grammar-rhs)
(parser-generator-test--get-list-permutations)
- (parser-generator-test--merge-max-terminals)
+ (parser-generator-test--merge-max-terminal-sets)
(parser-generator-test--sort-list)
(parser-generator-test--valid-context-sensitive-attribute-p)
(parser-generator-test--valid-context-sensitive-attributes-p)
