BNF (Backus-Naur Form)

Introduction

The syntax of a programming language consists of symbols and rules. The syntax of a programming language may be specified using flow diagrams or with BNF. BNF is more commonly used. We shall use BNF from now on to describe the input and and output requirements for programming projects.
 
- History
- Symbols and terminology
Production: statement written in BNF
<> indicates word being defined or to be defined
Words and symbols appearing without the angle brackets are literals and appear in the language being defined exactly as they are specified.
::= "is an instance of"
| or
Examples
An id may be either a or b. <id> ::= a | b
An id may consist of one to three letters. <id> ::= <letter> | <letter><letter>
<letter><letter><letter>
<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
An id may consist of one or more letters. <id> ::= <letter> | <letter><id>
<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
A name is a first name, a middle initial, and a last name. <name> ::= <firstname><blank><middleinit>.<blank><lastname>
<firstname> ::= <capletter><lowerletter>|<firstname><lowerletter>
<capletter> ::= 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
<lowerletter> ::= 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
<blank> ::= ' '
<middleinit> ::= <capletter>
<lastname> ::= <firstname>

Analyzing strings using BNF

<a> ::= <b> | <c> | <a><b>
<bstr> ::= b | b<bstr>
<cstr> ::= c | c<cstr>

Are the following instances of <a>?
bbbb
ccccc
b
ccbbb
cb
bbbcccc
aabb
<c++id>
<c++id> ::= <letter><restofid> | _ <restofid>
<restofid> ::= | <validchar> | <restofid><validchar>
<validchar> ::= <letter> | <digit> | _
<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
<digit> ::= 1|2|3|4|5|6|7|8|9|0

Are the following instances of <c++id>?
Cnt
_notany
i
d3
3d

Possible BNF for C++ discussed so far in class

<c++prog> ::= <sysdirectives> <decdefs> main () {<body>}
<sysdirectives> ::= | #<includedir>
<includedir> ::= include '<'<filename>'>' for <filename> name of file from system library
<decdefs> ::= | <typedef> | <constdef> |<decdefs><typedef>| <decdefs> <constdef>
<typedef> ::= <type><idlist>;
<type> ::= int | float | char
<idlist> ::= <iditem> | <iditem>, <idlist>
<iditem> ::= <id> | <id> = <idvalue> for <idvalue> an initial value of the correct type
<id> ::= <letter><restofid> | _ <restofid>
<restofid> ::= | <validchar> | <restofid><validchar>
<validchar> ::= <letter> | <digit> | _
<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
<digit> ::= 1|2|3|4|5|6|7|8|9|0
<idlist> ::= <id> | <id>, <idlist>
<constdef> ::= const <type> <id> = <idvalue>; for <idvalue> an initial value of the correct type
<body> ::= | <statement> | <decdef> |<body> <statement> | <body> <decdef>
<statement> ::= <assignment>; | <inputstatement>; | <outputstatement>; | <condstatement>; | <iterativestatement>;
<assignment> ::= <id>++ | ++<id> | <id>-- | --<id> | <equalassign>
<equalassign> ::= <id> <equalsymbol> <expression> | <id> <equalsymbol> <equalassign>
<equalsymbol> ::= = | += | -= | *= | /=
<expression> ::= <term> | <sign><term> | <expression> <addoperator> <term>
<term> ::= <term> <multoperator> <factor> | <factor>
<factor> ::= <id> | (<expression>)
<multoperator> ::= * | / | %
<addoperator> ::= + | -
<inputstatement> ::= cin >> <inputlist> | cin.get(<charid>) for <charid> an <id> of type char
<inputlist> ::= <id> | <id> >> <inputlist>
<outputstatement> ::= cout << <outputlist> | cout.put(<charid>)
<outputlist> ::= <outputitem> | <outputitem> << <outputlist>
<outputitem> ::= <id> | '<character>' | "<characterstring>" for <character> any printable character including blank, tab,
end-of-line
<characterstring> ::= <character> | <character><characterstring>
<conditionalstatement> ::= <ifstatement> | <arithmeticif> | <switchstatement>
<ifstatement> ::= <ifthen> | <ifthenelse>
<ifthen> ::= if (<condition>) <statement> | if (<condition>) {<body>}
<condition> ::= <expression><relop><expression>| <condition><logicop><condition>
<relop> ::= < | > | <= | >= | == | !=
<logicop> ::= ! | && | ||
<ifthenelse> ::= <ifthen> else <body>
<arithmeticif> ::= <condition> ? <expression> : <expression>
<switchstatement> ::= switch (<expression>) {<cases>}
<cases> ::= case <valx>: <body> break; | <cases> case <valy>: <body> break; | <cases> default: <body> for <valx> and <valy> discrete values
<iterativestatement> ::= <while> | <for> | <dowhile>
<while> ::= while (<condition>) <statement> | while (<condition>) {<body>}
<dowhile> ::= do <statement> while (<condition>);| do {<body>} while (<condition>);

Back Home Up