[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[elpa] externals/parser-generator f8f5fe2 046/434: Started on function t
From: |
ELPA Syncer |
Subject: |
[elpa] externals/parser-generator f8f5fe2 046/434: Started on function to calculate lk-items for a viable prefix |
Date: |
Mon, 29 Nov 2021 15:59:05 -0500 (EST) |
branch: externals/parser-generator
commit f8f5fe218afa34008fd9890cf2d6238a18f1995d
Author: Christian Johansson <christian@cvj.se>
Commit: Christian Johansson <christian@cvj.se>
Started on function to calculate lk-items for a viable prefix
---
parser.el | 47 +++++++++++++++++++++++++++++++++++++++--------
1 file changed, 39 insertions(+), 8 deletions(-)
diff --git a/parser.el b/parser.el
index 3b117b4..70c3181 100644
--- a/parser.el
+++ b/parser.el
@@ -466,7 +466,7 @@
;; Algorithm 5.5, p. 357
(defun parser--first (β &optional disallow-e-first)
- "For sentential-form Β, in grammar, calculate first k terminals, optionally
DISALLOW-E-FIRST."
+ "For sentential-form Β, calculate first terminals, optionally
DISALLOW-E-FIRST."
(unless (listp β)
(setq β (list β)))
(unless (parser--valid-sentential-form-p β)
@@ -565,7 +565,7 @@
(setq first-list (sort first-list 'parser--sort-list))
first-list))))
-;; Definition p. 343
+;; Definition at p. 343
(defun parser--follow (β)
"Calculate follow-set of Β. FOLLOW(β) = w, w is the set {w | S =>* αβγ and
w is in FIRST(γ)}."
;; Make sure argument is a list
@@ -612,12 +612,43 @@
(setq follow-set (parser--distinct follow-set)))
follow-set))
-(defun parser--v-set (y)
- "Calculate valid LRk-sets for the viable-prefix Y in grammar G with
look-ahead K."
- (let ((v-set))
- (unless (parser--valid-grammar-p G)
- (error "Invalid grammar G!"))
- v-set))
+;; Algorithm 5.8, p. 386
+(defun parser--lr-items (γ)
+ "Calculate valid LR-items for the viable prefix Y."
+ (let ((lr-items)
+ (productions (parser--get-grammar-productions))
+ (start (parser--get-grammar-start)))
+ (unless (listp γ)
+ (setq γ (list γ)))
+ (unless (parser--valid-sentential-form-p γ)
+ (error "Invalid sentential form γ!"))
+ (let ((prefix-length (length γ))
+ (stack '((0 '1a))))
+ (while stack
+ (let ((stack-item (pop stack)))
+ (let ((index (nth 0 stack-item))
+ (state (nth 1 stack-item)))
+ (cond
+ ((eq state '1a)
+ ;; TODO 1.a. iterate every production who has the LHS = S, add
[S -> . a] to v-set(e)
+ ;; Iterate all productions in grammar
+ (let ()
+ (dolist (p productions)
+ (let ((production-lhs (car p)))
+ (when (eq production-lhs start)
+ )))))
+ ((eq state '1b)
+ ;; TODO 1.b. iterate every item in v-set(e), if [A -> . Bα, u]
is an item and B -> β is in P, then foreach x in FIRST(αu) add [B -> . β, x] to
v-set(e), provided it is not already there
+ )
+
+ ((eq state '1c)
+ ;; TODO 1.c. repeat b until no more items can be added to
v-set(e)
+ )
+ ((eq state '2a))
+ ((eq state '2b))
+ ((eq state '2c))
+ (t (error "Invalid state!")))))))
+ lr-items))
(provide 'parser)
- [elpa] externals/parser-generator ca85ef4 068/434: Created TODO items, (continued)
- [elpa] externals/parser-generator ca85ef4 068/434: Created TODO items, ELPA Syncer, 2021/11/29
- [elpa] externals/parser-generator b73c4ed 072/434: Made e-symbol customizable, ELPA Syncer, 2021/11/29
- [elpa] externals/parser-generator 55bf9a9 073/434: Removed references to 'e, ELPA Syncer, 2021/11/29
- [elpa] externals/parser-generator 01df803 051/434: Improved documentation, ELPA Syncer, 2021/11/29
- [elpa] externals/parser-generator 3e1f2b6 058/434: Passed first for calculating valid LR-sets for viable prefix γ, ELPA Syncer, 2021/11/29
- [elpa] externals/parser-generator 51cab75 061/434: More debugging, ELPA Syncer, 2021/11/29
- [elpa] externals/parser-generator f940be9 033/434: Added list of functions and usage examples, ELPA Syncer, 2021/11/29
- [elpa] externals/parser-generator b8d6476 038/434: Setting look-ahead-number clears cache storage, ELPA Syncer, 2021/11/29
- [elpa] externals/parser-generator 2829d36 039/434: More work on FOLLOW, ELPA Syncer, 2021/11/29
- [elpa] externals/parser-generator 0f8b422 043/434: Added another unit test for follow function, ELPA Syncer, 2021/11/29
- [elpa] externals/parser-generator f8f5fe2 046/434: Started on function to calculate lk-items for a viable prefix,
ELPA Syncer <=
- [elpa] externals/parser-generator 8d0a93e 053/434: More work on algorithm, ELPA Syncer, 2021/11/29
- [elpa] externals/parser-generator 6d2e231 059/434: Added two more failing valid LR-set calculation tests, ELPA Syncer, 2021/11/29
- [elpa] externals/parser-generator 15dc472 067/434: Added TODO items, ELPA Syncer, 2021/11/29
- [elpa] externals/parser-generator 44eb5a3 062/434: Passing unit test for V(e) and V(S), ELPA Syncer, 2021/11/29
- [elpa] externals/parser-generator a7d1cc0 070/434: Updated README, ELPA Syncer, 2021/11/29
- [elpa] externals/parser-generator 3373881 085/434: More work on GOTO-table generation, ELPA Syncer, 2021/11/29
- [elpa] externals/parser-generator 5957fad 076/434: First implementation of generating LR-items for grammar, ELPA Syncer, 2021/11/29
- [elpa] externals/parser-generator 7689ec5 086/434: More work, ELPA Syncer, 2021/11/29
- [elpa] externals/parser-generator c992a54 093/434: Added info in README.md about LR-items, ELPA Syncer, 2021/11/29
- [elpa] externals/parser-generator 4c75f65 101/434: Added TODO items, ELPA Syncer, 2021/11/29