[elpa] externals/parser-generator 9d6ca94d0e 02/82: More work on LL(k) parser

[Christian Johansson]

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

    More work on LL(k) parser
---
 parser-generator-ll.el           | 21 ++++++++++++++++++++-
 test/parser-generator-ll-test.el | 17 +++++++++++++++++
 2 files changed, 37 insertions(+), 1 deletion(-)

diff --git a/parser-generator-ll.el b/parser-generator-ll.el
index c488f3af48..b120cce04a 100644
--- a/parser-generator-ll.el
+++ b/parser-generator-ll.el
@@ -45,7 +45,26 @@
 ;; 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)
+        (distinct-table-p (make-hash-table :test 'equal))
+        ;; (1) Construct T_0, the LL(k) table associated with S {e}
+        (stack `((,(parser-generator--get-grammar-start) nil)))
+        (stack-item))
+    (while stack
+      (setq stack-item (pop stack))
+      (let* ((production (nth 0 stack-item))
+             (dot-look-ahead (nth 1 stack-item))
+             (first-production (parser-generator--first production nil t t))
+             (first-dot-look-ahead (parser-generator--first dot-look-ahead nil 
t t))
+             (look-aheads (parser-generator--merge-max-terminals 
first-production first-dot-look-ahead)))
+        (parser-generator--debug
+         (message "production: %S" production)
+         (message "dot-look-ahead: %S" dot-look-ahead)
+         (message "first-production: %S" first-production)
+         (message "first-dot-look-ahead: %S" first-dot-look-ahead)
+         (message "look-aheads: %S" look-aheads))))
+    tables))
 
 
 ;; TODO
diff --git a/test/parser-generator-ll-test.el b/test/parser-generator-ll-test.el
index 9c13d1fc95..11f4d773e7 100644
--- a/test/parser-generator-ll-test.el
+++ b/test/parser-generator-ll-test.el
@@ -23,6 +23,23 @@
   "Test `parser-generator-ll--generate-parsing-table'."
   (message "Started tests for (parser-generator-ll--generate-parsing-table)")
 
+  ;; Example 5.15 p. 351
+  (parser-generator-set-e-identifier 'e)
+  (parser-generator-set-look-ahead-number 2)
+  (parser-generator-set-grammar
+   '(
+     (S A)
+     (a b)
+     (
+      (S (a A a a) (b A b a))
+      (A b e)
+      )
+     S
+     )
+   )
+  (parser-generator-process-grammar)
+  (let ((tables (parser-generator-ll--generate-tables)))
+    (message "tables: %S" tables))
 
   (message "Passed tests for (parser-generator-ll--generate-parsing-table)"))