wiki:KrakenBNF
Last modified 7 months ago

Kraken BNF

  • Kraken BNF enables a target grammar to be written exclusively in Java. (do not need a preprocessor)
  • Support Extended BNF notation.
  • Top-down parser. You must avoid left recursive form.
  • All classes are thread-safe.
    • If your parsers are also thread-safe, you can build syntax only once and use it everywhere.
  • OSGi compliant

Author

Getting Started

  • Name List Syntax
    • <name list> ::= ( [ <name> { <comma> <name> } ... )
    • for example:
      • ()
      • (a)
      • (a, b, c)
  • Write target grammar in java 
    import static org.krakenapps.bnf.Syntax.*;

Syntax s = new Syntax();
s.add("name_list", new NameListParser(), t("("), option(ref("name"), repeat(rule(t(","), ref("name")))), t(")"));
s.add("name", null, idvar());
s.addRoot("name_list");
  • NameListParser class 
    class NameListParser implements Parser {
	@Override
	public Object parse(Binding b) {
		List<String> names = new ArrayList<String>();
		ParserUtil.buildList(b, names);
		return names;
	}
}
  • Use
    • List<String> names = s.eval("(a, b, c, d)");
    • System.out.println(names); will print [a, b, c, d]

Syntax, Rules and Placeholders

  • Syntax
    • Syntax.add(target, parser, rule)
      • if parser is null, binding (parse result) will move upward until meet parser.
      • if multiple bindings conflict (i.e. sequence rule), null will be transferred instead of parse result.
    • Syntax.addRoot(target)
      • you should define root symbol.
      • parser will try all root syntax rules.
  • Rules
    • empty()
      • empty rule
    • t("text")
      • exact match (case sensitive), it ignores preceding and trailing spaces
    • rule(a, b, c)
      • sequence rule. all elements should be matched.
    • choice(a, b, c)
      • try parse until matched. if no match found, it will throw exception.
    • ref("symbol")
      • references "symbol" rule.
    • option(r)
      • r may appear zero or one time.
    • repeat(r)
      • r may appear zero or many times.
  • Placeholders
    • idvar()
      • identifier should begin with an alphabet followed by alphanumeric characters. preceding and trailing spaces are ignored.
    • uint()
      • unsiged integer. preceding and trailing spaces are ignored.
    • custom placeholder
      • you can define your own placeholder (e.g. quoted string)
      • implements Placeholder interface and use it

Debugging

  • Syntax.eval(text, ParserTracer)
    • If you pass ParserTracer to eval(), it will trace all traversal of parse tree.
    • Use built-in TracePrinter class for standard output.
  • ParcerTracer interface 
    // begin of reference rule
ParserContext begin(String symbol, int position);

// result of reference rule
void handle(Rule rule, String token);
	
// exception in reference rule
void error(String symbol, int position);

// end of reference rule
void end(String symbol, int nextPosition);
  • Trace of Column List Syntax
    • (a, b, c) 
      -->begin parse: name_list, 0
  -->begin parse: name, 1
  <--end parse: name 2
  -->begin parse: name_list1, 2
    -->begin parse: name_list1', 2
      -->begin parse: name, 3
      <--end parse: name 5
      -->begin parse: name_list1', 5
        -->begin parse: name, 6
        <--end parse: name 8
        -->begin parse: name_list1', 8
        <--end parse: name_list1' 8
      <--end parse: name_list1' 8
    <--end parse: name_list1' 8
  <--end parse: name_list1 8
<--end parse: name_list 9

Maven configuration

  • Maven repository: http://download.krakenapps.org/ 
    <dependency>
  <groupId>org.krakenapps</groupId>
  <artifactId>kraken-bnf</artifactId>
  <version>1.0.0</version>
</dependency>

See also