branch: externals/parser-generator
commit 53fb7850be60912db15b1bab3c887cf408ef07de
Author: Christian Johansson <christ...@cvj.se>
Commit: Christian Johansson <christ...@cvj.se>
Verified examples in documentation, added infix notation calculator example
---
docs/Syntax-Analysis/LR0.md | 175 ++++++++++++++++-----------
docs/Syntax-Analysis/LRk-Infix-Calculator.md | 120 ++++++++++++++++++
docs/Syntax-Analysis/LRk.md | 3 +
test/parser-generator-lr-export-test.el | 58 +++++++++
4 files changed, 285 insertions(+), 71 deletions(-)
diff --git a/docs/Syntax-Analysis/LR0.md b/docs/Syntax-Analysis/LR0.md
index fed7694..e031b2f 100644
--- a/docs/Syntax-Analysis/LR0.md
+++ b/docs/Syntax-Analysis/LR0.md
@@ -26,6 +26,8 @@ Example with grammar with production: S -> SaSb and S is
non-terminal and a, b a
You can set global symbol operator precedence and also context-sensitive
precedence, like in GNU Bison. Example
``` emacs-lisp
+(require 'parser-generator-lr)
+
(setq
parser-generator--global-attributes
'(%left %precedence %right))
@@ -66,42 +68,53 @@ Perform a right-parse of input-stream. Example from
[Wikipedia](https://en.wikip
(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")
+ (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")
+
+ (switch-to-buffer buffer)
+ (kill-region (point-min) (point-max))
+ (insert "1+1*1")
+
+ (should
+ (equal
+ '(5 3 5 2 5 1)
+ (parser-generator-lr-parse)))
+ (message "Passed parse with k = 0 # 2")
+ (kill-buffer))
```
## Translate
@@ -109,42 +122,59 @@ Perform a right-parse of input-stream. Example from
[Wikipedia](https://en.wikip
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))))))
+(require 'parser-generator-lr)
+(require 'ert)
- (should
- (equal
- '((("1")) " . " ("1"))
- (parser-generator-lr-translate)))
- (message "Passed translation k=0")
- (kill-buffer))
+(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 (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))
```
## Export
@@ -152,6 +182,9 @@ Each production RHS can optionally contain a
lambda-expression that will be call
The export should be executed after a parser has been generated, example:
```emacs-lisp
+(require 'parser-generator-lr)
+(require 'ert)
+
(let ((buffer (generate-new-buffer "*a*")))
(switch-to-buffer buffer)
(kill-region (point-min) (point-max))
diff --git a/docs/Syntax-Analysis/LRk-Infix-Calculator.md
b/docs/Syntax-Analysis/LRk-Infix-Calculator.md
new file mode 100644
index 0000000..e0ef3e0
--- /dev/null
+++ b/docs/Syntax-Analysis/LRk-Infix-Calculator.md
@@ -0,0 +1,120 @@
+# Example LR(k) Infix Calculator
+
+Example reproduced from GNU Bison manual [Infix Notation
Calculator](https://www.gnu.org/software/bison/manual/html_node/Infix-Calc.html).
+
+``` emacs-lisp
+(require 'parser-generator-lr)
+(require 'ert)
+
+(setq
+ parser-generator--e-identifier
+ '%empty)
+(parser-generator-set-look-ahead-number 1)
+(setq
+ parser-generator--global-attributes
+ '(%left %precedence %right))
+(setq
+ parser-generator--context-sensitive-attributes
+ '(%prec))
+(setq
+ parser-generator-lr--global-precedence-attributes
+ '(%left %precedence %right))
+(setq
+ parser-generator-lr--context-sensitive-precedence-attribute
+ '%prec)
+(setq
+ parser-generator--global-declaration
+ '(
+ (%left "-" "+")
+ (%left "*" "/")
+ (%precedence NEG)
+ (%right "^")))
+(parser-generator-set-grammar
+ '(
+ (start input line exp)
+ ("+" "-" "*" "/" "^" "(" ")" "\n" NUM)
+ (
+ (start input)
+ (input
+ %empty
+ (input line (lambda(args) (nth 1 args))))
+ (line
+ "\n"
+ (exp "\n" (lambda(args) (nth 0 args))))
+ (exp
+ NUM
+ (exp "+" exp (lambda(args) (+ (float (nth 0 args)) (nth 2 args))))
+ (exp "-" exp (lambda(args) (- (float (nth 0 args)) (nth 2 args))))
+ (exp "*" exp (lambda(args) (* (float (nth 0 args)) (nth 2 args))))
+ (exp "/" exp (lambda(args) (/ (float (nth 0 args)) (nth 2 args))))
+ ("-" exp %prec NEG (lambda(args) (- (float (nth 1 args)))))
+ (exp "^" exp (lambda(args) (expt (float (nth 0 args)) (nth 2 args))))
+ ("(" exp ")" (lambda(args) (nth 1 args)))))
+ start))
+(setq
+ parser-generator-lex-analyzer--function
+ (lambda (index)
+ (with-current-buffer "*buffer*"
+ (let ((token))
+ (when
+ (<
+ index
+ (point-max))
+ (goto-char
+ index)
+
+ ;; Skip white-space(s)
+ (when (looking-at-p "[\t ]+")
+ (when
+ (search-forward-regexp "[^\t ]" nil t)
+ (forward-char -1)))
+
+ (cond
+ ((looking-at "\\([0-9]+\\.[0-9]+\\|[0-9]+\\)")
+ (setq
+ token
+ `(NUM ,(match-beginning 0) . ,(match-end 0))))
+ ((looking-at "\\(\\+\\|-\\|*\\|/\\|\\^\\|)\\|(\\|\n\\)")
+ (let ((symbol
+ (buffer-substring-no-properties
+ (match-beginning 0)
+ (match-end 0))))
+ (setq
+ token
+ `(,symbol ,(match-beginning 0) . ,(match-end 0)))))
+ (t (error "Unexpected input at %d!" index))))
+ token))))
+
+(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))
+ (let ((symbol
+ (buffer-substring-no-properties start end)))
+ (when
+ (string-match-p "^\\([0-9]+\\.[0-9]+\\|[0-9]+\\)$" symbol)
+ (setq
+ symbol
+ (string-to-number symbol)))
+ symbol))))))
+
+(parser-generator-process-grammar)
+(parser-generator-lr-generate-parser-tables)
+
+(let ((buffer (generate-new-buffer "*buffer*")))
+ (switch-to-buffer buffer)
+ (insert "4 + 4.5 - (34/(8*3+-3))\n")
+ (let ((translate (parser-generator-lr-translate)))
+ (should
+ (equal
+ 6.880952380952381
+ translate)))
+ (message "Passed correct precedence of 4 + 4.5 - (34/(8*3+-3)) =
6.880952380952381")
+ (kill-buffer))
+```
+
+[Back to LR(k) Parser](../LRk.md)
+[Back to syntax analysis](../Syntax-Analysis.md)
diff --git a/docs/Syntax-Analysis/LRk.md b/docs/Syntax-Analysis/LRk.md
index db12254..484012e 100644
--- a/docs/Syntax-Analysis/LRk.md
+++ b/docs/Syntax-Analysis/LRk.md
@@ -27,6 +27,7 @@ Example with grammar with production: S -> SaSb and S is
non-terminal and a, b a
You can set global symbol operator precedence and also context-sensitive
precedence, like in GNU Bison. Example
``` emacs-lisp
+(require 'parser-generator-lr)
(setq
parser-generator--global-attributes
'(%left %precedence %right))
@@ -63,6 +64,7 @@ You can set global symbol operator precedence and also
context-sensitive precede
Calculate the set of LR items valid for any viable prefix S.
``` emacs-lisp
+(require 'parser-generator-lr)
(require 'ert)
(parser-set-grammar '((Sp S) (a b) ((Sp S) (S (S a S b)) (S e)) Sp))
@@ -276,5 +278,6 @@ The export should be executed after a parser has been
generated, example:
(message "Passed parse for exported parser")))
```
+[Example LR(k) Infix Calculator](../LRk-Infix-Calculator.md)
[Back to syntax analysis](../Syntax-Analysis.md)
diff --git a/test/parser-generator-lr-export-test.el
b/test/parser-generator-lr-export-test.el
index c2f0b68..53127b0 100644
--- a/test/parser-generator-lr-export-test.el
+++ b/test/parser-generator-lr-export-test.el
@@ -250,6 +250,64 @@
(fa-translate))))
(message "Passed translate for exported parser")))
+
+ ;; Test exported LR(0) Parser
+ (generate-new-buffer "*a*")
+ (switch-to-buffer "*a*")
+ (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 "*a*"
+ (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 "*a*"
+ (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)))
+
+ ;; Export parser
+ (let ((export (parser-generator-lr-export-to-elisp "e--")))
+
+ (with-temp-buffer
+ (insert export)
+ (eval-buffer)
+ (should
+ (equal
+ t
+ (fboundp 'e---parse)))
+
+ (when (fboundp 'e---parse)
+ (should
+ (equal
+ '(5 3 5 2)
+ (e---parse))))
+ (message "Passed parse for exported LR(0) parser")))
+ (kill-buffer)
+
(message "Passed parse tests"))
(defun parser-generator-lr-export-test-translate ()
