[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[elpa] externals/parser-generator 23805731c1 34/82: More work on LL-pars
From: |
Christian Johansson |
Subject: |
[elpa] externals/parser-generator 23805731c1 34/82: More work on LL-parser |
Date: |
Thu, 12 May 2022 13:28:15 -0400 (EDT) |
branch: externals/parser-generator
commit 23805731c1b150cc0789332a1fddc3de38244c0a
Author: Christian Johansson <christian@cvj.se>
Commit: Christian Johansson <christian@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)"))
- [elpa] externals/parser-generator e55a3f8a37 38/82: Updated TODO items, (continued)
- [elpa] externals/parser-generator e55a3f8a37 38/82: Updated TODO items, Christian Johansson, 2022/05/12
- [elpa] externals/parser-generator 7ee5504003 45/82: More work on LLk parser, Christian Johansson, 2022/05/12
- [elpa] externals/parser-generator fd2f90dd81 47/82: Added TODO-item, Christian Johansson, 2022/05/12
- [elpa] externals/parser-generator b41b2dbffe 68/82: Removed debug output, Christian Johansson, 2022/05/12
- [elpa] externals/parser-generator 566228f16c 71/82: More work on LLk translation, Christian Johansson, 2022/05/12
- [elpa] externals/parser-generator 234a6ca2db 70/82: More work on LLk SDT, Christian Johansson, 2022/05/12
- [elpa] externals/parser-generator ff261d9a4e 75/82: Using stack for symbols value in SDT, Christian Johansson, 2022/05/12
- [elpa] externals/parser-generator de7c45c511 78/82: Started with LL-export functions, Christian Johansson, 2022/05/12
- [elpa] externals/parser-generator 5be162966b 80/82: Fixed byte-compilation issue in exported LL parser, Christian Johansson, 2022/05/12
- [elpa] externals/parser-generator 2869417d78 31/82: Made new helper functions to make LL-parsing easier, Christian Johansson, 2022/05/12
- [elpa] externals/parser-generator 23805731c1 34/82: More work on LL-parser,
Christian Johansson <=
- [elpa] externals/parser-generator 8cc2a5b315 44/82: More work on LLk parsing, Christian Johansson, 2022/05/12
- [elpa] externals/parser-generator 5aeee49bd0 48/82: Added another todo note, Christian Johansson, 2022/05/12
- [elpa] externals/parser-generator 4c93e895b3 49/82: Added TODO item, Christian Johansson, 2022/05/12
- [elpa] externals/parser-generator ec0711fa84 53/82: Tweaks on internal functions of LLk parsing, Christian Johansson, 2022/05/12
- [elpa] externals/parser-generator ed9933eeba 57/82: Passing a lot of LLk tests, Christian Johansson, 2022/05/12
- [elpa] externals/parser-generator 87ded78c28 63/82: LL(1) parser passes test for generating tables and parsing, Christian Johansson, 2022/05/12
- [elpa] externals/parser-generator 1ccc742678 72/82: LLk parser passes translation tests, Christian Johansson, 2022/05/12
- [elpa] externals/parser-generator 1f36aeafdd 74/82: Updated documentation with translate example for LL(1) grammar, Christian Johansson, 2022/05/12
- [elpa] externals/parser-generator 5e6ee66f1f 77/82: Added failing parse tests, Christian Johansson, 2022/05/12
- [elpa] externals/parser-generator 0a86c69ef1 19/82: More work on LL-table generation, Christian Johansson, 2022/05/12