[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[elpa] externals/parser-generator bd887ff 277/434: LR(0) Parser passing
|
From: |
ELPA Syncer |
|
Subject: |
[elpa] externals/parser-generator bd887ff 277/434: LR(0) Parser passing translation test |
|
Date: |
Mon, 29 Nov 2021 15:59:57 -0500 (EST) |
branch: externals/parser-generator
commit bd887ff2757ed1aff9104f841f4a273a2caf131d
Author: Christian Johansson <christian@cvj.se>
Commit: Christian Johansson <christian@cvj.se>
LR(0) Parser passing translation test
---
parser-generator-lex-analyzer.el | 2 +-
parser-generator-lr.el | 176 +++++++++++++++++++++++----------------
test/parser-generator-lr-test.el | 12 ++-
3 files changed, 111 insertions(+), 79 deletions(-)
diff --git a/parser-generator-lex-analyzer.el b/parser-generator-lex-analyzer.el
index 7353be4..52a1c34 100644
--- a/parser-generator-lex-analyzer.el
+++ b/parser-generator-lex-analyzer.el
@@ -36,7 +36,7 @@
(defun parser-generator-lex-analyzer--get-function (token)
"Get information about TOKEN."
(unless parser-generator-lex-analyzer--get-function
- (error "Missing lex-analyzer get function!"))
+ (error "Missing lex-analyzer get function! Token: %s" token))
(let ((meta-information))
(condition-case error
(progn
diff --git a/parser-generator-lr.el b/parser-generator-lr.el
index 6d4ae1b..6cf7bf8 100644
--- a/parser-generator-lr.el
+++ b/parser-generator-lr.el
@@ -282,11 +282,11 @@
(setq
lr-item-set-new-index
(1+ lr-item-set-new-index))
- ;; Mark the initial set
- (puthash
- e-set
- lr-item-set-new-index
- marked-lr-item-sets))
+ ;; Mark the initial set
+ (puthash
+ e-set
+ lr-item-set-new-index
+ marked-lr-item-sets))
;; (2) If a set of items a in S is unmarked
;; (3) Repeat step (2) until all sets of items in S are marked.
@@ -322,12 +322,12 @@
(or
(parser-generator--valid-terminal-p next-symbol)
(parser-generator--valid-non-terminal-p next-symbol))
- (not
- (gethash
- (list
- lr-item-set-index
- next-symbol)
- next-symbols-found)))
+ (not
+ (gethash
+ (list
+ lr-item-set-index
+ next-symbol)
+ next-symbols-found)))
(push
next-symbol
next-symbols)
@@ -553,8 +553,8 @@
(parser-generator--get-grammar-rhs start))
(e-list parser-generator--e-identifier)
(eof-list (parser-generator--generate-list-of-symbol
- parser-generator--look-ahead-number
- parser-generator--eof-identifier)))
+ parser-generator--look-ahead-number
+ parser-generator--eof-identifier)))
;; (a)
(dolist (rhs start-productions)
@@ -723,8 +723,8 @@
(let ((lr-new-item)
(lr-item-exists (make-hash-table :test 'equal))
(eof-list (parser-generator--generate-list-of-symbol
- parser-generator--look-ahead-number
- parser-generator--eof-identifier)))
+ parser-generator--look-ahead-number
+ parser-generator--eof-identifier)))
(parser-generator--debug (message "x: %s" x))
(dolist (lr-item previous-lr-item)
@@ -903,12 +903,13 @@
translation
history)
"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
- input-tape-index
- pushdown-list
- output
- translation
- history)))
+ (let ((result
+ (parser-generator-lr--parse
+ input-tape-index
+ pushdown-list
+ output
+ translation
+ history)))
(nth 1 result)))
;; Algorithm 5.7, p. 375
@@ -925,7 +926,9 @@
(unless pushdown-list
(push 0 pushdown-list))
(unless translation-symbol-table
- (setq translation-symbol-table (make-hash-table :test 'equal)))
+ (setq
+ translation-symbol-table
+ (make-hash-table :test 'equal)))
(if (and
input-tape-index
@@ -943,12 +946,9 @@
(let ((accept)
(pre-index 0))
-
(while (not accept)
- ;; (message "output: %s, index: %s" output
parser-generator-lex-analyzer--index)
-
- ;; Save history when index has changed
+ ;; Save history when index has changed to enable incremental parsing /
translating
(when
(>
parser-generator-lex-analyzer--index
@@ -1160,56 +1160,84 @@
(setq popped-items (1+ popped-items)))))
(push production-number output)
- ;; Perform translation at reduction if specified
- (when
- (parser-generator--get-grammar-translation-by-number
- production-number)
-
- (let ((popped-items-meta-contents))
- (dolist (popped-item popped-items-contents)
- (parser-generator--debug
- (message
- "popped-item: %s"
- popped-item))
- (if (and
- (listp popped-item)
- (cdr popped-item))
+ (let ((popped-items-meta-contents)
+ (all-expanded t))
+ ;; Collect arguments for translation
+ (dolist (popped-item popped-items-contents)
+ (parser-generator--debug
+ (message
+ "popped-item: %s"
+ 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 (gethash
+ popped-item
+ translation-symbol-table)
(push
- (parser-generator-lex-analyzer--get-function
- popped-item)
+ (gethash
+ popped-item
+ translation-symbol-table)
popped-items-meta-contents)
- (if (gethash
- popped-item
- translation-symbol-table)
- (push
- (gethash
- popped-item
- translation-symbol-table)
- popped-items-meta-contents)
- (push
- nil
- popped-items-meta-contents))))
- (setq
- popped-items-meta-contents
- (nreverse popped-items-meta-contents))
-
- (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"
- production-lhs
- partial-translation))
- (puthash
- production-lhs
- partial-translation
- translation-symbol-table)
- (setq
- translation
- partial-translation))))
+ (setq
+ all-expanded
+ nil)
+ (push
+ nil
+ popped-items-meta-contents))))
+ (setq
+ popped-items-meta-contents
+ (nreverse 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"
+ production-lhs
+ partial-translation))
+ (puthash
+ production-lhs
+ partial-translation
+ translation-symbol-table)
+ (setq
+ translation
+ partial-translation))
+
+ ;; When no translation is specified just use
arguments as translation
+ (when all-expanded
+ (let ((partial-translation
+ popped-items-meta-contents))
+ (parser-generator--debug
+ (message
+ "translation-symbol-table: %s = %s (generic)"
+ production-lhs
+ partial-translation))
+ (puthash
+ production-lhs
+ partial-translation
+ translation-symbol-table)
+ (setq
+ translation
+ partial-translation)))))
(let ((new-table-index (car pushdown-list)))
(let ((goto-table
diff --git a/test/parser-generator-lr-test.el b/test/parser-generator-lr-test.el
index b07f6d3..f409c51 100644
--- a/test/parser-generator-lr-test.el
+++ b/test/parser-generator-lr-test.el
@@ -77,7 +77,7 @@
(parser-generator--hash-to-list
parser-generator-lr--action-tables)))
- (message "Ended tests for (parser-generator-lr--generate-action-tables)"))
+ (message "Passed tests for (parser-generator-lr--generate-action-tables)"))
(defun parser-generator-lr-test--generate-goto-tables ()
"Test `parser-generator-lr--generate-goto-tables'."
@@ -308,6 +308,10 @@
(push (nth (1- index) string) tokens)
(setq index (1+ index)))
(nreverse tokens))))
+ (setq
+ parser-generator-lex-analyzer--get-function
+ (lambda (token)
+ (car token)))
(should
(equal
'(2 2 2 1 1)
@@ -708,7 +712,7 @@
(should
(equal
- '("begin" "test" "end")
+ '(("begin" "test" "end"))
(parser-generator-lr-translate)))
(message "Passed translation k=2")
@@ -940,7 +944,7 @@
(insert "1+1")
(parser-generator-set-grammar
- '((S E B) ("*" "+" "0" "1") ((S (E $)) (E (E "*" B (lambda(args) (list
(nth 0 args) " x " (nth 2 args)))) (E "+" B (lambda(args) (list (nth 0 args) "
. " (nth 2 args)))) (B)) (B ("0") ("1"))) S))
+ '((S E B) ("*" "+" "0" "1") ((S (E $)) (E (E "*" B (lambda(args) (let
((ret (list (nth 0 args)))) (when (nth 2 args) (setq ret (append ret `(" x "
,(nth 2 args))))) ret))) (E "+" B (lambda(args) (let ((ret (list (nth 0
args)))) (when (nth 2 args) (setq ret (append ret `(" . " ,(nth 2 args)))))
ret))) (B)) (B ("0") ("1"))) S))
(parser-generator-set-look-ahead-number 0)
(parser-generator-process-grammar)
(parser-generator-lr-generate-parser-tables)
@@ -966,7 +970,7 @@
(should
(equal
- '("1" " . " "1")
+ '((("1")) " . " ("1"))
(parser-generator-lr-translate)))
(message "Passed translation k=0")
- [elpa] externals/parser-generator d1f4682 248/434: Added a function that converts a FIRST-item to a look-ahead item, (continued)
- [elpa] externals/parser-generator d1f4682 248/434: Added a function that converts a FIRST-item to a look-ahead item, ELPA Syncer, 2021/11/29
- [elpa] externals/parser-generator 6845262 243/434: Passed GOTO-tables k=2, ELPA Syncer, 2021/11/29
- [elpa] externals/parser-generator 3a0d4cd 255/434: Added translation test for LRk=2, ELPA Syncer, 2021/11/29
- [elpa] externals/parser-generator 03ca2e9 247/434: Look-ahead generation now supports EOF symbol, ELPA Syncer, 2021/11/29
- [elpa] externals/parser-generator 3563720 266/434: Updated docs about lexical analysis, ELPA Syncer, 2021/11/29
- [elpa] externals/parser-generator 412fd2a 273/434: Passing generation of GOTO-table for LR(0) grammar, ELPA Syncer, 2021/11/29
- [elpa] externals/parser-generator bc23604 274/434: Fixed look-ahead, first and e-free-first with k = 0, ELPA Syncer, 2021/11/29
- [elpa] externals/parser-generator 1879cb0 271/434: Merge branch 'master' of git.cvj.se:/home/git/emacs-parser-generator, ELPA Syncer, 2021/11/29
- [elpa] externals/parser-generator 16bb2d8 262/434: Added translation example LRk parser, ELPA Syncer, 2021/11/29
- [elpa] externals/parser-generator d173c1e 281/434: More work on exporting parser as code function, ELPA Syncer, 2021/11/29
- [elpa] externals/parser-generator bd887ff 277/434: LR(0) Parser passing translation test,
ELPA Syncer <=
- [elpa] externals/parser-generator 852f969 283/434: Merge branch 'master' of git.cvj.se:/home/git/emacs-parser-generator, ELPA Syncer, 2021/11/29
- [elpa] externals/parser-generator 0d6d46d 294/434: Debugging incremental issue with exported translator, ELPA Syncer, 2021/11/29
- [elpa] externals/parser-generator c4c68b2 302/434: Added progress-indicator to goto-table generation, ELPA Syncer, 2021/11/29
- [elpa] externals/parser-generator 586789d 308/434: Added cache to first calculation, ELPA Syncer, 2021/11/29
- [elpa] externals/parser-generator 236a124 322/434: More work on resolving conflicts, ELPA Syncer, 2021/11/29
- [elpa] externals/parser-generator 04c360b 318/434: LR-items set validation now supports symbols with attributes, ELPA Syncer, 2021/11/29
- [elpa] externals/parser-generator ea02245 325/434: Improved debug output, ELPA Syncer, 2021/11/29
- [elpa] externals/parser-generator e56bcff 324/434: Improved output of productions and action-tables, ELPA Syncer, 2021/11/29
- [elpa] externals/parser-generator fb29641 337/434: Passing old context-sensitive precedence example with new structure, ELPA Syncer, 2021/11/29
- [elpa] externals/parser-generator 928b31d 343/434: More work on infix calculator, ELPA Syncer, 2021/11/29