branch: externals/parser-generator
commit 8cc2a5b3153d7f500cb4089c55b9db704b915821
Author: Christian Johansson <christ...@cvj.se>
Commit: Christian Johansson <christ...@cvj.se>
More work on LLk parsing
---
parser-generator-ll.el | 30 +++++++++++++++++++---------
test/parser-generator-ll-test.el | 42 +++++++++++++++++++++++++++++++++++++++-
2 files changed, 62 insertions(+), 10 deletions(-)
diff --git a/parser-generator-ll.el b/parser-generator-ll.el
index d22a23fb3a..649ebd26a4 100644
--- a/parser-generator-ll.el
+++ b/parser-generator-ll.el
@@ -74,17 +74,28 @@
(stack
(list
(list
- (parser-generator--get-grammar-start)
- parser-generator--eof-identifier)))
+ (list
+ (parser-generator--get-grammar-start))
+ (list
+ parser-generator--eof-identifier))))
(output))
- (while accept
+ (parser-generator-lex-analyzer--reset)
+ (while (not accept)
(let* ((state (car stack))
(state-action-table
(gethash
state
parser-generator-ll--parsing-table))
- (look-ahead
- (parser-generator-lex-analyzer--peek-next-look-ahead)))
+ (look-ahead-list
+ (parser-generator-lex-analyzer--peek-next-look-ahead))
+ (look-ahead))
+
+ (unless state-action-table
+ (signal
+ 'error
+ (format
+ "State action table lacks actions for state: '%S'!"
+ state)))
(unless look-ahead
(signal
@@ -92,14 +103,15 @@
(format
"Reached end of input without accepting!")))
+ (setq
+ look-ahead
+ (car (car look-ahead-list)))
+
(unless (gethash look-ahead state-action-table)
(let ((possible-look-aheads))
(maphash
(lambda (k _v) (push k possible-look-aheads))
state-action-table)
- (setq
- possible-look-aheads
- (sort state-action-table 'string>))
(signal
'error
(format
@@ -115,7 +127,7 @@
(cond
((equal action-type 'pop)
(push
- (parser-generator-lex-analyzer--pop-token)
+ (car (parser-generator-lex-analyzer--pop-token))
stack))
((equal action-type 'reduce)
diff --git a/test/parser-generator-ll-test.el b/test/parser-generator-ll-test.el
index 8e0277a8e0..2f260c10d6 100644
--- a/test/parser-generator-ll-test.el
+++ b/test/parser-generator-ll-test.el
@@ -118,7 +118,6 @@
)
(message "Passed Example 5.17 p. 354")
-
(message "Passed tests for (parser-generator-ll--generate-tables)"))
(defun parser-generator-ll-test--generate-parsing-table ()
@@ -278,7 +277,48 @@
"Test `parser-generator-ll-parse'."
(message "Started tests for (parser-generator-ll-parse)")
+ (parser-generator-set-eof-identifier '$)
+ (parser-generator-set-e-identifier 'e)
+ (parser-generator-set-look-ahead-number 1)
+ (parser-generator-set-grammar
+ '(
+ (S A)
+ (a b)
+ (
+ (S (a A S) b)
+ (A a (b S a))
+ )
+ S
+ )
+ )
+ (parser-generator-process-grammar)
+ (parser-generator-ll-generate-parser-tables)
+ (message "parser-generator-ll--parsing-table: %S"
parser-generator-ll--parsing-table)
+ (setq
+ parser-generator-lex-analyzer--function
+ (lambda (index)
+ (let* ((string '((a 1 . 2) (b 2 . 3) (b 3 . 4) (a 4 . 5) (b 5 . 6)))
+ (string-length (length string))
+ (max-index index)
+ (tokens))
+ (while (and
+ (< (1- index) string-length)
+ (< (1- index) max-index))
+ (push (nth (1- index) string) tokens)
+ (setq index (1+ index)))
+ (nreverse tokens))))
+ (setq
+ parser-generator-lex-analyzer--get-function
+ (lambda (token)
+ (car token)))
+ (parser-generator-ll-parse)
+ (should
+ (equal
+ '(1 4 2 3 2)
+ (parser-generator-ll-parse)))
;; TODO Test example 5.5 p. 340
+
+
;; TODO Test example 5.12 p. 346-347
;; TODO Test example 5.16 p. 352
;; TODO Test example 5.17 p. 355
