A BNF (Backus-Naur Form) parser and a LL input sequence scanner with backtracking
- non-terminals between
<>
- rules end at newline
\n
- assign with
::=
- operators:
- alternative derivations separated by
|
- group items between
()
- optional items between
{}
or with postfix?
operator - zero or more repetitions with postfix
*
operator - one or more repetitions with postfix
+
operator
- alternative derivations separated by
- set of terminal values between
[]
: in set[aeiou]
, not in set[^aeiou]
or ranges[a-z]
The BNF compiler uses a LL parser with backtracking:
- no left-recursion:
<X> :== <X> ...
- no
a+ a
alike sequences - longest rule first: rule
<X> ::= a | a b
must be replaced by<X> ::= a b | a
- special chars
\\<>(){}[]|+*?:=
each must be quoted with\\
Grammar example for a python tuple of integer literals (tuple.bnf
):
<tuple> ::= \( <body> \) | \( \)
<body> ::= <elem> <num> | <elem>
<elem> ::= <num> , <elem> | <num> ,
<num> ::= <dig> <num> | <dig>
<dig> ::= [0-9]
Test if an input sequence matches the above grammar with:
echo -n "(12,34,)" | python3 -m bnf tuple.bnf
The printed result should be True
or False
whether
the input sequence is accepted by the grammar, or not, respectively.
Note: input sequence must not contain a newline (\n
) if grammar does not support it (use echo -n
)
Use the environment DEBUG=1
for a verbose output
(DEBUG=2
for a more verbose output):
echo -n "(12,34,)" | DEBUG=1 python3 -m bnf tuple.bnf
In interactive mode:
>>> from bnf import grammar, parse
>>> grammar("<tuple> ::= \( <body> \) | \( \)\n<body> ::= <elem> <num> | <elem>\n<elem> ::= <num> , <elem> | <num> ,\n<num> ::= <dig> <num> | <dig>\n<dig> ::= [0-9]\n")
>>> parse("(12,34,)")
- terminal symbols must be quoted between
""
:"if"
- rules end with
;
not a newline
remaining rules are the same as for BNF syntax.
The tuple example in eBNF becomes (tuple.ebnf
):
tuple ::= '(' body ')' | '(' ')' ;
body ::= elem num | elem ;
elem ::= num ',' elem | num ',' ;
num ::= dig num | dig ;
dig ::= [0-9] ;
Test if an input sequence matches the above grammar with:
echo -n "(12,34,)" | python3 -m ebnf tuple.ebnf
In interactive mode:
>>> from ebnf import grammar, parse
>>> grammar("tuple ::= '(' body ')' | '(' ')' ;body ::= elem num | elem ;elem ::= num ',' elem | num ',' ;num ::= dig num | dig ;dig ::= [0-9] ;")
>>> parse("(12,34,)")
- bnf.py: BNF parser and input sequence scanner
- ebnf.py: extended BNF parser and input sequence scanner
Documentation in the docs/ directory:
- tutorial.html: an introduction guide
- internals.html: bnf/ebnf routine description
Code examples:
- exs/: some demonstration examples
(C) prs, IST 2022