[elpa] externals/parser-generator a046c8584d 73/82: Started on documentation for LL(k) and LL(1)

[Christian Johansson]

branch: externals/parser-generator
commit a046c8584ded8dc73567ad7b078bc048a34d3859
Author: Christian Johansson <christian@cvj.se>
Commit: Christian Johansson <christian@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 ()