[elpa] externals/parser-generator 586a38e 047/434: More work on algorithm 5.8

[ELPA Syncer]

branch: externals/parser-generator
commit 586a38e28b86925ba526fd8b711297e856c9b760
Author: Christian Johansson <christian@cvj.se>
Commit: Christian Johansson <christian@cvj.se>

    More work on algorithm 5.8
---
 parser.el | 64 ++++++++++++++++++++++++++++++++++-----------------------------
 1 file changed, 35 insertions(+), 29 deletions(-)

diff --git a/parser.el b/parser.el
index 70c3181..21af745 100644
--- a/parser.el
+++ b/parser.el
@@ -614,41 +614,47 @@
 
 ;; Algorithm 5.8, p. 386
 (defun parser--lr-items (γ)
-  "Calculate valid LR-items for the viable prefix Y."
-  (let ((lr-items)
+  "Calculate valid LR-items for the viable prefix Γ."
+  (let ((lr-items (make-hash-table :test 'equal))
         (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))
+    (let ((prefix-length (length γ)))
+
+      ;; 1
+
+      ;; Iterate all productions in grammar
+      (let ((lr-items-e))
+
+        ;; a
+        (dolist (p productions)
+          (let ((production-lhs (car p)))
+            ;; For all productions of the form S -> . α
+            (when (eq production-lhs start)
+              (let ((production-rhs (cdr p)))
+                (dolist (rhs production-rhs)
+
+                  ;; Make sure RHS is a list
+                  (unless (listp rhs)
+                    (setq rhs (list rhs)))
+
+                  ;; Add [S -> . α] to V(e)
+                  (push `(,production-lhs ,nil ,rhs) lr-items-e))))))
+
+        ;; b, c
+        ;; 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
+        ;; TODO 1.c. repeat b until no more items can be added to v-set(e)
+        (puthash 'e lr-items-e lr-items))
+
+      ;; 2
+      ;; a
+      ;; b
+      ;; c
+
+      lr-items)))
 
 
 (provide 'parser)