[elpa] externals/parser-generator 3615fad 276/434: Fixed issue with lex-analyzer in LR(0) Parser

[ELPA Syncer]

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

    Fixed issue with lex-analyzer in LR(0) Parser
---
 parser-generator-lex-analyzer.el | 14 +++++++++-----
 parser-generator-lr.el           | 34 ++++++++++++++++++++++++++++------
 test/parser-generator-lr-test.el | 31 ++++++++++++++-----------------
 3 files changed, 51 insertions(+), 28 deletions(-)

diff --git a/parser-generator-lex-analyzer.el b/parser-generator-lex-analyzer.el
index ba831da..7353be4 100644
--- a/parser-generator-lex-analyzer.el
+++ b/parser-generator-lex-analyzer.el
@@ -62,10 +62,13 @@
     (error "Missing look-ahead-number!"))
   (let ((look-ahead)
         (look-ahead-length 0)
-        (index parser-generator-lex-analyzer--index))
+        (index parser-generator-lex-analyzer--index)
+        (k (max
+            1
+            parser-generator--look-ahead-number)))
     (while (<
             look-ahead-length
-            parser-generator--look-ahead-number)
+            k)
       (condition-case error
           (progn
             (let ((next-look-ahead
@@ -79,7 +82,7 @@
                     (dolist (next-look-ahead-item next-look-ahead)
                       (when (<
                              look-ahead-length
-                             parser-generator--look-ahead-number)
+                             k)
                         (push next-look-ahead-item look-ahead)
                         (setq look-ahead-length (1+ look-ahead-length))
                         (setq index (cdr (cdr next-look-ahead-item))))))
@@ -114,8 +117,9 @@
                 (unless (listp (car token))
                   (setq token (list token)))
                 (let ((first-token (car token)))
-                  (setq parser-generator-lex-analyzer--index
-                        (cdr (cdr first-token)))
+                  (setq
+                   parser-generator-lex-analyzer--index
+                   (cdr (cdr first-token)))
                   (push first-token tokens)))))
         (error (error
                 "Lex-analyze failed to pop token at %s, error: %s"
diff --git a/parser-generator-lr.el b/parser-generator-lr.el
index 33b19a9..6d4ae1b 100644
--- a/parser-generator-lr.el
+++ b/parser-generator-lr.el
@@ -997,6 +997,12 @@
                table-index
                pushdown-list))
 
+            (parser-generator--debug
+             (message
+              "Action-table %d: %s"
+              table-index
+              action-table))
+
             (let ((action-match nil)
                   (action-table-length (length action-table))
                   (action-index 0)
@@ -1011,12 +1017,28 @@
                     (push
                      action-look-ahead
                      possible-look-aheads)
-                    (when (equal
-                           action-look-ahead
-                           look-ahead)
-                      (setq action-match
-                            (cdr action)))))
-                (setq action-index (1+ action-index)))
+                    (when
+                        (equal
+                         action-look-ahead
+                         look-ahead)
+                      (setq
+                       action-match
+                       (cdr action)))
+                    (when
+                        (and
+                         (=
+                          parser-generator--look-ahead-number
+                          0)
+                         (not
+                          action-look-ahead))
+                      ;; LR(0) reduce actions occupy entire row
+                      ;; and is applied regardless of look-ahead
+                      (setq
+                       action-match
+                       (cdr action))))
+                  (setq
+                   action-index
+                   (1+ action-index))))
 
               (unless action-match
                 ;; (c) If f(u) = error, we halt parsing (and, in practice
diff --git a/test/parser-generator-lr-test.el b/test/parser-generator-lr-test.el
index 00135de..b07f6d3 100644
--- a/test/parser-generator-lr-test.el
+++ b/test/parser-generator-lr-test.el
@@ -881,20 +881,16 @@
         (8 ((nil reduce 1))))
       (parser-generator--hash-to-list
        parser-generator-lr--action-tables)))
-    (message "Passed ACTION-tables k = 0")
-
-    )
-
-  ;; TODO Replace below with parse of k=0
+    (message "Passed ACTION-tables k = 0"))
 
   (let ((buffer (generate-new-buffer "*a*")))
     (switch-to-buffer buffer)
     (kill-region (point-min) (point-max))
-    (insert "abac")
+    (insert "1+1")
 
     (parser-generator-set-grammar
-     '((Sp S R T) ("a" "b" "c") ((Sp S) (S (R S) (R)) (R ("a" "b" T)) (T ("a" 
T) ("c") (e))) Sp))
-    (parser-generator-set-look-ahead-number 2)
+     '((S E B) ("*" "+" "0" "1") ((S (E $)) (E (E "*" B) (E "+" B) (B)) (B 
("0") ("1"))) S))
+    (parser-generator-set-look-ahead-number 0)
     (parser-generator-process-grammar)
     (parser-generator-lr-generate-parser-tables)
 
@@ -915,22 +911,23 @@
          (let ((start (car (cdr token)))
                (end (cdr (cdr token))))
            (when (<= end (point-max))
-             (buffer-substring-no-properties start end))))))
+             (buffer-substring-no-properties
+              start
+              end))))))
 
     (should
      (equal
-      '(5 4 3 2)
+      '(5 3 5 2)
       (parser-generator-lr-parse)))
-
     (message "Passed parse with k = 0 # 1")
 
     (switch-to-buffer buffer)
     (kill-region (point-min) (point-max))
-    (insert "aba")
+    (insert "1+1*1")
 
     (should
      (equal
-      '(6 4 3 2)
+      '(5 3 5 2 5 1)
       (parser-generator-lr-parse)))
 
     (message "Passed parse with k = 0 # 2")
@@ -940,11 +937,11 @@
   (let ((buffer (generate-new-buffer "*a*")))
     (switch-to-buffer buffer)
     (kill-region (point-min) (point-max))
-    (insert "abac")
+    (insert "1+1")
 
     (parser-generator-set-grammar
-     '((Sp S R T) ("a" "b" "c") ((Sp S) (S (R S) (R)) (R ("a" "b" T 
(lambda(args) (list "begin" (nth 2 args) "end")))) (T ("a" T (lambda(args) 
"test")) ("c") (e))) Sp))
-    (parser-generator-set-look-ahead-number 2)
+     '((S E B) ("*" "+" "0" "1") ((S (E $)) (E (E "*" B (lambda(args) (list 
(nth 0 args) " x " (nth 2 args)))) (E "+" B (lambda(args) (list (nth 0 args) " 
. " (nth 2 args)))) (B)) (B ("0") ("1"))) S))
+    (parser-generator-set-look-ahead-number 0)
     (parser-generator-process-grammar)
     (parser-generator-lr-generate-parser-tables)
 
@@ -969,7 +966,7 @@
 
     (should
      (equal
-      '("begin" "test" "end")
+      '("1" " . " "1")
       (parser-generator-lr-translate)))
 
     (message "Passed translation k=0")