[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[elpa] externals/parser-generator fe728f8ad8 23/82: Passing test for gen
From: |
Christian Johansson |
Subject: |
[elpa] externals/parser-generator fe728f8ad8 23/82: Passing test for generating LLk parser table |
Date: |
Thu, 12 May 2022 13:28:14 -0400 (EDT) |
branch: externals/parser-generator
commit fe728f8ad8e921b817098077219c6e78180d465a
Author: Christian Johansson <christian@cvj.se>
Commit: Christian Johansson <christian@cvj.se>
Passing test for generating LLk parser table
---
parser-generator-ll.el | 52 ++++++++++++++++++++++++++++++++++++----
test/parser-generator-ll-test.el | 23 ++++++++++++++++--
2 files changed, 69 insertions(+), 6 deletions(-)
diff --git a/parser-generator-ll.el b/parser-generator-ll.el
index 6c2410a2e3..96d0493ada 100644
--- a/parser-generator-ll.el
+++ b/parser-generator-ll.el
@@ -224,11 +224,58 @@
sorted-tables)))
-;; TODO
;; Algorithm 5.3 p. 351
(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))
+
+ ;; (3) M($, e) = accept
+ ;; (2) M(a, av) = pop for all v in E where |E| = k-1
+ (let ((eof-look-ahead
+ (parser-generator--generate-list-of-symbol
+ parser-generator--look-ahead-number
+ parser-generator--eof-identifier))
+ (terminal-mutations
+ (parser-generator--get-grammar-look-aheads))
+ (terminal-buffer)
+ (last-terminal))
+ (dolist (terminal-mutation terminal-mutations)
+ (if (equal terminal-mutation eof-look-ahead)
+ (push
+ (list
+ parser-generator--eof-identifier
+ (list
+ eof-look-ahead
+ 'accept))
+ parsing-table)
+ (let ((stack-item (nth 0 terminal-mutation)))
+ (when (and
+ last-terminal
+ (not (equal last-terminal stack-item)))
+ (push
+ (list
+ last-terminal
+ terminal-buffer)
+ parsing-table)
+ (setq
+ terminal-buffer
+ nil))
+
+ (push
+ (list terminal-mutation 'pop)
+ terminal-buffer)
+ (setq
+ last-terminal
+ stack-item))))
+ (when (and
+ last-terminal
+ terminal-buffer)
+ (push
+ (list
+ last-terminal
+ terminal-buffer)
+ parsing-table)))
+
(dolist (table tables)
(let* ((key (nth 0 table))
(value (nth 1 table))
@@ -284,9 +331,6 @@
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
-
parsing-table))
diff --git a/test/parser-generator-ll-test.el b/test/parser-generator-ll-test.el
index 01bbe32066..37c84fa6cb 100644
--- a/test/parser-generator-ll-test.el
+++ b/test/parser-generator-ll-test.el
@@ -104,7 +104,6 @@
tables)))
;; (message "parser-tables: %S" parser-tables)
- ;; TODO Make this pass
(should
(equal
'(
@@ -124,12 +123,32 @@
)
)
(
- ((A) (b a)) ;; T2
+ ((A) (b a));; T2
(
((b a) reduce (e) 3)
((b b) reduce (b) 2)
)
)
+ (
+ b
+ (
+ ((b b) pop)
+ ((b a) pop)
+ ((b $) pop)
+ )
+ )
+ (
+ a
+ (
+ ((a b) pop)
+ ((a a) pop)
+ ((a $) pop)
+ )
+ )
+ (
+ $
+ (($ $) accept)
+ )
)
parser-tables)))
- [elpa] externals/parser-generator 08ed55d35a 62/82: More work on k=1, (continued)
- [elpa] externals/parser-generator 08ed55d35a 62/82: More work on k=1, Christian Johansson, 2022/05/12
- [elpa] externals/parser-generator 4f85cc5616 66/82: Passes byte-compilation tests, Christian Johansson, 2022/05/12
- [elpa] externals/parser-generator 7a265c9a84 67/82: LL-tests now runs on make tests command, Christian Johansson, 2022/05/12
- [elpa] externals/parser-generator a046c8584d 73/82: Started on documentation for LL(k) and LL(1), Christian Johansson, 2022/05/12
- [elpa] externals/parser-generator f07939a440 76/82: Added example from Wikipedia and passing test, Christian Johansson, 2022/05/12
- [elpa] externals/parser-generator 03a11c4369 14/82: Started test for LL(k) parser-table generation, Christian Johansson, 2022/05/12
- [elpa] externals/parser-generator 9d6ca94d0e 02/82: More work on LL(k) parser, Christian Johansson, 2022/05/12
- [elpa] externals/parser-generator 6ce0dd9429 04/82: Improved function to calculate merge max terminal sets, Christian Johansson, 2022/05/12
- [elpa] externals/parser-generator 52734d7160 16/82: Updated TODO items, Christian Johansson, 2022/05/12
- [elpa] externals/parser-generator 7b77032f71 22/82: Parser table generation for LLk now works for productions, Christian Johansson, 2022/05/12
- [elpa] externals/parser-generator fe728f8ad8 23/82: Passing test for generating LLk parser table,
Christian Johansson <=
- [elpa] externals/parser-generator 3b9977b51b 28/82: More work on LLk test, Christian Johansson, 2022/05/12
- [elpa] externals/parser-generator f23bc217d8 30/82: More wrestling, Christian Johansson, 2022/05/12
- [elpa] externals/parser-generator 6e91a4b498 32/82: More work on helper functions, Christian Johansson, 2022/05/12
- [elpa] externals/parser-generator 80dd506b65 33/82: More work on LL-helper functions, Christian Johansson, 2022/05/12
- [elpa] externals/parser-generator e6f9ac545f 37/82: Cleanup after byte-compilation, Christian Johansson, 2022/05/12
- [elpa] externals/parser-generator cf4332ef0e 40/82: Started on LLk parsing algorithm, Christian Johansson, 2022/05/12
- [elpa] externals/parser-generator f5f7b2c82b 41/82: Added TODO items, Christian Johansson, 2022/05/12
- [elpa] externals/parser-generator 2e76c4b57e 42/82: Added TODO items, Christian Johansson, 2022/05/12
- [elpa] externals/parser-generator 8f9e4d4537 46/82: Passing 2 parse examples with k=2, Christian Johansson, 2022/05/12
- [elpa] externals/parser-generator fe0decba88 50/82: Passed one test for LLk where k=1, Christian Johansson, 2022/05/12