[elpa] externals/parser-generator 0a86c69ef1 19/82: More work on LL-table generation

[Christian Johansson]

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

    More work on LL-table generation
---
 parser-generator-ll.el           | 48 ++++++++++++++--------
 test/parser-generator-ll-test.el | 88 +++++++++++++++++-----------------------
 2 files changed, 68 insertions(+), 68 deletions(-)

diff --git a/parser-generator-ll.el b/parser-generator-ll.el
index 4ccc6ca159..1bce7e702c 100644
--- a/parser-generator-ll.el
+++ b/parser-generator-ll.el
@@ -44,7 +44,6 @@
 ;; Algorithm 5.2 p. 350
 (defun parser-generator-ll--generate-tables ()
   "Construction of LL(k)-tables.  Output the set of LL(k) tables needed to 
construct a parsing table for the grammar G."
-
   (let ((tables (make-hash-table :test 'equal))
         (distinct-item-p (make-hash-table :test 'equal))
         (stack)
@@ -78,7 +77,9 @@
               (parser-generator--first production-rhs nil t t))
              (first-parent-follow
               (parser-generator--first parent-follow nil t t))
-             (look-aheads))
+             (look-aheads)
+             (sets)
+             (distinct-set-item-p (make-hash-table :test 'equal)))
 
         (cond
          ((and first-rhs
@@ -149,6 +150,16 @@
                                (list sub-symbol)
                                sub-symbol-rhs
                                local-follow)))
+                        (unless (gethash
+                                 local-follow
+                                 distinct-set-item-p)
+                          (puthash
+                           local-follow
+                           t
+                           distinct-set-item-p)
+                          (push
+                           local-follow
+                           sets))
                         (parser-generator--debug
                          (message "new-stack-item: %S" new-stack-item))
                         (push
@@ -165,7 +176,8 @@
             (let ((table
                    (list
                     look-ahead
-                    production-rhs))
+                    production-rhs
+                    sets))
                   (item-hash-key
                    (format
                     "%S-%S-%S"
@@ -208,12 +220,11 @@
          (message "first-parent-follow: %S" first-parent-follow)
          (message "look-aheads: %S" look-aheads))))
 
-    ;; TODO Add deterministic sorting here
     (let ((sorted-tables))
       (maphash
        (lambda (k v)
          (push
-          (list k v)
+          (list k (sort v 'parser-generator--sort-list))
           sorted-tables))
        tables)
       sorted-tables)))
@@ -224,19 +235,20 @@
 (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))
-
-    ;; (2) M(a, av) = pop for all v in E where |E| = k-1
-
-    ;; (3) M($, e) = accept
-    (push
-     `(,parser-generator--eof-identifier
-       (
-        ,(parser-generator--generate-list-of-symbol
-          parser-generator--look-ahead-number
-          parser-generator--eof-identifier)
-        accept)
-       )
-     parsing-table)
+    (dolist (table tables)
+      (let* ((key (nth 0 table))
+             (value (nth 1 table))
+             (stack-symbol (car (nth 0 key)))
+             (local-follow-set (nth 1 key)))
+        (dolist (look-ahead-row value)
+          (let ((look-ahead (nth 0 look-ahead-row))
+                (right-hand-side (nth 1 look-ahead-row)))
+            (dolist (right-hand-symbol right-hand-side))
+            ))))
+
+    ;; 
+    ;; (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 561b5ad7cc..6585373579 100644
--- a/test/parser-generator-ll-test.el
+++ b/test/parser-generator-ll-test.el
@@ -33,34 +33,35 @@
    )
   (parser-generator-process-grammar)
   (let ((tables (parser-generator-ll--generate-tables)))
-    (message "tables: %S" tables)
+    ;; (message "tables: %S" tables)
     (should
      (equal
       tables
       '(
         (
-         ((S) nil)
+         ((A) (b a))
          (
-          ((a b) (a A a a))
-          ((a a) (a A a a))
-          ((b b) (b A b a))
+          ((b b) (b) nil)
+          ((b a) (e) nil)
           )
          )
         (
          ((A) (a a))
          (
-          ((a a) (e))
-          ((b a) (b))
+          ((a a) (e) nil)
+          ((b a) (b) nil)
           )
          )
         (
-         ((A) (b a))
+         ((S) nil)
          (
-          ((b b) (b))
-          ((b a) (e))
+          ((a b) (a A a a) ((a a)))
+          ((a a) (a A a a) ((a a)))
+          ((b b) (b A b a) ((b a)))
           )
          )
-        )))
+        )
+      ))
     tables)
 
   (message "Passed tests for (parser-generator-ll--generate-tables)"))
@@ -73,10 +74,9 @@
   (parser-generator-set-e-identifier 'e)
   (parser-generator-set-look-ahead-number 2)
   (let* ((tables
-         '(
-           (0 (((S) nil (a b) (a A a a)) ((S) nil (a a) (a A a a)) ((S) nil (b 
b) (b A b a))))
-           (1 (((A) (a a) (a a) (e)) ((A) (a a) (b a) (b))))
-           (2 (((A) (b a) (b b) (b)) ((A) (b a) (b a) (e))))))
+          '((((A) (b a)) (((b b) (b) nil) ((b a) (e) nil)))
+            (((A) (a a)) (((a a) (e) nil) ((b a) (b) nil)))
+            (((S) nil) (((a b) (a A a a) ((a a))) ((a a) (a A a a) ((a a))) 
((b b) (b A b a) ((b a)))))))
          (parser-tables
           (parser-generator-ll--generate-parsing-table
            tables)))
@@ -86,42 +86,30 @@
     (should
      (equal
       '(
-        (T0 (
-             ((a a) reduce (a T1 a a) 1)
-             ((a b) reduce (a T1 a a) 1)
-             ((b b) reduce (b T2 b a) 2)
-             )
-            )
-        (T1 (
-             ((a a) reduce (e) 4)
-             ((b a) reduce (b) 3)
-             )
-            )
-        (T2 (
-             ((b a) reduce (e) 4)
-             ((b b) reduce (b) 3)
-             )
-            )
-        (a (
-            ((a a) pop)
-            ((a b) pop)
-            ((a $) pop)
-            )
-           )
-        (b (
-            ((b a) pop)
-            ((b b) pop)
-            ((b $) pop)
-            )
-           )
-        ($ (
-            (($ $) accept)
-            )
-           )
+        (
+         ((S) nil)
+         (
+          ((a a) reduce (a T1 a a) 1)
+          ((a b) reduce (a T1 a a) 1)
+          ((b b) reduce (b T2 b a) 2)
+          )
+         )
+        (
+         ((A) (a a))
+         (
+          ((a a) reduce (e) 4)
+          ((b a) reduce (b) 3)
+          )
+         )
+        (
+         ((A) (a b))
+         (
+          ((b a) reduce (e) 4)
+          ((b b) reduce (b) 3)
+          )
+         )
         )
-      ))
-
-    )
+      parser-tables)))
 
   (message "Passed tests for (parser-generator-ll--generate-parsing-table)"))