[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[elpa] externals/parser-generator 63bd6c0 423/434: LR-parser now has SDT
From: |
ELPA Syncer |
Subject: |
[elpa] externals/parser-generator 63bd6c0 423/434: LR-parser now has SDT as optional feature to speed up plain parses |
Date: |
Mon, 29 Nov 2021 16:00:29 -0500 (EST) |
branch: externals/parser-generator
commit 63bd6c0326839cdf78d254d78b10fb6b48727836
Author: Christian Johansson <christian@cvj.se>
Commit: Christian Johansson <christian@cvj.se>
LR-parser now has SDT as optional feature to speed up plain parses
---
parser-generator-lr-export.el | 175 +++++++++++++++--------------
parser-generator-lr.el | 189 ++++++++++++++++----------------
test/parser-generator-lr-export-test.el | 3 +-
test/parser-generator-lr-test.el | 7 +-
4 files changed, 194 insertions(+), 180 deletions(-)
diff --git a/parser-generator-lr-export.el b/parser-generator-lr-export.el
index 584f63e..dfc2c1f 100644
--- a/parser-generator-lr-export.el
+++ b/parser-generator-lr-export.el
@@ -449,13 +449,14 @@
(defun
%s--parse
(&optional
+ perform-sdt
input-tape-index
pushdown-list
output
translation
translation-symbol-table-list
history)
- \"Perform a LR-parse via lex-analyzer, optionally at INPUT-TAPE-INDEX with
PUSHDOWN-LIST, OUTPUT, TRANSLATION, TRANSLATION-SYMBOL-TABLE-LIST and HISTORY.\"
+ \"Perform a LR-parse via lex-analyzer, optionally PERFORM-SDT means to
perform syntax-directed translation and optioanlly start at INPUT-TAPE-INDEX
with PUSHDOWN-LIST, OUTPUT, TRANSLATION, TRANSLATION-SYMBOL-TABLE-LIST and
HISTORY.\"
(unless input-tape-index
(setq input-tape-index 1))
(unless pushdown-list
@@ -721,20 +722,21 @@
(setq popped-items (1+ popped-items)))))
(push production-number output)
- (let ((popped-items-meta-contents))
- (setq
- popped-items-contents
- (reverse popped-items-contents))
- ;; Collect arguments for translation
- (dolist (popped-item popped-items-contents)
- (if (and
- (listp popped-item)
- (cdr popped-item))
- ;; If item is a terminal, use it's literal
value
- (push
- (%s-lex-analyzer--get-function
- popped-item)
- popped-items-meta-contents)"
+ (when perform-sdt
+ (let ((popped-items-meta-contents))
+ (setq
+ popped-items-contents
+ (reverse popped-items-contents))
+ ;; Collect arguments for translation
+ (dolist (popped-item popped-items-contents)
+ (if (and
+ (listp popped-item)
+ (cdr popped-item))
+ ;; If item is a terminal, use it's literal
value
+ (push
+ (%s-lex-analyzer--get-function
+ popped-item)
+ popped-items-meta-contents)"
namespace
namespace
namespace
@@ -744,61 +746,89 @@
(insert "
- ;; If item is a non-terminal
- (let ((temp-hash-key
- (format
- \"%S\"
- popped-item)))
+ ;; If item is a non-terminal
+ (let ((temp-hash-key
+ (format
+ \"%S\"
+ popped-item)))
")
(insert (format "
- ;; If we have a translation for symbol, pop one
- ;; otherwise push nil on translation argument
stack
- (if (gethash
- temp-hash-key
- translation-symbol-table)
+ ;; If we have a translation for symbol, pop one
+ ;; otherwise push nil on translation argument
stack
+ (if (gethash
+ temp-hash-key
+ translation-symbol-table)
+ (let ((symbol-translations
+ (gethash
+ temp-hash-key
+ translation-symbol-table)))
+ (let ((symbol-translation
+ (pop symbol-translations)))
+ (push
+ symbol-translation
+ popped-items-meta-contents)
+ (puthash
+ temp-hash-key
+ symbol-translations
+ translation-symbol-table)))
+ (push
+ nil
+ popped-items-meta-contents)))))
+
+ ;; If we just have one argument, pass it as a
instead of a list
+ (when (= (length popped-items-meta-contents) 1)
+ (setq
+ popped-items-meta-contents
+ (car popped-items-meta-contents)))
+
+ ;; Perform translation at reduction if specified
+ (if
+ (%s--get-grammar-translation-by-number
+ production-number)
+ (let ((partial-translation
+ (funcall
+
(%s--get-grammar-translation-by-number
+ production-number)
+ popped-items-meta-contents)))"
+ namespace
+ namespace))
+
+ (insert "
+ (let ((temp-hash-key
+ (format
+ \"%S\"
+ production-lhs)))"
+ )
+
+ (insert (format "
(let ((symbol-translations
(gethash
temp-hash-key
translation-symbol-table)))
- (let ((symbol-translation
- (pop symbol-translations)))
- (push
- symbol-translation
- popped-items-meta-contents)
- (puthash
- temp-hash-key
- symbol-translations
- translation-symbol-table)))
- (push
- nil
- popped-items-meta-contents)))))
-
- ;; If we just have one argument, pass it as a
instead of a list
- (when (= (length popped-items-meta-contents) 1)
- (setq
- popped-items-meta-contents
- (car popped-items-meta-contents)))
-
- ;; Perform translation at reduction if specified
- (if
- (%s--get-grammar-translation-by-number
- production-number)
+ (push
+ partial-translation
+ symbol-translations)
+ (puthash
+ temp-hash-key
+ symbol-translations
+ translation-symbol-table)
+ (setq
+ translation
+ partial-translation))))
+
+ ;; When no translation is specified just use
popped contents as translation
(let ((partial-translation
- (funcall
- (%s--get-grammar-translation-by-number
- production-number)
- popped-items-meta-contents)))"
- namespace
- namespace))
-
- (insert "
+ popped-items-meta-contents))"
+ ))
+ (insert "
(let ((temp-hash-key
(format
\"%S\"
- production-lhs)))")
+ production-lhs)))"
+ )
- (insert (format "
+ (insert (format "
(let ((symbol-translations
(gethash
temp-hash-key
@@ -812,32 +842,7 @@
translation-symbol-table)
(setq
translation
- partial-translation))))
-
- ;; When no translation is specified just use
popped contents as translation
- (let ((partial-translation
- popped-items-meta-contents))"))
- (insert "
- (let ((temp-hash-key
- (format
- \"%S\"
- production-lhs)))")
-
- (insert (format "
- (let ((symbol-translations
- (gethash
- temp-hash-key
- translation-symbol-table)))
- (push
- partial-translation
- symbol-translations)
- (puthash
- temp-hash-key
- symbol-translations
- translation-symbol-table)
- (setq
- translation
- partial-translation))))))
+ partial-translation)))))))
(let ((new-table-index (car pushdown-list)))
(let ((goto-table-distinct-index
@@ -921,6 +926,7 @@
\"Perform a LR-parse via lex-analyzer, optionally at INPUT-TAPE-INDEX with
PUSHDOWN-LIST, OUTPUT, TRANSLATION and HISTORY.\"
(let ((result
(%s--parse
+ nil
input-tape-index
pushdown-list
output
@@ -943,6 +949,7 @@
\"Perform a LR-parse via lex-analyzer, optionally at INPUT-TAPE-INDEX with
PUSHDOWN-LIST, OUTPUT, TRANSLATION and HISTORY.\"
(let ((result
(%s--parse
+ t
input-tape-index
pushdown-list
output
diff --git a/parser-generator-lr.el b/parser-generator-lr.el
index 8f54db9..76b0d0f 100644
--- a/parser-generator-lr.el
+++ b/parser-generator-lr.el
@@ -1661,6 +1661,7 @@
"Perform a LR-parse via lex-analyzer, optionally at INPUT-TAPE-INDEX with
PUSHDOWN-LIST, OUTPUT, TRANSLATION and HISTORY."
(let ((result
(parser-generator-lr--parse
+ nil
input-tape-index
pushdown-list
output
@@ -1678,6 +1679,7 @@
"Perform a LR-parse via lex-analyzer, optionally at INPUT-TAPE-INDEX with
PUSHDOWN-LIST, OUTPUT, TRANSLATION and HISTORY."
(let ((result
(parser-generator-lr--parse
+ t
input-tape-index
pushdown-list
output
@@ -1687,13 +1689,14 @@
;; Algorithm 5.7, p. 375
(defun parser-generator-lr--parse
- (&optional input-tape-index
+ (&optional perform-sdt
+ input-tape-index
pushdown-list
output
translation
translation-symbol-table-list
history)
- "Perform a LR-parse via lex-analyzer, optionally at INPUT-TAPE-INDEX with
PUSHDOWN-LIST, OUTPUT, TRANSLATION, TRANSLATION-SYMBOL-TABLE-LIST and HISTORY."
+ "Perform a LR-parse via lex-analyzer, optionally PERFORM-SDT means to
perform syntax-directed translation and optioanlly start at INPUT-TAPE-INDEX
with PUSHDOWN-LIST, OUTPUT, TRANSLATION, TRANSLATION-SYMBOL-TABLE-LIST and
HISTORY."
(unless input-tape-index
(setq input-tape-index 1))
(unless pushdown-list
@@ -1967,79 +1970,107 @@
(setq popped-items (1+ popped-items)))))
(push production-number output)
- (let ((popped-items-meta-contents))
- (setq
- popped-items-contents
- (reverse popped-items-contents))
- ;; Collect arguments for translation
- (dolist (popped-item popped-items-contents)
- (parser-generator--debug
- (message
- "popped-item: %s (for translation)"
- popped-item))
- (if (and
- (listp popped-item)
- (cdr popped-item))
+ (when perform-sdt
+ (let ((popped-items-meta-contents))
+ (setq
+ popped-items-contents
+ (reverse popped-items-contents))
+ ;; Collect arguments for translation
+ (dolist (popped-item popped-items-contents)
+ (parser-generator--debug
+ (message
+ "popped-item: %s (for translation)"
+ popped-item))
+ (if (and
+ (listp popped-item)
+ (cdr popped-item))
- ;; If item is a terminal, use it's literal
value
- (push
- (parser-generator-lex-analyzer--get-function
- popped-item)
- popped-items-meta-contents)
+ ;; If item is a terminal, use it's literal
value
+ (push
+
(parser-generator-lex-analyzer--get-function
+ popped-item)
+ popped-items-meta-contents)
- ;; If item is a non-terminal
- (let ((temp-hash-key
- (format
- "%S"
- popped-item)))
+ ;; If item is a non-terminal
+ (let ((temp-hash-key
+ (format
+ "%S"
+ popped-item)))
- ;; If we have a translation for symbol, pop
one
- ;; otherwise push nil on translation
argument stack
- (if (gethash
- temp-hash-key
- translation-symbol-table)
+ ;; If we have a translation for symbol,
pop one
+ ;; otherwise push nil on translation
argument stack
+ (if (gethash
+ temp-hash-key
+ translation-symbol-table)
+ (let ((symbol-translations
+ (gethash
+ temp-hash-key
+ translation-symbol-table)))
+ (let ((symbol-translation
+ (pop symbol-translations)))
+ (push
+ symbol-translation
+ popped-items-meta-contents)
+ (puthash
+ temp-hash-key
+ symbol-translations
+ translation-symbol-table)))
+ (push
+ nil
+ popped-items-meta-contents)))))
+
+ ;; If we just have one argument, pass it as a
instead of a list
+ (when (= (length popped-items-meta-contents) 1)
+ (setq
+ popped-items-meta-contents
+ (car popped-items-meta-contents)))
+
+ (parser-generator--debug
+ (message
+ "Production arguments: %s -> %s = %s"
+ production-lhs
+ production-rhs
+ popped-items-meta-contents))
+
+ ;; Perform translation at reduction if specified
+ (if
+
(parser-generator--get-grammar-translation-by-number
+ production-number)
+ (let ((partial-translation
+ (funcall
+
(parser-generator--get-grammar-translation-by-number
+ production-number)
+ popped-items-meta-contents)))
+ (parser-generator--debug
+ (message
+ "translation-symbol-table: %S = %S
(processed)"
+ production-lhs
+ partial-translation))
+ (let ((temp-hash-key
+ (format
+ "%S"
+ production-lhs)))
(let ((symbol-translations
(gethash
temp-hash-key
translation-symbol-table)))
- (let ((symbol-translation
- (pop symbol-translations)))
- (push
- symbol-translation
- popped-items-meta-contents)
- (puthash
- temp-hash-key
- symbol-translations
- translation-symbol-table)))
- (push
- nil
- popped-items-meta-contents)))))
-
- ;; If we just have one argument, pass it as a
instead of a list
- (when (= (length popped-items-meta-contents) 1)
- (setq
- popped-items-meta-contents
- (car popped-items-meta-contents)))
+ (push
+ partial-translation
+ symbol-translations)
+ (puthash
+ temp-hash-key
+ symbol-translations
+ translation-symbol-table)
+ (setq
+ translation
+ partial-translation))))
- (parser-generator--debug
- (message
- "Production arguments: %s -> %s = %s"
- production-lhs
- production-rhs
- popped-items-meta-contents))
-
- ;; Perform translation at reduction if specified
- (if
-
(parser-generator--get-grammar-translation-by-number
- production-number)
+ ;; When no translation is specified just use
popped contents as translation
(let ((partial-translation
- (funcall
-
(parser-generator--get-grammar-translation-by-number
- production-number)
- popped-items-meta-contents)))
+ popped-items-meta-contents))
(parser-generator--debug
(message
- "translation-symbol-table: %S = %S
(processed)"
+ "translation-symbol-table: %S = %S
(generic)"
production-lhs
partial-translation))
(let ((temp-hash-key
@@ -2059,34 +2090,7 @@
translation-symbol-table)
(setq
translation
- partial-translation))))
-
- ;; When no translation is specified just use
popped contents as translation
- (let ((partial-translation
- popped-items-meta-contents))
- (parser-generator--debug
- (message
- "translation-symbol-table: %S = %S (generic)"
- production-lhs
- partial-translation))
- (let ((temp-hash-key
- (format
- "%S"
- production-lhs)))
- (let ((symbol-translations
- (gethash
- temp-hash-key
- translation-symbol-table)))
- (push
- partial-translation
- symbol-translations)
- (puthash
- temp-hash-key
- symbol-translations
- translation-symbol-table)
- (setq
- translation
- partial-translation))))))
+ partial-translation)))))))
(let ((new-table-index (car pushdown-list)))
(let ((goto-table-distinct-index
@@ -2143,6 +2147,7 @@
"Invalid action-match: %s!"
action-match)
action-match))))))))))
+
(unless accept
(signal
'error
diff --git a/test/parser-generator-lr-export-test.el
b/test/parser-generator-lr-export-test.el
index 53127b0..ceefa20 100644
--- a/test/parser-generator-lr-export-test.el
+++ b/test/parser-generator-lr-export-test.el
@@ -93,7 +93,7 @@
(fboundp 'ba--parse)))
(when (fboundp 'ba--parse)
- (let ((regular-parse (ba--parse)))
+ (let ((regular-parse (ba--parse t)))
(let ((regular-parse-history (nth 3 regular-parse)))
;; (message "regular-parse-history: %s" regular-parse-history)
(let ((history-length (length regular-parse-history))
@@ -121,6 +121,7 @@
(let ((incremental-parse
(ba--parse
+ t
input-tape-index
pushdown-list
output
diff --git a/test/parser-generator-lr-test.el b/test/parser-generator-lr-test.el
index 417e61f..95eaab71 100644
--- a/test/parser-generator-lr-test.el
+++ b/test/parser-generator-lr-test.el
@@ -12,7 +12,7 @@
(defun parser-generator-lr-test--parse-incremental-vs-regular ()
"Verify that regular and incremental parse results in same data."
- (let ((regular-parse (parser-generator-lr--parse)))
+ (let ((regular-parse (parser-generator-lr--parse t)))
;; (message "regular-parse: %s" regular-parse)
(let ((regular-parse-history (nth 3 regular-parse)))
;; (message "regular-parse-history: %s" regular-parse-history)
@@ -37,6 +37,7 @@
(let ((incremental-parse
(parser-generator-lr--parse
+ t
input-tape-index
pushdown-list
output
@@ -977,7 +978,7 @@
(setq index (1+ index)))
(nreverse tokens))))
(should-error
- (parser-generator-lr--parse))
+ (parser-generator-lr--parse t))
(message "Passed test with terminals as symbols, invalid syntax")
(parser-generator-set-grammar '((Sp S) ("a" "b") ((Sp S) (S (S "a" S "b"))
(S e)) Sp))
@@ -1023,7 +1024,7 @@
(setq index (1+ index)))
(nreverse tokens))))
(should-error
- (parser-generator-lr--parse))
+ (parser-generator-lr--parse t))
(message "Passed test with terminals as string, invalid syntax")
(setq
- [elpa] externals/parser-generator 6733b57 415/434: Added feature to move lex-analyzer forward, (continued)
- [elpa] externals/parser-generator 6733b57 415/434: Added feature to move lex-analyzer forward, ELPA Syncer, 2021/11/29
- [elpa] externals/parser-generator 9eca533 410/434: Added test and implementation of calculating FIRST on multiple symbols were first is a non-terminal that expands into an e-identifier, ELPA Syncer, 2021/11/29
- [elpa] externals/parser-generator ca21bcd 412/434: Shortened doc-string, ELPA Syncer, 2021/11/29
- [elpa] externals/parser-generator 0a3f5f5 426/434: Added test for LR(1) PHP 8.0 match grammar, ELPA Syncer, 2021/11/29
- [elpa] externals/parser-generator c9906f7 420/434: Move order of export of LR lex-analyzer, ELPA Syncer, 2021/11/29
- [elpa] externals/parser-generator a4c5d9f 429/434: Syntax-directed translations now have access to terminal data if any is available, ELPA Syncer, 2021/11/29
- [elpa] externals/parser-generator 428207c 432/434: Fixed bug with exported lr-parser with partial translation, ELPA Syncer, 2021/11/29
- [elpa] externals/parser-generator fa43f05 301/434: More cpu optimizations, ELPA Syncer, 2021/11/29
- [elpa] externals/parser-generator a65b652 307/434: Added TODO-items, ELPA Syncer, 2021/11/29
- [elpa] externals/parser-generator ac7207a 292/434: Passed translate test on exported parser, ELPA Syncer, 2021/11/29
- [elpa] externals/parser-generator 63bd6c0 423/434: LR-parser now has SDT as optional feature to speed up plain parses,
ELPA Syncer <=
- [elpa] externals/parser-generator 9c41807 424/434: Code-styling fix, ELPA Syncer, 2021/11/29
- [elpa] externals/parser-generator 231bf85 422/434: Using (signal) instead of (error) in LR-parser and exported LR-parser when encountering syntax error, ELPA Syncer, 2021/11/29
- [elpa] externals/parser-generator 48f109c 417/434: Fixed typo in exported LR parser, ELPA Syncer, 2021/11/29
- [elpa] externals/parser-generator da14fbd 431/434: Passing more metadata about terminals to SDT, ELPA Syncer, 2021/11/29
- [elpa] externals/parser-generator af9ad94 418/434: Move lexer flag now affecting global state, ELPA Syncer, 2021/11/29