Test if a sentence can be generated by given BNFs (Backus-Naur-Form).
Based on some very simple generation rule in BNF it should be possible to decide whether a sentence could be generated or not.
The program expects 2 different
- BNF-Definitions, starting with
#def name
(multiple BNFs allowed, see example) - and tests, starting with
#tests
(only one section allowed). On each following line, the program expects a name for the test case and the test case itself, separated by a space (the test case itself mustn't contain spaces).
BNF definitions should follow the following syntax:
a := a | "b" a | a "c" a | ...
where quoted terms mean Terminals and the recursively defined word a
is a Nonterminal. This "production rule" simply means that a
can be expanded to one of the following terms. The different possibilities are separated by |
.
Currently it is not possible to work with more than one Nonterminal (as the exercise in the course only stated the simple BNFs from below :).
For two given BNFs and some examples as from the HCI-book, they can be written as stated,
#def bnf1
sentence := _ | "hello" sentence | "(" sentence ")" sentence
#def bnf2
sentence := "hello" | sentence sentence | "(" sentence | sentence ")"
#tests
(a) hello
(b) hello(hello)
(c) ((hello)
(d) ()
...
Where _ is a metavariable with the meaning (empty). All spaces or quote signs will be ignored.
This should yield the following result:
Definition found: bnf1
Definition found: bnf2
Building rules...
Cleaning rules...
rules: [['x', '', 'hellox', '(x)x'], ['x', 'hello', 'xx', '(x', 'x)']]
Running tests...
Test (a) hello <-- bnf1 bnf2
Test (b) hello(hello) <-- bnf1 bnf2
Test (c) ((hello) <-- bnf2
Test (d) () <-- bnf1
Test (e) (hello)hello <-- bnf1 bnf2
Test (f) ((hello))hello <-- bnf1 bnf2
Test (g) hello()hello <-- bnf1
Test (h) (hellohello) <-- bnf1 bnf2
Test (i) )hello( <--
Test (j) hello)(hello <-- bnf2
Test (k) hello() <-- bnf1
Test (l) (hello)hello(hello) <-- bnf1 bnf2
Test (m) (hello((hello)hello <-- bnf2
Test (n) (((hello)))) <-- bnf2
Test (o) ((((hello)))) <-- bnf1 bnf2
Test (p) ((((hello()))) <--
Test (q) (((hello()))) <-- bnf1
Example (n) here is only a valid production in bnf2
, but not in bnf1
. (a) is valid in both and (i) is valid in neither of them.
No warranty for use. The code was written for validating sentences in the course Human-Computer-Interaction.