Backus-Naur Form (BNF)
- John Backus and Peter Naur introduced a formal notation to describe the syntax of a given language
- A ‘language’ is defined as set words, formed by glyphs/characters, assembled into sentences in an order, defined by a set of rules (syntax)
- Syntax governs how the various phrases (commands, expressions, declarations) can be combined to form programs
- Within a formal language:
- A natural language is a set of finite-length strings comprised from a given alphabet
- An alphabet is the set of symbols or characters within a language, also known as a language set
- Therefore, a string, in the context of a formal language, is a finite sequence of symbols from an alphabet
The basics of BNF
-
BNF provides syntax through definitions
-
Once something is defined, it can be used again. To do this, BNF makes use of recursive definitions
- Imagine we define a <letter> as running from ‘a’ to ‘Z’
<word>::=<letter> | <word><letter>
Syntax Diagram / Tree
- A syntax diagram (aka railroad diagram) pictographically represents context-free grammar
- Grammar free of context relates to formal languages (terminal and non-terminal symbols)
- Syntax diagrams were created to help those unfamiliar by BNF notation
- Each diagram has an entry point and end point
- The diagram describes possible paths between these two points by going through other non-terminals and terminals
- Terminals are represented by round boxes while non-terminals are represented by square boxes
Examples:
