branch: externals/parser-generator
commit 16bb2d8863a0f637bb16965654cb5fed1e006817
Author: Christian Johansson <christ...@cvj.se>
Commit: Christian Johansson <christ...@cvj.se>
Added translation example LRk parser
---
docs/Syntax-Analysis/LRk.md | 111 ++++++++++++++++++++++++++++++++++++++------
1 file changed, 97 insertions(+), 14 deletions(-)
diff --git a/docs/Syntax-Analysis/LRk.md b/docs/Syntax-Analysis/LRk.md
index 6c6eec7..04c8d59 100644
--- a/docs/Syntax-Analysis/LRk.md
+++ b/docs/Syntax-Analysis/LRk.md
@@ -15,12 +15,12 @@ A valid LR-item for a viable prefix has this structure:
Example with grammar with production: S -> SaSb and S is non-terminal and a, b
are terminals. Look-ahead number: 1
``` emacs-lisp
-(S nil (S a S b) (a))
+((S) nil (S a S b) (a))
```
* A is the production LHS
-* B, C is parts of the production RHS, if the dot is 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
-* L is the terminal look-ahead
+* 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
+* L is the item look-ahead
## LR items for prefix (S)
@@ -35,12 +35,12 @@ Calculate the set of LR items valid for any viable prefix S.
(should
(equal
- '((S nil (S a S b) (a))
- (S nil (S a S b) (e))
- (S nil nil (a))
- (S nil nil (e))
- (Sp nil (S) (e)))
- (parser--lr-items-for-prefix 'e)))
+ '(((S) nil (S a S b) ($))
+ ((S) nil (S a S b) (a))
+ ((S) nil nil ($))
+ ((S) nil nil (a))
+ ((Sp) nil (S) ($)))
+ (parser-generator-lr--items-for-prefix 'e)))
```
``` emacs-lisp
@@ -52,10 +52,10 @@ Calculate the set of LR items valid for any viable prefix S.
(should
(equal
- '((S (S) (a S b) (a))
- (S (S) (a S b) (e))
- (Sp (S) nil (e)))
- (parser--lr-items-for-prefix 'S)))
+ '(((S) (S) (a S b) ($))
+ ((S) (S) (a S b) (a))
+ ((Sp) (S) nil ($)))
+ (parser-generator-lr--items-for-prefix 'S)))
```
## Parse
@@ -93,6 +93,89 @@ Perform a right-parse of input-stream.
## Translate
-Coming soon!
+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)
+ (insert "if (a) { b; }")
+
+ (parser-generator-set-grammar '((Sp S) (";" OPEN_ROUND_BRACKET
CLOSE_ROUND_BRACKET ECHO IF OPEN_CURLY_BRACKET CLOSE_CURLY_BRACKET VARIABLE)
((Sp S) (S (IF OPEN_ROUND_BRACKET VARIABLE CLOSE_ROUND_BRACKET
OPEN_CURLY_BRACKET VARIABLE ";" CLOSE_CURLY_BRACKET (lambda(args) (format
"(when %s %s)" (nth 2 args) (nth 5 args)))))) Sp))
+ (parser-generator-set-look-ahead-number 1)
+ (parser-generator-process-grammar)
+ (parser-generator-lr-generate-parser-tables)
+
+ (setq
+ parser-generator-lex-analyzer--function
+ (lambda (index)
+ (with-current-buffer buffer
+ (unless (>= index (point-max))
+ (goto-char index)
+ (unless (looking-at "[^ \n\t]")
+ (search-forward-regexp "[^ \n\t]" nil t nil)
+ (forward-char -1))
+ (let ((token))
+ (cond
+ ((looking-at "if")
+ (setq token `(IF ,(match-beginning 0) . ,(match-end 0))))
+ ((looking-at "echo")
+ (setq token `(ECHO ,(match-beginning 0) . ,(match-end 0))))
+ ((looking-at "(")
+ (setq token `(OPEN_ROUND_BRACKET ,(match-beginning 0) .
,(match-end 0))))
+ ((looking-at ")")
+ (setq token `(CLOSE_ROUND_BRACKET ,(match-beginning 0) .
,(match-end 0))))
+ ((looking-at "{")
+ (setq token `(OPEN_CURLY_BRACKET ,(match-beginning 0) .
,(match-end 0))))
+ ((looking-at "}")
+ (setq token `(CLOSE_CURLY_BRACKET ,(match-beginning 0) .
,(match-end 0))))
+ ((looking-at ";")
+ (setq token `(";" ,(match-beginning 0) . ,(match-end 0))))
+ ((looking-at "[a-zA-Z]+")
+ (setq token `(VARIABLE ,(match-beginning 0) . ,(match-end 0))))
+ (t (error "Invalid syntax! Could not lex-analyze at %s!"
(point))))
+ 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))
+ (buffer-substring-no-properties start end))))))
+
+ (should
+ (equal
+ "(when a b)"
+ (parser-generator-lr-translate)))
+ (message "Passed test with non-nested translation")
+
+ (switch-to-buffer buffer)
+ (kill-region (point-min) (point-max))
+
+ (parser-generator-set-grammar '((Sp S T) (";" OPEN_ROUND_BRACKET
CLOSE_ROUND_BRACKET ECHO IF OPEN_CURLY_BRACKET CLOSE_CURLY_BRACKET VARIABLE)
((Sp S) (S (IF OPEN_ROUND_BRACKET VARIABLE CLOSE_ROUND_BRACKET
OPEN_CURLY_BRACKET T CLOSE_CURLY_BRACKET (lambda(args) (format "(when %s %s)"
(nth 2 args) (nth 5 args))))) (T (ECHO VARIABLE ";" (lambda(args) (format
"(message %s)" (nth 1 args)))) (VARIABLE ";" (lambda(args) (format "%s" (nth 0
args)))))) Sp))
+ (parser-generator-set-look-ahead-number 1)
+ (parser-generator-process-grammar)
+ (parser-generator-lr-generate-parser-tables)
+
+ (insert "if (a) { echo b; }")
+
+ (should
+ (equal
+ "(when a (message b))"
+ (parser-generator-lr-translate)))
+
+ (message "Passed test with nested-translation with depth 2")
+
+ (switch-to-buffer buffer)
+ (kill-region (point-min) (point-max))
+ (goto-char 1)
+ (insert "if (a) { echo b }")
+
+ (should-error
+ (parser-generator-lr-parse))
+
+ (kill-buffer buffer))
+```
[Back to syntax analysis](../../Syntax-Analysis.md)
