[elpa] externals/parser-generator fe728f8ad8 23/82: Passing test for generating LLk parser table

[Christian Johansson]

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

    Passing test for generating LLk parser table
---
 parser-generator-ll.el           | 52 ++++++++++++++++++++++++++++++++++++----
 test/parser-generator-ll-test.el | 23 ++++++++++++++++--
 2 files changed, 69 insertions(+), 6 deletions(-)

diff --git a/parser-generator-ll.el b/parser-generator-ll.el
index 6c2410a2e3..96d0493ada 100644
--- a/parser-generator-ll.el
+++ b/parser-generator-ll.el
@@ -224,11 +224,58 @@
       sorted-tables)))
 
 
-;; TODO
 ;; Algorithm 5.3 p. 351
 (defun parser-generator-ll--generate-parsing-table (tables)
   "Generate a parsing table for an LL(k) grammar G and TABLES.  Output M, a 
valid parsing table for G."
   (let ((parsing-table))
+
+    ;; (3) M($, e) = accept
+    ;; (2) M(a, av) = pop for all v in E where |E| = k-1
+    (let ((eof-look-ahead
+           (parser-generator--generate-list-of-symbol
+            parser-generator--look-ahead-number
+            parser-generator--eof-identifier))
+          (terminal-mutations
+           (parser-generator--get-grammar-look-aheads))
+          (terminal-buffer)
+          (last-terminal))
+      (dolist (terminal-mutation terminal-mutations)
+        (if (equal terminal-mutation eof-look-ahead)
+            (push
+             (list
+              parser-generator--eof-identifier
+              (list
+               eof-look-ahead
+               'accept))
+             parsing-table)
+          (let ((stack-item (nth 0 terminal-mutation)))
+            (when (and
+                   last-terminal
+                   (not (equal last-terminal stack-item)))
+              (push
+               (list
+                last-terminal
+                terminal-buffer)
+               parsing-table)
+              (setq
+               terminal-buffer
+               nil))
+
+            (push
+             (list terminal-mutation 'pop)
+             terminal-buffer)
+            (setq
+             last-terminal
+             stack-item))))
+      (when (and
+             last-terminal
+             terminal-buffer)
+        (push
+         (list
+          last-terminal
+          terminal-buffer)
+         parsing-table)))
+
     (dolist (table tables)
       (let* ((key (nth 0 table))
              (value (nth 1 table))
@@ -284,9 +331,6 @@
           parse-table)
          parsing-table)))
 
-    ;; (2) M(a, av) = pop for all v in E where |E| = k-1 -> move to parser 
logic
-    ;; (3) M($, e) = accept -> move to parser logic
-
     parsing-table))
 
 
diff --git a/test/parser-generator-ll-test.el b/test/parser-generator-ll-test.el
index 01bbe32066..37c84fa6cb 100644
--- a/test/parser-generator-ll-test.el
+++ b/test/parser-generator-ll-test.el
@@ -104,7 +104,6 @@
            tables)))
     ;; (message "parser-tables: %S" parser-tables)
 
-    ;; TODO Make this pass
     (should
      (equal
       '(
@@ -124,12 +123,32 @@
           )
          )
         (
-         ((A) (b a)) ;; T2
+         ((A) (b a));; T2
          (
           ((b a) reduce (e) 3)
           ((b b) reduce (b) 2)
           )
          )
+        (
+         b
+         (
+          ((b b) pop)
+          ((b a) pop)
+          ((b $) pop)
+          )
+         )
+        (
+         a
+         (
+          ((a b) pop)
+          ((a a) pop)
+          ((a $) pop)
+          )
+         )
+        (
+         $
+         (($ $) accept)
+         )
         )
       parser-tables)))