branch: externals/parser-generator
commit 7d87a2d15461e68ac3e3e0f7e22efca0bc0e412a
Author: Christian Johansson <christ...@cvj.se>
Commit: Christian Johansson <christ...@cvj.se>
Implemented exported LL(k) and LL(1) parser
---
Makefile | 14 ++-
docs/Syntax-Analysis/LL1.md | 144 ++++++++++++++++++--------
docs/Syntax-Analysis/LLk.md | 69 ++++++++++++-
parser-generator-ll-export.el | 99 ++++++++++++------
test/parser-generator-ll-export-test.el | 176 ++++++++++++++++++++++++++++++++
5 files changed, 422 insertions(+), 80 deletions(-)
diff --git a/Makefile b/Makefile
index d08bcf2ea1..86a23ae36f 100644
--- a/Makefile
+++ b/Makefile
@@ -4,7 +4,7 @@ ifdef emacs
endif
EMACS_CMD := $(EMACS) -Q -batch -L . -L test/
-EL := parser-generator.el parser-generator-lex-analyzer.el
parser-generator-ll.el parser-generator-lr.el parser-generator-lr-export.el
test/parser-generator-test.el test/parser-generator-lex-analyzer-test.el
test/parser-generator-lr-export-test.el test/parser-generator-ll-test.el
test/parser-generator-lr-test.el
+EL := parser-generator.el parser-generator-lex-analyzer.el
parser-generator-ll.el parser-generator-ll-export.el parser-generator-lr.el
parser-generator-lr-export.el test/parser-generator-test.el
test/parser-generator-lex-analyzer-test.el
test/parser-generator-lr-export-test.el test/parser-generator-ll-test.el
test/parser-generator-ll-export-test.el test/parser-generator-lr-test.el
ELC := $(EL:.el=.elc)
.PHONY: clean
@@ -27,13 +27,17 @@ test-lex-analyzer:
test-lr:
$(EMACS_CMD) -l test/parser-generator-lr-test.el -f
"parser-generator-lr-test"
+.PHONY: test-lr-export
+test-lr-export:
+ $(EMACS_CMD) -l test/parser-generator-lr-export-test.el -f
"parser-generator-lr-export-test"
+
.PHONY: test-ll
test-ll:
$(EMACS_CMD) -l test/parser-generator-ll-test.el -f
"parser-generator-ll-test"
-.PHONY: test-lr-export
-test-lr-export:
- $(EMACS_CMD) -l test/parser-generator-lr-export-test.el -f
"parser-generator-lr-export-test"
+.PHONY: test-ll-export
+test-ll-export:
+ $(EMACS_CMD) -l test/parser-generator-ll-export-test.el -f
"parser-generator-ll-export-test"
.PHONY: tests
-tests: test test-lex-analyzer test-lr test-lr-export test-ll
+tests: test test-lex-analyzer test-lr test-lr-export test-ll test-ll-export
diff --git a/docs/Syntax-Analysis/LL1.md b/docs/Syntax-Analysis/LL1.md
index 741be84429..0d0e5d9db2 100644
--- a/docs/Syntax-Analysis/LL1.md
+++ b/docs/Syntax-Analysis/LL1.md
@@ -63,54 +63,112 @@ Perform a left-parse of input-stream.
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
+(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 (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")
+ )
+(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*
+```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)))
+(let ((export (parser-generator-ll-export-to-elisp "ba3")))
+ (with-temp-buffer
+ (insert export)
+ (eval-buffer)
+ (should
+ (equal
+ t
+ (fboundp 'ba3-parse)))
+ (should
+ (equal
+ t
+ (fboundp 'ba3-translate)))
+ (when (fboundp 'ba3-parse)
+ (should
+ (equal
+ '(0 3 1 2 1)
+ (ba3-parse))))))
+(message "Passed exported test for example 5.5 p. 340")
+```
[Back to syntax analysis](../Syntax-Analysis.md)
diff --git a/docs/Syntax-Analysis/LLk.md b/docs/Syntax-Analysis/LLk.md
index 9881f3a7f2..bf7130b452 100644
--- a/docs/Syntax-Analysis/LLk.md
+++ b/docs/Syntax-Analysis/LLk.md
@@ -106,6 +106,73 @@ Each production RHS can optionally contain a
lambda-expression that will be call
## Export
-*WIP*
+```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 (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)))
+(let ((export (parser-generator-ll-export-to-elisp "ba")))
+ (with-temp-buffer
+ (insert export)
+ (eval-buffer)
+ (should
+ (equal
+ t
+ (fboundp 'ba-parse)))
+ (should
+ (equal
+ t
+ (fboundp 'ba-translate)))
+ (when (fboundp 'ba-parse)
+ (should
+ (equal
+ '(1 3)
+ (ba-parse))))
+ (when (fboundp 'ba-translate)
+ (should
+ (equal
+ "delta ingrid laval"
+ (ba-translate))))))
+(message "Passed exported test for example 5.16 p. 352")
+```
+
[Back to syntax analysis](../Syntax-Analysis.md)
diff --git a/parser-generator-ll-export.el b/parser-generator-ll-export.el
index 8fff6ed74c..869259463c 100644
--- a/parser-generator-ll-export.el
+++ b/parser-generator-ll-export.el
@@ -61,7 +61,16 @@
(insert "\n;;; Variables:\n\n\n")
- ;; Action-tables
+ ;; Grammar start
+ (insert
+ (format
+ "(defvar\n %s--grammar-start\n %S\n \"The start of grammar.\")\n\n"
+ namespace
+ (if (symbolp (parser-generator--get-grammar-start))
+ (quote (parser-generator--get-grammar-start))
+ (parser-generator--get-grammar-start))))
+
+ ;; Generated table
(insert
(format
"(defvar\n %s--table\n %S\n \"The generated table.\")\n\n"
@@ -410,6 +419,20 @@
namespace
namespace))
+ ;; Generate list of symbol
+ (insert
+ (format "
+(defun %s--generate-list-of-symbol (k symbol)
+ \"Generate list of K number of SYMBOL.\"
+ (let ((list-index 0)
+ (list))
+ (while (< list-index k)
+ (push symbol list)
+ (setq list-index (1+ list-index)))
+ list))
+"
+ namespace))
+
;; Get grammar translation by number
(insert
(format "
@@ -434,13 +457,13 @@
(list
(list
(list
- (%s--get-grammar-start))
+ %s--grammar-start)
(%s--generate-list-of-symbol
%s--look-ahead-number
%s--eof-identifier))
%s--eof-identifier)
(list
- (%s--get-grammar-start)
+ %s--grammar-start
%s--eof-identifier)))
(output)
(eof-look-ahead
@@ -513,7 +536,7 @@
((equal action-type 'pop)
(let ((popped-tokens
- (parser-generator-lex-analyzer--pop-token)))
+ (%s-lex-analyzer--pop-token)))
;; Is it time for SDT?
(when (and
@@ -654,7 +677,7 @@
(dolist (rhs-item production-rhs)
(cond
- ((parser-generator--valid-non-terminal-p
+ ((%s--valid-non-terminal-p
rhs-item)
(let* ((non-terminal-value-list
(gethash rhs-item symbol-table))
@@ -671,10 +694,10 @@
non-terminal-value-list
symbol-table)))
- ((parser-generator--valid-terminal-p
+ ((%s--valid-terminal-p
rhs-item)
(push
- (parser-generator-lex-analyzer--get-function
+ (%s-lex-analyzer--get-function
(nth terminal-index terminals))
args-1)
(push
@@ -690,30 +713,16 @@
args-2
(reverse args-2))
- (parser-generator--debug
- (message
- "Perform translation %d: %S -> %S via args-1: %S and args-2: %S"
- production-number
- production-lhs
- production-rhs
- args-1
- args-2))
-
- (if (parser-generator--get-grammar-translation-by-number
+ (if (%s--get-grammar-translation-by-number
production-number)
(let ((partial-translation
(funcall
- (parser-generator--get-grammar-translation-by-number
+ (%s--get-grammar-translation-by-number
production-number)
args-1
args-2))
(old-symbol-value
(gethash production-lhs symbol-table)))
- (parser-generator--debug
- (message
- "\ntranslation-symbol-table: %S = %S (processed)\n"
- production-lhs
- partial-translation))
(push
(list
partial-translation
@@ -734,11 +743,6 @@
args-2))
(old-symbol-value
(gethash production-lhs symbol-table)))
- (parser-generator--debug
- (message
- "\ntranslation-symbol-table: %S = %S (generic)\n"
- production-lhs
- partial-translation))
(push
partial-translation
old-symbol-value)
@@ -752,7 +756,40 @@
translation))
-")
+"
+ namespace
+ namespace
+ namespace
+ namespace
+ namespace
+ namespace
+ namespace
+ namespace
+ namespace
+ namespace
+ namespace
+ namespace
+ namespace
+ namespace
+ namespace
+ namespace
+ namespace
+ namespace
+ namespace
+ namespace
+ namespace
+ namespace
+ namespace
+ namespace
+ namespace
+ namespace
+ namespace
+ namespace
+ namespace
+ namespace
+ namespace
+ namespace
+ ))
;; Footer
(insert
@@ -774,6 +811,6 @@
code))
-(provide 'parser-generator-lr-export)
+(provide 'parser-generator-ll-export)
-;;; parser-generator-lr-export.el ends here
+;;; parser-generator-ll-export.el ends here
diff --git a/test/parser-generator-ll-export-test.el
b/test/parser-generator-ll-export-test.el
new file mode 100644
index 0000000000..17d7ac0468
--- /dev/null
+++ b/test/parser-generator-ll-export-test.el
@@ -0,0 +1,176 @@
+;; parser-generator-ll-export-test.el --- Tests for Exported Generated LL(k)
Parser -*- lexical-binding: t -*-
+
+;; Copyright (C) 2020-2022 Free Software Foundation, Inc.
+
+
+;;; Commentary:
+
+
+;;; Code:
+
+
+(require 'parser-generator-ll-export)
+(require 'ert)
+
+(defun parser-generator-ll-export-test-to-elisp ()
+ "Test `parser-generator-ll-export-to-elisp'."
+ (message "Started tests for (parser-generator-ll-export-to-elisp)")
+
+ (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)))
+ (let ((export (parser-generator-ll-export-to-elisp "ba")))
+ (with-temp-buffer
+ (insert export)
+ (eval-buffer)
+ (should
+ (equal
+ t
+ (fboundp 'ba-parse)))
+ (should
+ (equal
+ t
+ (fboundp 'ba-translate)))
+ (when (fboundp 'ba-parse)
+ (should
+ (equal
+ '(1 3)
+ (ba-parse))))
+ (when (fboundp 'ba-translate)
+ (should
+ (equal
+ "delta ingrid laval"
+ (ba-translate))))))
+ (message "Passed exported test for example 5.16 p. 352")
+
+ (setq
+ parser-generator-lex-analyzer--function
+ (lambda (index)
+ (let* ((string '((b 1 . 2) (b 2 . 3) (b 3 . 4) (a 4 . 5)))
+ (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))))
+ (let ((export (parser-generator-ll-export-to-elisp "ba2")))
+ (with-temp-buffer
+ (insert export)
+ (eval-buffer)
+ (should
+ (equal
+ t
+ (fboundp 'ba2-parse)))
+ (should
+ (equal
+ t
+ (fboundp 'ba2-translate)))
+ (when (fboundp 'ba2-translate)
+ (should
+ (equal
+ "delta sven laval"
+ (ba2-translate))))))
+ (message "Passed exported test failing parse")
+
+ (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)))
+ (let ((export (parser-generator-ll-export-to-elisp "ba3")))
+ (with-temp-buffer
+ (insert export)
+ (eval-buffer)
+ (should
+ (equal
+ t
+ (fboundp 'ba3-parse)))
+ (should
+ (equal
+ t
+ (fboundp 'ba3-translate)))
+ (when (fboundp 'ba3-parse)
+ (should
+ (equal
+ '(0 3 1 2 1)
+ (ba3-parse))))))
+ (message "Passed exported test for example 5.5 p. 340")
+
+ (message "Passed tests for (parser-generator-ll-export-to-elisp)"))
+
+
+(defun parser-generator-ll-export-test ()
+ "Run test."
+ (parser-generator-ll-export-test-to-elisp))
+
+
+(provide 'parser-generator-ll-export-test)
+
+;;; parser-generator-ll-export-test.el ends here
