[elpa] externals/parser-generator 6ce0dd9429 04/82: Improved function to calculate merge max terminal sets

[Christian Johansson]

branch: externals/parser-generator
commit 6ce0dd9429fbc0c4178eb34df4f4c072693d9199
Author: Christian Johansson <christian@cvj.se>
Commit: Christian Johansson <christian@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)