branch: externals/parser-generator
commit 7b77032f7179d7911d04db1be725b03622de153a
Author: Christian Johansson <[email protected]>
Commit: Christian Johansson <[email protected]>
Parser table generation for LLk now works for productions
---
parser-generator-ll.el | 52 ++++++++++++++++++++++++++++++----------
test/parser-generator-ll-test.el | 18 +++++++-------
2 files changed, 49 insertions(+), 21 deletions(-)
diff --git a/parser-generator-ll.el b/parser-generator-ll.el
index 5ec448db43..6c2410a2e3 100644
--- a/parser-generator-ll.el
+++ b/parser-generator-ll.el
@@ -234,6 +234,7 @@
(value (nth 1 table))
(key-stack-symbol (car (nth 0 key)))
(key-parent-follow-set (nth 1 key))
+ (left-hand-side (nth 0 key))
(parse-table))
(dolist (look-ahead-row value)
(let* ((look-ahead (nth 0 look-ahead-row))
@@ -241,21 +242,48 @@
(local-follow-sets (nth 2 look-ahead-row))
(non-terminal-index 0)
(sub-symbol-index 0)
- (sub-symbol-length (length right-hand-side)))
- (while (< sub-symbol-index sub-symbol-length)
- (let ((sub-symbol (nth sub-symbol-index right-hand-side)))
- (when (parser-generator--valid-non-terminal-p
+ (sub-symbol-length (length right-hand-side))
+ (production (list left-hand-side right-hand-side))
+ (production-number
+ (parser-generator--get-grammar-production-number
+ production))
+ (modified-right-hand-side))
+ (while (< sub-symbol-index sub-symbol-length)
+ (let ((sub-symbol (nth sub-symbol-index right-hand-side)))
+ (if (parser-generator--valid-non-terminal-p
sub-symbol)
- (let ((local-follow (nth non-terminal-index
local-follow-sets)))
- )
- (setq
- non-terminal-index
- (1+ non-terminal-index))))
+ (let ((local-follow (nth non-terminal-index
local-follow-sets)))
+ (push
+ (list
+ (list sub-symbol)
+ local-follow)
+ modified-right-hand-side)
+ (setq
+ non-terminal-index
+ (1+ non-terminal-index)))
+ (push
+ sub-symbol
+ modified-right-hand-side)))
+ (setq
+ sub-symbol-index
+ (1+ sub-symbol-index)))
(setq
- sub-symbol-index
- (1+ sub-symbol-index)))))))
+ modified-right-hand-side
+ (reverse modified-right-hand-side))
+
+ (push
+ (list
+ look-ahead
+ 'reduce
+ modified-right-hand-side
+ production-number)
+ parse-table)))
+ (push
+ (list
+ key
+ parse-table)
+ parsing-table)))
- ;;
;; (2) M(a, av) = pop for all v in E where |E| = k-1 -> move to parser
logic
;; (3) M($, e) = accept -> move to parser logic
diff --git a/test/parser-generator-ll-test.el b/test/parser-generator-ll-test.el
index 7a5f86dbe2..01bbe32066 100644
--- a/test/parser-generator-ll-test.el
+++ b/test/parser-generator-ll-test.el
@@ -102,7 +102,7 @@
(parser-tables
(parser-generator-ll--generate-parsing-table
tables)))
- (message "parser-tables: %S" parser-tables)
+ ;; (message "parser-tables: %S" parser-tables)
;; TODO Make this pass
(should
@@ -111,23 +111,23 @@
(
((S) nil) ;; T0
(
- ((a a) reduce (a ((A) (a a)) a a) 1)
- ((a b) reduce (a ((A) (a a)) a a) 1)
- ((b b) reduce (b ((A) (b a)) b a) 2)
+ ((b b) reduce (b ((A) (b a)) b a) 1)
+ ((a a) reduce (a ((A) (a a)) a a) 0)
+ ((a b) reduce (a ((A) (a a)) a a) 0)
)
)
(
((A) (a a)) ;; T1
(
- ((a a) reduce (e) 4)
- ((b a) reduce (b) 3)
+ ((b a) reduce (b) 2)
+ ((a a) reduce (e) 3)
)
)
(
- ((A) (a b)) ;; T2
+ ((A) (b a)) ;; T2
(
- ((b a) reduce (e) 4)
- ((b b) reduce (b) 3)
+ ((b a) reduce (e) 3)
+ ((b b) reduce (b) 2)
)
)
)
