[elpa] externals/parser-generator 8f9e4d4537 46/82: Passing 2 parse examples with k=2

[Christian Johansson]

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

    Passing 2 parse examples with k=2
---
 parser-generator-ll.el           |  42 +++++++-----
 test/parser-generator-ll-test.el | 137 ++++++++++++++++++++++++++++++++++++---
 2 files changed, 153 insertions(+), 26 deletions(-)

diff --git a/parser-generator-ll.el b/parser-generator-ll.el
index 19ff1790fd..3cd5a1825f 100644
--- a/parser-generator-ll.el
+++ b/parser-generator-ll.el
@@ -77,8 +77,15 @@
            (list
             (parser-generator--get-grammar-start))
            (list
-            parser-generator--eof-identifier))))
-        (output))
+            parser-generator--eof-identifier))
+          parser-generator--eof-identifier))
+        (output)
+        (eof-look-ahead
+         (parser-generator--generate-list-of-symbol
+          parser-generator--look-ahead-number
+          parser-generator--eof-identifier))
+        (e-reduction
+         (list parser-generator--e-identifier)))
     (parser-generator-lex-analyzer--reset)
     (while (not accept)
       (let* ((state (car stack))
@@ -89,8 +96,10 @@
              (look-ahead-list
               (parser-generator-lex-analyzer--peek-next-look-ahead))
              (look-ahead))
-        (message "\nstate: %S" state)
-        (message "\nstate-action-table: %S" state-action-table)
+        (message "\nstack: %S" stack)
+        (message "output: %S" output)
+        (message "state: %S" state)
+        (message "state-action-table: %S" state-action-table)
 
         (unless state-action-table
           (signal
@@ -103,12 +112,12 @@
         (if look-ahead-list
             (progn
               (message "look-ahead-list: %S" look-ahead-list)
-              (setq
-               look-ahead
-               (list (car (car look-ahead-list)))))
+              (dolist (look-ahead-list-item look-ahead-list)
+                (push (car look-ahead-list-item) look-ahead))
+              (setq look-ahead (reverse look-ahead)))
           (setq
            look-ahead
-           (list parser-generator--eof-identifier)))
+           eof-look-ahead))
 
         (message "look-ahead: %S" look-ahead)
 
@@ -137,24 +146,25 @@
             (setq action-type (car action)))
           (message "action-type: %S" action-type)
           (cond
+
            ((equal action-type 'pop)
-            (message "pushed: %S" look-ahead-list)
-            (push
-             (car (parser-generator-lex-analyzer--pop-token))
-             stack))
+            (message "pushed: %S" look-ahead)
+            (parser-generator-lex-analyzer--pop-token)
+            (pop stack))
 
            ((equal action-type 'reduce)
             (message "reduced: %S" (nth 1 action))
-            (push
-             (nth 1 action)
-             stack)
+            (pop stack)
+            (unless (equal (nth 1 action) e-reduction)
+              (dolist (reduce-item (reverse (nth 1 action)))
+                (push reduce-item stack)))
             (push
              (nth 2 action)
              output))
 
            ((equal action-type 'accept)
             (setq accept t))))))
-    output))
+    (reverse output)))
 
 
 ;;; Algorithms
