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

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

[elpa] externals/parser-generator 5957fad 076/434: First implementation


From: ELPA Syncer
Subject: [elpa] externals/parser-generator 5957fad 076/434: First implementation of generating LR-items for grammar
Date: Mon, 29 Nov 2021 15:59:12 -0500 (EST)

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

    First implementation of generating LR-items for grammar
---
 parser.el           | 70 ++++++++++++++++++++++++++++++++++++-----------------
 test/parser-test.el | 14 ++++++++++-
 2 files changed, 61 insertions(+), 23 deletions(-)

diff --git a/parser.el b/parser.el
index 97e64d0..7dab2dc 100644
--- a/parser.el
+++ b/parser.el
@@ -653,32 +653,58 @@
     follow-set))
 
 ;; Algorithm 5.9, p. 389
-(defun parser-test--lr-items-for-grammar ()
+(defun parser--lr-items-for-grammar ()
   "Calculate set of valid LR(k) items for grammar."
-  (let ((S)
-        (marked-sets (make-hash-table :test 'equal))
+  (let ((prefixes)
+        (marked-prefixes (make-hash-table :test 'equal))
+        (lr-items)
         (symbols (append (parser--get-grammar-non-terminals) 
(parser--get-grammar-terminals))))
+
     (let ((e-set (parser--lr-items-for-prefix parser--e-identifier)))
       ;;(1) Place V(e) in S. The set V(e) is initially unmarked.
-      (push `(,e-set nil) S))
-    (let ((found-unmarked t))
-
-      ;; (3) Repeat step (2) until all sets of items in S are marked.
-      (while found-unmarked
-        (setq found-unmarked nil)
-        (dolist (set S)
-          ;; (2) If a set of items a in S is unmarked
-          (unless (car (cdr set))
-            ;; TODO (2) Mark a by computing for each X in N u E, GOTO (a, X). 
(Algorithm 5.8 can be used here.)
-            ;; If a' = GOTO(a, X) is nonempty and is not already in S,
-            ;; then add a' to S as an unmarked set of items
-            (dolist (symbol symbols)
-              
-              )
-
-            (setq found-unmarked t)))))
-
-    S))
+      (push e-set lr-items)
+      (push `(,parser--e-identifier) prefixes))
+
+    ;; (3) Repeat step (2) until all sets of items in S are marked.
+    (let ((prefix))
+
+      ;; (2) If a set of items a in S is unmarked
+      (while prefixes
+
+        ;; (2) Mark a by computing for each X in N u E, GOTO (a, X). 
(Algorithm 5.8 can be used here.)
+        (setq prefix (pop prefixes))
+
+        ;; e-identifier is converted to nil prefix
+        (when (and
+               (= (length prefix) 1)
+               (parser--valid-e-p (car prefix)))
+          (setq prefix nil))
+
+        (message "prefix: %s" prefix)
+
+        (puthash prefix t marked-prefixes)
+
+        ;; V(X1,...,Xi) = GOTO(V(X1,...,Xi-1), Xi)
+        (dolist (symbol symbols)
+          (let ((alternative-prefix (append prefix (list symbol))))
+            (message "alternative-prefix: %s" alternative-prefix)
+
+            ;; and is not already in S
+            (unless (gethash alternative-prefix marked-prefixes)
+              (let ((prefix-lr-items (parser--lr-items-for-prefix 
alternative-prefix)))
+
+                (message "V%s = %s" alternative-prefix prefix-lr-items)
+
+                ;; If a' = GOTO(a, X) is nonempty
+                (when prefix-lr-items
+
+                  (message "Added to stack.")
+
+                  ;; then add a' to S as an unmarked set of items
+                  (push alternative-prefix prefixes)
+                  (push prefix-lr-items lr-items))))))))
+
+    lr-items))
 
 ;; Algorithm 5.8, p. 386
 (defun parser--lr-items-for-prefix (γ)
diff --git a/test/parser-test.el b/test/parser-test.el
index 711d48a..9ca16d3 100644
--- a/test/parser-test.el
+++ b/test/parser-test.el
@@ -227,7 +227,19 @@
   "Test `parser--lr-items-for-grammar'."
   (message "Starting tests for (parser--lr-items-for-grammar)")
 
-  ;; TODO Do tests here
+  ;; Example 5.30, p. 389
+  (parser--set-grammar '((Sp S) (a b) ((Sp S) (S (S a S b)) (S e)) Sp))
+  (parser--set-look-ahead-number 1)
+
+  (should
+   (equal
+    '((S nil (S a S b) (a))
+      (S nil (S a S b) (e))
+      (S nil nil (a))
+      (S nil nil (e))
+      (Sp nil (S) (e)))
+    (parser--lr-items-for-grammar)))
+  (message "Passed LR-items for example 5.30")
 
   (message "Passed tests for (parser--lr-items-for-grammar)"))
 



reply via email to

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