- Notifications
You must be signed in to change notification settings - Fork26
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
Topics
Resources
License
Code of conduct
Uh oh!
There was an error while loading.Please reload this page.
Stars
Watchers
Forks
Packages0
Uh oh!
There was an error while loading.Please reload this page.