[elpa] externals/parser-generator 99b531f 300/434: Made some cpu complexity optimizations

[ELPA Syncer]

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

    Made some cpu complexity optimizations
---
 parser-generator-lr-export.el    |  2 ++
 parser-generator-lr.el           | 24 ++++++++++++++--
 parser-generator.el              | 61 +++++++++++++++++++++++++---------------
 test/parser-generator-lr-test.el | 25 ++++++++++++++++
 4 files changed, 87 insertions(+), 25 deletions(-)

diff --git a/parser-generator-lr-export.el b/parser-generator-lr-export.el
index ec4cdce..09436fe 100644
--- a/parser-generator-lr-export.el
+++ b/parser-generator-lr-export.el
@@ -11,6 +11,7 @@
 
 (defun parser-generator-lr-export-to-elisp (namespace)
   "Export parser with NAMESPACE."
+  (message "\nStarting generation of elips..\n")
 
   ;; Make sure all requisites are defined
   (unless parser-generator-lr--action-tables
@@ -831,6 +832,7 @@
        (buffer-substring-no-properties
         (point-min)
         (point-max))))
+    (message "\nCompleted generation of elips.\n")
     code))
 
 
diff --git a/parser-generator-lr.el b/parser-generator-lr.el
index bb25210..a101e79 100644
--- a/parser-generator-lr.el
+++ b/parser-generator-lr.el
@@ -29,15 +29,18 @@
 
 (defun parser-generator-lr-generate-parser-tables ()
   "Generate parsing tables for grammar."
+  (message "\nStarting generation of parser-tables..\n")
   (let ((table-lr-items
          (parser-generator-lr--generate-goto-tables)))
     (parser-generator-lr--generate-action-tables
      table-lr-items)
+    (message "\nCompleted generation of parser-tables.\n")
     table-lr-items))
 
 ;; Algorithm 5.11, p. 393
 (defun parser-generator-lr--generate-action-tables (table-lr-items)
   "Generate action-tables for lr-grammar based on TABLE-LR-ITEMS."
+  (message "\nStarting generation of action-tables..\n")
   (let ((action-tables)
         (states '(shift reduce error))
         (added-actions (make-hash-table :test 'equal))
@@ -239,6 +242,10 @@
         (parser-generator--debug
          (message "%s actions %s" goto-index action-table))
         (when action-table
+          (message
+           "ACTION-TABLE (%d): %s\n"
+           goto-index
+           action-table)
           (push
            (list
             goto-index
@@ -256,11 +263,13 @@
          table-index
          (car (cdr (nth table-index action-tables)))
          parser-generator-lr--action-tables)
-        (setq table-index (1+ table-index))))))
+        (setq table-index (1+ table-index)))))
+  (message "\nCompleted generation of action-tables..\n"))
 
 ;; Algorithm 5.9, p. 389
 (defun parser-generator-lr--generate-goto-tables ()
   "Calculate set of valid LR(k) items for grammar and a GOTO-table."
+  (message "\nStarting generation of goto-tables..\n")
   (parser-generator--debug
    (message "(parser-generator-lr--generate-goto-tables)"))
   (let ((lr-item-set-new-index 0)
@@ -416,6 +425,10 @@
          (sort
           goto-table-table
           'parser-generator--sort-list))
+        (message
+         "GOTO-TABLE (%d): %s\n"
+         lr-item-set-index
+         goto-table-table)
         (push
          `(
            ,lr-item-set-index
@@ -444,6 +457,7 @@
           table-lr-items
           t))
       (error "Inconsistent grammar!"))
+    (message "\nCompleted generation of goto-tables.\n")
     table-lr-items))
 
 ;; Algorithm 5.10, p. 391
@@ -719,6 +733,7 @@
            (message "γ: %s" γ))
           prefix-previous)))))
 
+;; TODO Optimize this function 1. first and 2. sort
 (defun parser-generator-lr--items-for-goto (previous-lr-item x)
   "Calculate LR-items for GOTO(PREVIOUS-LR-ITEM, X)."
   (let ((lr-new-item)
@@ -812,7 +827,10 @@
 
                   (let ((lr-item-suffix-rest-first
                          (parser-generator--first
-                          lr-item-suffix-rest)))
+                          lr-item-suffix-rest
+                          nil
+                          t
+                          t)))
                     (parser-generator--debug
                      (message
                       "lr-item-suffix-rest-first (before): %s"
@@ -875,7 +893,7 @@
        lr-new-item
        (sort
         lr-new-item
-        'parser-generator--sort-list)))
+        'parser-generator--sort-list))) ;; TODO Optimize this
 
     lr-new-item))
 
diff --git a/parser-generator.el b/parser-generator.el
index c64ca46..282bba6 100644
--- a/parser-generator.el
+++ b/parser-generator.el
@@ -92,7 +92,8 @@
       (unless (gethash element processed)
         (puthash element t processed)
         (push element new-elements)))
-    (nreverse new-elements)))
+    (nreverse
+     new-elements)))
 
 (defun parser-generator--generate-list-of-symbol (k symbol)
   "Generate list of K number of SYMBOL."
@@ -437,6 +438,10 @@
                  (list
                   lhs
                   (reverse new-rhs)))
+                (message
+                 "Production %s: %s"
+                 production-index
+                 production)
                 (parser-generator--debug
                  (message
                   "Production %s: %s"
@@ -510,6 +515,7 @@
 
 (defun parser-generator-process-grammar ()
   "Process grammar."
+  (message "\nStarting process of grammar..\n")
   (parser-generator--clear-cache)
   (unless parser-generator--look-ahead-number
     (error "No look-ahead-number defined!"))
@@ -523,7 +529,8 @@
       (parser-generator--valid-grammar-p
        parser-generator--grammar)
     (error "Invalid grammar G!"))
-  (parser-generator--load-symbols))
+  (parser-generator--load-symbols)
+  (message "\nCompleted process of grammar\n"))
 
 (defun parser-generator--sort-list (a b)
   "Return non-nil if a element in A is greater than a element in B in 
lexicographic order."
@@ -1418,11 +1425,13 @@
      f-set)))
 
 ;; Algorithm 5.5, p. 357
-(defun parser-generator--first (β &optional disallow-e-first)
-  "For sentential-form Β, calculate first terminals, optionally 
DISALLOW-E-FIRST."
+(defun parser-generator--first (β &optional disallow-e-first ignore-validation 
skip-sorting)
+  "For sentential-form Β, calculate first terminals, optionally 
DISALLOW-E-FIRST, IGNORE-VALIDATION and SKIP-SORTING."
   (unless (listp β)
     (setq β (list β)))
-  (unless (parser-generator--valid-sentential-form-p β)
+  (unless (or
+           ignore-validation
+           (parser-generator--valid-sentential-form-p β))
     (error "Invalid sentential form β! %s" β))
   (let ((k
          (max
@@ -1432,7 +1441,8 @@
     ;; Generate F-sets only once per grammar
     (parser-generator--generate-f-sets)
 
-    (let ((first-list nil))
+    (let ((first-list nil)
+          (first-items (make-hash-table :test 'equal)))
       ;; Iterate each symbol in β using a PDA algorithm
       (let ((input-tape β)
             (input-tape-length (length β))
@@ -1534,7 +1544,7 @@
                               "stopped looking since non-terminal starts with 
e-identifier: %s"
                               symbol-f-set))
                             (setq keep-looking nil))
-                          
+                        
                         ;; Handle this scenario here were a non-terminal can 
result in different FIRST sets
                         (when (>
                                (length symbol-f-set)
@@ -1604,21 +1614,28 @@
                   (setq first (reverse first))
                   ;; (message "first-after-fill: %s" first)
                   )
-                (parser-generator--debug
-                 (message
-                  "push to first-list: %s to %s"
-                  first
-                  first-list))
-                (push
-                 first
-                 first-list))))))
-
-      (setq
-       first-list
-       (parser-generator--distinct first-list))
-      (setq
-       first-list
-       (sort first-list 'parser-generator--sort-list))
+                (unless
+                    (gethash
+                     first
+                     first-items)
+                  (parser-generator--debug
+                   (message
+                    "push to first-list: %s to %s"
+                    first
+                    first-list))
+                  (puthash
+                   first
+                   t
+                   first-items)
+                  (push
+                   first
+                   first-list)))))))
+      (unless skip-sorting
+        (setq
+         first-list
+         (sort
+          first-list
+          'parser-generator--sort-list)))
       first-list)))
 
 ;; Definition at p. 343
diff --git a/test/parser-generator-lr-test.el b/test/parser-generator-lr-test.el
index 49c4071..beab25b 100644
--- a/test/parser-generator-lr-test.el
+++ b/test/parser-generator-lr-test.el
@@ -76,6 +76,31 @@
       (7 (((a) reduce 1) ((b) reduce 1))))
     (parser-generator--hash-to-list
      parser-generator-lr--action-tables)))
+  (message "Passed Example 5.32 p. 393")
+
+  ;; Cyclical grammar
+  (parser-generator-set-grammar
+   '(
+     (Sp S A B)
+     (a b c)
+     (
+      (Sp S)
+      (S A B)
+      (A (a b A) (a B))
+      (B (c S))
+      )
+     Sp))
+  (parser-generator-set-look-ahead-number 1)
+  (parser-generator-process-grammar)
+  (let ((table-lr-items
+         (parser-generator-lr--generate-goto-tables)))
+    ;; (message "cyclical lr-items: %s" table-lr-items)
+    (parser-generator-lr--generate-action-tables
+     table-lr-items)
+    ;; (message "cyclical goto-tables: %s" parser-generator-lr--goto-tables)
+    ;; (message "cyclical action-tables: %s" 
parser-generator-lr--action-tables)
+    )
+  (message "Passed cyclical grammar")
 
   (message "Passed tests for (parser-generator-lr--generate-action-tables)"))