Menu
Extended Backus–Naur Form: EBNF
I'm very new to parsing concepts. Where can I get sufficiently easy to read and follow material for writing a grammar for the boost::spirit library, which uses a grammar similar to EBNF?
Currently I am looking into EBNF from Wikipedia.
587
In terms of power, they are all equivalent. They are just syntactical differences. For example, in traditional BNF, the lhs/rhs separator is ::= , but in books, often → . In EBNF and ABNF it's = .
BNF (Backus–Naur Form) is a syntactic metalanguage (i.e., a language about a language). The metalanguage is a formal notation for specifying the grammar that describes the syntax of a programming language.
In computer science, extended Backus–Naur form (EBNF) is a family of metasyntax notations, any of which can be used to express a context-free grammar. EBNF is used to make a formal description of a formal language such as a computer programming language.
Uses of BNF and EBNF This has two advantages: there can be no disagreement on what the syntax of the language is, and it makes it much easier to make compilers, because the parser for the compiler can be generated automatically with a compiler-compiler like YACC.
The Wikipedia article is accurate. If you have access, definitely read Wirth's original article on EBNF.
The other thing to know is that EBNF was designed to make it easy to hand-write recursive-descent parsers for languages in which each syntactic construct has identifying keywords at the beginning. Curly braces translate to while loops; square brackets (optional stuff) translates to if, and alternatives translate to if-then-else or case statements. If you have the luxury of designing your language this way you can knock out a parser quickly and give good error messages.
The only place this gets a bit tedious is when you have a language in which there are infix operators with many different levels of precedence. For that you want Dave Hanson's paper Compact Recursive-Descent Parsing of Expressions. Maybe the Princeton tech report series has a free version, and you can always look at the code in Hanson's C front end.
56
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
