- Notifications
You must be signed in to change notification settings - Fork24
Parse BNF grammar definitions
License
shnewto/bnf
Folders and files
| Name | Name | Last commit message | Last commit date | |
|---|---|---|---|---|
Repository files navigation
A library for parsing Backus–Naur form context-free grammars.
The following grammar from theWikipedia page on Backus-Naur formexemplifies a compatible grammar. (*Note: parser allows for an optional ';'to indicate the end of a production)
<postal-address> ::= <name-part> <street-address> <zip-part> <name-part> ::= <personal-part> <last-name> <opt-suffix-part> <EOL> | <personal-part> <name-part> <personal-part> ::= <initial> "." | <first-name> <street-address> ::= <house-num> <street-name> <opt-apt-num> <EOL> <zip-part> ::= <town-name> "," <state-code> <ZIP-code> <EOL><opt-suffix-part> ::= "Sr." | "Jr." | <roman-numeral> | "" <opt-apt-num> ::= <apt-num> | ""Take the following grammar for DNA sequences to be input to this library'sparse function.
<dna> ::= <base> | <base> <dna><base> ::= "A" | "C" | "G" | "T"The output is aGrammar object representing a tree that looks like this:
Grammar { productions: [ Production { lhs: Nonterminal( "dna" ), rhs: [ Expression { terms: [ Nonterminal( "base" ) ] }, Expression { terms: [ Nonterminal( "base" ), Nonterminal( "dna" ) ] } ] }, Production { lhs: Nonterminal( "base" ), rhs: [ Expression { terms: [ Terminal( "A" ) ] }, Expression { terms: [ Terminal( "C" ) ] }, Expression { terms: [ Terminal( "G" ) ] }, Expression { terms: [ Terminal( "T" ) ] } ] } ]}Once theGrammar object is populated, to generate a random sentence from itcall the object's generate function.grammar.generate(). For the above grammaryou could expect something likeTGGC orAG.
If the generate function can't find a production for a nonterminal it triesto evaluate it will print the identifer as a nonterminal, i.e.<identifier>.
The generate function will return an error if it detects an infinite loop causedby a production such as<PATTERN> ::= <PATTERN>.
use bnf::Grammar;let input ="<postal-address> ::= <name-part> <street-address> <zip-part> <name-part> ::= <personal-part> <last-name> <opt-suffix-part> <EOL> | <personal-part> <name-part> <personal-part> ::= <initial> '.' | <first-name> <street-address> ::= <house-num> <street-name> <opt-apt-num> <EOL> <zip-part> ::= <town-name> ',' <state-code> <ZIP-code> <EOL> <opt-suffix-part> ::= 'Sr.' | 'Jr.' | <roman-numeral> | '' <opt-apt-num> ::= <apt-num> | ''";let grammar:Result<Grammar,_> = input.parse();match grammar{Ok(g) =>println!("{:#?}", g),Err(e) =>println!("Failed to make grammar from String: {}", e),}
use bnf::Grammar;let input ="<dna> ::= <base> | <base> <dna> <base> ::= 'A' | 'C' | 'G' | 'T'";let grammar:Grammar = input.parse().unwrap();let sentence = grammar.generate();match sentence{Ok(s) =>println!("random sentence: {}", s),Err(e) =>println!("something went wrong: {}!", e)}
use bnf::Grammar;let input ="<dna> ::= <base> | <base> <dna> <base> ::= 'A' | 'C' | 'G' | 'T'";let grammar:Grammar = input.parse().unwrap();let sentence ="GATTACA";letmut parse_trees = grammar.parse_input(sentence);match parse_trees.next(){Some(parse_tree) =>println!("{}", parse_tree), _ =>println!("Grammar could not parse sentence"),}
About
Parse BNF grammar definitions