[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[elpa] externals/parser-generator cbf9e07 278/434: Added documentation a
From: |
ELPA Syncer |
Subject: |
[elpa] externals/parser-generator cbf9e07 278/434: Added documentation about LR(0) Parser |
Date: |
Mon, 29 Nov 2021 15:59:57 -0500 (EST) |
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 ()
- [elpa] externals/parser-generator e1315c3 246/434: Updated so E-FREE-FIRST(x) only uses E-FREE-FIRST on first symbol, (continued)
- [elpa] externals/parser-generator e1315c3 246/434: Updated so E-FREE-FIRST(x) only uses E-FREE-FIRST on first symbol, ELPA Syncer, 2021/11/29
- [elpa] externals/parser-generator 53ae129 245/434: Commented out useless code, ELPA Syncer, 2021/11/29
- [elpa] externals/parser-generator 24e96cb 261/434: Improved description of LRk, ELPA Syncer, 2021/11/29
- [elpa] externals/parser-generator 40907b7 257/434: white-space fixes, ELPA Syncer, 2021/11/29
- [elpa] externals/parser-generator 37d9fcb 260/434: Improved documentation, ELPA Syncer, 2021/11/29
- [elpa] externals/parser-generator 08b696f 267/434: Fixed typo in doc about token, ELPA Syncer, 2021/11/29
- [elpa] externals/parser-generator b80fc6e 264/434: Updated README, ELPA Syncer, 2021/11/29
- [elpa] externals/parser-generator 1b9d8db 268/434: Improved wording about lexical analysis, ELPA Syncer, 2021/11/29
- [elpa] externals/parser-generator 3615fad 276/434: Fixed issue with lex-analyzer in LR(0) Parser, ELPA Syncer, 2021/11/29
- [elpa] externals/parser-generator 732cd78 282/434: Constants and variables are exported correctly, ELPA Syncer, 2021/11/29
- [elpa] externals/parser-generator cbf9e07 278/434: Added documentation about LR(0) Parser,
ELPA Syncer <=
- [elpa] externals/parser-generator af71d8b 285/434: Lex-analyzer is now exported, ELPA Syncer, 2021/11/29
- [elpa] externals/parser-generator 500d082 284/434: Added Lex-Analyzer Rest Function to export, ELPA Syncer, 2021/11/29
- [elpa] externals/parser-generator cf42e67 288/434: Exported parser passes test, ELPA Syncer, 2021/11/29
- [elpa] externals/parser-generator 1e0418d 295/434: Incremental parse and translate of exported parser passes tests, ELPA Syncer, 2021/11/29
- [elpa] externals/parser-generator 7584880 298/434: Added failing unit test for calculating FIRST in grammar with cycles, ELPA Syncer, 2021/11/29
- [elpa] externals/parser-generator f338734 303/434: Improved output of progress, ELPA Syncer, 2021/11/29
- [elpa] externals/parser-generator 98c9d94 213/434: Debugging parse with look-ahead > 1, ELPA Syncer, 2021/11/29
- [elpa] externals/parser-generator 2b0d5b8 215/434: More debugging, ELPA Syncer, 2021/11/29
- [elpa] externals/parser-generator 640feed 216/434: Passing all tests for canonical LRk Parser with k = 1, ELPA Syncer, 2021/11/29
- [elpa] externals/parser-generator e5aa179 218/434: Some fixes for LRk parser k > 1, ELPA Syncer, 2021/11/29