[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)
- [elpa] externals/parser-generator b8faa17 002/434: FIRSTk and EFFk working, (continued)
- [elpa] externals/parser-generator b8faa17 002/434: FIRSTk and EFFk working, ELPA Syncer, 2021/11/29
- [elpa] externals/parser-generator ee0a623 003/434: Added TRAVIS and LICENSE, ELPA Syncer, 2021/11/29
- [elpa] externals/parser-generator f5bfa40 004/434: Fixed typo in README, ELPA Syncer, 2021/11/29
- [elpa] externals/parser-generator 58798c8 010/434: Starting on calculation of valid LK-sets for a valid grammar prefix, ELPA Syncer, 2021/11/29
- [elpa] externals/parser-generator f9c8348 008/434: Updated Travis and Makefil rule name, ELPA Syncer, 2021/11/29
- [elpa] externals/parser-generator 5f65cfc 015/434: More refactoring, using lists instead of string as grammar data type, ELPA Syncer, 2021/11/29
- [elpa] externals/parser-generator f2791c1 022/434: Passed unit test 3 intermediate grammar, ELPA Syncer, 2021/11/29
- [elpa] externals/parser-generator 5d9b98c 011/434: Added functions to validate G and k and tests, ELPA Syncer, 2021/11/29
- [elpa] externals/parser-generator 356720c 030/434: Passing all unit tests using new data structure, ELPA Syncer, 2021/11/29
- [elpa] externals/parser-generator e4fd795 007/434: Added compilation to test, ELPA Syncer, 2021/11/29
- [elpa] externals/parser-generator 42d92f1 014/434: More refactoring,
ELPA Syncer <=
- [elpa] externals/parser-generator f648b52 020/434: Passing first unit test for FIRST after new data-structure refactor, ELPA Syncer, 2021/11/29
- [elpa] externals/parser-generator a4bbb2f 026/434: Using PDA algorithm for FIRST when β is above 1 symbol, ELPA Syncer, 2021/11/29
- [elpa] externals/parser-generator e02d5d7 049/434: More work on calculating valid LR-items, ELPA Syncer, 2021/11/29
- [elpa] externals/parser-generator 0465b58 045/434: Improved commenting, ELPA Syncer, 2021/11/29
- [elpa] externals/parser-generator 85dde51 009/434: Added License and Travis build logos, ELPA Syncer, 2021/11/29
- [elpa] externals/parser-generator 7bc3b70 017/434: Updated tests to use new data structure, ELPA Syncer, 2021/11/29
- [elpa] externals/parser-generator ab4b4db 021/434: Passed second FIRST test again, ELPA Syncer, 2021/11/29
- [elpa] externals/parser-generator 80cf73d 019/434: Passing tests for valid-grammar syntax, ELPA Syncer, 2021/11/29
- [elpa] externals/parser-generator bbbdea3 034/434: More improvement of documentation, ELPA Syncer, 2021/11/29
- [elpa] externals/parser-generator 9d0d9e5 027/434: Various debugging, ELPA Syncer, 2021/11/29