branch: externals/parser-generator
commit daf93e05932bdcf07cd57da45f919b274cc06881
Author: Christian Johansson <christ...@cvj.se>
Commit: Christian Johansson <christ...@cvj.se>
Added failing unit test for action tables generation
---
parser-lr.el | 31 ++++++++++++++++++++++---------
test/parser-lr-test.el | 29 ++++++++++++++++++++++++++++-
2 files changed, 50 insertions(+), 10 deletions(-)
diff --git a/parser-lr.el b/parser-lr.el
index 0aa54d4..25799ad 100644
--- a/parser-lr.el
+++ b/parser-lr.el
@@ -25,7 +25,7 @@
"Hash-table for distinct LR-items in grammar.")
-;; Functions
+;; Helper Functions
(defun parser-lr--reset ()
@@ -37,6 +37,26 @@
;; Main Algorithms
+
+;; Algorithm 5.11, p. 393
+(defun parser-lr--generate-action-tables ()
+ "Generate action-tables for lr-grammar."
+ (unless parser-lr--action-tables
+ (let ((action-tables nil)
+ (terminals (parser--get-grammar-terminals)))
+ (dolist (goto-table parser-lr--goto-tables)
+ ;; (message "goto-table: %s" goto-table)
+ (let ((goto-index (car goto-table))
+ (gotos (car (cdr goto-table))))
+ (let ((lr-items (gethash goto-index parser-lr--items)))
+ (dolist (lr-item lr-items)
+ ;; TODO (a) f(u) = shift if [A -> B . C, v] is in a, C != e and
u is in EFF(Cv)
+ ;; TODO (b) f(u) = reduce i if [A -> B ., u] is in a and A -> B
is product i in P, i > 1
+ ;; TODO (c) f(e) = accept if [S' -> S ., e] is in a
+ ;; TODO (d) f(u) = error otherwise
+ ))))
+ (setq parser-lr--action-table action-tables))))
+
;; Algorithm 5.9, p. 389
(defun parser-lr--generate-goto-tables ()
"Calculate set of valid LR(k) items for grammar and a GOTO-table."
@@ -117,8 +137,7 @@
(unless
(parser-lr--items-valid-p
(parser--hash-values-to-list parser-lr--items t))
- (error "Inconsistent grammar!")))
- t)
+ (error "Inconsistent grammar!"))))
;; Algorithm 5.10, p. 391
(defun parser-lr--items-valid-p (lr-item-sets)
@@ -370,12 +389,6 @@
(setq lr-new-item (sort lr-new-item 'parser--sort-list))
lr-new-item))
-;; Algorithm 5.11, p. 393
-(defun parser-lr--generate-action-tables ()
- "Generate action-tables for lr-grammar."
- ;; TODO This
- t)
-
(provide 'parser-lr)
diff --git a/test/parser-lr-test.el b/test/parser-lr-test.el
index 8988a3b..d57acd1 100644
--- a/test/parser-lr-test.el
+++ b/test/parser-lr-test.el
@@ -9,6 +9,32 @@
(require 'parser-lr)
(require 'ert)
+(defun parser-lr-test--generate-action-tables ()
+ "Test `parser-lr--generate-action-tables'."
+ (message "Starting tests for (parser-lr--generate-action-tables)")
+
+ ;; Example 5.32 p. 393
+ (parser-lr--reset)
+ (parser--set-grammar '((Sp S) (a b) ((Sp S) (S (S a S b)) (S e)) Sp))
+ (parser--set-look-ahead-number 1)
+ (parser-lr--generate-goto-tables)
+ (parser-lr--generate-action-tables)
+
+ ;; Fig. 5.9 p. 374
+ (should
+ (equal
+ '((0 ((a reduce 2) (e reduce 2)))
+ (1 ((a shift) (e accept)))
+ (2 ((a reduce 2) (b reduce 2)))
+ (3 ((a shift) (b shift)))
+ (4 ((a reduce 2) (b reduce 2)))
+ (5 ((a reduce 1) (e reduce 1)))
+ (6 ((a shift) (b shift)))
+ (7 ((a reduce 1) (b reduce 1))))
+ parser-lr--action-tables))
+
+ (message "Ended tests for (parser-lr--generate-action-tables)"))
+
(defun parser-lr-test--generate-goto-tables ()
"Test `parser-lr--generate-goto-tables'."
(message "Starting tests for (parser-lr--generate-goto-tables)")
@@ -165,8 +191,9 @@
;; (setq debug-on-error t)
(parser-lr-test--items-for-prefix)
+ (parser-lr-test--items-valid-p)
(parser-lr-test--generate-goto-tables)
- (parser-lr-test--items-valid-p))
+ (parser-lr-test--generate-action-tables))
(provide 'parser-lr-test)
