[elpa] externals/parser-generator 84ffb4e 181/434: f-set max index is now set depending on if all non-terminals have been expanded or not

[ELPA Syncer]

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

    f-set max index is now set depending on if all non-terminals have been 
expanded or not
---
 parser-generator.el           | 57 +++++++++++++++++++++++++++++--------------
 test/parser-generator-test.el | 17 -------------
 2 files changed, 39 insertions(+), 35 deletions(-)

diff --git a/parser-generator.el b/parser-generator.el
index 6b3dcae..bb77a76 100644
--- a/parser-generator.el
+++ b/parser-generator.el
@@ -30,10 +30,18 @@
   nil
   "Generated F-sets for grammar.")
 
+(defvar parser-generator--f-sets-max-index
+  nil
+  "Max index for generated F-sets for grammar.")
+
 (defvar parser-generator--f-free-sets
   nil
   "Generated e-free F-sets for grammar.")
 
+(defvar parser-generator--f-free-sets-max-index
+  nil
+  "Max index for generated e-free F-sets for grammar.")
+
 (defvar parser-generator--look-ahead-number
   nil
   "Current look-ahead number used.")
@@ -588,13 +596,14 @@
            parser-generator--f-free-sets)
     (let ((productions (parser-generator--get-grammar-productions))
           (k parser-generator--look-ahead-number))
-      (let ((i-max (* 2 (length productions)))
-            (disallow-set '(nil t)))
+      (let ((disallow-set '(nil t))
+            (expanded-all nil))
         (dolist (disallow-e-first disallow-set)
           (let ((f-sets (make-hash-table :test 'equal))
                 (i 0))
-            (while (< i i-max)
+            (while (not expanded-all)
               (parser-generator--debug (message "i = %s" i))
+              (setq expanded-all t)
               (let ((f-set (make-hash-table :test 'equal)))
 
                 ;; Iterate all productions, set F_i
@@ -611,7 +620,8 @@
                     (let ((f-p-set))
                       (dolist (rhs-p production-rhs)
                         (let ((rhs-string rhs-p))
-                          (let ((rhs-leading-terminals
+                          (let ((rhs-leading-terminals)
+                                (f-set-return
                                  (parser-generator--f-set
                                   rhs-string
                                   `(
@@ -620,6 +630,10 @@
                                     ,f-sets
                                     ,disallow-e-first)
                                   '(("" t 0)))))
+                            (unless (nth 0 f-set-return)
+                              (setq expanded-all nil))
+                            (setq rhs-leading-terminals
+                                  (nth 1 f-set-return))
                             (parser-generator--debug
                              (message
                               "Leading %d terminals at index %s (%s) -> %s = 
%s"
@@ -662,8 +676,11 @@
                 (puthash i f-set f-sets)
                 (setq i (+ i 1))))
             (if disallow-e-first
-                (setq parser-generator--f-free-sets f-sets)
-              (setq parser-generator--f-sets f-sets)))))
+                (progn
+                  (setq parser-generator--f-free-sets f-sets)
+                  (setq parser-generator--f-free-sets-max-index (1- i)))
+              (setq parser-generator--f-sets f-sets)
+              (setq parser-generator--f-sets-max-index (1- i))))))
       (parser-generator--debug
        (message "Generated F-sets")))))
 
@@ -682,7 +699,8 @@
         (k (nth 0 state))
         (i (nth 1 state))
         (f-sets (nth 2 state))
-        (disallow-e-first (nth 3 state)))
+        (disallow-e-first (nth 3 state))
+        (expanded-all t))
     (parser-generator--debug
      (message "disallow-e-first: %s" disallow-e-first)
      (message "input-tape-length: %s" input-tape-length)
@@ -706,7 +724,8 @@
           (when (parser-generator--valid-e-p leading-terminals)
             (setq e-first-p t))
 
-          (parser-generator--debug (message "e-first-p: %s" e-first-p))
+          (parser-generator--debug
+           (message "e-first-p: %s" e-first-p))
 
           ;; If leading terminal is the e-identifier and we have input-tape 
left, disregard it
           (when (and
@@ -745,10 +764,11 @@
                  ((equal rhs-type 'NON-TERMINAL)
                   (if (> i 0)
                       (let ((sub-terminal-sets
-                             (gethash rhs-element
-                                      (gethash
-                                       (1- i)
-                                       f-sets))))
+                             (gethash
+                              rhs-element
+                              (gethash
+                               (1- i)
+                               f-sets))))
                         (if sub-terminal-sets
                             (progn
                               (parser-generator--debug
@@ -782,7 +802,7 @@
                                             (when (and
                                                    disallow-e-first
                                                    (= leading-terminals-count 
0))
-                                                  (setq 
alternative-all-leading-terminals-p nil)))
+                                              (setq 
alternative-all-leading-terminals-p nil)))
 
                                           (let ((sub-rhs-leading-terminals
                                                  (append
@@ -817,7 +837,9 @@
                                   (setq leading-terminals-count k))))
                           (parser-generator--debug
                            (message "Found no subsets for %s %s" rhs-element 
(1- i)))
+                          (setq expanded-all nil)
                           (setq all-leading-terminals-p nil)))
+                    (setq expanded-all nil)
                     (setq all-leading-terminals-p nil)))
 
                  ((equal rhs-type 'E-IDENTIFIER)
@@ -843,7 +865,7 @@
               (unless (listp leading-terminals)
                 (setq leading-terminals (list leading-terminals)))
               (push leading-terminals f-set))))))
-    f-set))
+    (list expanded-all f-set)))
 
 ;; Algorithm 5.5, p. 357
 (defun parser-generator--first (β &optional disallow-e-first)
@@ -854,7 +876,6 @@
     (error "Invalid sentential form β! %s" β))
   (let ((productions (parser-generator--get-grammar-productions))
         (k parser-generator--look-ahead-number))
-    (let ((i-max (* 2 (length productions))))
 
       ;; Generate F-sets only once per grammar
       (parser-generator--generate-f-sets)
@@ -900,8 +921,8 @@
                         (if (and
                              disallow-e-first
                              (= first-length 0))
-                            (setq symbol-f-set (gethash symbol (gethash (1- 
i-max) parser-generator--f-free-sets)))
-                          (setq symbol-f-set (gethash symbol (gethash (1- 
i-max) parser-generator--f-sets))))
+                            (setq symbol-f-set (gethash symbol (gethash 
parser-generator--f-free-sets-max-index parser-generator--f-free-sets)))
+                          (setq symbol-f-set (gethash symbol (gethash 
parser-generator--f-sets-max-index parser-generator--f-sets))))
                         (parser-generator--debug
                          (message "symbol-f-set: %s" symbol-f-set))
                         (if (not symbol-f-set)
@@ -935,7 +956,7 @@
                   (push first first-list))))))
 
         (setq first-list (sort first-list 'parser-generator--sort-list))
-        first-list))))
+        first-list)))
 
 ;; Definition at p. 343
 (defun parser-generator--follow (β)
diff --git a/test/parser-generator-test.el b/test/parser-generator-test.el
index d9b6ba1..aa42d97 100644
--- a/test/parser-generator-test.el
+++ b/test/parser-generator-test.el
@@ -148,7 +148,6 @@
   (parser-generator-set-grammar '((S) (a) ((S a)) S))
   (parser-generator-set-look-ahead-number 1)
   (parser-generator-process-grammar)
-
   (should
    (equal
     '((a))
@@ -158,7 +157,6 @@
   (parser-generator-set-grammar '((S) (a) ((S a)) S))
   (parser-generator-set-look-ahead-number 1)
   (parser-generator-process-grammar)
-
   (should
    (equal
     '((a))
@@ -168,7 +166,6 @@
   (parser-generator-set-grammar '((S) (a) ((S a)) S))
   (parser-generator-set-look-ahead-number 2)
   (parser-generator-process-grammar)
-
   (should
    (equal
     '((a a))
@@ -178,7 +175,6 @@
   (parser-generator-set-grammar '((S) (a) ((S a)) S))
   (parser-generator-set-look-ahead-number 2)
   (parser-generator-process-grammar)
-
   (should
    (equal
     '((a))
@@ -188,7 +184,6 @@
   (parser-generator-set-grammar '((S) ("a" "b" "c") ((S ("a" "b" "c"))) S))
   (parser-generator-set-look-ahead-number 2)
   (parser-generator-process-grammar)
-
   (should
    (equal
     '(("a" "b"))
@@ -198,7 +193,6 @@
   (parser-generator-set-grammar '((S) ("a" b "c") ((S ("a" b "c"))) S))
   (parser-generator-set-look-ahead-number 3)
   (parser-generator-process-grammar)
-
   (should
    (equal
     '(("a" b "c"))
@@ -208,7 +202,6 @@
   (parser-generator-set-grammar '((S A) (b) ((S A) (A b)) S))
   (parser-generator-set-look-ahead-number 2)
   (parser-generator-process-grammar)
-
   (should
    (equal
     '((b))
@@ -218,7 +211,6 @@
   (parser-generator-set-grammar '((S A) ("a" "b") ((S A) (A ("b" "a"))) S))
   (parser-generator-set-look-ahead-number 2)
   (parser-generator-process-grammar)
-
   (should
    (equal
     '(("b" "a"))
@@ -228,7 +220,6 @@
   (parser-generator-set-grammar '((S A) ("a" "b" "c" "d") ((S A) (A ("b" "a" 
"c" "d"))) S))
   (parser-generator-set-look-ahead-number 3)
   (parser-generator-process-grammar)
-
   (should
    (equal
     '(("b" "a" "c"))
@@ -238,7 +229,6 @@
   (parser-generator-set-grammar '((S A B) ("c" "d") ((S A) (A B) (B "c" "d")) 
S))
   (parser-generator-set-look-ahead-number 1)
   (parser-generator-process-grammar)
-
   (should
    (equal
     '(("c") ("d"))
@@ -248,7 +238,6 @@
   (parser-generator-set-grammar '((S A B) (a c d f) ((S (A a)) (A B) (B (c f) 
d)) S))
   (parser-generator-set-look-ahead-number 2)
   (parser-generator-process-grammar)
-
   (should
    (equal
     '((c f) (d a))
@@ -258,7 +247,6 @@
   (parser-generator-set-grammar '((S A B) ("a" "c" "d" "m") ((S A) (A (B "a" 
"m")) (B "c" "d")) S))
   (parser-generator-set-look-ahead-number 3)
   (parser-generator-process-grammar)
-
   (should
    (equal
     '(("c" "a" "m") ("d" "a" "m"))
@@ -268,7 +256,6 @@
   (parser-generator-set-grammar '((S A B C) (a b c) ((S (A B)) (A (B a) e) (B 
(C b) C) (C c e)) S))
   (parser-generator-set-look-ahead-number 1)
   (parser-generator-process-grammar)
-
   (should
    (equal
     '((a) (b) (c) (e))
@@ -279,7 +266,6 @@
   (parser-generator-set-grammar '((S A B C) (a b c) ((S (A B)) (A (B a) e) (B 
(C b) C) (C c e)) S))
   (parser-generator-set-look-ahead-number 2)
   (parser-generator-process-grammar)
-
   (should
    (equal
     '((a b) (a c) (a) (b a) (b) (c a) (c) (c b) (e))
@@ -289,7 +275,6 @@
   (parser-generator-set-grammar '((S A B C) (a b c) ((S (A B)) (A (B a) e) (B 
(C b) C) (C c e)) S))
   (parser-generator-set-look-ahead-number 3)
   (parser-generator-process-grammar)
-
   (should
    (equal
     '((a) (a b) (a c) (a c b) (b a) (b a b) (b a c) (b) (c a) (c a b) (c a c) 
(c b) (c) (c b a) (e))
@@ -313,8 +298,6 @@
     '((a) (e))
     (parser-generator--first 'S)))
   (message "Passed first 5 with complex grammar with starting e-identifier 
variant 2")
-
-  ;; TODO Fix i-max so it automatically is the highest needed number
   
   (parser-generator-set-grammar '((Sp S) (a b) ((Sp S) (S (S a S b) e)) Sp))
   (parser-generator-set-look-ahead-number 2)