[elpa] externals/parser-generator af3740c46a 59/82: More refactoring

[Christian Johansson]

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

    More refactoring
---
 parser-generator-ll.el           |  97 ++++++++++----
 test/parser-generator-ll-test.el | 265 ++++++++++++++++++++-------------------
 2 files changed, 211 insertions(+), 151 deletions(-)

diff --git a/parser-generator-ll.el b/parser-generator-ll.el
index 55eaeaecef..05d4fcbd1d 100644
--- a/parser-generator-ll.el
+++ b/parser-generator-ll.el
@@ -17,9 +17,9 @@
 
 
 (defvar
-  parser-generator-ll--parsing-table
+  parser-generator-ll--table
   nil
-  "Parsing-table for grammar.")
+  "Table for grammar.")
 
 
 ;;; Functions
@@ -27,11 +27,14 @@
 
 (defun parser-generator-ll-generate-tables ()
   "Generate tables for grammar."
-  (message "\n;; Starting generation of LL(k) tables..\n")
   (if (> parser-generator--look-ahead-number 1)
-      (parser-generator-ll--generate-parser-tables-k-gt-1)
-    (parser-generator-ll--generate-parser-tables-k-eq-1))
-  (message "\n;; Completed generation of LL(k) tables.\n"))
+      (progn
+        (message "\n;; Starting generation of LL(k) tables..\n")
+        (parser-generator-ll--generate-tables-k-gt-1)
+        (message "\n;; Completed generation of LL(k) tables.\n"))
+    (message "\n;; Starting generation of LL(1) tables..\n")
+    (parser-generator-ll--generate-tables-k-eq-1)
+    (message "\n;; Completed generation of LL(1) tables.\n")))
 
 ;; Generally described at .p 339
 (defun parser-generator-ll-parse ()
@@ -59,7 +62,7 @@
              (state-action-table
               (gethash
                (format "%S" state)
-               parser-generator-ll--parsing-table))
+               parser-generator-ll--table))
              (look-ahead-list
               (parser-generator-lex-analyzer--peek-next-look-ahead))
              (look-ahead))
@@ -142,16 +145,28 @@
 ;;; Algorithms
 
 
