A BNF (Backus-Naur Form) parser and a LL input sequence scanner with backtracking
Project description
A BNF (Backus-Naur Form) parser and a LL input sequence scanner with backtracking
BNF syntax:
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
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):
`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,)") `
EBNF syntax:
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):
`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 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,)") `
The bnf/ package includes:
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 introdution guide
internals.html: bnf/ebnf routine description
Code examples:
exs/: some demonstration examples
prs, IST 2022
Download files
Download the file for your platform. If you're not sure which to choose, learn more about installing packages.
