[elpa] externals/parser-generator cbf9e07 278/434: Added documentation about LR(0) Parser

[ELPA Syncer]

branch: externals/parser-generator
commit cbf9e07c9e0d28ce1a792ff6cfabf227b8be0a86
Author: Christian Johansson <christian@cvj.se>
Commit: Christian Johansson <christian@cvj.se>

    Added documentation about LR(0) Parser
---
 docs/Syntax-Analysis.md          |   1 +
 docs/Syntax-Analysis/LR0.md      | 114 +++++++++++++++++++++++++++++++++++++++
 docs/Syntax-Analysis/LRk.md      |   2 +-
 test/parser-generator-lr-test.el |   5 --
 4 files changed, 116 insertions(+), 6 deletions(-)

diff --git a/docs/Syntax-Analysis.md b/docs/Syntax-Analysis.md
index 7bca4da..b384185 100644
--- a/docs/Syntax-Analysis.md
+++ b/docs/Syntax-Analysis.md
@@ -14,6 +14,7 @@ We use push down transducer (PDT) based algorithms.
 * LL(k) *WIP*
 * Deterministic Shift-Reduce Parsing *WIP*
 * [LR(k)](Syntax-Analysis/LRk.md)
+* [LR(0)](Syntax-Analysis/LR0.md)
 * Formal Shift-Reduce Parsing Algorithms *WIP*
 * Simple Precedence Grammars *WIP*
 * Extended Precedence Grammars *WIP*
diff --git a/docs/Syntax-Analysis/LR0.md b/docs/Syntax-Analysis/LR0.md
new file mode 100644
index 0000000..5dd9262
--- /dev/null
+++ b/docs/Syntax-Analysis/LR0.md
@@ -0,0 +1,114 @@
+# LR(0) Parser
+
+LR(k) parser is a Left-to-right, Rightmost derivation in reverse without a 
look-ahead invented by Donald Knuth.
+
+This library contains functions to parse, translate, validate grammars as well 
as exporting parser, parser/translators as stand-alone emacs-lisp code. *WIP*
+
+## LR Item
+
+A valid LR-item for a viable prefix has this structure:
+
+``` emacs-lisp
+(A B C)
+```
+
+Example with grammar with production: S -> SaSb and S is non-terminal and a, b 
are terminals. Look-ahead number: 0
+
+``` emacs-lisp
+((S) nil (S a S b))
+```
+
+* A is the production LHS
+* B, C is parts of the production RHS, if the dot is at the left B is nil and 
C is the entire RHS. If the dot is at the right then B is the production RHS 
and C is nil, otherwise B and C contains parts of the RHS
+
+## Parse
+
+Perform a right-parse of input-stream. Example from 
[Wikipedia](https://en.wikipedia.org/wiki/LR_parser#Constructing_LR(0)_parsing_tables).
+
+```emacs-lisp
+(require 'parser-generator-lr)
+(require 'ert)
+
+(let ((buffer (generate-new-buffer "*a*")))
+  (switch-to-buffer buffer)
+  (kill-region (point-min) (point-max))
+  (insert "1+1")
+
+  (parser-generator-set-grammar
+   '((S E B) ("*" "+" "0" "1") ((S (E $)) (E (E "*" B) (E "+" B) (B)) (B ("0") 
("1"))) S))
+  (parser-generator-set-look-ahead-number 0)
+  (parser-generator-process-grammar)
+  (parser-generator-lr-generate-parser-tables)
+
+  ;; Setup lex-analyzer
+  (setq
+   parser-generator-lex-analyzer--function
+   (lambda (index)
+     (with-current-buffer buffer
+       (when (<= (+ index 1) (point-max))
+         (let ((start index)
+               (end (+ index 1)))
+           (let ((token (buffer-substring-no-properties start end)))
+             `(,token ,start . ,end)))))))
+  (setq
+   parser-generator-lex-analyzer--get-function
+   (lambda (token)
+     (with-current-buffer buffer
+       (let ((start (car (cdr token)))
+             (end (cdr (cdr token))))
+         (when (<= end (point-max))
+           (buffer-substring-no-properties
+            start
+            end))))))
+
+  (should
+   (equal
+    '(5 3 5 2)
+    (parser-generator-lr-parse)))
+  (message "Passed parse with k = 0 # 1")
+```
+
+## Translate
+
+Each production RHS can optionally contain a lambda-expression that will be 
called if specified when a reduction is made, example:
+
+```emacs-lisp
+(let ((buffer (generate-new-buffer "*a*")))
+  (switch-to-buffer buffer)
+  (kill-region (point-min) (point-max))
+  (insert "1+1")
+
+  (parser-generator-set-grammar
+   '((S E B) ("*" "+" "0" "1") ((S (E $)) (E (E "*" B (lambda(args) (let ((ret 
(list (nth 0 args)))) (when (nth 2 args) (setq ret (append ret `(" x " ,(nth 2 
args))))) ret))) (E "+" B (lambda(args) (let ((ret (list (nth 0 args)))) (when 
(nth 2 args) (setq ret (append ret `(" . " ,(nth 2 args))))) ret))) (B)) (B 
("0") ("1"))) S))
+  (parser-generator-set-look-ahead-number 0)
+  (parser-generator-process-grammar)
+  (parser-generator-lr-generate-parser-tables)
+
+  ;; Setup lex-analyzer
+  (setq
+   parser-generator-lex-analyzer--function
+   (lambda (index)
+     (with-current-buffer buffer
+       (when (<= (+ index 1) (point-max))
+         (let ((start index)
+               (end (+ index 1)))
+           (let ((token (buffer-substring-no-properties start end)))
+             `(,token ,start . ,end)))))))
+  (setq
+   parser-generator-lex-analyzer--get-function
+   (lambda (token)
+     (with-current-buffer buffer
+       (let ((start (car (cdr token)))
+             (end (cdr (cdr token))))
+         (when (<= end (point-max))
+           (buffer-substring-no-properties start end))))))
+
+  (should
+   (equal
+    '((("1")) " . " ("1"))
+    (parser-generator-lr-translate)))
+  (message "Passed translation k=0")
+  (kill-buffer))
+```
+
+[Back to syntax analysis](../Syntax-Analysis.md)
diff --git a/docs/Syntax-Analysis/LRk.md b/docs/Syntax-Analysis/LRk.md
index cc11a9a..70b3cd0 100644
--- a/docs/Syntax-Analysis/LRk.md
+++ b/docs/Syntax-Analysis/LRk.md
@@ -1,4 +1,4 @@
-# LRk Parser
+# LR(k) Parser
 
 LR(k) parser is a Left-to-right, Rightmost derivation in reverse with 
look-ahead number k invented by Donald Knuth.
 
diff --git a/test/parser-generator-lr-test.el b/test/parser-generator-lr-test.el
index f409c51..49c4071 100644
--- a/test/parser-generator-lr-test.el
+++ b/test/parser-generator-lr-test.el
@@ -933,9 +933,7 @@
      (equal
       '(5 3 5 2 5 1)
       (parser-generator-lr-parse)))
-
     (message "Passed parse with k = 0 # 2")
-
     (kill-buffer))
 
   (let ((buffer (generate-new-buffer "*a*")))
@@ -972,12 +970,9 @@
      (equal
       '((("1")) " . " ("1"))
       (parser-generator-lr-translate)))
-
     (message "Passed translation k=0")
-     
     (kill-buffer))
 
-
   (message "Passed tests for (parser-generator-lr--parse-k-0)"))
 
 (defun parser-generator-lr-test-translate ()