branch: externals/parser-generator
commit ee0ef5d576fd507c39157a00a22af14d2c733c73
Author: Christian Johansson <[email protected]>
Commit: Christian Johansson <[email protected]>
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)
