branch: externals/parser-generator commit 175a5794397e7ffaa2a8b55dffeb46f359e43a55 Author: Christian Johansson <christ...@cvj.se> Commit: Christian Johansson <christ...@cvj.se>
Passed test for generation action-table LR(0) grammar
---
parser-generator-lr.el | 102 +++++++++++++++++++++++++++------------
test/parser-generator-lr-test.el | 13 +++--
2 files changed, 76 insertions(+), 39 deletions(-)
diff --git a/parser-generator-lr.el b/parser-generator-lr.el
index 0fa4e2d..33b19a9 100644
--- a/parser-generator-lr.el
+++ b/parser-generator-lr.el
@@ -103,8 +103,9 @@
(if
(parser-generator--valid-look-ahead-p
eff-item)
- (let ((hash-key
- (format "%s-%s-%s" goto-index
state eff-item)))
+ (let
+ ((hash-key
+ (format "%s-%s-%s" goto-index
state eff-item)))
(parser-generator--debug
(message
"Valid look-ahead: %s"
@@ -125,16 +126,27 @@
hash-key
t
added-actions)
- (push
- (list
- eff-item
- 'shift
- )
- action-table)
- (setq
- found-action
- t)
- ))
+ (if
+ (and
+ (=
+
parser-generator--look-ahead-number
+ 0)
+ (equal
+ eff-item
+
`(,parser-generator--eof-identifier)))
+ ;; An extra column for '$'
(end of input) is added to the action table that contains acc for every item
set that contains an item of the form S → w • eof.
+ (progn
+ (push (list eff-item
'accept) action-table)
+ (setq found-accept t))
+ (push
+ (list
+ eff-item
+ 'shift
+ )
+ action-table)))
+ (setq
+ found-action
+ t))
(parser-generator--debug
(message
"Not valid look-ahead: %s"
@@ -153,11 +165,13 @@
(u (nth 3 lr-item)))
(unless B
(setq B (list parser-generator--e-identifier)))
- (when (parser-generator--valid-look-ahead-p u)
- (let ((hash-key
- (format "%s-%s-%s" goto-index state u)))
- (unless (gethash hash-key added-actions)
- (puthash hash-key t added-actions)
+ (if
+ (=
+ parser-generator--look-ahead-number
+ 0)
+
+ ;; LR(0) uses a different algorithm for
determining reduce actions
+ (unless (nth 2 lr-item)
(let ((production (list A B)))
(let
((production-number
@@ -173,21 +187,45 @@
(message "production: %s (%s)" production
production-number)
(message "u: %s" u))
- (if (and
- (= production-number 0)
- (>= (length u) 1)
- (parser-generator--valid-eof-p
- (nth (1- (length u)) u)))
- (progn
- ;; Reduction by first production
- ;; of empty look-ahead means grammar
has been accepted
- (push (list u 'accept) action-table)
- (setq found-accept t)
- (setq found-action t))
-
- ;; save reduction action in action table
- (push (list u 'reduce production-number)
action-table)
- (setq found-action t))))))))))
+ (push (list nil 'reduce production-number)
action-table)
+ (setq found-action t)
+ (setq continue-loop nil))))
+
+ (when (parser-generator--valid-look-ahead-p u)
+ (let ((hash-key
+ (format "%s-%s-%s" goto-index state u)))
+ (unless (gethash hash-key added-actions)
+ (puthash hash-key t added-actions)
+ (let ((production (list A B)))
+ (let
+ ((production-number
+
(parser-generator--get-grammar-production-number
+ production)))
+ (unless production-number
+ (error
+ "Expecting production number for %s
from LR-item %s!"
+ production
+ lr-item))
+
+ (parser-generator--debug
+ (message "production: %s (%s)" production
production-number)
+ (message "u: %s" u))
+
+ (if (and
+ (= production-number 0)
+ (>= (length u) 1)
+ (parser-generator--valid-eof-p
+ (nth (1- (length u)) u)))
+ (progn
+ ;; Reduction by first production
+ ;; of empty look-ahead means grammar
has been accepted
+ (push (list u 'accept) action-table)
+ (setq found-accept t)
+ (setq found-action t))
+
+ ;; save reduction action in action table
+ (push (list u 'reduce production-number)
action-table)
+ (setq found-action t)))))))))))
((eq state 'error)
(unless found-action
diff --git a/test/parser-generator-lr-test.el b/test/parser-generator-lr-test.el
index 39938cb..00135de 100644
--- a/test/parser-generator-lr-test.el
+++ b/test/parser-generator-lr-test.el
@@ -871,15 +871,14 @@
(equal
'(
(0 ((("0") shift) (("1") shift)))
- (1 ((("*") reduce 3) (("+" reduce 3)) (("0") reduce 3) (("1") reduce
3) (($) reduce 3)))
- (2 ((("*") reduce 6) (("+") reduce 6) (("0") reduce 6) (("1") reduce
6) (($) reduce 6)))
- (3 ((("*") reduce 4) (("+") reduce 4) (("0") reduce 4) (("1") reduce
4) (($) accept)))
- (4 ((("*") shift) (("+") shift) (($) accept)))
+ (1 ((nil reduce 4)))
+ (2 ((nil reduce 5)))
+ (3 ((nil reduce 3)))
+ (4 ((($) accept) (("*") shift) (("+") shift)))
(5 ((("0") shift) (("1") shift)))
(6 ((("0") shift) (("1") shift)))
- (7 ((("*") reduce 2) (("+") reduce 2) (("0") reduce 2) (("1") reduce
2) (($) reduce 1)))
- (8 ((("*") reduce 1) (("+") reduce 1) (("0") reduce 1) (("1") reduce
1) (($) reduce 2)))
- )
+ (7 ((nil reduce 2)))
+ (8 ((nil reduce 1))))
(parser-generator--hash-to-list
parser-generator-lr--action-tables)))
(message "Passed ACTION-tables k = 0")
