branch: externals/parser-generator
commit 84ffb4e5ea1e18b0c6ca902db370b8202c6f3e45
Author: Christian Johansson <christ...@cvj.se>
Commit: Christian Johansson <christ...@cvj.se>
f-set max index is now set depending on if all non-terminals have been
expanded or not
---
parser-generator.el | 57 +++++++++++++++++++++++++++++--------------
test/parser-generator-test.el | 17 -------------
2 files changed, 39 insertions(+), 35 deletions(-)
diff --git a/parser-generator.el b/parser-generator.el
index 6b3dcae..bb77a76 100644
--- a/parser-generator.el
+++ b/parser-generator.el
@@ -30,10 +30,18 @@
nil
"Generated F-sets for grammar.")
+(defvar parser-generator--f-sets-max-index
+ nil
+ "Max index for generated F-sets for grammar.")
+
(defvar parser-generator--f-free-sets
nil
"Generated e-free F-sets for grammar.")
+(defvar parser-generator--f-free-sets-max-index
+ nil
+ "Max index for generated e-free F-sets for grammar.")
+
(defvar parser-generator--look-ahead-number
nil
"Current look-ahead number used.")
@@ -588,13 +596,14 @@
parser-generator--f-free-sets)
(let ((productions (parser-generator--get-grammar-productions))
(k parser-generator--look-ahead-number))
- (let ((i-max (* 2 (length productions)))
- (disallow-set '(nil t)))
+ (let ((disallow-set '(nil t))
+ (expanded-all nil))
(dolist (disallow-e-first disallow-set)
(let ((f-sets (make-hash-table :test 'equal))
(i 0))
- (while (< i i-max)
+ (while (not expanded-all)
(parser-generator--debug (message "i = %s" i))
+ (setq expanded-all t)
(let ((f-set (make-hash-table :test 'equal)))
;; Iterate all productions, set F_i
@@ -611,7 +620,8 @@
(let ((f-p-set))
(dolist (rhs-p production-rhs)
(let ((rhs-string rhs-p))
- (let ((rhs-leading-terminals
+ (let ((rhs-leading-terminals)
+ (f-set-return
(parser-generator--f-set
rhs-string
`(
@@ -620,6 +630,10 @@
,f-sets
,disallow-e-first)
'(("" t 0)))))
+ (unless (nth 0 f-set-return)
+ (setq expanded-all nil))
+ (setq rhs-leading-terminals
+ (nth 1 f-set-return))
(parser-generator--debug
(message
"Leading %d terminals at index %s (%s) -> %s =
%s"
@@ -662,8 +676,11 @@
(puthash i f-set f-sets)
(setq i (+ i 1))))
(if disallow-e-first
- (setq parser-generator--f-free-sets f-sets)
- (setq parser-generator--f-sets f-sets)))))
+ (progn
+ (setq parser-generator--f-free-sets f-sets)
+ (setq parser-generator--f-free-sets-max-index (1- i)))
+ (setq parser-generator--f-sets f-sets)
+ (setq parser-generator--f-sets-max-index (1- i))))))
(parser-generator--debug
(message "Generated F-sets")))))
@@ -682,7 +699,8 @@
(k (nth 0 state))
(i (nth 1 state))
(f-sets (nth 2 state))
- (disallow-e-first (nth 3 state)))
+ (disallow-e-first (nth 3 state))
+ (expanded-all t))
(parser-generator--debug
(message "disallow-e-first: %s" disallow-e-first)
(message "input-tape-length: %s" input-tape-length)
@@ -706,7 +724,8 @@
(when (parser-generator--valid-e-p leading-terminals)
(setq e-first-p t))
- (parser-generator--debug (message "e-first-p: %s" e-first-p))
+ (parser-generator--debug
+ (message "e-first-p: %s" e-first-p))
;; If leading terminal is the e-identifier and we have input-tape
left, disregard it
(when (and
@@ -745,10 +764,11 @@
((equal rhs-type 'NON-TERMINAL)
(if (> i 0)
(let ((sub-terminal-sets
- (gethash rhs-element
- (gethash
- (1- i)
- f-sets))))
+ (gethash
+ rhs-element
+ (gethash
+ (1- i)
+ f-sets))))
(if sub-terminal-sets
(progn
(parser-generator--debug
@@ -782,7 +802,7 @@
(when (and
disallow-e-first
(= leading-terminals-count
0))
- (setq
alternative-all-leading-terminals-p nil)))
+ (setq
alternative-all-leading-terminals-p nil)))
(let ((sub-rhs-leading-terminals
(append
@@ -817,7 +837,9 @@
(setq leading-terminals-count k))))
(parser-generator--debug
(message "Found no subsets for %s %s" rhs-element
(1- i)))
+ (setq expanded-all nil)
(setq all-leading-terminals-p nil)))
+ (setq expanded-all nil)
(setq all-leading-terminals-p nil)))
((equal rhs-type 'E-IDENTIFIER)
@@ -843,7 +865,7 @@
(unless (listp leading-terminals)
(setq leading-terminals (list leading-terminals)))
(push leading-terminals f-set))))))
- f-set))
+ (list expanded-all f-set)))
;; Algorithm 5.5, p. 357
(defun parser-generator--first (β &optional disallow-e-first)
@@ -854,7 +876,6 @@
(error "Invalid sentential form β! %s" β))
(let ((productions (parser-generator--get-grammar-productions))
(k parser-generator--look-ahead-number))
- (let ((i-max (* 2 (length productions))))
;; Generate F-sets only once per grammar
(parser-generator--generate-f-sets)
@@ -900,8 +921,8 @@
(if (and
disallow-e-first
(= first-length 0))
- (setq symbol-f-set (gethash symbol (gethash (1-
i-max) parser-generator--f-free-sets)))
- (setq symbol-f-set (gethash symbol (gethash (1-
i-max) parser-generator--f-sets))))
+ (setq symbol-f-set (gethash symbol (gethash
parser-generator--f-free-sets-max-index parser-generator--f-free-sets)))
+ (setq symbol-f-set (gethash symbol (gethash
parser-generator--f-sets-max-index parser-generator--f-sets))))
(parser-generator--debug
(message "symbol-f-set: %s" symbol-f-set))
(if (not symbol-f-set)
@@ -935,7 +956,7 @@
(push first first-list))))))
(setq first-list (sort first-list 'parser-generator--sort-list))
- first-list))))
+ first-list)))
;; Definition at p. 343
(defun parser-generator--follow (β)
diff --git a/test/parser-generator-test.el b/test/parser-generator-test.el
index d9b6ba1..aa42d97 100644
--- a/test/parser-generator-test.el
+++ b/test/parser-generator-test.el
@@ -148,7 +148,6 @@
(parser-generator-set-grammar '((S) (a) ((S a)) S))
(parser-generator-set-look-ahead-number 1)
(parser-generator-process-grammar)
-
(should
(equal
'((a))
@@ -158,7 +157,6 @@
(parser-generator-set-grammar '((S) (a) ((S a)) S))
(parser-generator-set-look-ahead-number 1)
(parser-generator-process-grammar)
-
(should
(equal
'((a))
@@ -168,7 +166,6 @@
(parser-generator-set-grammar '((S) (a) ((S a)) S))
(parser-generator-set-look-ahead-number 2)
(parser-generator-process-grammar)
-
(should
(equal
'((a a))
@@ -178,7 +175,6 @@
(parser-generator-set-grammar '((S) (a) ((S a)) S))
(parser-generator-set-look-ahead-number 2)
(parser-generator-process-grammar)
-
(should
(equal
'((a))
@@ -188,7 +184,6 @@
(parser-generator-set-grammar '((S) ("a" "b" "c") ((S ("a" "b" "c"))) S))
(parser-generator-set-look-ahead-number 2)
(parser-generator-process-grammar)
-
(should
(equal
'(("a" "b"))
@@ -198,7 +193,6 @@
(parser-generator-set-grammar '((S) ("a" b "c") ((S ("a" b "c"))) S))
(parser-generator-set-look-ahead-number 3)
(parser-generator-process-grammar)
-
(should
(equal
'(("a" b "c"))
@@ -208,7 +202,6 @@
(parser-generator-set-grammar '((S A) (b) ((S A) (A b)) S))
(parser-generator-set-look-ahead-number 2)
(parser-generator-process-grammar)
-
(should
(equal
'((b))
@@ -218,7 +211,6 @@
(parser-generator-set-grammar '((S A) ("a" "b") ((S A) (A ("b" "a"))) S))
(parser-generator-set-look-ahead-number 2)
(parser-generator-process-grammar)
-
(should
(equal
'(("b" "a"))
@@ -228,7 +220,6 @@
(parser-generator-set-grammar '((S A) ("a" "b" "c" "d") ((S A) (A ("b" "a"
"c" "d"))) S))
(parser-generator-set-look-ahead-number 3)
(parser-generator-process-grammar)
-
(should
(equal
'(("b" "a" "c"))
@@ -238,7 +229,6 @@
(parser-generator-set-grammar '((S A B) ("c" "d") ((S A) (A B) (B "c" "d"))
S))
(parser-generator-set-look-ahead-number 1)
(parser-generator-process-grammar)
-
(should
(equal
'(("c") ("d"))
@@ -248,7 +238,6 @@
(parser-generator-set-grammar '((S A B) (a c d f) ((S (A a)) (A B) (B (c f)
d)) S))
(parser-generator-set-look-ahead-number 2)
(parser-generator-process-grammar)
-
(should
(equal
'((c f) (d a))
@@ -258,7 +247,6 @@
(parser-generator-set-grammar '((S A B) ("a" "c" "d" "m") ((S A) (A (B "a"
"m")) (B "c" "d")) S))
(parser-generator-set-look-ahead-number 3)
(parser-generator-process-grammar)
-
(should
(equal
'(("c" "a" "m") ("d" "a" "m"))
@@ -268,7 +256,6 @@
(parser-generator-set-grammar '((S A B C) (a b c) ((S (A B)) (A (B a) e) (B
(C b) C) (C c e)) S))
(parser-generator-set-look-ahead-number 1)
(parser-generator-process-grammar)
-
(should
(equal
'((a) (b) (c) (e))
@@ -279,7 +266,6 @@
(parser-generator-set-grammar '((S A B C) (a b c) ((S (A B)) (A (B a) e) (B
(C b) C) (C c e)) S))
(parser-generator-set-look-ahead-number 2)
(parser-generator-process-grammar)
-
(should
(equal
'((a b) (a c) (a) (b a) (b) (c a) (c) (c b) (e))
@@ -289,7 +275,6 @@
(parser-generator-set-grammar '((S A B C) (a b c) ((S (A B)) (A (B a) e) (B
(C b) C) (C c e)) S))
(parser-generator-set-look-ahead-number 3)
(parser-generator-process-grammar)
-
(should
(equal
'((a) (a b) (a c) (a c b) (b a) (b a b) (b a c) (b) (c a) (c a b) (c a c)
(c b) (c) (c b a) (e))
@@ -313,8 +298,6 @@
'((a) (e))
(parser-generator--first 'S)))
(message "Passed first 5 with complex grammar with starting e-identifier
variant 2")
-
- ;; TODO Fix i-max so it automatically is the highest needed number
(parser-generator-set-grammar '((Sp S) (a b) ((Sp S) (S (S a S b) e)) Sp))
(parser-generator-set-look-ahead-number 2)
