Introduction
Backus Naur Form (BNF) stands for Backus Naur Form notation.
It is a formal method for describing the syntax of a programming
language.
BNFs describe how to combine different symbols to produce
a syntactically correct sequence.
Definitions
| Concept | Definition |
|---|
| Grammar |
A system of rules that defines the structure of a language. |
| Parse |
Analyze (a sentence) into its parts and describe their
syntactic roles.
|
| Parser |
A parser uses the grammar of a language to divide
a sentence (code) into
functional parts.
The grammar used must be unambiguous. |
| Semantics |
The meaning of words, signs, and sentence structure. |
| Syntax |
The arrangement of words and phrases to create well-formed
sentences in a language. |
BNF of My Simple Programming Language
Note:
- A program is zero or more statements; One statement per line.
- The symbol ::= means "expand into" and
"replaced with".
- Every name in Backus-Naur form is surrounded
by angle brackets, < >.
- This uses my version of BNF
[] enclose optional items
() enclose optional items, one of which is required
{} zero or more optional item; not required.
| separate alternatives (indicates choice).
trailing + means 1 or more times
trailing * means 0 or more times
"" empty string
::= means to "expand into"
<program> :== <statement>*
<statement> ::= <set> | <loop> | <print>
| <if> | <goto> | <comment> | <exit> | ""
<set> ::= "set" <variable> <expr>
<expr> :== <integer> | <value> <mathop> <value>
<loop> ::= "loop" (<letter> | <digit>)+
<print> ::= "print" (<string> | <variable>)*
<if> ::= "if" <expr>1 ":" <goto> | <set> | <exit>
<goto> ::= "goto" (<letter> | <digit>)+
<comment> ::= "#"
<exit> ::= "exit"
<mathop> ::= "+" | "-"
<comparop> ::= "<" | "=" | ">"
<value> ::= <integer> | <variable>
<variable> ::= <letter>
<integer> ::= <sign> <digit>+
<sign> ::= "" | "+" | "-"
<string> ::= '"' <character>* '"'
<digit> ::= "0" | "1" | "2" | "3" | "4" | "5"
| "6" | "7" | "8" | "9"
<letter> ::= "A" | "B" | "C" | "D" | "E" | "F" | "G"
| "H" | "I" | "J" | "K" | "L" | "M" | "N"
| "O" | "P" | "Q" | "R" | "S" | "T" | "U"
| "V" | "W" | "X" | "Y" | "Z" | "a" | "b"
| "c" | "d" | "e" | "f" | "g" | "h" | "i"
| "j" | "k" | "l" | "m" | "n" | "o" | "p"
| "q" | "r" | "s" | "t" | "u" | "v" | "w"
| "x" | "y" | "z"
<character> ::= <any printable character>
1Note: 0 or "" is false all else is true
FYI:
ASCII (American Standard Code for Information Interchange) is A
character encoding standard that uses a 7-bit binary number to
represent 128 characters, including letters (both uppercase and
lowercase), digits, punctuation marks, and control characters.
Links
BNF Notation in Compiler Design
Backus–Naur form
(Wikipedia)
Notations for context-free grammars
The syntax of C in Backus-Naur Form