[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[elpa] externals/parser-generator 175a579 275/434: Passed test for gener
|
From: |
ELPA Syncer |
|
Subject: |
[elpa] externals/parser-generator 175a579 275/434: Passed test for generation action-table LR(0) grammar |
|
Date: |
Mon, 29 Nov 2021 15:59:56 -0500 (EST) |
branch: externals/parser-generator
commit 175a5794397e7ffaa2a8b55dffeb46f359e43a55
Author: Christian Johansson <christian@cvj.se>
Commit: Christian Johansson <christian@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")
- [elpa] externals/parser-generator 2a9a23e 219/434: More debugging, (continued)
- [elpa] externals/parser-generator 2a9a23e 219/434: More debugging, ELPA Syncer, 2021/11/29
- [elpa] externals/parser-generator ddd5967 221/434: Passed test for nested translations, ELPA Syncer, 2021/11/29
- [elpa] externals/parser-generator bc817d1 224/434: Passing all tests for k=1 again, ELPA Syncer, 2021/11/29
- [elpa] externals/parser-generator b2f1d7a 236/434: More debugging k > 1, ELPA Syncer, 2021/11/29
- [elpa] externals/parser-generator 16f6586 242/434: Fixed bug in lr-item generation were look-ahead was disregarded, ELPA Syncer, 2021/11/29
- [elpa] externals/parser-generator 36701c0 238/434: Optimized closure algorithm to only use possible next-symbols instead of iterating all symbols, ELPA Syncer, 2021/11/29
- [elpa] externals/parser-generator 3e096f7 258/434: Improved translation handling for each production, ELPA Syncer, 2021/11/29
- [elpa] externals/parser-generator 96cd5de 259/434: Improved validation of grammar structure, ELPA Syncer, 2021/11/29
- [elpa] externals/parser-generator bbdbd18 269/434: Started on test for LR Parse k=0, ELPA Syncer, 2021/11/29
- [elpa] externals/parser-generator 56363c1 263/434: Fixed last TODO items, ELPA Syncer, 2021/11/29
- [elpa] externals/parser-generator 175a579 275/434: Passed test for generation action-table LR(0) grammar,
ELPA Syncer <=
- [elpa] externals/parser-generator ecbbf21 290/434: Added test for exported translator, ELPA Syncer, 2021/11/29
- [elpa] externals/parser-generator cecf8fd 287/434: More TODO items, ELPA Syncer, 2021/11/29
- [elpa] externals/parser-generator 688e685 291/434: Lex-analyzer index is now buffer-local variable, ELPA Syncer, 2021/11/29
- [elpa] externals/parser-generator 0702765 293/434: Added incremental unit test for exported parser/translator, ELPA Syncer, 2021/11/29
- [elpa] externals/parser-generator 552c0c5 304/434: Using better hash-key for goto-tables generation, ELPA Syncer, 2021/11/29
- [elpa] externals/parser-generator d0d3201 299/434: FIRST calculation now handles cyclic productions, ELPA Syncer, 2021/11/29
- [elpa] externals/parser-generator 5145cda 306/434: Improved hash-key integrity for LRk Parser, ELPA Syncer, 2021/11/29
- [elpa] externals/parser-generator 2227cae 313/434: Moved validation of valid lr-item set to generation of goto-tables, ELPA Syncer, 2021/11/29
- [elpa] externals/parser-generator a86c658 305/434: Improved output, ELPA Syncer, 2021/11/29
- [elpa] externals/parser-generator dcbbdee 315/434: Started on support for symbol attributes, ELPA Syncer, 2021/11/29