[elpa] externals/parser-generator a4bbb2f 026/434: Using PDA algorithm for FIRST when β is above 1 symbol

[ELPA Syncer]

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

    Using PDA algorithm for FIRST when β is above 1 symbol
---
 parser.el           | 91 ++++++++++++++++++++++++++++-------------------------
 test/parser-test.el |  8 ++---
 2 files changed, 53 insertions(+), 46 deletions(-)

diff --git a/parser.el b/parser.el
index 34b3ae7..82a8358 100644
--- a/parser.el
+++ b/parser.el
@@ -487,48 +487,55 @@
       (parser--debug
        (message "Generated F-sets"))
 
-      ;; Iterate each symbol in β using a PDA algorithm
-      (let ((input-tape β)
-            (input-tape-length (length β))
-            (stack '((0 0 nil)))
-            (first-list nil))
-        (while stack
-          (let ((stack-topmost (pop stack)))
-            (parser--debug
-             (message "stack-topmost: %s" stack-topmost))
-            (let ((input-tape-index (car stack-topmost))
-                  (first-length (car (cdr stack-topmost)))
-                  (first (car (cdr (cdr stack-topmost)))))
-              (while (and
-                      (< input-tape-index input-tape-length)
-                      (< first-length k))
-                (let ((symbol (nth input-tape-index input-tape)))
-                  (cond
-                   ((parser--valid-terminal-p symbol)
-                    (push symbol first)
-                    (setq first-length (1+ first-length)))
-                   ((parser--valid-non-terminal-p symbol)
-                    (parser--debug
-                     (message "non-terminal symbol: %s" symbol))
-                    (let ((symbol-f-set (gethash symbol (gethash (1- i-max) 
parser--f-sets))))
-                      (parser--debug
-                       (message "symbol-f-set: %s" symbol-f-set))
-                      (when (> (length symbol-f-set) 1)
-                        ;; Handle this scenario here were a non-terminal can 
result in different FIRST sets
-                        (let ((symbol-f-set-index 1)
-                              (symbol-f-set-length (length symbol-f-set)))
-                          (while (< symbol-f-set-index symbol-f-set-length)
-                            (let ((symbol-f-set-element (nth 
symbol-f-set-index symbol-f-set)))
-                              (let ((alternative-first-length (+ first-length 
(length symbol-f-set-element)))
-                                    (alternative-first (append first 
symbol-f-set-element))
-                                    (alternative-tape-index (1+ 
input-tape-index)))
-                                (push `(,alternative-tape-index 
,alternative-first-length ,alternative-first) stack)))
-                            (setq symbol-f-set-index (1+ 
symbol-f-set-index)))))
-                      (setq first-length (+ first-length (length (car 
symbol-f-set))))
-                      (setq first (append first (car symbol-f-set)))))))
-                (setq input-tape-index (1+ input-tape-index)))
-              (when (> first-length 0)
-                (push first first-list)))))
+      (let ((first-list nil))
+        (if (> (length β) 1)
+            ;; Iterate each symbol in β using a PDA algorithm
+            (let ((input-tape β)
+                  (input-tape-length (length β))
+                  (stack '((0 0 nil)))
+                  (first-list nil))
+              (while stack
+                (let ((stack-topmost (pop stack)))
+                  (parser--debug
+                   (message "stack-topmost: %s" stack-topmost))
+                  (let ((input-tape-index (car stack-topmost))
+                        (first-length (car (cdr stack-topmost)))
+                        (first (car (cdr (cdr stack-topmost)))))
+                    (while (and
+                            (< input-tape-index input-tape-length)
+                            (< first-length k))
+                      (let ((symbol (nth input-tape-index input-tape)))
+                        (cond
+                         ((parser--valid-terminal-p symbol)
+                          (push symbol first)
+                          (setq first-length (1+ first-length)))
+                         ((parser--valid-non-terminal-p symbol)
+                          (parser--debug
+                           (message "non-terminal symbol: %s" symbol))
+                          (let ((symbol-f-set (gethash symbol (gethash (1- 
i-max) parser--f-sets))))
+                            (parser--debug
+                             (message "symbol-f-set: %s" symbol-f-set))
+                            (when (> (length symbol-f-set) 1)
+                              ;; Handle this scenario here were a non-terminal 
can result in different FIRST sets
+                              (let ((symbol-f-set-index 1)
+                                    (symbol-f-set-length (length 
symbol-f-set)))
+                                (while (< symbol-f-set-index 
symbol-f-set-length)
+                                  (let ((symbol-f-set-element (nth 
symbol-f-set-index symbol-f-set)))
+                                    (let ((alternative-first-length (+ 
first-length (length symbol-f-set-element)))
+                                          (alternative-first (append first 
symbol-f-set-element))
+                                          (alternative-tape-index (1+ 
input-tape-index)))
+                                      (parser--debug
+                                       (message "alternative-first: %s" 
alternative-first))
+                                      (push `(,alternative-tape-index 
,alternative-first-length ,alternative-first) stack)))
+                                  (setq symbol-f-set-index (1+ 
symbol-f-set-index)))))
+                            (parser--debug
+                             (message "main-symbol-f-set: %s" (car 
symbol-f-set)))
+                            (setq first-length (+ first-length (length (car 
symbol-f-set))))
+                            (setq first (append first (car symbol-f-set)))))))
+                      (setq input-tape-index (1+ input-tape-index)))
+                    (when (> first-length 0)
+                      (push first first-list))))))
+          (setq first-list (gethash (car β) (gethash (1- i-max) 
parser--f-sets))))
         first-list))))
 
 (defun parser--v-set (y)
diff --git a/test/parser-test.el b/test/parser-test.el
index 2c77500..1b27845 100644
--- a/test/parser-test.el
+++ b/test/parser-test.el
@@ -73,28 +73,28 @@
   (parser--set-grammar '((S A B) ("c" "d") ((S A) (A B) (B "c" "d")) S) 1)
   (should
    (equal
-    '(("d") ("c"))
+    '(("c") ("d"))
     (parser--first 'S)))
   (message "Passed first 1 with semi-complex grammar")
 
   (parser--set-grammar '((S A B) (a c d f) ((S (A a)) (A B) (B (c f) d)) S) 2)
   (should
    (equal
-    '((d a) (c f))
+    '((c f) (d a))
     (parser--first 'S)))
   (message "Passed first 2 with semi-complex grammar")
 
   (parser--set-grammar '((S A B) ("a" "c" "d" "m") ((S A) (A (B "a" "m")) (B 
"c" "d")) S) 3)
   (should
    (equal
-    '(("d" "a" "m") ("c" "a" "m"))
+    '(("c" "a" "m") ("d" "a" "m"))
     (parser--first 'S)))
   (message "Passed first 3 with semi-complex grammar")
 
   (parser--set-grammar '((S A B C) (a b c) ((S A B) (A (B a) e) (B (C b) C) (C 
c e)) S) 1)
   (should
    (equal
-    '((e) (c) (b) (a))
+    '((a) (e) (c) (b) )
     (parser--first 'S)))
   (message "Passed first 1 with complex grammar")