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

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

[elpa] externals/parser-generator 42d92f1 014/434: More refactoring


From: ELPA Syncer
Subject: [elpa] externals/parser-generator 42d92f1 014/434: More refactoring
Date: Mon, 29 Nov 2021 15:58:58 -0500 (EST)

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

    More refactoring
---
 parser.el | 80 ++++++++++++++++++++++++++++++++++++++++++---------------------
 1 file changed, 54 insertions(+), 26 deletions(-)

diff --git a/parser.el b/parser.el
index 5c1092a..102138f 100644
--- a/parser.el
+++ b/parser.el
@@ -43,10 +43,6 @@
 ;; Helper Functions
 
 
-(defun parser--empty-p (symbol)
-  "Return whether SYMBOL is empty identifier or not."
-  (eq symbol 'e))
-
 (defun parser--distinct (elements)
   "Return distinct of ELEMENTS."
   (let ((processed (make-hash-table :test 'equal))
@@ -100,19 +96,6 @@
     (dolist (non-terminal non-terminals)
       (puthash non-terminal t parser--table-non-terminal-p))))
 
-(defun parser--non-terminal-p (symbol)
-  "Return whether SYMBOL is a non-terminal in grammar or not."
-  (unless parser--table-non-terminal-p
-    (error "Table for non-terminals is undefined!"))
-  (if (gethash symbol parser--table-non-terminal-p)
-      t
-    nil))
-
-(defun parser--sentential-form-p (symbols)
-  "Return whether SYMBOLS is a valid sentential form in grammar or not."
-  ;; TODO Implement this
-  )
-
 (defun parser--set-grammar (G k)
   "Set grammar G with look-ahead number K."
   (unless (parser--valid-grammar-p G)
@@ -123,13 +106,9 @@
   (setq parser--look-ahead-number k)
   (parser--load-symbols))
 
-(defun parser--terminal-p (symbol)
-  "Return whether SYMBOL is a terminal in grammar or not."
-  (unless parser--table-terminal-p
-    (error "Table for terminals is undefined!"))
-  (if (gethash symbol parser--table-terminal-p)
-      t
-    nil))
+(defun parser--valid-empty-p (symbol)
+  "Return whether SYMBOL is empty identifier or not."
+  (eq symbol "e"))
 
 (defun parser--valid-grammar-p (G)
   "Return if grammar G is valid or not.  Grammar should contain list with 4 
elements: non-terminals (N), terminals (T), productions (P), start (S) where N, 
T and P are lists and S is a symbol."
@@ -146,7 +125,7 @@
             (not (listp (nth 0 G)))
             (not (listp (nth 1 G)))
             (not (listp (nth 2 G)))
-            (not (symbolp (nth 3 G)))))
+            (not (stringp (nth 3 G)))))
       (setq valid-p nil))
     valid-p))
 
@@ -156,6 +135,39 @@
    (integerp k)
    (>= k 0)))
 
+(defun parser--valid-non-terminal-p (symbol)
+  "Return whether SYMBOL is a non-terminal in grammar or not."
+  (unless parser--table-non-terminal-p
+    (error "Table for non-terminals is undefined!"))
+  (if (gethash symbol parser--table-non-terminal-p)
+      t
+    nil))
+
+(defun parser--valid-sentential-form-p (symbols)
+  "Return whether SYMBOLS is a valid sentential form in grammar or not."
+  (let ((is-valid t))
+    (let ((symbols-string (symbol-name symbols)))
+      (let ((symbols-length (length symbols-string))
+            (symbol-index 0))
+        (while (and
+                is-valid
+                (< symbol-index symbols-length))
+          (let ((symbol-string (substring symbols-string symbol-index (1+ 
symbol-index))))
+            (unless (or
+                     (parser--valid-empty-p symbol-string)
+                     (parser--valid-non-terminal-p symbol-string)
+                     (parser--valid-terminal-p symbol-string))
+              (setq is-valid nil))))))
+    is-valid))
+
+(defun parser--valid-terminal-p (symbol)
+  "Return whether SYMBOL is a terminal in grammar or not."
+  (unless parser--table-terminal-p
+    (error "Table for terminals is undefined!"))
+  (if (gethash symbol parser--table-terminal-p)
+      t
+    nil))
+
 
 ;; Main Algorithms
 
@@ -165,6 +177,7 @@
   "For sentential string Α, Calculate e-free-first k terminals in grammar."
   (parser--first α t))
 
+;; p. 358
 (defun parser--f-set (input-tape state stack)
   "A deterministic push-down transducer (DPDT) for building F-sets from 
INPUT-TAPE, STATE and STACK."
   (parser--debug
@@ -293,6 +306,7 @@
     f-set))
 
 ;; Algorithm 5.5, p. 357
+;; TODO Make this work on strings instead of symbols
 (defun parser--first (β &optional disallow-e-first)
   "For sentential-form Β, in grammar, calculate first k terminals, optionally 
DISALLOW-E-FIRST."
   (unless (parser--sentential-form-p β)
@@ -340,7 +354,21 @@
           (puthash i f-set f-sets)
           (setq i (+ i 1))))
 
-      ;; TODO Iterate each symbol in β
+      ;; TODO Iterate each symbol in β using a PDA algorithm
+      (let ((symbol-length (length β))
+            (symbol-index 0)
+            (first-string "")
+            (first-length 0))
+        (while (and
+                (< symbol-index symbol-length)
+                (< first-length k))
+          (let ((symbol-string (substring β symbol-index (1+ symbol-index))))
+            (cond
+             ((parser--valid-terminal-p symbol-string)
+              (setq first-string (concat first-string symbol-string))
+              (setq first-length (1+ first-length)))
+             ((parser--valid-non-terminal-p symbol-string)
+              ;; TODO Handle this scenario here were a non-terminal can result 
in different FIRST sets
       (sort (gethash (symbol-name production) (gethash (1- i-max) f-sets)) 
'string<))))
 
 (defun parser--v-set (y)



reply via email to

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