diff --git a/test/parser-generator-ll-test.el b/test/parser-generator-ll-test.el
index 03d012f2e0..0ad363b268 100644
--- a/test/parser-generator-ll-test.el
+++ b/test/parser-generator-ll-test.el
@@ -279,25 +279,63 @@
 
   (parser-generator-set-eof-identifier '$)
   (parser-generator-set-e-identifier 'e)
-  (parser-generator-set-look-ahead-number 1)
+  (parser-generator-set-look-ahead-number 2)
   (parser-generator-set-grammar
    '(
      (S A)
      (a b)
      (
-      (S (a A S) b)
-      (A a (b S a))
+      (S (a A a a) (b A b a))
+      (A b e)
+      )
+     S
+     )
+   )
+  (parser-generator-process-grammar)
+  (parser-generator-ll-generate-parser-tables)
+  (setq
+   parser-generator-lex-analyzer--function
+   (lambda (index)
+     (let* ((string '((b 1 . 2) (b 2 . 3) (a 3 . 4)))
+            (string-length (length string))
+            (max-index index)
+            (tokens))
+       (while (and
+               (< (1- index) string-length)
+               (< (1- index) max-index))
+         (push (nth (1- index) string) tokens)
+         (setq index (1+ index)))
+       (nreverse tokens))))
+  (setq
+   parser-generator-lex-analyzer--get-function
+   (lambda (token)
+     (car token)))
+  (should
+   (equal
+    '(1 3) ;; Example is indexed from 1 so that is why they have '(2 4)
+    (parser-generator-ll-parse)))
+  (message "Passed example 5.16 p. 352")
+
+  (parser-generator-set-eof-identifier '$)
+  (parser-generator-set-e-identifier 'e)
+  (parser-generator-set-look-ahead-number 2)
+  (parser-generator-set-grammar
+   '(
+     (S A)
+     (a b)
+     (
+      (S e (a b A))
+      (A (S a a) b)
       )
      S
      )
    )
   (parser-generator-process-grammar)
   (parser-generator-ll-generate-parser-tables)
-  ;; (message "parser-generator-ll--parsing-table: %S" 
parser-generator-ll--parsing-table)
   (setq
    parser-generator-lex-analyzer--function
    (lambda (index)
-     (let* ((string '((a 1 . 2) (b 2 . 3) (b 3 . 4) (a 4 . 5) (b 5 . 6)))
+     (let* ((string '((a 1 . 2) (b 2 . 3) (a 3 . 4) (a 4 . 5)))
             (string-length (length string))
             (max-index index)
             (tokens))
@@ -314,14 +352,93 @@
   (parser-generator-ll-parse)
   (should
    (equal
-    '(1 4 2 3 2)
+    '(1 2 0) ;; Example is indexed from 1 so that is why they have '(2 3 1)
     (parser-generator-ll-parse)))
-  ;; TODO Test example 5.5 p. 340
+  (message "Passed example 5.17 p. 355")
 
+  (parser-generator-set-eof-identifier '$)
+  (parser-generator-set-e-identifier 'e)
+  (parser-generator-set-look-ahead-number 1)
+  (parser-generator-set-grammar
+   '(
+     (E E2 T T2 F)
+     ("a" "(" ")" "+" "*")
+     (
+      (E (T E2))
+      (E2 ("+" T E2) e)
+      (T (F T2))
+      (T2 ("*" F T2) e)
+      (F ("(" E ")") "a")
+      )
+     E
+     )
+   )
+  (parser-generator-process-grammar)
+  (parser-generator-ll-generate-parser-tables)
+  ;; (message "parser-generator-ll--parsing-table: %S" 
parser-generator-ll--parsing-table)
+  (setq
+   parser-generator-lex-analyzer--function
+   (lambda (index)
+     (let* ((string '(("(" 1 . 2) ("a" 2 . 3) ("*" 3 . 4) ("a" 4 . 5) (")" 5 . 
6)))
+            (string-length (length string))
+            (max-index index)
+            (tokens))
+       (while (and
+               (< (1- index) string-length)
+               (< (1- index) max-index))
+         (push (nth (1- index) string) tokens)
+         (setq index (1+ index)))
+       (nreverse tokens))))
+  (setq
+   parser-generator-lex-analyzer--get-function
+   (lambda (token)
+     (car token)))
+  (parser-generator-ll-parse)
+  (should
+   (equal
+    '(0 3 6 0 3 7 5 2 5) ;; Example is 1-indexed '(1 4 7 1 4 8 5 8 6 3 6 3)
+    (parser-generator-ll-parse)))
+  (message "Passed example 5.12 p. 346-347")
 
-  ;; TODO Test example 5.12 p. 346-347
-  ;; TODO Test example 5.16 p. 352
-  ;; TODO Test example 5.17 p. 355
+  (parser-generator-set-eof-identifier '$)
+  (parser-generator-set-e-identifier 'e)
+  (parser-generator-set-look-ahead-number 2)
+  (parser-generator-set-grammar
+   '(
+     (S A)
+     (a b)
+     (
+      (S e (a b A))
+      (A (S a a) b)
+      )
+     S
+     )
+   )
+  (parser-generator-process-grammar)
+  (parser-generator-ll-generate-parser-tables)
+  (setq
+   parser-generator-lex-analyzer--function
+   (lambda (index)
+     (let* ((string '((a 1 . 2) (b 2 . 3) (a 3 . 4) (a 4 . 5)))
+            (string-length (length string))
+            (max-index index)
+            (tokens))
+       (while (and
+               (< (1- index) string-length)
+               (< (1- index) max-index))
+         (push (nth (1- index) string) tokens)
+         (setq index (1+ index)))
+       (nreverse tokens))))
+  (setq
+   parser-generator-lex-analyzer--get-function
+   (lambda (token)
+     (car token)))
+  (parser-generator-ll-parse)
+  (should
+   (equal
+    '(1 2 0) ;; Example is indexed from 1 so that is why they have '(2 3 1)
+    (parser-generator-ll-parse)))
+  ;; TODO Test example 5.5 p. 340
 
   (message "Passed tests for (parser-generator-ll-parse)"))