branch: externals/parser-generator
commit 99b531f035afcca6c06cc5ae863316377a3bd4a3
Author: Christian Johansson <christ...@cvj.se>
Commit: Christian Johansson <christ...@cvj.se>
Made some cpu complexity optimizations
---
parser-generator-lr-export.el | 2 ++
parser-generator-lr.el | 24 ++++++++++++++--
parser-generator.el | 61 +++++++++++++++++++++++++---------------
test/parser-generator-lr-test.el | 25 ++++++++++++++++
4 files changed, 87 insertions(+), 25 deletions(-)
diff --git a/parser-generator-lr-export.el b/parser-generator-lr-export.el
index ec4cdce..09436fe 100644
--- a/parser-generator-lr-export.el
+++ b/parser-generator-lr-export.el
@@ -11,6 +11,7 @@
(defun parser-generator-lr-export-to-elisp (namespace)
"Export parser with NAMESPACE."
+ (message "\nStarting generation of elips..\n")
;; Make sure all requisites are defined
(unless parser-generator-lr--action-tables
@@ -831,6 +832,7 @@
(buffer-substring-no-properties
(point-min)
(point-max))))
+ (message "\nCompleted generation of elips.\n")
code))
diff --git a/parser-generator-lr.el b/parser-generator-lr.el
index bb25210..a101e79 100644
--- a/parser-generator-lr.el
+++ b/parser-generator-lr.el
@@ -29,15 +29,18 @@
(defun parser-generator-lr-generate-parser-tables ()
"Generate parsing tables for grammar."
+ (message "\nStarting generation of parser-tables..\n")
(let ((table-lr-items
(parser-generator-lr--generate-goto-tables)))
(parser-generator-lr--generate-action-tables
table-lr-items)
+ (message "\nCompleted generation of parser-tables.\n")
table-lr-items))
;; Algorithm 5.11, p. 393
(defun parser-generator-lr--generate-action-tables (table-lr-items)
"Generate action-tables for lr-grammar based on TABLE-LR-ITEMS."
+ (message "\nStarting generation of action-tables..\n")
(let ((action-tables)
(states '(shift reduce error))
(added-actions (make-hash-table :test 'equal))
@@ -239,6 +242,10 @@
(parser-generator--debug
(message "%s actions %s" goto-index action-table))
(when action-table
+ (message
+ "ACTION-TABLE (%d): %s\n"
+ goto-index
+ action-table)
(push
(list
goto-index
@@ -256,11 +263,13 @@
table-index
(car (cdr (nth table-index action-tables)))
parser-generator-lr--action-tables)
- (setq table-index (1+ table-index))))))
+ (setq table-index (1+ table-index)))))
+ (message "\nCompleted generation of action-tables..\n"))
;; Algorithm 5.9, p. 389
(defun parser-generator-lr--generate-goto-tables ()
"Calculate set of valid LR(k) items for grammar and a GOTO-table."
+ (message "\nStarting generation of goto-tables..\n")
(parser-generator--debug
(message "(parser-generator-lr--generate-goto-tables)"))
(let ((lr-item-set-new-index 0)
@@ -416,6 +425,10 @@
(sort
goto-table-table
'parser-generator--sort-list))
+ (message
+ "GOTO-TABLE (%d): %s\n"
+ lr-item-set-index
+ goto-table-table)
(push
`(
,lr-item-set-index
@@ -444,6 +457,7 @@
table-lr-items
t))
(error "Inconsistent grammar!"))
+ (message "\nCompleted generation of goto-tables.\n")
table-lr-items))
;; Algorithm 5.10, p. 391
@@ -719,6 +733,7 @@
(message "γ: %s" γ))
prefix-previous)))))
+;; TODO Optimize this function 1. first and 2. sort
(defun parser-generator-lr--items-for-goto (previous-lr-item x)
"Calculate LR-items for GOTO(PREVIOUS-LR-ITEM, X)."
(let ((lr-new-item)
@@ -812,7 +827,10 @@
(let ((lr-item-suffix-rest-first
(parser-generator--first
- lr-item-suffix-rest)))
+ lr-item-suffix-rest
+ nil
+ t
+ t)))
(parser-generator--debug
(message
"lr-item-suffix-rest-first (before): %s"
@@ -875,7 +893,7 @@
lr-new-item
(sort
lr-new-item
- 'parser-generator--sort-list)))
+ 'parser-generator--sort-list))) ;; TODO Optimize this
lr-new-item))
diff --git a/parser-generator.el b/parser-generator.el
index c64ca46..282bba6 100644
--- a/parser-generator.el
+++ b/parser-generator.el
@@ -92,7 +92,8 @@
(unless (gethash element processed)
(puthash element t processed)
(push element new-elements)))
- (nreverse new-elements)))
+ (nreverse
+ new-elements)))
(defun parser-generator--generate-list-of-symbol (k symbol)
"Generate list of K number of SYMBOL."
@@ -437,6 +438,10 @@
(list
lhs
(reverse new-rhs)))
+ (message
+ "Production %s: %s"
+ production-index
+ production)
(parser-generator--debug
(message
"Production %s: %s"
@@ -510,6 +515,7 @@
(defun parser-generator-process-grammar ()
"Process grammar."
+ (message "\nStarting process of grammar..\n")
(parser-generator--clear-cache)
(unless parser-generator--look-ahead-number
(error "No look-ahead-number defined!"))
@@ -523,7 +529,8 @@
(parser-generator--valid-grammar-p
parser-generator--grammar)
(error "Invalid grammar G!"))
- (parser-generator--load-symbols))
+ (parser-generator--load-symbols)
+ (message "\nCompleted process of grammar\n"))
(defun parser-generator--sort-list (a b)
"Return non-nil if a element in A is greater than a element in B in
lexicographic order."
@@ -1418,11 +1425,13 @@
f-set)))
;; Algorithm 5.5, p. 357
-(defun parser-generator--first (β &optional disallow-e-first)
- "For sentential-form Β, calculate first terminals, optionally
DISALLOW-E-FIRST."
+(defun parser-generator--first (β &optional disallow-e-first ignore-validation
skip-sorting)
+ "For sentential-form Β, calculate first terminals, optionally
DISALLOW-E-FIRST, IGNORE-VALIDATION and SKIP-SORTING."
(unless (listp β)
(setq β (list β)))
- (unless (parser-generator--valid-sentential-form-p β)
+ (unless (or
+ ignore-validation
+ (parser-generator--valid-sentential-form-p β))
(error "Invalid sentential form β! %s" β))
(let ((k
(max
@@ -1432,7 +1441,8 @@
;; Generate F-sets only once per grammar
(parser-generator--generate-f-sets)
- (let ((first-list nil))
+ (let ((first-list nil)
+ (first-items (make-hash-table :test 'equal)))
;; Iterate each symbol in β using a PDA algorithm
(let ((input-tape β)
(input-tape-length (length β))
@@ -1534,7 +1544,7 @@
"stopped looking since non-terminal starts with
e-identifier: %s"
symbol-f-set))
(setq keep-looking nil))
-
+
;; Handle this scenario here were a non-terminal can
result in different FIRST sets
(when (>
(length symbol-f-set)
@@ -1604,21 +1614,28 @@
(setq first (reverse first))
;; (message "first-after-fill: %s" first)
)
- (parser-generator--debug
- (message
- "push to first-list: %s to %s"
- first
- first-list))
- (push
- first
- first-list))))))
-
- (setq
- first-list
- (parser-generator--distinct first-list))
- (setq
- first-list
- (sort first-list 'parser-generator--sort-list))
+ (unless
+ (gethash
+ first
+ first-items)
+ (parser-generator--debug
+ (message
+ "push to first-list: %s to %s"
+ first
+ first-list))
+ (puthash
+ first
+ t
+ first-items)
+ (push
+ first
+ first-list)))))))
+ (unless skip-sorting
+ (setq
+ first-list
+ (sort
+ first-list
+ 'parser-generator--sort-list)))
first-list)))
;; Definition at p. 343
diff --git a/test/parser-generator-lr-test.el b/test/parser-generator-lr-test.el
index 49c4071..beab25b 100644
--- a/test/parser-generator-lr-test.el
+++ b/test/parser-generator-lr-test.el
@@ -76,6 +76,31 @@
(7 (((a) reduce 1) ((b) reduce 1))))
(parser-generator--hash-to-list
parser-generator-lr--action-tables)))
+ (message "Passed Example 5.32 p. 393")
+
+ ;; Cyclical grammar
+ (parser-generator-set-grammar
+ '(
+ (Sp S A B)
+ (a b c)
+ (
+ (Sp S)
+ (S A B)
+ (A (a b A) (a B))
+ (B (c S))
+ )
+ Sp))
+ (parser-generator-set-look-ahead-number 1)
+ (parser-generator-process-grammar)
+ (let ((table-lr-items
+ (parser-generator-lr--generate-goto-tables)))
+ ;; (message "cyclical lr-items: %s" table-lr-items)
+ (parser-generator-lr--generate-action-tables
+ table-lr-items)
+ ;; (message "cyclical goto-tables: %s" parser-generator-lr--goto-tables)
+ ;; (message "cyclical action-tables: %s"
parser-generator-lr--action-tables)
+ )
+ (message "Passed cyclical grammar")
(message "Passed tests for (parser-generator-lr--generate-action-tables)"))
