branch: externals/parser-generator
commit 26bf153ffcab96f5f8f52ddc456479cce4baa44d
Author: Christian Johansson <[email protected]>
Commit: Christian Johansson <[email protected]>
Setting look-ahead-number is now separated from setting grammar
---
README.md | 42 ++++++++++++++++++++++++++++++------------
parser.el | 13 ++++++++-----
test/parser-test.el | 45 ++++++++++++++++++++++++++++++---------------
3 files changed, 68 insertions(+), 32 deletions(-)
diff --git a/README.md b/README.md
index 892c2f9..02ce116 100644
--- a/README.md
+++ b/README.md
@@ -36,7 +36,7 @@ We use push down transducer (PDT) based algorithms:
## Grammar
-Grammar consists of `N`, `T`, `P` and `S`, where `N` is non-terminals, `T` is
terminals, `P` is productions and `S` is start-production. N, T, P consists of
lists of one or more strings and symbols, S is the left-hand-side (LHS) of a
production in P. When initializing grammar you also set the number of
look-ahead to use, like this:
+Grammar consists of `N`, `T`, `P` and `S`, where `N` is non-terminals, `T` is
terminals, `P` is productions and `S` is start-production. Example:
* N = `'(S A B C)`
* T = `'(a b c)`
@@ -44,7 +44,7 @@ Grammar consists of `N`, `T`, `P` and `S`, where `N` is
non-terminals, `T` is te
* S = `'S`
``` emacs-lisp
-(parser--set-grammar '((S A B C) (a b c) ((S (A B)) (A (B a) e) (B (C b) C) (C
c e)) S) 2)
+(parser--set-grammar '((S A B C) (a b c) ((S (A B)) (A (B a) e) (B (C b) C) (C
c e)) S))
```
### Non-terminals
@@ -55,6 +55,10 @@ A non-terminal is either a symbol or a string so `"A"` and
`A` are equally valid
A terminal is either a symbol or a string so `"{"` and `A` are equally valid.
+### Sentential-form
+
+A list of one or more non-terminals and terminals, example `'(A "A" c ":")`
+
### Productions
A production consists of a list of at least two elements. The first element is
the left-hand-side (LHS) and should contain at least one element. The
right-hand-side (RHS) consists of the rest of the elements, if there is more
than one list in RHS then each list will be treated as a alternative production
RHS.
@@ -71,42 +75,56 @@ Another example, production `S -> IF "{" EXPRESSION "}" |
EXIT` is declared as:
'(S (IF "{" EXPRESSION "}") EXIT)
```
-### Look-ahead number
+### Start
-Is a simple integer above zero.
+The start symbol is the entry-point of the grammar and should be either a
string or a symbol and should exists in the list of productions as the LHS.
-### Start
+## Look-ahead number
+
+Is a simple integer above zero. You set it like this:
`(parser--set-look-ahead-number 1)` for `1` number look-ahead.
-The start symbol is either a string or a symbol and should exists in the list
of productions as the LHS.
+## Syntax-directed-translation (SDT)
+
+*WIP* Where should this be defined?
+
+## Semantic-actions (SA)
+
+*WIP* Where should this be defined?
## Functions
-### Calculate FIRST(k, S)
+### FIRST(S)
-Calculate first `k` terminals of sentential-form `S`, example:
+Calculate the first look-ahead number of terminals of the sentential-form `S`,
example:
``` emacs-lisp
(require 'ert)
-(parser--set-grammar '((S A B C) (a b c) ((S (A B)) (A (B a) e) (B (C b) C) (C
c e)) S) 2)
+(parser--set-grammar '((S A B C) (a b c) ((S (A B)) (A (B a) e) (B (C b) C) (C
c e)) S))
+(parser--set-look-ahead-number 2)
(should
(equal
'((a) (a c) (a b) (c a) (b a) (e) (c) (b) (c b))
(parser--first 'S)))
```
-### Calculate E-FREE-FIRST(k, S)
+### E-FREE-FIRST(S)
-Calculate e-free-first `k` terminals of sentential-form `S`, example:
+Calculate the e-free-first look-ahead number of terminals of sentential-form
`S`, example:
``` emacs-lisp
(require 'ert)
-(parser--set-grammar '((S A B C) (a b c) ((S (A B)) (A (B a) e) (B (C b) C) (C
c e)) S) 2)
+(parser--set-grammar '((S A B C) (a b c) ((S (A B)) (A (B a) e) (B (C b) C) (C
c e)) S))
+(parser--set-look-ahead-number 2)
(should
(equal
'((c b) (c a))
(parser--e-free-first 'S)))
```
+### FOLLOW(S)
+
+*WIP*
+
## Test
Run in terminal `make clean && make tests && make compile`
diff --git a/parser.el b/parser.el
index 1208d27..43b6fa9 100644
--- a/parser.el
+++ b/parser.el
@@ -100,14 +100,17 @@
(dolist (non-terminal non-terminals)
(puthash non-terminal t parser--table-non-terminal-p))))
-(defun parser--set-grammar (G k)
- "Set grammar G with look-ahead number K."
- (unless (parser--valid-grammar-p G)
- (error "Invalid grammar G!"))
+(defun parser--set-look-ahead-number (k)
+ "Set look-ahead number K."
(unless (parser--valid-look-ahead-number-p k)
(error "Invalid look-ahead number k!"))
+ (setq parser--look-ahead-number k))
+
+(defun parser--set-grammar (G)
+ "Set grammar G.."
+ (unless (parser--valid-grammar-p G)
+ (error "Invalid grammar G!"))
(setq parser--grammar G)
- (setq parser--look-ahead-number k)
(setq parser--f-sets nil)
(parser--load-symbols))
diff --git a/test/parser-test.el b/test/parser-test.el
index b66379a..11f4915 100644
--- a/test/parser-test.el
+++ b/test/parser-test.el
@@ -28,84 +28,96 @@
"Test `parser--first'."
(message "Starting tests for (parser--first)")
- (parser--set-grammar '((S) (a) ((S a)) S) 1)
+ (parser--set-grammar '((S) (a) ((S a)) S))
+ (parser--set-look-ahead-number 1)
(should
(equal
'((a))
(parser--first 'S)))
(message "Passed first 1 with rudimentary grammar")
- (parser--set-grammar '((S) (a) ((S a)) S) 1)
+ (parser--set-grammar '((S) (a) ((S a)) S))
+ (parser--set-look-ahead-number 1)
(should
(equal
'((a))
(parser--first '(S a))))
(message "Passed first 1b with rudimentary grammar")
- (parser--set-grammar '((S) (a) ((S a)) S) 2)
+ (parser--set-grammar '((S) (a) ((S a)) S))
+ (parser--set-look-ahead-number 2)
(should
(equal
'((a a))
(parser--first '(S a))))
(message "Passed first 1c with rudimentary grammar")
- (parser--set-grammar '((S) ("a" "b" "c") ((S ("a" "b" "c"))) S) 2)
+ (parser--set-grammar '((S) ("a" "b" "c") ((S ("a" "b" "c"))) S))
+ (parser--set-look-ahead-number 2)
(should
(equal
'(("a" "b"))
(parser--first 'S)))
(message "Passed first 2 with rudimentary grammar")
- (parser--set-grammar '((S) ("a" b "c") ((S ("a" b "c"))) S) 3)
+ (parser--set-grammar '((S) ("a" b "c") ((S ("a" b "c"))) S))
+ (parser--set-look-ahead-number 3)
(should
(equal
'(("a" b "c"))
(parser--first 'S)))
(message "Passed first 3 with rudimentary grammar")
- (parser--set-grammar '((S A) (b) ((S A) (A b)) S) 2)
+ (parser--set-grammar '((S A) (b) ((S A) (A b)) S))
+ (parser--set-look-ahead-number 2)
(should
(equal
'((b))
(parser--first 'S)))
(message "Passed first 1 with intermediate grammar")
- (parser--set-grammar '((S A) ("a" "b") ((S A) (A ("b" "a"))) S) 2)
+ (parser--set-grammar '((S A) ("a" "b") ((S A) (A ("b" "a"))) S))
+ (parser--set-look-ahead-number 2)
(should
(equal
'(("b" "a"))
(parser--first 'S)))
(message "Passed first 2 with intermediate grammar")
- (parser--set-grammar '((S A) ("a" "b" "c" "d") ((S A) (A ("b" "a" "c" "d")))
S) 3)
+ (parser--set-grammar '((S A) ("a" "b" "c" "d") ((S A) (A ("b" "a" "c" "d")))
S))
+ (parser--set-look-ahead-number 3)
(should
(equal
'(("b" "a" "c"))
(parser--first 'S)))
(message "Passed first 3 with intermediate grammar")
- (parser--set-grammar '((S A B) ("c" "d") ((S A) (A B) (B "c" "d")) S) 1)
+ (parser--set-grammar '((S A B) ("c" "d") ((S A) (A B) (B "c" "d")) S))
+ (parser--set-look-ahead-number 1)
(should
(equal
'(("c") ("d"))
(parser--first 'S)))
(message "Passed first 1 with semi-complex grammar")
- (parser--set-grammar '((S A B) (a c d f) ((S (A a)) (A B) (B (c f) d)) S) 2)
+ (parser--set-grammar '((S A B) (a c d f) ((S (A a)) (A B) (B (c f) d)) S))
+ (parser--set-look-ahead-number 2)
(should
(equal
'((c f) (d a))
(parser--first 'S)))
(message "Passed first 2 with semi-complex grammar")
- (parser--set-grammar '((S A B) ("a" "c" "d" "m") ((S A) (A (B "a" "m")) (B
"c" "d")) S) 3)
+ (parser--set-grammar '((S A B) ("a" "c" "d" "m") ((S A) (A (B "a" "m")) (B
"c" "d")) S))
+ (parser--set-look-ahead-number 3)
(should
(equal
'(("c" "a" "m") ("d" "a" "m"))
(parser--first 'S)))
(message "Passed first 3 with semi-complex grammar")
- (parser--set-grammar '((S A B C) (a b c) ((S A B) (A (B a) e) (B (C b) C) (C
c e)) S) 1)
+ (parser--set-grammar '((S A B C) (a b c) ((S A B) (A (B a) e) (B (C b) C) (C
c e)) S))
+ (parser--set-look-ahead-number 1)
(should
(equal
'((a) (e) (c) (b) )
@@ -113,14 +125,16 @@
(message "Passed first 1 with complex grammar")
;; Example 5.28 p 382
- (parser--set-grammar '((S A B C) (a b c) ((S (A B)) (A (B a) e) (B (C b) C)
(C c e)) S) 2)
+ (parser--set-grammar '((S A B C) (a b c) ((S (A B)) (A (B a) e) (B (C b) C)
(C c e)) S))
+ (parser--set-look-ahead-number 2)
(should
(equal
'((a) (a c) (a b) (c a) (b a) (e) (c) (b) (c b))
(parser--first 'S)))
(message "Passed first 2 with complex grammar")
- (parser--set-grammar '((S A B C) (a b c) ((S (A B)) (A (B a) e) (B (C b) C)
(C c e)) S) 3)
+ (parser--set-grammar '((S A B C) (a b c) ((S (A B)) (A (B a) e) (B (C b) C)
(C c e)) S))
+ (parser--set-look-ahead-number 3)
(should
(equal
'((a c b) (a) (a c) (a b) (c a) (c a c) (c a b) (b a) (b a c) (b a b) (c
b) (e) (c) (b) (c b a))
@@ -135,7 +149,8 @@
(message "Starting tests for (parser--e-free-first)")
;; Example 5.28 p 402
- (parser--set-grammar '((S A B C) (a b c) ((S (A B)) (A (B a) e) (B (C b) C)
(C c e)) S) 2)
+ (parser--set-grammar '((S A B C) (a b c) ((S (A B)) (A (B a) e) (B (C b) C)
(C c e)) S))
+ (parser--set-look-ahead-number 2)
(should
(equal
'((c b) (c a))
