[elpa] externals/parser-generator 23805731c1 34/82: More work on LL-parser

[Christian Johansson]

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

    More work on LL-parser
---
 parser-generator-ll.el           |  6 +----
 parser-generator.el              | 50 ++++++++++++++++++++++++++++++++++------
 test/parser-generator-ll-test.el |  8 ++++---
 test/parser-generator-test.el    | 28 +++++++++++++++-------
 4 files changed, 69 insertions(+), 23 deletions(-)

diff --git a/parser-generator-ll.el b/parser-generator-ll.el
index a7acf6f73e..34ca0ce155 100644
--- a/parser-generator-ll.el
+++ b/parser-generator-ll.el
@@ -88,7 +88,7 @@
               (parser-generator-generate-terminal-saturated-first-set
                first-rhs))
              (first-parent-follow
-              (parser-generator--first parent-follow nil t t))
+              (parser-generator--first parent-follow nil t t t))
              (look-aheads)
              (sets))
         (parser-generator--debug
@@ -98,10 +98,6 @@
          (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 satured-first-rhs
                (not first-parent-follow))
diff --git a/parser-generator.el b/parser-generator.el
index 617d9f1088..0d62f64796 100644
--- a/parser-generator.el
+++ b/parser-generator.el
@@ -1327,23 +1327,55 @@
         (a-length (length a))
         (b-element)
         (b-index 0)
-        (b-length (length b)))
+        (b-length (length b))
+        (only-eof))
+
     (while (and
             (< a-index a-length)
             (< merge-count k))
       (setq a-element (nth a-index a))
-      (unless (parser-generator--valid-e-p a-element)
+
+      (when (parser-generator--valid-eof-p
+             a-element)
+        (setq only-eof t))
+
+      (when (or
+             (and
+              only-eof
+              (parser-generator--valid-eof-p
+               a-element))
+             (and
+              (not only-eof)
+              (parser-generator--valid-terminal-p
+               a-element)))
         (push a-element merged)
         (setq merge-count (1+ merge-count)))
+
       (setq a-index (1+ a-index)))
+
     (while (and
             (< b-index b-length)
             (< merge-count k))
       (setq b-element (nth b-index b))
-      (unless (parser-generator--valid-e-p b-element)
+
+      (when (parser-generator--valid-eof-p
+             b-element)
+        (setq only-eof t))
+
+      (when (or
+             (and
+              only-eof
+              (parser-generator--valid-eof-p
+               b-element))
+             (and
+              (not only-eof)
+              (parser-generator--valid-terminal-p
+               b-element)))
         (push b-element merged)
         (setq merge-count (1+ merge-count)))
+
       (setq b-index (1+ b-index)))
+
     (if (> merge-count 0)
         (nreverse merged)
       nil)))
@@ -1599,8 +1631,8 @@
 
 ;; Algorithm 5.5, p. 357
 (defun parser-generator--first
-    (β &optional disallow-e-first ignore-validation skip-sorting)
-  "For sentential-form Β, calculate first terminals, optionally 
DISALLOW-E-FIRST, IGNORE-VALIDATION and SKIP-SORTING."
+    (β &optional disallow-e-first ignore-validation skip-sorting 
use-eof-for-trailing-symbols)
+  "For sentential-form Β, calculate first terminals, optionally 
DISALLOW-E-FIRST, IGNORE-VALIDATION, SKIP-SORTING and 
USE-EOF-FOR-TRAILING-SYMBOLS."
 
   ;; Make sure we are dealing with a list of symbols
   (unless (listp β)
@@ -1955,14 +1987,18 @@
                           (missing-symbol-index 0))
                       (while (< missing-symbol-index missing-symbol-count)
                         (push
-                         parser-generator--e-identifier
+                         (if use-eof-for-trailing-symbols
+                             parser-generator--eof-identifier
+                             parser-generator--e-identifier)
                          processed-list)
                         (setq
                          missing-symbol-index
                          (1+ missing-symbol-index)))
                       (parser-generator--debug
                        (message
-                        "Added %d trailing e-identifiers to set"
+                        (if use-eof-for-trailing-symbols
+                          "Added %d trailing EOF-identifiers to set"
+                          "Added %d trailing e-identifiers to set")
                         missing-symbol-count))))
 
                   (when (> (length processed-list) k)
diff --git a/test/parser-generator-ll-test.el b/test/parser-generator-ll-test.el
index e1f88745f9..8a3068dcca 100644
--- a/test/parser-generator-ll-test.el
+++ b/test/parser-generator-ll-test.el
@@ -33,7 +33,7 @@
    )
   (parser-generator-process-grammar)
   (let ((tables (parser-generator-ll--generate-tables)))
-    (message "tables 1: %S" tables)
+    ;; (message "tables 1: %S" tables)
     (should
      (equal
       tables
@@ -63,6 +63,7 @@
         )
       )
      ))
+  (message "Passed Example 5.14 p. 350")
 
   ;; TODO Pass Example 5.17 here
   (parser-generator-set-eof-identifier '$)
@@ -88,14 +89,14 @@
       tables
       '(
         (
-         ((S) nil) ;; T0
+         ((S) ($)) ;; T0
          (
           (($ $) (e) nil)
           ((a b) (a b A) $)
           )
          )
         (
-         ((A) nil) ;; T1
+         ((A) ($)) ;; T1
          (
           ((b $) (b) nil)
           ((a a) (S a a) ((a a)))
@@ -120,6 +121,7 @@
         )
       ))
     )
+  (message "Passed Example 5.17")
 
 
   (message "Passed tests for (parser-generator-ll--generate-tables)"))
diff --git a/test/parser-generator-test.el b/test/parser-generator-test.el
index a7d415abc3..e5869fa554 100644
--- a/test/parser-generator-test.el
+++ b/test/parser-generator-test.el
@@ -971,6 +971,9 @@
   "Test `parser-generator--merge-max-terminal-sets'."
   (message "Starting tests for (parser-generator--merge-max-terminal-sets)")
 
+  (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)
+
   ;; Example 5.13 p. 348
   (parser-generator-set-e-identifier 'e)
   (parser-generator-set-look-ahead-number 2)
@@ -982,15 +985,24 @@
      '((b) (b a b)))))
 
   ;; Example 5.14 p. 350
-    (parser-generator-set-e-identifier 'e)
-    (parser-generator-set-look-ahead-number 2)
-    (should
-     (equal
-      '((a a) (a b) (b b))
-      (parser-generator--merge-max-terminal-sets
-       '((a b) (a e a) (b b) (b e b))
-       nil)))
+  (parser-generator-set-e-identifier 'e)
+  (parser-generator-set-look-ahead-number 2)
+  (should
+   (equal
+    '((a a) (a b) (b b))
+    (parser-generator--merge-max-terminal-sets
+     '((a b) (a e a) (b b) (b e b))
+     nil)))
 
+  (parser-generator-set-eof-identifier '$)
+  (parser-generator-set-e-identifier 'e)
+  (parser-generator-set-look-ahead-number 2)
+  (should
+   (equal
+    '(($ $) (a $) (a a))
+    (parser-generator--merge-max-terminal-sets
+     '((a e) ($))
+     '(($ $) (a $)))))
 
   (message "Passed tests for (parser-generator--merge-max-terminal-sets)"))