[elpa] externals/parser-generator ee0ef5d 115/434: Added failing unit test for Algorithm 5.7

[ELPA Syncer]

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

    Added failing unit test for Algorithm 5.7
---
 parser-lr.el           | 40 ++++++++++++++++++++++++++++++++++++++++
 test/parser-lr-test.el | 17 ++++++++++++++++-
 2 files changed, 56 insertions(+), 1 deletion(-)

diff --git a/parser-lr.el b/parser-lr.el
index c640c74..197d03c 100644
--- a/parser-lr.el
+++ b/parser-lr.el
@@ -471,6 +471,46 @@
     (setq lr-new-item (sort lr-new-item 'parser--sort-list))
     lr-new-item))
 
+;; Algorithm 5.7, p. 375
+(defun parser-lr--parse (input-tape &optional input-tape-index stack)
+  "Perform a LR-parse of INPUT-TAPE optionally at INPUT-TAPE-INDEX with STACK."
+  (unless input-tape-index
+    (setq input-tape-index 0))
+  (let ((input-tape-length (length input-tape))
+        (right-parse)
+        (goto-tables (parser-lr--generate-goto-tables)))
+    (let ((action-tables (parser-lr--generate-action-tables)))
+
+      ;; TODO (1) The lookahead string u, consisting of the next k input 
symbols, is determined.
+
+      ;; TODO (2) The parsing action f of the table on top of the pushdown 
list is applied to the lookahead string u.
+
+      ;;    TODO (a) If f(u) = shift, then the next input symbol, say a
+      ;;    is removed from the input and shifted onto the pushdown list.
+      ;;    The goto function g of the table on top of the pushdown list
+      ;;    is applied to a to determine the new table to be placed on
+      ;;    top of the pushdown list. We then return to step(1). If
+      ;;    there is no next input symbol or g(a) is undefined, halt
+      ;;    and declare error.
+
+      ;;    TODO (b) If f(u) = reduce i and production i is A -> a,
+      ;;    then 2|a| symbols are removed from the top of the pushdown
+      ;;    list, and production number i is placed in the output
+      ;;    buffer. A new table T' is then exposed as the top table
+      ;;    of the pushdown list, and the goto function of T' is applied
+      ;;    to A to determine the next table to be placed on top of the
+      ;;    pushdown list. We place A and this new table on top of the
+      ;;    the pushdown list and return to step (1)
+
+      ;;    TODO (c) If f(u) = error, we halt parsing (and, in practice
+      ;;    transfer to an error recovery routine).
+
+      ;;    TODO (d) If f(u) = accept, we halt and declare the string
+      ;;    in the output buffer to be the right parse of the original
+      ;;    input string.
+      
+      )
+    right-parse))
 
 (provide 'parser-lr)
 
diff --git a/test/parser-lr-test.el b/test/parser-lr-test.el
index 1c7105f..fabe46a 100644
--- a/test/parser-lr-test.el
+++ b/test/parser-lr-test.el
@@ -217,6 +217,20 @@
 
   (message "Passed tests for (parser-lr--items-valid-p)"))
 
+(defun parser-lr-test--parse ()
+  "Test `parser-lr--parse'."
+  (message "Passed tests for (parser-lr--parse)")
+
+  (parser--set-grammar '((Sp S) (a b) ((Sp S) (S (S a S b)) (S e)) Sp))
+  (parser--set-look-ahead-number 1)
+  (parser--process-grammar)
+  (should
+   (equal
+    '(2 2 2 1 1)
+    (parser-lr--parse "aabb")))
+
+  (message "Passed tests for (parser-lr--parse)"))
+
 (defun parser-lr-test ()
   "Run test."
   ;; (setq debug-on-error t)
@@ -224,7 +238,8 @@
   (parser-lr-test--items-for-prefix)
   (parser-lr-test--items-valid-p)
   (parser-lr-test--generate-goto-tables)
-  (parser-lr-test--generate-action-tables))
+  (parser-lr-test--generate-action-tables)
+  (parser-lr-test--parse))
 
 (provide 'parser-lr-test)