8
I was reading an answer here and I came across this term, so what does this term mean, and what is the relationship/influence on current languages?
2 answers
10
It is a notation for expressing context-free grammars. It is usually used in programming language grammars. But it is also used to express communication protocols, data format, other types of languages, etc. It is not usually used in natural language because this notation is not suitable for context-dependent grammars.
In a way we can say that it is a language for writing languages (specification, not implementation of language).
She demonstrates how the tokens can be used validly in the text that will be produced with that language or format.
It has some rules that indicate which characters are accepted, which are the tokens more basic and a name is given for each group of these characters. It can also be expressed as these tokens may be composed to form other tokens, and so on. Indeed in general the opposite is expressed, the tokens more complex are expressed first and each component of that token is expressed after.
The notation allows to tell which are the sequences of tokens valid, whether it can be repeated or not, or even omitted, or whether there are alternatives to use. It generally allows recursion in the use of tokens. Obviously for this you need to express in a way that recursion is not infinite, through the alternative.
See an example that is legal because the BNF notation itself can be expressed in BNF, as wikipedia article:
<syntax> ::= <rule> | <rule> <syntax>
<rule> ::= <opt-whitespace> "<" <rule-name> ">" <opt-whitespace> "::=" <opt-whitespace> <expression> <line-end>
<opt-whitespace> ::= " " <opt-whitespace> | ""
<expression> ::= <list> | <list> <opt-whitespace> "|" <opt-whitespace> <expression>
<line-end> ::= <opt-whitespace> <EOL> | <line-end> <line-end>
<list> ::= <term> | <term> <opt-whitespace> <list>
<term> ::= <literal> | "<" <rule-name> ">"
<literal> ::= '"' <text1> '"' | "'" <text2> "'"
<text1> ::= "" | <character1> <text1>
<text2> ::= "" | <character2> <text2>
<character> ::= <letter> | <digit> | <symbol>
<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> ::= "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"
<symbol> ::= "|" | " " | "-" | "!" | "#" | "$" | "%" | "&" | "(" | ")" | "*" | "+" | "," | "-" | "." | "/" | ":" | ";" | "<" | "=" | ">" | "?" | "@" | "[" | "\" | "]" | "^" | "_" | "`" | "{" | "|" | "}" | "~"
<character1> ::= <character> | "'"
<character2> ::= <character> | '"'
<rule-name> ::= <letter> | <rule-name> <rule-char>
<rule-char> ::= <letter> | <digit> | "-"
There the token <syntax> may be composed of a <rule>, OR by a set of <rule> followed by a <syntax> (noted the recursion?).
To find out how the <rule>, is below. To know how is composed each of its elements, go looking at each BNF rule listed.
Some are terminators, that is, have nothing more to look at. That is the case, in this example of <letter>, <digit> and <symbol>. Terminators are also used optionally in other rules.
There are notation extensions to better express some situations.
EBNF of a version of Ecmascript.
3
BNF (Backus-Naur Form), originally created by John Backus and Peter Naur, is a metasyntax used to express context-free grammars. With it, it is possible to specify which strings of symbols constitute a syntactically valid program in a given language.
The relationship/influence in programming languages is that BNF was initially developed to specify and document the Algol 60 language. It was later used to define several languages including C, Pascal and Ada.
The blog imaster, has an interesting article on the subject: What is BNF and why developers should be importing?
Browser other questions tagged terminology compiler-project
You are not signed in. Login or sign up in order to post.