[elpa] externals/parser-generator 2869417d78 31/82: Made new helper functions to make LL-parsing easier

[Christian Johansson]

branch: externals/parser-generator
commit 2869417d78e8db6eeccf2387900b190f3a65ba62
Author: Christian Johansson <christian@cvj.se>
Commit: Christian Johansson <christian@cvj.se>

    Made new helper functions to make LL-parsing easier
---
 parser-generator-ll.el        |  19 ++++----
 parser-generator.el           | 101 +++++++++++++++++++++++++++++++++---------
 test/parser-generator-test.el |  77 ++++++++++++++++++++++++++++++++
 3 files changed, 168 insertions(+), 29 deletions(-)

diff --git a/parser-generator-ll.el b/parser-generator-ll.el
index 95816fd0d7..5345ec0724 100644
--- a/parser-generator-ll.el
+++ b/parser-generator-ll.el
@@ -75,6 +75,9 @@
               (nth 2 stack-item))
              (first-rhs
               (parser-generator--first production-rhs nil t t))
+             (satured-first-rhs
+              (parser-generator-generate-terminal-saturated-first-set
+               first-rhs))
              (first-parent-follow
               (parser-generator--first parent-follow nil t t))
              (look-aheads)
@@ -84,6 +87,10 @@
          (message "production-rhs: %S" production-rhs)
          (message "parent-follow: %S" parent-follow))
 
+        ;; 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
                (not first-parent-follow))
@@ -91,24 +98,21 @@
            look-aheads
            (parser-generator--merge-max-terminal-sets
             first-rhs
-            nil
-            t)))
+            nil)))
          ((and first-parent-follow
                (not first-rhs))
           (setq
            look-aheads
            (parser-generator--merge-max-terminal-sets
             nil
-            first-parent-follow
-            t)))
+            first-parent-follow)))
          ((and first-rhs
                first-parent-follow)
           (setq
            look-aheads
            (parser-generator--merge-max-terminal-sets
             first-rhs
-            first-parent-follow
-            t)))
+            first-parent-follow)))
          (t (error
              "Unexpected empty FIRST for production: %S and parent-follow: %S"
              production
@@ -412,8 +416,7 @@
                       (let ((merged-terminal-sets
                              (parser-generator--merge-max-terminal-sets
                               first-sub-symbol-rhs
-                              first-local-follow-sets
-                              t)))
+                              first-local-follow-sets)))
                         (parser-generator--debug
                          (message "sub-symbol-rhs: %S" sub-symbol-rhs)
                          (message "first-sub-symbol-rhs: %S" 
first-sub-symbol-rhs)
diff --git a/parser-generator.el b/parser-generator.el
index 05e637536f..28be004d80 100644
--- a/parser-generator.el
+++ b/parser-generator.el
@@ -1238,8 +1238,8 @@
          look-ahead)))
     (nreverse look-ahead)))
 
-(defun parser-generator--merge-max-terminal-sets (a b &optional 
abort-on-e-identifier)
-  "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, optionally ABORT-ON-E-IDENTIFIER."
+(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))
@@ -1255,8 +1255,7 @@
                   ((merged-element
                     (parser-generator--merge-max-terminals
                      a-element
-                     b-element
-                     abort-on-e-identifier)))
+                     b-element)))
                 (if merged-lists
                     (setq
                      merged-lists
@@ -1275,8 +1274,7 @@
               ((merged-element
                 (parser-generator--merge-max-terminals
                  a-element
-                 nil
-                 abort-on-e-identifier)))
+                 nil)))
             (if merged-lists
                 (setq
                  merged-lists
@@ -1296,8 +1294,7 @@
                 ((merged-element
                   (parser-generator--merge-max-terminals
                    nil
-                   b-element
-                   abort-on-e-identifier)))
+                   b-element)))
               (if merged-lists
                   (setq
                    merged-lists
@@ -1320,8 +1317,8 @@
     merged-lists))
 
 ;; Lemma 5.1 p. 348
-(defun parser-generator--merge-max-terminals (a b &optional 
abort-on-e-identifier)
-  "Calculate L1 (+) L2 which is a merge of all terminals in A and B but with 
exactly length of the set look-ahead number, optionally ABORT-ON-E-IDENTIFIER."
+(defun parser-generator--merge-max-terminals (a b)
+  "Calculate L1 (+) L2 which is a merge of all terminals in A and B but with 
exactly length of the set look-ahead number."
   (let ((k (max 1 parser-generator--look-ahead-number))
         (merged)
         (merge-count 0)
@@ -1330,31 +1327,24 @@
         (a-length (length a))
         (b-element)
         (b-index 0)
-        (b-length (length b))
-        (continue t))
+        (b-length (length b)))
     (while (and
-            continue
             (< a-index a-length)
             (< merge-count k))
       (setq a-element (nth a-index a))
-      (if (parser-generator--valid-e-p a-element)
-          (when abort-on-e-identifier
-            (setq continue nil))
+      (unless (parser-generator--valid-e-p a-element)
         (push a-element merged)
         (setq merge-count (1+ merge-count)))
       (setq a-index (1+ a-index)))
     (while (and
-            continue
             (< b-index b-length)
             (< merge-count k))
       (setq b-element (nth b-index b))
-      (if (parser-generator--valid-e-p b-element)
-          (when abort-on-e-identifier
-            (setq continue nil))
+      (unless (parser-generator--valid-e-p b-element)
         (push b-element merged)
         (setq merge-count (1+ merge-count)))
       (setq b-index (1+ b-index)))
-    (if (= merge-count k)
+    (if (> merge-count 0)
         (nreverse merged)
       nil)))
 
@@ -2098,6 +2088,75 @@
             (parser-generator--distinct follow-set)))
     follow-set))
 
