branch: externals/parser-generator
commit 8f9e4d4537343d89432de56048c4d8afc3736aea
Author: Christian Johansson <christ...@cvj.se>
Commit: Christian Johansson <christ...@cvj.se>
Passing 2 parse examples with k=2
---
parser-generator-ll.el | 42 +++++++-----
test/parser-generator-ll-test.el | 137 ++++++++++++++++++++++++++++++++++++---
2 files changed, 153 insertions(+), 26 deletions(-)
diff --git a/parser-generator-ll.el b/parser-generator-ll.el
index 19ff1790fd..3cd5a1825f 100644
--- a/parser-generator-ll.el
+++ b/parser-generator-ll.el
@@ -77,8 +77,15 @@
(list
(parser-generator--get-grammar-start))
(list
- parser-generator--eof-identifier))))
- (output))
+ parser-generator--eof-identifier))
+ parser-generator--eof-identifier))
+ (output)
+ (eof-look-ahead
+ (parser-generator--generate-list-of-symbol
+ parser-generator--look-ahead-number
+ parser-generator--eof-identifier))
+ (e-reduction
+ (list parser-generator--e-identifier)))
(parser-generator-lex-analyzer--reset)
(while (not accept)
(let* ((state (car stack))
@@ -89,8 +96,10 @@
(look-ahead-list
(parser-generator-lex-analyzer--peek-next-look-ahead))
(look-ahead))
- (message "\nstate: %S" state)
- (message "\nstate-action-table: %S" state-action-table)
+ (message "\nstack: %S" stack)
+ (message "output: %S" output)
+ (message "state: %S" state)
+ (message "state-action-table: %S" state-action-table)
(unless state-action-table
(signal
@@ -103,12 +112,12 @@
(if look-ahead-list
(progn
(message "look-ahead-list: %S" look-ahead-list)
- (setq
- look-ahead
- (list (car (car look-ahead-list)))))
+ (dolist (look-ahead-list-item look-ahead-list)
+ (push (car look-ahead-list-item) look-ahead))
+ (setq look-ahead (reverse look-ahead)))
(setq
look-ahead
- (list parser-generator--eof-identifier)))
+ eof-look-ahead))
(message "look-ahead: %S" look-ahead)
@@ -137,24 +146,25 @@
(setq action-type (car action)))
(message "action-type: %S" action-type)
(cond
+
((equal action-type 'pop)
- (message "pushed: %S" look-ahead-list)
- (push
- (car (parser-generator-lex-analyzer--pop-token))
- stack))
+ (message "pushed: %S" look-ahead)
+ (parser-generator-lex-analyzer--pop-token)
+ (pop stack))
((equal action-type 'reduce)
(message "reduced: %S" (nth 1 action))
- (push
- (nth 1 action)
- stack)
+ (pop stack)
+ (unless (equal (nth 1 action) e-reduction)
+ (dolist (reduce-item (reverse (nth 1 action)))
+ (push reduce-item stack)))
(push
(nth 2 action)
output))
((equal action-type 'accept)
(setq accept t))))))
- output))
+ (reverse output)))
;;; Algorithms
diff --git a/test/parser-generator-ll-test.el b/test/parser-generator-ll-test.el
index 03d012f2e0..0ad363b268 100644
--- a/test/parser-generator-ll-test.el
+++ b/test/parser-generator-ll-test.el
@@ -279,25 +279,63 @@
(parser-generator-set-eof-identifier '$)
(parser-generator-set-e-identifier 'e)
- (parser-generator-set-look-ahead-number 1)
+ (parser-generator-set-look-ahead-number 2)
(parser-generator-set-grammar
'(
(S A)
(a b)
(
- (S (a A S) b)
- (A a (b S a))
+ (S (a A a a) (b A b a))
+ (A b e)
+ )
+ S
+ )
+ )
+ (parser-generator-process-grammar)
+ (parser-generator-ll-generate-parser-tables)
+ (setq
+ parser-generator-lex-analyzer--function
+ (lambda (index)
+ (let* ((string '((b 1 . 2) (b 2 . 3) (a 3 . 4)))
+ (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)))
+ (should
+ (equal
+ '(1 3) ;; Example is indexed from 1 so that is why they have '(2 4)
+ (parser-generator-ll-parse)))
+ (message "Passed example 5.16 p. 352")
+
+ (parser-generator-set-eof-identifier '$)
+ (parser-generator-set-e-identifier 'e)
+ (parser-generator-set-look-ahead-number 2)
+ (parser-generator-set-grammar
+ '(
+ (S A)
+ (a b)
+ (
+ (S e (a b A))
+ (A (S a a) b)
)
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)))
+ (let* ((string '((a 1 . 2) (b 2 . 3) (a 3 . 4) (a 4 . 5)))
(string-length (length string))
(max-index index)
(tokens))
@@ -314,14 +352,93 @@
(parser-generator-ll-parse)
(should
(equal
- '(1 4 2 3 2)
+ '(1 2 0) ;; Example is indexed from 1 so that is why they have '(2 3 1)
(parser-generator-ll-parse)))
- ;; TODO Test example 5.5 p. 340
+ (message "Passed example 5.17 p. 355")
+ (parser-generator-set-eof-identifier '$)
+ (parser-generator-set-e-identifier 'e)
+ (parser-generator-set-look-ahead-number 1)
+ (parser-generator-set-grammar
+ '(
+ (E E2 T T2 F)
+ ("a" "(" ")" "+" "*")
+ (
+ (E (T E2))
+ (E2 ("+" T E2) e)
+ (T (F T2))
+ (T2 ("*" F T2) e)
+ (F ("(" E ")") "a")
+ )
+ E
+ )
+ )
+ (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 '(("(" 1 . 2) ("a" 2 . 3) ("*" 3 . 4) ("a" 4 . 5) (")" 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
+ '(0 3 6 0 3 7 5 2 5) ;; Example is 1-indexed '(1 4 7 1 4 8 5 8 6 3 6 3)
+ (parser-generator-ll-parse)))
+ (message "Passed example 5.12 p. 346-347")
- ;; TODO Test example 5.12 p. 346-347
- ;; TODO Test example 5.16 p. 352
- ;; TODO Test example 5.17 p. 355
+ (parser-generator-set-eof-identifier '$)
+ (parser-generator-set-e-identifier 'e)
+ (parser-generator-set-look-ahead-number 2)
+ (parser-generator-set-grammar
+ '(
+ (S A)
+ (a b)
+ (
+ (S e (a b A))
+ (A (S a a) b)
+ )
+ S
+ )
+ )
+ (parser-generator-process-grammar)
+ (parser-generator-ll-generate-parser-tables)
+ (setq
+ parser-generator-lex-analyzer--function
+ (lambda (index)
+ (let* ((string '((a 1 . 2) (b 2 . 3) (a 3 . 4) (a 4 . 5)))
+ (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 2 0) ;; Example is indexed from 1 so that is why they have '(2 3 1)
+ (parser-generator-ll-parse)))
+ ;; TODO Test example 5.5 p. 340
(message "Passed tests for (parser-generator-ll-parse)"))
