branch: externals/parser-generator
commit b09b22c0be79355eb793254246c0210699ce5413
Author: Christian Johansson <christ...@cvj.se>
Commit: Christian Johansson <christ...@cvj.se>
Passing test for LL(k) table Example 5.15
---
parser-generator-ll.el | 73 ++++++++++++++++++++--------------------
parser-generator.el | 2 +-
test/parser-generator-ll-test.el | 10 +++++-
3 files changed, 47 insertions(+), 38 deletions(-)
diff --git a/parser-generator-ll.el b/parser-generator-ll.el
index c0628e31a8..6578d57639 100644
--- a/parser-generator-ll.el
+++ b/parser-generator-ll.el
@@ -41,7 +41,6 @@
;;; Algorithms
-;; TODO
;; Algorithm 5.2 p. 350
(defun parser-generator-ll--generate-tables ()
"Construction of LL(k)-tables. Output the set of LL(k) tables needed to
construct a parsing table for the grammar G."
@@ -113,41 +112,43 @@
;; For each non-terminal in the production right-hand side
;; push a new item to stack with a local-follow
;; and a new left-hand-side
- (let ((sub-symbol-index 0))
- (dolist (sub-symbol production-rhs)
- (when (parser-generator--valid-non-terminal-p
- sub-symbol)
- (let* ((follow-set
- (nthcdr (1+ sub-symbol-index) production-rhs))
- (merged-follow
- (append follow-set parent-follow))
- (local-follow-set
- (parser-generator--first merged-follow nil t t))
- (sub-symbol-rhss
- (parser-generator--get-grammar-rhs
- sub-symbol)))
- (parser-generator--debug
- (message "\nfollow-set: %S" follow-set)
- (message "merged-follow: %S" follow-set)
- (message "local-follow-set: %S" local-follow-set)
- (message "sub-symbol-rhss: %S" sub-symbol-rhss))
- (dolist (local-follow local-follow-set)
- (dolist (sub-symbol-rhs sub-symbol-rhss)
- (let* ((sub-symbol-production
- (list (list sub-symbol) sub-symbol-rhs))
- (new-stack-item
- (list
- (list sub-symbol)
- sub-symbol-rhs
- local-follow)))
- (parser-generator--debug
- (message "new-stack-item: %S" new-stack-item))
- (push
- new-stack-item
- stack)))))))
- (setq
- sub-symbol-index
- (1+ sub-symbol-index)))
+ (let ((sub-symbol-index 0)
+ (sub-symbol-length (length production-rhs)))
+ (while (< sub-symbol-index sub-symbol-length)
+ (let ((sub-symbol (nth sub-symbol-index production-rhs)))
+ (when (parser-generator--valid-non-terminal-p
+ sub-symbol)
+ (let* ((follow-set
+ (nthcdr (1+ sub-symbol-index) production-rhs))
+ (merged-follow
+ (append follow-set parent-follow))
+ (local-follow-set
+ (parser-generator--first merged-follow nil t t))
+ (sub-symbol-rhss
+ (parser-generator--get-grammar-rhs
+ sub-symbol)))
+ (parser-generator--debug
+ (message "\nfollow-set: %S for %S in %S" follow-set (nth
sub-symbol-index production-rhs) production-rhs)
+ (message "merged-follow: %S" follow-set)
+ (message "local-follow-set: %S" local-follow-set)
+ (message "sub-symbol-rhss: %S" sub-symbol-rhss))
+ (dolist (local-follow local-follow-set)
+ (dolist (sub-symbol-rhs sub-symbol-rhss)
+ (let* ((sub-symbol-production
+ (list (list sub-symbol) sub-symbol-rhs))
+ (new-stack-item
+ (list
+ (list sub-symbol)
+ sub-symbol-rhs
+ local-follow)))
+ (parser-generator--debug
+ (message "new-stack-item: %S" new-stack-item))
+ (push
+ new-stack-item
+ stack)))))))
+ (setq
+ sub-symbol-index
+ (1+ sub-symbol-index))))
;; Add all distinct combinations of left-hand-side,
;; look-ahead and parent-follow to tables list here
diff --git a/parser-generator.el b/parser-generator.el
index acc025ae6e..67f35c455b 100644
--- a/parser-generator.el
+++ b/parser-generator.el
@@ -45,7 +45,7 @@
(defvar
parser-generator--debug
- t
+ nil
"Whether to print debug messages or not.")
(defvar
diff --git a/test/parser-generator-ll-test.el b/test/parser-generator-ll-test.el
index 4511bb25c9..3d2b8b9be3 100644
--- a/test/parser-generator-ll-test.el
+++ b/test/parser-generator-ll-test.el
@@ -41,7 +41,15 @@
)
(parser-generator-process-grammar)
(let ((tables (parser-generator-ll--generate-tables)))
- (message "tables: %S" tables))
+ ;; (message "tables: %S" tables)
+ (should
+ (equal
+ tables
+ '(
+ (0 (((S) nil (a b) (a A a a)) ((S) nil (a a) (a A a a)) ((S) nil (b b)
(b A b a))))
+ (1 (((A) (a a) (a a) (e)) ((A) (a a) (b a) (b))))
+ (2 (((A) (b a) (b b) (b)) ((A) (b a) (b a) (e))))
+ ))))
(message "Passed tests for (parser-generator-ll--generate-parsing-table)"))
