branch: externals/parser-generator
commit 0a86c69ef1af587693e45778a21538918cfea642
Author: Christian Johansson <christ...@cvj.se>
Commit: Christian Johansson <christ...@cvj.se>
More work on LL-table generation
---
parser-generator-ll.el | 48 ++++++++++++++--------
test/parser-generator-ll-test.el | 88 +++++++++++++++++-----------------------
2 files changed, 68 insertions(+), 68 deletions(-)
diff --git a/parser-generator-ll.el b/parser-generator-ll.el
index 4ccc6ca159..1bce7e702c 100644
--- a/parser-generator-ll.el
+++ b/parser-generator-ll.el
@@ -44,7 +44,6 @@
;; Algorithm 5.2 p. 350
(defun parser-generator-ll--generate-tables ()
"Construction of LL(k)-tables. Output the set of LL(k) tables needed to
construct a parsing table for the grammar G."
-
(let ((tables (make-hash-table :test 'equal))
(distinct-item-p (make-hash-table :test 'equal))
(stack)
@@ -78,7 +77,9 @@
(parser-generator--first production-rhs nil t t))
(first-parent-follow
(parser-generator--first parent-follow nil t t))
- (look-aheads))
+ (look-aheads)
+ (sets)
+ (distinct-set-item-p (make-hash-table :test 'equal)))
(cond
((and first-rhs
@@ -149,6 +150,16 @@
(list sub-symbol)
sub-symbol-rhs
local-follow)))
+ (unless (gethash
+ local-follow
+ distinct-set-item-p)
+ (puthash
+ local-follow
+ t
+ distinct-set-item-p)
+ (push
+ local-follow
+ sets))
(parser-generator--debug
(message "new-stack-item: %S" new-stack-item))
(push
@@ -165,7 +176,8 @@
(let ((table
(list
look-ahead
- production-rhs))
+ production-rhs
+ sets))
(item-hash-key
(format
"%S-%S-%S"
@@ -208,12 +220,11 @@
(message "first-parent-follow: %S" first-parent-follow)
(message "look-aheads: %S" look-aheads))))
- ;; TODO Add deterministic sorting here
(let ((sorted-tables))
(maphash
(lambda (k v)
(push
- (list k v)
+ (list k (sort v 'parser-generator--sort-list))
sorted-tables))
tables)
sorted-tables)))
@@ -224,19 +235,20 @@
(defun parser-generator-ll--generate-parsing-table (tables)
"Generate a parsing table for an LL(k) grammar G and TABLES. Output M, a
valid parsing table for G."
(let ((parsing-table))
-
- ;; (2) M(a, av) = pop for all v in E where |E| = k-1
-
- ;; (3) M($, e) = accept
- (push
- `(,parser-generator--eof-identifier
- (
- ,(parser-generator--generate-list-of-symbol
- parser-generator--look-ahead-number
- parser-generator--eof-identifier)
- accept)
- )
- parsing-table)
+ (dolist (table tables)
+ (let* ((key (nth 0 table))
+ (value (nth 1 table))
+ (stack-symbol (car (nth 0 key)))
+ (local-follow-set (nth 1 key)))
+ (dolist (look-ahead-row value)
+ (let ((look-ahead (nth 0 look-ahead-row))
+ (right-hand-side (nth 1 look-ahead-row)))
+ (dolist (right-hand-symbol right-hand-side))
+ ))))
+
+ ;;
+ ;; (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
parsing-table))
diff --git a/test/parser-generator-ll-test.el b/test/parser-generator-ll-test.el
index 561b5ad7cc..6585373579 100644
--- a/test/parser-generator-ll-test.el
+++ b/test/parser-generator-ll-test.el
@@ -33,34 +33,35 @@
)
(parser-generator-process-grammar)
(let ((tables (parser-generator-ll--generate-tables)))
- (message "tables: %S" tables)
+ ;; (message "tables: %S" tables)
(should
(equal
tables
'(
(
- ((S) nil)
+ ((A) (b a))
(
- ((a b) (a A a a))
- ((a a) (a A a a))
- ((b b) (b A b a))
+ ((b b) (b) nil)
+ ((b a) (e) nil)
)
)
(
((A) (a a))
(
- ((a a) (e))
- ((b a) (b))
+ ((a a) (e) nil)
+ ((b a) (b) nil)
)
)
(
- ((A) (b a))
+ ((S) nil)
(
- ((b b) (b))
- ((b a) (e))
+ ((a b) (a A a a) ((a a)))
+ ((a a) (a A a a) ((a a)))
+ ((b b) (b A b a) ((b a)))
)
)
- )))
+ )
+ ))
tables)
(message "Passed tests for (parser-generator-ll--generate-tables)"))
@@ -73,10 +74,9 @@
(parser-generator-set-e-identifier 'e)
(parser-generator-set-look-ahead-number 2)
(let* ((tables
- '(
- (0 (((S) nil (a b) (a A a a)) ((S) nil (a a) (a A a a)) ((S) nil (b
b) (b A b a))))
- (1 (((A) (a a) (a a) (e)) ((A) (a a) (b a) (b))))
- (2 (((A) (b a) (b b) (b)) ((A) (b a) (b a) (e))))))
+ '((((A) (b a)) (((b b) (b) nil) ((b a) (e) nil)))
+ (((A) (a a)) (((a a) (e) nil) ((b a) (b) nil)))
+ (((S) nil) (((a b) (a A a a) ((a a))) ((a a) (a A a a) ((a a)))
((b b) (b A b a) ((b a)))))))
(parser-tables
(parser-generator-ll--generate-parsing-table
tables)))
@@ -86,42 +86,30 @@
(should
(equal
'(
- (T0 (
- ((a a) reduce (a T1 a a) 1)
- ((a b) reduce (a T1 a a) 1)
- ((b b) reduce (b T2 b a) 2)
- )
- )
- (T1 (
- ((a a) reduce (e) 4)
- ((b a) reduce (b) 3)
- )
- )
- (T2 (
- ((b a) reduce (e) 4)
- ((b b) reduce (b) 3)
- )
- )
- (a (
- ((a a) pop)
- ((a b) pop)
- ((a $) pop)
- )
- )
- (b (
- ((b a) pop)
- ((b b) pop)
- ((b $) pop)
- )
- )
- ($ (
- (($ $) accept)
- )
- )
+ (
+ ((S) nil)
+ (
+ ((a a) reduce (a T1 a a) 1)
+ ((a b) reduce (a T1 a a) 1)
+ ((b b) reduce (b T2 b a) 2)
+ )
+ )
+ (
+ ((A) (a a))
+ (
+ ((a a) reduce (e) 4)
+ ((b a) reduce (b) 3)
+ )
+ )
+ (
+ ((A) (a b))
+ (
+ ((b a) reduce (e) 4)
+ ((b b) reduce (b) 3)
+ )
+ )
)
- ))
-
- )
+ parser-tables)))
(message "Passed tests for (parser-generator-ll--generate-parsing-table)"))
