branch: externals/parser-generator
commit a046c8584ded8dc73567ad7b078bc048a34d3859
Author: Christian Johansson <christ...@cvj.se>
Commit: Christian Johansson <christ...@cvj.se>
Started on documentation for LL(k) and LL(1)
---
docs/Syntax-Analysis.md | 4 +-
docs/Syntax-Analysis/LL1.md | 110 ++++++++++++++++++++++++++++++++++++++
docs/Syntax-Analysis/LLk.md | 111 +++++++++++++++++++++++++++++++++++++++
parser-generator.el | 2 +-
test/parser-generator-ll-test.el | 49 +++++++++++++++--
5 files changed, 269 insertions(+), 7 deletions(-)
diff --git a/docs/Syntax-Analysis.md b/docs/Syntax-Analysis.md
index daaa363800..c391d346f0 100644
--- a/docs/Syntax-Analysis.md
+++ b/docs/Syntax-Analysis.md
@@ -11,8 +11,8 @@ We use push down transducer (PDT) based algorithms.
## Without Backtracking
-* LL(1) *WIP*
-* LL(k) *WIP*
+* [LL(1)](Syntax-Analysis/LL1.md)
+* [LL(k)](Syntax-Analysis/LLk.md)
* [LR(k)](Syntax-Analysis/LRk.md)
* [LR(0)](Syntax-Analysis/LR0.md)
* Formal Shift-Reduce Parsing Algorithms *WIP*
diff --git a/docs/Syntax-Analysis/LL1.md b/docs/Syntax-Analysis/LL1.md
new file mode 100644
index 0000000000..50c74d9650
--- /dev/null
+++ b/docs/Syntax-Analysis/LL1.md
@@ -0,0 +1,110 @@
+# LL(1) Parser
+
+LL(1) parser is a Left-to-right, Leftmost derivation with look-ahead number k
= 1.
+
+This library contains functions to parse, translate, validate grammars.
+
+## Parse
+
+Perform a left-parse of input-stream.
+
+```emacs-lisp
+(require 'parser-generator-ll)
+(require 'ert)
+(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-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
+ '(0 3 1 2 1) ;; Example is indexed from 1 so that is why they have '(1 4 2 3
2)
+ (parser-generator-ll-parse)))
+(message "Passed example 5.5 p. 340")
+```
+
+## Translate
+
+Each production RHS can optionally contain a lambda-expression that will be
called if specified when stack is reduced:
+
+```emacs-lisp
+ (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
+ (a A a a (lambda(a b) (format "alfa %s laval" (nth 1 a))))
+ (b A b a (lambda(a b) (format "delta %s laval" (nth 1 a))))
+ )
+ (A
+ (b (lambda(a b) "sven"))
+ (e (lambda(a b) "ingrid"))
+ )
+ )
+ S
+ )
+ )
+ (parser-generator-process-grammar)
+ (parser-generator-ll-generate-table)
+ (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
+ "delta ingrid laval"
+ (parser-generator-ll-translate)))
+ (message "Passed translation test 1")
+```
+
+## Export
+
+*WIP*
+
+[Back to syntax analysis](../Syntax-Analysis.md)
diff --git a/docs/Syntax-Analysis/LLk.md b/docs/Syntax-Analysis/LLk.md
new file mode 100644
index 0000000000..9881f3a7f2
--- /dev/null
+++ b/docs/Syntax-Analysis/LLk.md
@@ -0,0 +1,111 @@
+# LL(k) Parser
+
+LL(k) parser is a Left-to-right, Leftmost derivation with look-ahead number k
> 1.
+
+This library contains functions to parse, translate, validate grammars.
+
+## Parse
+
+Perform a left-parse of input-stream.
+
+```emacs-lisp
+(require 'parser-generator-ll)
+(require 'ert)
+
+(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 (a A a a) (b A b a))
+ (A b e)
+ )
+ S
+ )
+ )
+(parser-generator-process-grammar)
+(parser-generator-ll-generate-table)
+(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")
+```
+
+## Translate
+
+Each production RHS can optionally contain a lambda-expression that will be
called if specified when stack is reduced:
+
+```emacs-lisp
+ (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
+ (a A a a (lambda(a b) (format "alfa %s laval" (nth 1 a))))
+ (b A b a (lambda(a b) (format "delta %s laval" (nth 1 a))))
+ )
+ (A
+ (b (lambda(a b) "sven"))
+ (e (lambda(a b) "ingrid"))
+ )
+ )
+ S
+ )
+ )
+ (parser-generator-process-grammar)
+ (parser-generator-ll-generate-table)
+ (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
+ "delta ingrid laval"
+ (parser-generator-ll-translate)))
+ (message "Passed translation test 1")
+```
+
+## Export
+
+*WIP*
+
+[Back to syntax analysis](../Syntax-Analysis.md)
diff --git a/parser-generator.el b/parser-generator.el
index 4b749f7f31..dfd698663e 100644
--- a/parser-generator.el
+++ b/parser-generator.el
@@ -45,7 +45,7 @@
(defvar
parser-generator--debug
- nil
+ t
"Whether to print debug messages or not.")
(defvar
diff --git a/test/parser-generator-ll-test.el b/test/parser-generator-ll-test.el
index d59f9ddbcb..e5cf346430 100644
--- a/test/parser-generator-ll-test.el
+++ b/test/parser-generator-ll-test.el
@@ -280,8 +280,6 @@
parser-generator-lex-analyzer--get-function
(lambda (token)
(car token)))
- ;; (message "parsing-table: %S" (parser-generator--hash-to-list
parser-generator-ll--table t))
-
(should
(equal
'(1 3) ;; Example is indexed from 1 so that is why they have '(2 4)
@@ -321,7 +319,6 @@
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)
@@ -361,7 +358,6 @@
parser-generator-lex-analyzer--get-function
(lambda (token)
(car token)))
- (parser-generator-ll-parse)
(should
(equal
'(0 3 1 2 1) ;; Example is indexed from 1 so that is why they have '(1 4 2
3 2)
@@ -480,6 +476,51 @@
(parser-generator-ll-translate)))
(message "Passed translation test 2")
+ (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 (lambda(a b) (format "alfa %s %s" (nth 1 a) (nth 2 a))))
+ (b (lambda(a b) "beta"))
+ )
+ (A
+ (a (lambda(a b) "delta"))
+ (b S A (lambda(a b) (format "gamma %s %s" (nth 1 a) (nth 2 a))))
+ )
+ )
+ S
+ )
+ )
+ (parser-generator-process-grammar)
+ (parser-generator-ll-generate-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)))
+ (should
+ (equal
+ "delta sven laval"
+ (parser-generator-ll-translate)))
+ (message "Passed translation test 3")
+
(message "Passed tests for (parser-generator-ll-translate)"))
(defun parser-generator-ll-test-generate-table ()
