branch: externals/parser-generator
commit 3615fad763c8c8d014edb9db7b6b3801dda4ab21
Author: Christian Johansson <[email protected]>
Commit: Christian Johansson <[email protected]>
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")