-(defun parser-generator-ll--generate-parser-tables-k-gt-1 ()
-  "Generate parsing tables for grammar k > 1."
-  (message "\n;; Starting generation of LL(k) parser-tables..\n")
-  (unless (parser-generator-ll--valid-grammar-p-k-gt-1)
-    (error "Invalid grammar specified!"))
+(defun parser-generator-ll--generate-table-k-eq-1 ()
+  "Generate table for LL(1) grammar."
+  (message "\n;; Starting generation of LL(1) table..\n")
+  (unless (parser-generator-ll--valid-grammar-p-k-eq-1)
+    (error "Invalid LL(1) grammar specified!"))
+  (let (hash-parsing-table (make-hash-table :test 'equal))
+    ;; TODO Iterate all non-terminals here
+    ;; TODO Add non-terminal -> FIRST(non-terminal) -> reduce RHS, 
production-number
+    ;; TODO Iterate all possible look-aheds
+    ;; TODO Added EOF symbol
+    (setq
+     parser-generator-ll--table
+     hash-parsing-table)))
+
+(defun parser-generator-ll--generate-table-k-gt-1 ()
+  "Generate table for LL(k) grammar."
+  (message "\n;; Starting generation of LL(k) table..\n")
+  (unless (parser-generator-ll--valid-grammar-k-gt-1-p)
+    (error "Invalid LL(k) grammar specified!"))
   (let ((list-parsing-table
-         (if (> parser-generator--look-ahead-number 1)
-             (parser-generator-ll--generate-parsing-table-k-gt-1
-              (parser-generator-ll--generate-tables-k-gt-1))
-           (parser-generator-ll--generate-parsing-table-k-eq-1)))
+         (parser-generator-ll--generate-action-table-k-gt-1
+          (parser-generator-ll--generate-goto-table-k-gt-1)))
         (hash-parsing-table (make-hash-table :test 'equal)))
     (dolist (state-list list-parsing-table)
       (let ((state-key (nth 0 state-list))
@@ -181,12 +196,12 @@
          state-hash-table
          hash-parsing-table)))
     (setq
-     parser-generator-ll--parsing-table
+     parser-generator-ll--table
      hash-parsing-table)))
 
 ;; Algorithm 5.2 p. 350
-(defun parser-generator-ll--generate-tables-k-gt-1 ()
-  "Construction of LL(k)-tables were k > 1.  Output the set of LL(k) tables 
needed to construct a parsing table for the grammar G."
+(defun parser-generator-ll--generate-goto-table-k-gt-1 ()
+  "Construction of LL(k) GOTO-table.  Output the set of LL(k) tables needed to 
construct a action table for the grammar G."
   (let ((tables (make-hash-table :test 'equal))
         (distinct-item-p (make-hash-table :test 'equal))
         (stack)
@@ -395,8 +410,8 @@
       sorted-tables)))
 
 ;; Algorithm 5.3 p. 351
-(defun parser-generator-ll--generate-parsing-table-k-gt-1 (tables)
-  "Generate a parsing table for an LL(k) grammar G and TABLES.  Output M, a 
valid parsing table for G."
+(defun parser-generator-ll--generate-action-table-k-gt-1 (tables)
+  "Generate a action table for an LL(k) grammar G and TABLES.  Output M, a 
valid parsing table for G."
   (let ((parsing-table))
 
     ;; (3) M($, e) = accept
@@ -503,9 +518,45 @@
 
     parsing-table))
 
+(defun parser-generator-ll--valid-grammar-k-eq-1-p ()
+  "Test for LL(1)-ness.  Output t if grammar is LL(1), nil otherwise."
+  (let* ((non-terminals (parser-generator--get-grammar-non-terminals))
+         (non-terminal-length (length non-terminals))
+         (non-terminal-index 0)
+         (non-terminal)
+         (valid t))
+    (while (and
+            valid
+            (< non-terminal-index non-terminal-length))
+      (setq non-terminal (nth non-terminal-index non-terminals))
+      (let* ((rhss (parser-generator--get-grammar-rhs non-terminals))
+             (rhss-length (length rhss))
+             (rhss-index 0)
+             (rhs)
+             (look-aheads (make-hash-table :test 'equal)))
+        (while (and
+                valid
+                (< rhss-index rhss-length))
+          (setq rhs (nth rhss-index rhss))
+          (let* ((firsts-rhs (parser-generator--first rhs))
+                 (firsts-rhs-length (length firsts-rhs))
+                 (firsts-index 0))
+            (while (and
+                    valid
+                    (< firsts-index firsts-rhs-length))
+              (setq first-rhs (nth firsts-index firsts-rhs))
+              (let ((first-rhs-hash (format "%S" first-rhs)))
+                (if (gethash first-rhs-hash look-aheads)
+                    (setq valid nil)
+                  (puthash first-rhs-hash t look-aheads)))
+              (setq firsts-index (1+ firsts-index))))
+          (setq rhss-index (1+ rhss-index))))
+      (setq non-terminal-index (1+ non-terminal-index)))
+    valid))
+
 ;; Algorithm 5.4 p. 357
-(defun parser-generator-ll--valid-grammar-p-k-gt-1 ()
-  "Test for LL(k)-ness.  Output t if grammar is LL(k).  nil otherwise."
+(defun parser-generator-ll--valid-grammar-k-gt-1-p ()
+  "Test for LL(k)-ness.  Output t if grammar is LL(k), nil otherwise."
   (let ((stack)
         (stack-item)
         (distinct-production-p (make-hash-table :test 'equal))
diff --git a/test/parser-generator-ll-test.el b/test/parser-generator-ll-test.el
index e9026532a0..785362e46f 100644
--- a/test/parser-generator-ll-test.el
+++ b/test/parser-generator-ll-test.el
@@ -12,9 +12,9 @@
 (require 'parser-generator-ll)
 (require 'ert)
 
-(defun parser-generator-ll-test--generate-tables-k-gt-1 ()
-  "Test `parser-generator-ll--generate-tables-k-gt-1'."
-  (message "Started tests for (parser-generator-ll--generate-tables-k-gt-1)")
+(defun parser-generator-ll-test--generate-goto-table-k-gt-1 ()
+  "Test `parser-generator-ll--generate-goto-table-k-gt-1'."
+  (message "Started tests for 
(parser-generator-ll--generate-goto-table-k-gt-1)")
 
   (parser-generator-set-e-identifier 'e)
   (parser-generator-set-look-ahead-number 2)
@@ -30,7 +30,7 @@
      )
    )
   (parser-generator-process-grammar)
-  (let ((tables (parser-generator-ll--generate-tables-k-gt-1)))
+  (let ((tables (parser-generator-ll--generate-goto-table-k-gt-1)))
     ;; (message "tables: %S" tables)
     (should
      (equal
@@ -79,7 +79,7 @@
    )
   (parser-generator-process-grammar)
   (let* ((tables
-          (parser-generator-ll--generate-tables-k-gt-1)))
+          (parser-generator-ll--generate-goto-table-k-gt-1)))
     ;; (message "tables: %S" tables)
     (should
      (equal
@@ -138,7 +138,7 @@
    )
   (parser-generator-process-grammar)
   (let* ((tables
-          (parser-generator-ll--generate-tables)))
+          (parser-generator-ll--generate-goto-table-k-gt-1)))
     ;; (message "tables: %S" tables)
     (should
      (equal
@@ -181,7 +181,7 @@
      )
    )
   (parser-generator-process-grammar)
-  (let ((tables (parser-generator-ll--generate-tables)))
+  (let ((tables (parser-generator-ll--generate-goto-table-k-gt-1)))
     ;; (message "tables: %S" tables)
     (should
      (equal
@@ -225,13 +225,11 @@
       tables)))
   (message "Passed Example 5.12 p. 346-347")
 
-  (message "Passed tests for (parser-generator-ll--generate-tables-k-gt-1)"))
+  (message "Passed tests for 
(parser-generator-ll--generate-goto-table-k-gt-1)"))
 
-(defun parser-generator-ll-test--generate-parsing-table-k-gt-1 ()
-  "Test `parser-generator-ll--generate-parsing-table'."
-  (message "Started tests for 
(parser-generator-ll--generate-parsing-table-k-gt-1)")
-
-  ;; TODO Need to make this tests pass, RHS after reduction should be single 
dimension list
+(defun parser-generator-ll-test--generate-action-table-k-gt-1 ()
+  "Test `parser-generator-ll--generate-action-table-k-gt-1'."
+  (message "Started tests for 
(parser-generator-ll--generate-action-table-k-gt-1)")
 
   (parser-generator-set-e-identifier 'e)
   (parser-generator-set-look-ahead-number 2)
@@ -248,8 +246,8 @@
    )
   (parser-generator-process-grammar)
   (let ((parser-tables
-         (parser-generator-ll--generate-parsing-table-k-gt-1
-          (parser-generator-ll--generate-tables))))
+         (parser-generator-ll--generate-action-table-k-gt-1
+          (parser-generator-ll--generate-goto-table-k-gt-1))))
     ;; (message "parser-tables: %S" parser-tables)
     (should
      (equal
@@ -299,9 +297,9 @@
    )
   (parser-generator-process-grammar)
   (let* ((tables
-          (parser-generator-ll--generate-tables))
+          (parser-generator-ll--generate-goto-table-k-gt-1))
          (parser-tables
-          (parser-generator-ll--generate-parsing-table-k-gt-1
+          (parser-generator-ll--generate-action-table-k-gt-1
            tables)))
     ;; (message "tables: %S" tables)
     ;; (message "parser-tables: %S" parser-tables)
@@ -345,105 +343,7 @@
       parser-tables)))
   (message "Passed Example 5.17 p. 356")
 
-  ;; TODO Move below to separate test
-
-  (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-process-grammar)
-  (let* ((tables
-          (parser-generator-ll--generate-tables))
-          (parser-tables
-           (parser-generator-ll--generate-parsing-table-k-gt-1
-            tables)))
-    ;; (message "tables: %S" tables)
-    ;; (message "parser-tables: %S" parser-tables)
-    (should
-     (equal
-      '(
-        (
-         ((E) ($))
-         (
-          (("a") reduce (((T) ($)) ((T) ("+")) ((E2) ($))) 0)
-          (("(") reduce (((T) ($)) ((T) ("+")) ((E2) ($))) 0)
-          )
-         )
-        (
-         ((E2) ($))
-         (
-          (("+") reduce ("+" ((T) ($)) ((T) ("+")) ((E2) ($))) 1)
-          (($) reduce (e) 2)
-          )
-         )
-        (
-         ((T) ("+"))
-         (
-          (("a") reduce (((F) ("*")) ((F) ("+")) ((T2) ("+"))) 3)
-          (("(") reduce (((F) ("*")) ((F) ("+")) ((T2) ("+"))) 3)
-          )
-         )
-        (
-         ((T2) ("+"))
-         (
-          (("+") reduce (e) 5)
-          (("*") reduce ("*" ((F) ("*")) ((F) ("+")) ((T2) ("+"))) 4)
-          )
-         )
-        (
-         ((F) ("+"))
-         (
-          (("a") reduce ("a") 7)
-          (("(") reduce ("(" ((E) (")")) ")") 6)
-          )
-         )
-        (
-         ((E) (")"))
-         (
-          (("a") reduce (((T) (")")) ((T) ("+")) ((E2) (")"))) 0)
-          (("(") reduce (((T) (")")) ((T) ("+")) ((E2) (")"))) 0)
-          )
-         )
-        (
-         ((E2) (")"))
-         (
-          (("+") reduce ("+" ((T) (")")) ((T) ("+")) ((E2) (")"))) 1)
-          ((")") reduce (e) 2)
-          )
-         )
-        (((T) (")")) ((("a") reduce (((F) (")")) ((F) ("*")) ((T2) (")"))) 3) 
(("(") reduce (((F) (")")) ((F) ("*")) ((T2) (")"))) 3)))
-        (((T2) (")")) ((("*") reduce ("*" ((F) (")")) ((F) ("*")) ((T2) 
(")"))) 4) ((")") reduce (e) 5)))
-        (((F) (")")) ((("a") reduce ("a") 7) (("(") reduce ("(" ((E) (")")) 
")") 6)))
-        (((F) ("*")) ((("a") reduce ("a") 7) (("(") reduce ("(" ((E) (")")) 
")") 6)))
-        (((T) ($)) ((("a") reduce (((F) ($)) ((F) ("*")) ((T2) ($))) 3) (("(") 
reduce (((F) ($)) ((F) ("*")) ((T2) ($))) 3)))
-        (((T2) ($)) ((("*") reduce ("*" ((F) ($)) ((F) ("*")) ((T2) ($))) 4) 
(($) reduce (e) 5)))
-        (((F) ($)) ((("a") reduce ("a") 7) (("(") reduce ("(" ((E) (")")) ")") 
6)))
-        ("a" ((("a") pop)))
-        ("+" ((("+") pop)))
-        ("*" ((("*") pop)))
-        (")" (((")") pop)))
-        ("(" ((("(") pop)))
-        ($ ((($) accept)))
-        )
-      parser-tables)))
-  ;; TODO Verify above
-  (message "Passed Example 5.12 p. 346-347")
-
-  (message "Passed tests for (parser-generator-ll--generate-parsing-table)"))
+  (message "Passed tests for 
(parser-generator-ll--generate-action-table-k-gt-1)"))
 
 (defun parser-generator-ll-test--parse ()
   "Test `parser-generator-ll-parse'."
@@ -678,9 +578,9 @@
 
   (message "Passed tests for (parser-generator-ll-generate-tables)"))
 
-(defun parser-generator-ll-test--valid-grammar-p-k-gt-1 ()
-  "Test `parser-generator-ll--valid-grammar-p-k-gt-1'."
-  (message "Started tests for (parser-generator-ll--valid-grammar-p-k-gt-1)")
+(defun parser-generator-ll-test--valid-grammar-k-gt-1-p ()
+  "Test `parser-generator-ll--valid-grammar-k-gt-1-p'."
+  (message "Started tests for (parser-generator-ll--valid-grammar-k-gt-1-p)")
 
   ;; Example 5.14 p. 350
   ;; Example 5.15 p. 351
@@ -700,7 +600,7 @@
   (parser-generator-process-grammar)
   (should
    (equal
-    (parser-generator-ll--valid-grammar-p-k-gt-1)
+    (parser-generator-ll--valid-grammar-k-gt-1-p)
     t))
   (message "Passed first valid test")
 
@@ -720,24 +620,133 @@
   (parser-generator-process-grammar)
   (should
    (equal
-    (parser-generator-ll--valid-grammar-p-k-gt-1)
+    (parser-generator-ll--valid-grammar-k-gt-1-p)
     nil))
   (message "Passed second valid test")
 
-  ;; TODO Example 5.19
+  (message "Passed tests for (parser-generator-ll--valid-grammar-k-gt-1-p)"))
 
-  (message "Passed tests for (parser-generator-ll--valid-grammar-p-k-gt-1)"))
+(defun parser-generator-ll-test--generate-table-k-eq-1 ()
+  "Test `parser-generator-ll--generate-table-k-eq-1'."
+  (message "Started tests for (parser-generator-ll--generate-table-k-eq-1)")
+
+  ;; TODO Implement this
+
+  (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-process-grammar)
+  (let ((parser-tables (parser-generator-ll--generate-action-table-k-eq-1)))
+    ;; (message "parser-tables: %S" parser-tables)
+    (should
+     (equal
+      '(
+        (
+         ((E) ($))
+         (
+          (("a") reduce (((T) ($)) ((T) ("+")) ((E2) ($))) 0)
+          (("(") reduce (((T) ($)) ((T) ("+")) ((E2) ($))) 0)
+          )
+         )
+        (
+         ((E2) ($))
+         (
+          (("+") reduce ("+" ((T) ($)) ((T) ("+")) ((E2) ($))) 1)
+          (($) reduce (e) 2)
+          )
+         )
+        (
+         ((T) ("+"))
+         (
+          (("a") reduce (((F) ("*")) ((F) ("+")) ((T2) ("+"))) 3)
+          (("(") reduce (((F) ("*")) ((F) ("+")) ((T2) ("+"))) 3)
+          )
+         )
+        (
+         ((T2) ("+"))
+         (
+          (("+") reduce (e) 5)
+          (("*") reduce ("*" ((F) ("*")) ((F) ("+")) ((T2) ("+"))) 4)
+          )
+         )
+        (
+         ((F) ("+"))
+         (
+          (("a") reduce ("a") 7)
+          (("(") reduce ("(" ((E) (")")) ")") 6)
+          )
+         )
+        (
+         ((E) (")"))
+         (
+          (("a") reduce (((T) (")")) ((T) ("+")) ((E2) (")"))) 0)
+          (("(") reduce (((T) (")")) ((T) ("+")) ((E2) (")"))) 0)
+          )
+         )
+        (
+         ((E2) (")"))
+         (
+          (("+") reduce ("+" ((T) (")")) ((T) ("+")) ((E2) (")"))) 1)
+          ((")") reduce (e) 2)
+          )
+         )
+        (((T) (")")) ((("a") reduce (((F) (")")) ((F) ("*")) ((T2) (")"))) 3) 
(("(") reduce (((F) (")")) ((F) ("*")) ((T2) (")"))) 3)))
+        (((T2) (")")) ((("*") reduce ("*" ((F) (")")) ((F) ("*")) ((T2) 
(")"))) 4) ((")") reduce (e) 5)))
+        (((F) (")")) ((("a") reduce ("a") 7) (("(") reduce ("(" ((E) (")")) 
")") 6)))
+        (((F) ("*")) ((("a") reduce ("a") 7) (("(") reduce ("(" ((E) (")")) 
")") 6)))
+        (((T) ($)) ((("a") reduce (((F) ($)) ((F) ("*")) ((T2) ($))) 3) (("(") 
reduce (((F) ($)) ((F) ("*")) ((T2) ($))) 3)))
+        (((T2) ($)) ((("*") reduce ("*" ((F) ($)) ((F) ("*")) ((T2) ($))) 4) 
(($) reduce (e) 5)))
+        (((F) ($)) ((("a") reduce ("a") 7) (("(") reduce ("(" ((E) (")")) ")") 
6)))
+        ("a" ((("a") pop)))
+        ("+" ((("+") pop)))
+        ("*" ((("*") pop)))
+        (")" (((")") pop)))
+        ("(" ((("(") pop)))
+        ($ ((($) accept)))
+        )
+      parser-tables)))
+  ;; TODO Verify above
+  (message "Passed Example 5.12 p. 346-347")
+
+  (message "Passed tests for (parser-generator-ll--generate-table-k-eq-1)"))
+
+(defun parser-generator-ll-test--valid-grammar-k-eq-1-p ()
+  "Test `parser-generator-ll--valid-grammar-k-eq-1-p'."
+  (message "Started tests for (parser-generator-ll--valid-grammar-k-eq-1-p)")
+
+  ;; TODO Implement this
+
+  (message "Passed tests for (parser-generator-ll--valid-grammar-k-eq-1-p)"))
 
 
 (defun parser-generator-ll-test ()
   "Run test."
 
   ;; Helpers
-  (parser-generator-ll-test--generate-tables-k-gt-1)
-  (parser-generator-ll-test--generate-parsing-table-k-gt-1)
-  ;; TODO Generate tables k eq 1
-  (parser-generator-ll-test--valid-grammar-p-k-gt-1)
-  ;; TODO Validate grammar k eq 1
+
+  ;; k > 1
+  (parser-generator-ll-test--generate-goto-table-k-gt-1)
+  (parser-generator-ll-test--generate-action-table-k-gt-1)
+  (parser-generator-ll-test--valid-grammar-k-gt-1-p)
+
+  ;; k = 1
+  (parser-generator-ll-test--generate-table-k-eq-1)
+  (parser-generator-ll-test--valid-grammar-k-eq-1-p)
 
   ;; Main stuff
   (parser-generator-ll-test-generate-tables)