[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[elpa] externals/parser-generator 3615fad 276/434: Fixed issue with lex-
From: |
ELPA Syncer |
Subject: |
[elpa] externals/parser-generator 3615fad 276/434: Fixed issue with lex-analyzer in LR(0) Parser |
Date: |
Mon, 29 Nov 2021 15:59:57 -0500 (EST) |
branch: externals/parser-generator
commit 3615fad763c8c8d014edb9db7b6b3801dda4ab21
Author: Christian Johansson <christian@cvj.se>
Commit: Christian Johansson <christian@cvj.se>
Fixed issue with lex-analyzer in LR(0) Parser
---
parser-generator-lex-analyzer.el | 14 +++++++++-----
parser-generator-lr.el | 34 ++++++++++++++++++++++++++++------
test/parser-generator-lr-test.el | 31 ++++++++++++++-----------------
3 files changed, 51 insertions(+), 28 deletions(-)
diff --git a/parser-generator-lex-analyzer.el b/parser-generator-lex-analyzer.el
index ba831da..7353be4 100644
--- a/parser-generator-lex-analyzer.el
+++ b/parser-generator-lex-analyzer.el
@@ -62,10 +62,13 @@
(error "Missing look-ahead-number!"))
(let ((look-ahead)
(look-ahead-length 0)
- (index parser-generator-lex-analyzer--index))
+ (index parser-generator-lex-analyzer--index)
+ (k (max
+ 1
+ parser-generator--look-ahead-number)))
(while (<
look-ahead-length
- parser-generator--look-ahead-number)
+ k)
(condition-case error
(progn
(let ((next-look-ahead
@@ -79,7 +82,7 @@
(dolist (next-look-ahead-item next-look-ahead)
(when (<
look-ahead-length
- parser-generator--look-ahead-number)
+ k)
(push next-look-ahead-item look-ahead)
(setq look-ahead-length (1+ look-ahead-length))
(setq index (cdr (cdr next-look-ahead-item))))))
@@ -114,8 +117,9 @@
(unless (listp (car token))
(setq token (list token)))
(let ((first-token (car token)))
- (setq parser-generator-lex-analyzer--index
- (cdr (cdr first-token)))
+ (setq
+ parser-generator-lex-analyzer--index
+ (cdr (cdr first-token)))
(push first-token tokens)))))
(error (error
"Lex-analyze failed to pop token at %s, error: %s"
diff --git a/parser-generator-lr.el b/parser-generator-lr.el
index 33b19a9..6d4ae1b 100644
--- a/parser-generator-lr.el
+++ b/parser-generator-lr.el
@@ -997,6 +997,12 @@
table-index
pushdown-list))
+ (parser-generator--debug
+ (message
+ "Action-table %d: %s"
+ table-index
+ action-table))
+
(let ((action-match nil)
(action-table-length (length action-table))
(action-index 0)
@@ -1011,12 +1017,28 @@
(push
action-look-ahead
possible-look-aheads)
- (when (equal
- action-look-ahead
- look-ahead)
- (setq action-match
- (cdr action)))))
- (setq action-index (1+ action-index)))
+ (when
+ (equal
+ action-look-ahead
+ look-ahead)
+ (setq
+ action-match
+ (cdr action)))
+ (when
+ (and
+ (=
+ parser-generator--look-ahead-number
+ 0)
+ (not
+ action-look-ahead))
+ ;; LR(0) reduce actions occupy entire row
+ ;; and is applied regardless of look-ahead
+ (setq
+ action-match
+ (cdr action))))
+ (setq
+ action-index
+ (1+ action-index))))
(unless action-match
;; (c) If f(u) = error, we halt parsing (and, in practice
diff --git a/test/parser-generator-lr-test.el b/test/parser-generator-lr-test.el
index 00135de..b07f6d3 100644
--- a/test/parser-generator-lr-test.el
+++ b/test/parser-generator-lr-test.el
@@ -881,20 +881,16 @@
(8 ((nil reduce 1))))
(parser-generator--hash-to-list
parser-generator-lr--action-tables)))
- (message "Passed ACTION-tables k = 0")
-
- )
-
- ;; TODO Replace below with parse of k=0
+ (message "Passed ACTION-tables k = 0"))
(let ((buffer (generate-new-buffer "*a*")))
(switch-to-buffer buffer)
(kill-region (point-min) (point-max))
- (insert "abac")
+ (insert "1+1")
(parser-generator-set-grammar
- '((Sp S R T) ("a" "b" "c") ((Sp S) (S (R S) (R)) (R ("a" "b" T)) (T ("a"
T) ("c") (e))) Sp))
- (parser-generator-set-look-ahead-number 2)
+ '((S E B) ("*" "+" "0" "1") ((S (E $)) (E (E "*" B) (E "+" B) (B)) (B
("0") ("1"))) S))
+ (parser-generator-set-look-ahead-number 0)
(parser-generator-process-grammar)
(parser-generator-lr-generate-parser-tables)
@@ -915,22 +911,23 @@
(let ((start (car (cdr token)))
(end (cdr (cdr token))))
(when (<= end (point-max))
- (buffer-substring-no-properties start end))))))
+ (buffer-substring-no-properties
+ start
+ end))))))
(should
(equal
- '(5 4 3 2)
+ '(5 3 5 2)
(parser-generator-lr-parse)))
-
(message "Passed parse with k = 0 # 1")
(switch-to-buffer buffer)
(kill-region (point-min) (point-max))
- (insert "aba")
+ (insert "1+1*1")
(should
(equal
- '(6 4 3 2)
+ '(5 3 5 2 5 1)
(parser-generator-lr-parse)))
(message "Passed parse with k = 0 # 2")
@@ -940,11 +937,11 @@
(let ((buffer (generate-new-buffer "*a*")))
(switch-to-buffer buffer)
(kill-region (point-min) (point-max))
- (insert "abac")
+ (insert "1+1")
(parser-generator-set-grammar
- '((Sp S R T) ("a" "b" "c") ((Sp S) (S (R S) (R)) (R ("a" "b" T
(lambda(args) (list "begin" (nth 2 args) "end")))) (T ("a" T (lambda(args)
"test")) ("c") (e))) Sp))
- (parser-generator-set-look-ahead-number 2)
+ '((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))
+ (parser-generator-set-look-ahead-number 0)
(parser-generator-process-grammar)
(parser-generator-lr-generate-parser-tables)
@@ -969,7 +966,7 @@
(should
(equal
- '("begin" "test" "end")
+ '("1" " . " "1")
(parser-generator-lr-translate)))
(message "Passed translation k=0")
- [elpa] externals/parser-generator 3807a72 237/434: Added failing unit test for LR-items k=2, (continued)
- [elpa] externals/parser-generator 3807a72 237/434: Added failing unit test for LR-items k=2, ELPA Syncer, 2021/11/29
- [elpa] externals/parser-generator 40473d3 252/434: Fixed bug with data in full look-ahead in parse function, ELPA Syncer, 2021/11/29
- [elpa] externals/parser-generator e1315c3 246/434: Updated so E-FREE-FIRST(x) only uses E-FREE-FIRST on first symbol, ELPA Syncer, 2021/11/29
- [elpa] externals/parser-generator 53ae129 245/434: Commented out useless code, ELPA Syncer, 2021/11/29
- [elpa] externals/parser-generator 24e96cb 261/434: Improved description of LRk, ELPA Syncer, 2021/11/29
- [elpa] externals/parser-generator 40907b7 257/434: white-space fixes, ELPA Syncer, 2021/11/29
- [elpa] externals/parser-generator 37d9fcb 260/434: Improved documentation, ELPA Syncer, 2021/11/29
- [elpa] externals/parser-generator 08b696f 267/434: Fixed typo in doc about token, ELPA Syncer, 2021/11/29
- [elpa] externals/parser-generator b80fc6e 264/434: Updated README, ELPA Syncer, 2021/11/29
- [elpa] externals/parser-generator 1b9d8db 268/434: Improved wording about lexical analysis, ELPA Syncer, 2021/11/29
- [elpa] externals/parser-generator 3615fad 276/434: Fixed issue with lex-analyzer in LR(0) Parser,
ELPA Syncer <=
- [elpa] externals/parser-generator 732cd78 282/434: Constants and variables are exported correctly, ELPA Syncer, 2021/11/29
- [elpa] externals/parser-generator cbf9e07 278/434: Added documentation about LR(0) Parser, ELPA Syncer, 2021/11/29
- [elpa] externals/parser-generator af71d8b 285/434: Lex-analyzer is now exported, ELPA Syncer, 2021/11/29
- [elpa] externals/parser-generator 500d082 284/434: Added Lex-Analyzer Rest Function to export, ELPA Syncer, 2021/11/29
- [elpa] externals/parser-generator cf42e67 288/434: Exported parser passes test, ELPA Syncer, 2021/11/29
- [elpa] externals/parser-generator 1e0418d 295/434: Incremental parse and translate of exported parser passes tests, ELPA Syncer, 2021/11/29
- [elpa] externals/parser-generator 7584880 298/434: Added failing unit test for calculating FIRST in grammar with cycles, ELPA Syncer, 2021/11/29
- [elpa] externals/parser-generator f338734 303/434: Improved output of progress, ELPA Syncer, 2021/11/29
- [elpa] externals/parser-generator 98c9d94 213/434: Debugging parse with look-ahead > 1, ELPA Syncer, 2021/11/29
- [elpa] externals/parser-generator 2b0d5b8 215/434: More debugging, ELPA Syncer, 2021/11/29