branch: externals/parser-generator
commit b37ba1eddffab043ef33c4be9473af1cb2f3760a
Author: Christian Johansson <[email protected]>
Commit: Christian Johansson <[email protected]>
Created TODO item
---
parser-generator-ll.el | 33 ++++++------
parser-generator.el | 2 +-
test/parser-generator-ll-test.el | 110 ++++++++++++++++++++-------------------
3 files changed, 74 insertions(+), 71 deletions(-)
diff --git a/parser-generator-ll.el b/parser-generator-ll.el
index dec9f6b668..4046699a19 100644
--- a/parser-generator-ll.el
+++ b/parser-generator-ll.el
@@ -259,8 +259,7 @@
;; push a new item to stack with a local-follow
;; and a new left-hand-side
(let ((sub-symbol-index 0)
- (sub-symbol-length (length production-rhs))
- (found-first-non-terminal-p))
+ (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
@@ -302,15 +301,14 @@
(message
"sub-symbol-rhss: %S"
sub-symbol-rhss))
+ (push
+ local-follow-set
+ sets)
+ (parser-generator--debug
+ (message
+ "pushed local follow set to sets: %S"
+ local-follow-set))
(dolist (local-follow local-follow-set)
- (unless found-first-non-terminal-p
- (parser-generator--debug
- (message
- "pushed local follow to set: %S"
- local-follow))
- (push
- local-follow
- sets))
(dolist (sub-symbol-rhs sub-symbol-rhss)
(let* ((new-stack-item
(list
@@ -330,15 +328,17 @@
distinct-stack-item-p)
(push
new-stack-item
- stack)))))
- (unless found-first-non-terminal-p
- (setq
- found-first-non-terminal-p
- t)))))
+ stack))))))))
(setq
sub-symbol-index
(1+ sub-symbol-index))))
+ (setq sets (reverse sets))
+ (parser-generator--debug
+ (message
+ "\nsets: %S"
+ sets))
+
;; Add all distinct combinations of left-hand-side,
;; look-aheads and parent-follow to tables list here
(when look-aheads
@@ -381,8 +381,7 @@
(puthash
table-hash-key
(list table)
- tables)
- )))))
+ tables))))))
(parser-generator--debug
(message "\nproduction-lhs: %S" production-lhs)
diff --git a/parser-generator.el b/parser-generator.el
index 7ee5f722d6..e0b8500766 100644
--- a/parser-generator.el
+++ b/parser-generator.el
@@ -45,7 +45,7 @@
(defvar
parser-generator--debug
- nil
+ t
"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 c06e25a076..2c566be67b 100644
--- a/test/parser-generator-ll-test.el
+++ b/test/parser-generator-ll-test.el
@@ -31,6 +31,7 @@
)
(parser-generator-process-grammar)
(let ((tables (parser-generator-ll--generate-tables)))
+ ;; (message "tables: %S" tables)
(should
(equal
tables
@@ -52,9 +53,9 @@
(
((S) ($)) ;; T0
(
- ((a b) (a A a a) ((a a)))
- ((a a) (a A a a) ((a a)))
- ((b b) (b A b a) ((b a)))
+ ((a b) (a A a a) (((a a))))
+ ((a a) (a A a a) (((a a))))
+ ((b b) (b A b a) (((b a))))
)
)
)
@@ -79,6 +80,7 @@
(parser-generator-process-grammar)
(let* ((tables
(parser-generator-ll--generate-tables)))
+ ;; (message "tables: %S" tables)
(should
(equal
tables
@@ -86,23 +88,23 @@
(
((A) (a a)) ;; T3
(
- ((a b) (S a a) ((a a)))
- ((a a) (S a a) ((a a)))
+ ((a b) (S a a) (((a a))))
+ ((a a) (S a a) (((a a))))
((b a) (b) nil)
)
)
(
((S) (a a)) ;; T2
(
- ((a b) (a b A) ((a a)))
+ ((a b) (a b A) (((a a))))
((a a) (e) nil)
)
)
(
((A) ($)) ;; T1
(
- ((a b) (S a a) ((a a)))
- ((a a) (S a a) ((a a)))
+ ((a b) (S a a) (((a a))))
+ ((a a) (S a a) (((a a))))
((b $) (b) nil)
)
)
@@ -110,7 +112,7 @@
((S) ($)) ;; T0
(
(($ $) (e) nil)
- ((a b) (a b A) (($)))
+ ((a b) (a b A) ((($))))
)
)
)
@@ -144,20 +146,20 @@
((A) (a))
(
((a) (a) nil)
- ((b) (b S A) ((b) (a)))
+ ((b) (b S A) (((a) (b)) ((a))))
)
)
(
((S) (a))
(
- ((a) (a A S) ((b) (a)))
+ ((a) (a A S) (((a) (b)) ((a))))
((b) (b) nil)
)
)
(
((S) (b))
(
- ((a) (a A S) ((b) (a)))
+ ((a) (a A S) (((a) (b)) ((b))))
((b) (b) nil)
)
)
@@ -165,20 +167,19 @@
((A) (b))
(
((a) (a) nil)
- ((b) (b S A) ((b) (a)))
+ ((b) (b S A) (((a) (b)) ((b))))
)
)
(
((S) ($))
(
- ((a) (a A S) ((b) (a)))
+ ((a) (a A S) (((a) (b)) (($))))
((b) (b) nil)
)
)
)
- )
)
- )
+ ))
(message "Passed Example 5.5 p. 340")
(parser-generator-set-eof-identifier '$)
@@ -203,59 +204,62 @@
(message "tables: %S" tables)
(should
(equal
- '(
+ '
+ (
+ (
+ ((E2) (")"))
(
- ((E2) (")"))
- (
- ((")") (e) nil)
- (("+") ("+" T E2) (("+")))
- )
+ ((")") (e) nil)
+ (("+") ("+" T E2) ((("+") (")")) ((")"))))
)
+ )
+ (
+ ((E) (")"))
(
- ((E) (")"))
- (
- (("(") (T E2) (("+")))
- (("a") (T E2) (("+")))
- )
+ (("(") (T E2) ((("+") (")")) ((")"))))
+ (("a") (T E2) ((("+") (")")) ((")"))))
)
+ )
+ (
+ ((F) ("*"))
(
- ((F) ("*"))
- (
- (("(") ("(" E ")") ((")")))
- (("a") ("a") nil)
- )
+ (("(") ("(" E ")") (((")"))))
+ (("a") ("a") nil)
)
+ )
+ (
+ ((T2) ("+"))
(
- ((T2) ("+"))
- (
- (("*") ("*" F T2) (("*")))
- (("+") (e) nil)
- )
+ (("*") ("*" F T2) ((("*") ("+")) (("+"))))
+ (("+") (e) nil)
)
+ )
+ (
+ ((T) ("+"))
(
- ((T) ("+"))
- (
- (("(") (F T2) (("*")))
- (("a") (F T2) (("*")))
- )
+ (("(") (F T2) ((("*") ("+")) (("+"))))
+ (("a") (F T2) ((("*") ("+")) (("+"))))
)
+ )
+ (
+ ((E2) ($))
(
- ((E2) ($))
- (
- (($) (e) nil)
- (("+") ("+" T E2) (("+")))
- )
+ (($) (e) nil)
+ (("+") ("+" T E2) ((("+") ($)) (($))))
)
+ )
+ (
+ ((E) ($))
(
- ((E) ($))
- (
- (("(") (T E2) (("+")))
- (("a") (T E2) (("+")))
- )
+ (("(") (T E2) ((("+") ($)) (($))))
+ (("a") (T E2) ((("+") ($)) (($))))
)
)
+ )
tables)))
- ;; TODO Verify above
+ ;; TODO Make above pass
+ ;; TODO There are issues calculating Y for a non-terminal
+ ;; were a non-terminal follows that has a alternative e-rule
(message "Passed Example 5.12 p. 346-347")
(message "Passed tests for (parser-generator-ll--generate-tables)"))
