branch: externals/parser-generator
commit 23805731c1b150cc0789332a1fddc3de38244c0a
Author: Christian Johansson <christ...@cvj.se>
Commit: Christian Johansson <christ...@cvj.se>
More work on LL-parser
---
parser-generator-ll.el | 6 +----
parser-generator.el | 50 ++++++++++++++++++++++++++++++++++------
test/parser-generator-ll-test.el | 8 ++++---
test/parser-generator-test.el | 28 +++++++++++++++-------
4 files changed, 69 insertions(+), 23 deletions(-)
diff --git a/parser-generator-ll.el b/parser-generator-ll.el
index a7acf6f73e..34ca0ce155 100644
--- a/parser-generator-ll.el
+++ b/parser-generator-ll.el
@@ -88,7 +88,7 @@
(parser-generator-generate-terminal-saturated-first-set
first-rhs))
(first-parent-follow
- (parser-generator--first parent-follow nil t t))
+ (parser-generator--first parent-follow nil t t t))
(look-aheads)
(sets))
(parser-generator--debug
@@ -98,10 +98,6 @@
(message "first-rhs: %S" first-rhs)
(message "satured-first-rhs: %S" satured-first-rhs))
- ;; TODO Remove items in first-rhs that ends with the e-identifier
- ;; TODO but only if it has other items that does not end with the
e-identifier
- ;; F('((a e) (a a))) = ((a a))
-
(cond
((and satured-first-rhs
(not first-parent-follow))
diff --git a/parser-generator.el b/parser-generator.el
index 617d9f1088..0d62f64796 100644
--- a/parser-generator.el
+++ b/parser-generator.el
@@ -1327,23 +1327,55 @@
(a-length (length a))
(b-element)
(b-index 0)
- (b-length (length b)))
+ (b-length (length b))
+ (only-eof))
+
(while (and
(< a-index a-length)
(< merge-count k))
(setq a-element (nth a-index a))
- (unless (parser-generator--valid-e-p a-element)
+
+ (when (parser-generator--valid-eof-p
+ a-element)
+ (setq only-eof t))
+
+ (when (or
+ (and
+ only-eof
+ (parser-generator--valid-eof-p
+ a-element))
+ (and
+ (not only-eof)
+ (parser-generator--valid-terminal-p
+ a-element)))
(push a-element merged)
(setq merge-count (1+ merge-count)))
+
(setq a-index (1+ a-index)))
+
(while (and
(< b-index b-length)
(< merge-count k))
(setq b-element (nth b-index b))
- (unless (parser-generator--valid-e-p b-element)
+
+ (when (parser-generator--valid-eof-p
+ b-element)
+ (setq only-eof t))
+
+ (when (or
+ (and
+ only-eof
+ (parser-generator--valid-eof-p
+ b-element))
+ (and
+ (not only-eof)
+ (parser-generator--valid-terminal-p
+ b-element)))
(push b-element merged)
(setq merge-count (1+ merge-count)))
+
(setq b-index (1+ b-index)))
+
(if (> merge-count 0)
(nreverse merged)
nil)))
@@ -1599,8 +1631,8 @@
;; Algorithm 5.5, p. 357
(defun parser-generator--first
- (β &optional disallow-e-first ignore-validation skip-sorting)
- "For sentential-form Β, calculate first terminals, optionally
DISALLOW-E-FIRST, IGNORE-VALIDATION and SKIP-SORTING."
+ (β &optional disallow-e-first ignore-validation skip-sorting
use-eof-for-trailing-symbols)
+ "For sentential-form Β, calculate first terminals, optionally
DISALLOW-E-FIRST, IGNORE-VALIDATION, SKIP-SORTING and
USE-EOF-FOR-TRAILING-SYMBOLS."
;; Make sure we are dealing with a list of symbols
(unless (listp β)
@@ -1955,14 +1987,18 @@
(missing-symbol-index 0))
(while (< missing-symbol-index missing-symbol-count)
(push
- parser-generator--e-identifier
+ (if use-eof-for-trailing-symbols
+ parser-generator--eof-identifier
+ parser-generator--e-identifier)
processed-list)
(setq
missing-symbol-index
(1+ missing-symbol-index)))
(parser-generator--debug
(message
- "Added %d trailing e-identifiers to set"
+ (if use-eof-for-trailing-symbols
+ "Added %d trailing EOF-identifiers to set"
+ "Added %d trailing e-identifiers to set")
missing-symbol-count))))
(when (> (length processed-list) k)
diff --git a/test/parser-generator-ll-test.el b/test/parser-generator-ll-test.el
index e1f88745f9..8a3068dcca 100644
--- a/test/parser-generator-ll-test.el
+++ b/test/parser-generator-ll-test.el
@@ -33,7 +33,7 @@
)
(parser-generator-process-grammar)
(let ((tables (parser-generator-ll--generate-tables)))
- (message "tables 1: %S" tables)
+ ;; (message "tables 1: %S" tables)
(should
(equal
tables
@@ -63,6 +63,7 @@
)
)
))
+ (message "Passed Example 5.14 p. 350")
;; TODO Pass Example 5.17 here
(parser-generator-set-eof-identifier '$)
@@ -88,14 +89,14 @@
tables
'(
(
- ((S) nil) ;; T0
+ ((S) ($)) ;; T0
(
(($ $) (e) nil)
((a b) (a b A) $)
)
)
(
- ((A) nil) ;; T1
+ ((A) ($)) ;; T1
(
((b $) (b) nil)
((a a) (S a a) ((a a)))
@@ -120,6 +121,7 @@
)
))
)
+ (message "Passed Example 5.17")
(message "Passed tests for (parser-generator-ll--generate-tables)"))
diff --git a/test/parser-generator-test.el b/test/parser-generator-test.el
index a7d415abc3..e5869fa554 100644
--- a/test/parser-generator-test.el
+++ b/test/parser-generator-test.el
@@ -971,6 +971,9 @@
"Test `parser-generator--merge-max-terminal-sets'."
(message "Starting tests for (parser-generator--merge-max-terminal-sets)")
+ (parser-generator-set-grammar '((S A B) (a b) ((S A) (S (B)) (B a) (A a) (A
(b a))) S))
+ (parser-generator-process-grammar)
+
;; Example 5.13 p. 348
(parser-generator-set-e-identifier 'e)
(parser-generator-set-look-ahead-number 2)
@@ -982,15 +985,24 @@
'((b) (b a b)))))
;; Example 5.14 p. 350
- (parser-generator-set-e-identifier 'e)
- (parser-generator-set-look-ahead-number 2)
- (should
- (equal
- '((a a) (a b) (b b))
- (parser-generator--merge-max-terminal-sets
- '((a b) (a e a) (b b) (b e b))
- nil)))
+ (parser-generator-set-e-identifier 'e)
+ (parser-generator-set-look-ahead-number 2)
+ (should
+ (equal
+ '((a a) (a b) (b b))
+ (parser-generator--merge-max-terminal-sets
+ '((a b) (a e a) (b b) (b e b))
+ nil)))
+ (parser-generator-set-eof-identifier '$)
+ (parser-generator-set-e-identifier 'e)
+ (parser-generator-set-look-ahead-number 2)
+ (should
+ (equal
+ '(($ $) (a $) (a a))
+ (parser-generator--merge-max-terminal-sets
+ '((a e) ($))
+ '(($ $) (a $)))))
(message "Passed tests for (parser-generator--merge-max-terminal-sets)"))
