emacs-elpa-diffs
[Top][All Lists]
Advanced

[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)



reply via email to

[Prev in Thread] Current Thread [Next in Thread]