+(defun parser-generator-generate-terminal-saturated-first-set (first-set)
+  "Generated a set from FIRST-SET with items that does not end with the 
e-identifier if there is alternative items that continues with terminals."
+  (let* ((max-terminal-count
+          (parser-generator-calculate-max-terminal-count
+           first-set))
+         (saturated-list
+          (parser-generator-generate-sets-of-terminals
+           first-set
+           max-terminal-count)))
+    saturated-list))
+
+(defun parser-generator-generate-sets-of-terminals (sets count)
+  "Generate set of terminals in sequence from SETS with COUNT."
+  (let ((sets-of-terminals))
+    (dolist (set sets)
+      (let ((item-count (length set))
+            (item-index 0)
+            (only-terminals t)
+            (terminal-count 0))
+        (while (and
+                only-terminals
+                (< item-index item-count))
+          (let ((item (nth item-index set)))
+            (if (parser-generator--valid-terminal-p item)
+                (setq
+                 terminal-count
+                 (1+ terminal-count))
+              (setq
+               only-terminals
+               nil)))
+          (setq
+           item-index
+           (1+ item-index)))
+        (when (and
+               only-terminals
+               (= terminal-count count))
+          (push
+           set
+           sets-of-terminals))))
+    (reverse sets-of-terminals)))
+
+(defun parser-generator-calculate-max-terminal-count (sets)
+  "Calculate maximum number of terminals in sequence in SETS."
+  (let ((max-terminal-count 0))
+    (dolist (set sets)
+      (let ((item-count (length set))
+            (item-index 0)
+            (only-terminals t)
+            (terminal-count 0))
+        (while (and
+                only-terminals
+                (< item-index item-count))
+          (let ((item (nth item-index set)))
+            (if (parser-generator--valid-terminal-p item)
+                (setq
+                 terminal-count
+                 (1+ terminal-count))
+              (setq
+               only-terminals
+               nil)))
+          (setq
+           item-index
+           (1+ item-index)))
+        (when (> terminal-count max-terminal-count)
+          (setq
+           max-terminal-count
+           terminal-count))))
+    max-terminal-count))
+
 
 (provide 'parser-generator)
 
diff --git a/test/parser-generator-test.el b/test/parser-generator-test.el
index 931053399e..e159585bf5 100644
--- a/test/parser-generator-test.el
+++ b/test/parser-generator-test.el
@@ -1056,6 +1056,80 @@
 
   (message "Passed tests for 
(parser-generator-test--generate-list-of-symbol)"))
 
+(defun parser-generator-test--calculate-max-terminal-count ()
+  "Test `parser-generator-calculate-max-terminal-count'."
+  (message "Starting tests for 
(parser-generator-calculate-max-terminal-count)")
+
+  (parser-generator-set-look-ahead-number 1)
+  (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
+    (parser-generator-calculate-max-terminal-count
+     '(("a" "a") ("b") ("a" e "b" "c") (B "a" "b" "c")))
+    2))
+  (should
+   (equal
+    (parser-generator-calculate-max-terminal-count
+     '(("a") ("b") ("a" e "b" "c") (B "a" "b" "c")))
+    1))
+
+  (message "Passed tests for (parser-generator-calculate-max-terminal-count)"))
+
+(defun parser-generator-test--generate-sets-of-terminals ()
+  "Test `parser-generator--generate-sets-of-terminals'."
+  (message "Starting tests for (parser-generator--generate-sets-of-terminals)")
+
+  (parser-generator-set-look-ahead-number 1)
+  (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"))))
+
+  (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"))))
+
+  (should
+   (equal
+    (parser-generator-generate-sets-of-terminals
+     '(("a" "a") ("b") ("b" "a") ("a" "b" "a") ("a" e S "b" "a") ("b" "b" A))
+     3)
+    '(("a" "b" "a"))))
+
+  (message "Passed tests for (parser-generator--generate-sets-of-terminals)"))
+
+(defun parser-generator-test--generate-terminal-saturated-first-set ()
+  "Test `parser-generator-generate-terminal-saturated-first-set'."
+  (message "Starting tests for 
(parser-generator-generate-terminal-saturated-first-set)")
+
+  (parser-generator-set-look-ahead-number 1)
+  (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
+    (parser-generator-generate-terminal-saturated-first-set
+     '(("a" "b") ("a" "a" e) ("b") ("a" e)))
+    '(("a" "b"))))
+  (should
+   (equal
+    (parser-generator-generate-terminal-saturated-first-set
+     '(("a" "b") ("a" "a" e) ("b" "b") ("a" e)))
+    '(("a" "b") ("b" "b"))))
+
+  (message "Passed tests for 
(parser-generator-generate-terminal-saturated-first-set)"))
+
 (defun parser-generator-test ()
   "Run test."
   ;; (setq debug-on-error t)
@@ -1079,6 +1153,9 @@
   (parser-generator-test--valid-sentential-form-p)
   (parser-generator-test--valid-terminal-p)
   (parser-generator-test--generate-f-sets)
+  (parser-generator-test--calculate-max-terminal-count)
+  (parser-generator-test--generate-sets-of-terminals)
+  (parser-generator-test--generate-terminal-saturated-first-set)
 
   ;; Algorithms
   (parser-generator-test--first)