The Backus -Naur Form or Backus Normal Form ( BNF short ) is a compact formal meta-language for representation of context-free grammars ( type 2 grammars in the Chomsky hierarchy ).
This includes the syntax of popular high-level programming.
It is also used for the notation of instruction sets and communication protocols.
Originally, it was named after John W. Backus, later it was named ( at the suggestion of Donald E. Knuth ) even after Peter Naur.
Both were pioneers of computer science that dealt with the creation of the Algol -60 rules and in particular the art of compiler design.
Due to the Backus- Naur form in the Algol 60 report the syntax of a programming language it was first possible to formally exactly, ie without the inaccuracies of natural languages to represent.
There are many variants of the Backus Naur form.
The Extended Backus -Naur Form ( EBNF ) is a common variant, which allows, among other things, a compact notation of repetitive elements.
For syntax definitions in Internet standards mainly enriched Backus -Naur Form ( ABNF ) is used.
Basics
A program initially consists of visible, so existing on the keyboard characters.
In addition there occur spaces and line separators.
The visible signs are counted as terminal symbols (English terminals ).
The BNF uses so-called derivation rules ( productions ), in which non-terminal symbols (English nonterminals ) are defined.
Here, the character is | (vertical bar ) as an alternative, the string :: = is used to define and the non-terminal symbols (also called syntactic variables ) are angle brackets <...> enclosed.
Alternative:
:: = 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
A number except zero is thus either a 1 or a 2 or a 3, etc. It may also be defined terminal sequences, ie one sequence.
As elements of terminal symbols and nonterminal symbols may occur.
Sequence:
:: = 0 |
:: =
:: = 1
:: = 42
A digit is thus a 0 or a digit other than zero.
A two-digit number is a digit other than zero followed by a digit.
Forty-two is a 4 followed by a second
Repetitions must be defined in BNF on recursions.
A derivation rule is this on the right side contain the symbol on the left side, about:
:: = |
Lies: A string of digits is a number or a digit followed by a sequence of digits.
Thus, a sequence of digits matches the symbol sequences 0, 1, 2, 10, 9870, 8,970,635, etc., however, to 00, 000, ....
A positive number can not begin with 0.
This is accomplished by the following rule:
:: = |
BNF and programming languages
To illustrate the syntax of programming languages such as Algol, Pascal or Java in BNF, the keywords (IF, SWITCH) must be counted among the terminal symbols.
In a compiler, they are in a preliminary phase, the lexical analysis recognized and passed as a special character.
Comments are recognized by the lexical analysis (and often away), sometimes also other elements such as floating point numbers, identifiers and strings.
Thus, the whole syntax can be, for example, a PASCAL program in BNF represent ( partially reduced ):
:: = ' PROGRAM ' ' BEGIN ' 'END '.
:: =
:: = |
:: = |
:: = A | B | C | D | ... | Z | a | b | ... | z *)
:: = 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
:: = ...
...
A parsing consists of the return of a program text to the nonterminal symbol .
A program must therefore begin with the word PROGRAM, which is followed by an identifier.
Identifiers begin with a letter, followed by any number of letters or digits.
The return on succeed in
PROGRAM Ggt BEGIN ... END.
PROGRAM DiesisteinlangerBezeichnermit123 BEGIN ... END.
but not in
Ggt BEGIN ... END.
( does not start with PROGRAM)
PROGRAM 123 BEGIN ... END.
(123 is not an identifier, identifiers must start with a letter )
example
Here is a BNF for a German postal address:
:: =
:: =
:: = |
<Namensteil> :: = <Vornamenteil> <Nachname> | <Vornamenteil> <Namensteil>
<Vornamenteil> :: = <Firstname> | <initial>.
<Street> :: = <Straßenname> <House Number> <EOL>
<City> :: = <Postleitzahl> <Stadtname> <EOL>
The formulation is:
</p>
<ul>
<li>A postal address consists of a persons part, followed by a street, followed by the city.
</li>
<li>The people part consists of a title part and a part of the name, followed by a newline.
</li>
<li>The title part consists of a title, or is empty.
</li>
<li>The name part is a given name or initial, followed by a point.
</li>
<li>The name part is a given name part, a surname or part of a name, and turn from one part of the name.
( This rule illustrates the use of recursion in BNF and represents the case that a person has multiple name and / or initials. )
</li>
<li>A road consists of a street name, followed by a number, followed by a newline.
</li>
<li>A city consists of a zip code, followed by a city name followed by a carriage return.
</li>
</ul>
<p>
Note that some (such as zip code or house number ) is not further specified.
It is believed that these lexical details depend on the context or otherwise specified.
</p>
<p>
Often the title is placed in square brackets, the title is omitted part.
This means that the title may be empty:
</p>
<p>
Option:
</p>
<p>
<Personenteil> :: = [ <Title> ] <Namensteil> <EOL>
This example is not a pure form from the Algol 60 report.
The square brackets [ ... ] represent an option; they were introduced a few years later in the definition of <a href="/ibm.html">IBM</a>'s PL / I, but are generally accepted only in EBNF.
</p>
<p>
Option:
</p>
<p>
<number> :: = [- ] <Positive Number>
The minus sign is optional.
This definition is equivalent to
</p>
<p>
<number> :: = <Positive Number> | - <Positive number>
A number is a positive number, or a minus sign, followed by a positive number.
</p>
<h2>
Modifications of the BNF
</h2>
<p>
The alternative and sequence are suitable for representing the BNF principle.
However, the characters can be |, [,] not differ from the BNF characters.
Often, characters such as point or minus can be difficult to detect.
</p>
<p>
The BNF is therefore somewhat modified and supplemented in the rule:
</p>
<ul>
<li>No angle brackets <...> for non-terminals.
</li>
<li>Mark as terminal symbols are enclosed in quotes ("0" | "1" ... )
</li>
<li>Nonterminal symbols in lowercase.
</li>
<li>Keywords in uppercase.
</li>
<li>Only = instead of :: =.
</li>
<li>A dot at the end of a rule.
Multi-line rules are possible.
</li>
</ul>
<p>
Digit = "0 " | " 1 " | " 2 " | " 3" | ... | "9".
digit other than zero = "1 " | " 2 " | " 3" | ... | "9".
digits follow = digit | numeral numerals follow.
number = [ "-"] digit other than zero [ digits follow ] | "0".
program = PROGRAM identifier
BEGIN set follow END ". ".
The option is sometimes not shown in square brackets, but by an attached question mark.
The repetition through recursion is often cumbersome:
</p>
<ul>
<li>Options are represented by an attached question mark.
</li>
<li>Repeats ( one or more times ) are represented by an attached plus sign.
</li>
<li>Optional repetitions ( not once, one or more times ) are represented by an attached star.
</li>
<li>Parentheses are used to group
</li>
</ul>
<p>
Digits follow :: = digit .
number :: = (" -")?
digit other than zero ( numbers sequence)?
| "0".
identifier :: = letter ( letter | digit ) *.
Extended Backus -Naur Form is other ways.
It uses square brackets [ ... ] for the option, but braces { ...} for the optional repetition.
Terminals and nonterminals are not strictly distinguished.
Here, the above example would be displayed as:
</p>
<p>
Sequence of digits = digit { digit };
Number = [ "-"] digit addition zero [ numeric string ] | "0";
Identifier = letter { letter | digit };
Self-definition of a (modified) BNF
</p>
<p>
A modified BNF can define yourself:
</p>
<p>
Modifiziertebnf :: = | set modifiziertebnf.
set :: = non- terminal ":" " ," "= " element list ". ".
list :: = element | element element list.
element :: = Terminal | nonterminally.
nonterminally :: = small letter | small letter not terminal.
terminal :: = keyword | anf anf sichtbareszeichen.
keyword :: = capital letter | open letter keyword.
anf :: = ' " '.
capital letter :: = "A" | "B" | ... | "Z".
small letter :: = "a" | "b" | ... | "z".
sichtbareszeichen :: = "!"
| "$" | "%" | ... ( All visible signs '' '').
In this version, keywords are shown in uppercase, lowercase nonterminals.
Repetitions must be defined via recursion.
Of this use is also made in your own definition ( modifiziertebnf, element list, not terminally, keyword ).
</p>
<h2>
BNF and parser generators
</h2>
<p>
Some parser generators use its own form of BNF as input and generate therefrom a parser for the underlying programming language.
</p>
<p>
That the Unix operating system included program yacc is such a program.
It generates a table-driven parser from a BNF definition, only productions (: instead of :: =) and alternatives (|) are allowed.
This is necessary because yacc allows an S- attribution, an optional part, however, no meaningful semantic type of the attribute can be assigned.
As output we obtain a sub-program in the programming language C. The underlying grammar must fulfill the LALR property.
</p>
</section>
<section class="relLinks">
<script async src="//pagead2.googlesyndication.com/pagead/js/adsbygoogle.js"></script>
<!-- memim 1 wide adaptive -->
<ins class="adsbygoogle"
style="display:block;clear:both;"
data-ad-client="ca-pub-8545452838648870"
data-ad-slot="6796476374"
data-ad-format="auto"></ins>
<script>
(adsbygoogle = window.adsbygoogle || []).push({});
</script>
<a href="/metalanguage.html">Metalanguage</a>
<a href="/communications-protocol.html">Communications protocol</a>
<a href="/donald-knuth.html">Donald Knuth</a>
<a href="/compiler-construction.html">Compiler construction</a>
<a href="/terminal-and-nonterminal-symbols.html">Terminal and nonterminal symbols</a>
<a href="/extended-backus-naur-form.html">Extended Backus–Naur Form</a>
<a href="/syntax-diagram.html">Syntax diagram</a>
<a href="/digital-object-identifier.html">Digital Object Identifier</a>
</section>
<div class="comments">
</div>
<section>
<script async src="//pagead2.googlesyndication.com/pagead/js/adsbygoogle.js"></script>
<ins class="adsbygoogle"
style="display:block"
data-ad-format="autorelaxed"
data-ad-client="ca-pub-8545452838648870"
data-ad-slot="9697283175"></ins>
<script>
(adsbygoogle = window.adsbygoogle || []).push({});
</script>
</section>
<span style="font-size:.5em">96259</span>
<div class="share_buttons">
<div class="addthis_sharing_toolbox"></div>
</div>
</main>
</div>
</td></tr><tr><td id="footer">
<div class="aligner">
<footer class="mainHolder" style="text-align:center;">
<!--LiveInternet counter--><script type="text/javascript"><!--
document.write("<a href='http://www.liveinternet.ru/click' "+
"target=_blank rel=nofollow><img src='//counter.yadro.ru/hit?t18.5;r"+
escape(document.referrer)+((typeof(screen)=="undefined")?"":
";s"+screen.width+"*"+screen.height+"*"+(screen.colorDepth?
screen.colorDepth:screen.pixelDepth))+";u"+escape(document.URL)+
";"+Math.random()+
"' alt='' title='LiveInternet' "+
"border='0' width='88' height='31'><\/a>")
//--></script><!--/LiveInternet-->
<br />
memim.com 2024<br />
All rights reserved<br />
<span style='font-size:0.5em'>Page generated in 0.0027<br /></span> <script type="text/javascript" src="//s7.addthis.com/js/300/addthis_widget.js#pubid=ra-5093bb6e1c1ddca0"></script>
<script>
function jr(ready){
if(window.jQuery){
//ready();
}else{
setTimeout(jr,100,ready);
}
}
jr(function() {
$(".imagesHolder img").each(function () {
var i=$(this);
console.log(i.attr('src')+' '+i.width()+' '+i.readyState);
//$(this).remove();
});
});
</script>
</footer>
</div>
</td></tr></table>
<span style="font-size:.3em">de</span>
</body>
</html>
