[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[elpa] externals/parser-generator 29bad0440f 09/82: More work on LL tabl
From: |
Christian Johansson |
Subject: |
[elpa] externals/parser-generator 29bad0440f 09/82: More work on LL table generation |
Date: |
Thu, 12 May 2022 13:28:13 -0400 (EDT) |
branch: externals/parser-generator
commit 29bad0440fa1eae5ce9a35ff42b4ad7d3b618cc2
Author: Christian Johansson <christian@cvj.se>
Commit: Christian Johansson <christian@cvj.se>
More work on LL table generation
---
parser-generator-ll.el | 82 ++++++++++++++++++++++++++++++++++++++------------
1 file changed, 62 insertions(+), 20 deletions(-)
diff --git a/parser-generator-ll.el b/parser-generator-ll.el
index 365c03f12f..9cba14f4fa 100644
--- a/parser-generator-ll.el
+++ b/parser-generator-ll.el
@@ -73,13 +73,16 @@
(nth 0 stack-item))
(production-rhs
(nth 1 stack-item))
- (production-number (nth 2 stack-item))
- (dot-look-ahead (nth 3 stack-item))
+ (production-number
+ (nth 2 stack-item))
+ (dot-look-ahead
+ (nth 3 stack-item))
(first-rhs
(parser-generator--first production-rhs nil t t))
(first-dot-look-ahead
(parser-generator--first dot-look-ahead nil t t))
(look-aheads))
+
(cond
((and first-rhs
(not first-dot-look-ahead))
@@ -107,30 +110,66 @@
production
dot-look-ahead)))
+ ;; For each non terminal in the right-hand side
+ ;; push to stack with a local look ahead
+ (let ((sub-symbol-index 0))
+ (dolist (sub-symbol production-rhs)
+ (when (parser-generator--valid-non-terminal-p
+ sub-symbol)
+ (let ((local-look-ahead
+ (nthcdr (1+ sub-symbol-index) production-rhs))
+ (sub-symbol-rhss
+ (parser-generator--get-grammar-rhs
+ sub-symbol)))
+ (dolist (sub-symbol-rhs sub-symbol-rhss)
+ (let* ((sub-symbol-production
+ (list (list sub-symbol) sub-symbol-rhs))
+ (sub-symbol-production-number
+ (parser-generator--get-grammar-production-number
+ sub-symbol-production)))
+ (push
+ (list
+ (list sub-symbol)
+ sub-symbol-rhs
+ sub-symbol-production-number
+ local-look-ahead)
+ stack))))))
+ (setq
+ sub-symbol-index
+ (1+ sub-symbol-index)))
+
+ ;; Add all distinct combinations of LHS, local-look-ahead and
look-ahead
+ ;; to tables list here
(when look-aheads
- (let ((table))
- (dolist (look-ahead look-aheads)
- (push
- (list
- production-lhs
- production-rhs
- production-number
- look-ahead
- dot-look-ahead)
- table))
- (let ((table-hash-key
- (format "%S" table)))
- (unless
+ (dolist (look-ahead look-aheads)
+ (let ((table
+ (list
+ production-lhs
+ production-rhs
+ production-number
+ look-ahead
+ dot-look-ahead))
+ (table-hash-key
+ (format
+ "%S"
+ (list dot-look-ahead production-lhs look-ahead))))
+ (if
(gethash
table-hash-key
distinct-table-p)
+ (message
+ "\nConflicting LL-items: %S vs %S"
+ table
+ (gethash
+ table-hash-key
+ distinct-table-p))
+ (push
+ table
+ tables)
(puthash
table-hash-key
table
- distinct-table-p)
- (push
- table
- tables)))))
+ distinct-table-p)))))
(parser-generator--debug
(message "\nproduction-lhs: %S" production-lhs)
@@ -140,7 +179,10 @@
(message "first-rhs: %S" first-rhs)
(message "first-dot-look-ahead: %S" first-dot-look-ahead)
(message "look-aheads: %S" look-aheads))))
- (nreverse tables)))
+
+ (sort
+ tables
+ 'parser-generator--sort-list)))
;; TODO
- [elpa] externals/parser-generator updated (bf7229332f -> db91a5f203), Christian Johansson, 2022/05/12
- [elpa] externals/parser-generator 8c467b1bb1 07/82: Added another test for merge max terminal sets, Christian Johansson, 2022/05/12
- [elpa] externals/parser-generator 1199586dad 11/82: More work on generating LL item, Christian Johansson, 2022/05/12
- [elpa] externals/parser-generator 89105668e8 01/82: Started on LL(k) implementation, Christian Johansson, 2022/05/12
- [elpa] externals/parser-generator 878b2900f2 05/82: Improved calculation of merged max terminals when one of the set is undefined, Christian Johansson, 2022/05/12
- [elpa] externals/parser-generator d397a1d48e 12/82: Improved variable naming, Christian Johansson, 2022/05/12
- [elpa] externals/parser-generator b09b22c0be 13/82: Passing test for LL(k) table Example 5.15, Christian Johansson, 2022/05/12
- [elpa] externals/parser-generator 7c10be74b8 06/82: Added TODO items, Christian Johansson, 2022/05/12
- [elpa] externals/parser-generator 1d1e4e4bf8 03/82: More work on LL(k) parser, Christian Johansson, 2022/05/12
- [elpa] externals/parser-generator 4cb0a0b941 08/82: More work on LL table generation, Christian Johansson, 2022/05/12
- [elpa] externals/parser-generator 29bad0440f 09/82: More work on LL table generation,
Christian Johansson <=
- [elpa] externals/parser-generator 87435188dd 15/82: Added function to set EOF-identifier, Christian Johansson, 2022/05/12
- [elpa] externals/parser-generator bab123bdda 17/82: Added reference to PHP 8.1, Christian Johansson, 2022/05/12
- [elpa] externals/parser-generator a2a629c16d 18/82: More work on data structure for LL-tables, Christian Johansson, 2022/05/12
- [elpa] externals/parser-generator 542a50d9c1 20/82: Remove usage of a hash-table, Christian Johansson, 2022/05/12
- [elpa] externals/parser-generator 221446d647 24/82: Started implementation of LLk validation, Christian Johansson, 2022/05/12
- [elpa] externals/parser-generator ab4ce4d668 25/82: Tests for validating LLk grammar passing, Christian Johansson, 2022/05/12
- [elpa] externals/parser-generator 04eb4d066c 27/82: Started on test for Example 5.17, Christian Johansson, 2022/05/12
- [elpa] externals/parser-generator 5c0bcd5f9a 36/82: Passing test for LL-table generation example 5.17, Christian Johansson, 2022/05/12
- [elpa] externals/parser-generator 1290048b84 39/82: Improved documentation, Christian Johansson, 2022/05/12
- [elpa] externals/parser-generator 57c6fdda2f 43/82: Passing test for generating LL-parser hash-table, Christian Johansson, 2022/05/12