Backus-Naur-vorm

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken

De Backus-Naur-vorm of Backus-normaal-vorm (of, onvertaald: Backus-Naur Form) (BNF), is een notatie voor context-vrije grammatica's, een wiskundig formalisme om de structuur van talen te beschrijven met productieregels.

De notatie is ontwikkeld door John Backus en licht gewijzigd door Peter Naur, voor het beschrijven van de syntaxis van de programmeertaal Algol 60. De techniek en notatie zijn daarna erg populair geworden voor het beschrijven van allerhande talen die in de informatica worden gebruikt.

Oorspronkelijk werd als naam Backus Normal Form gebruikt, maar BNF is geen normaalvorm.

Een voorbeeld uit het Algol-60-report:

<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
<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
<digit> ::= 0|1|2|3|4|5|6|7|8|9
<identifier> ::= <letter> | <identifier><letter> | <identifier><digit>

Hierin betekent het symbool ::= 'is gedefinieerd als' en | betekent 'of'. Met andere woorden:

  • een letter is gedefinieerd als 'A' of 'B' ... of 'Z', of 'a' ... of 'z'
  • een digit is gedefinieerd als '0' of ... '9'
  • een identifier is gedefinieerd als een letter, of als een identifier gevolgd door een letter, of als een identifier gevolgd door een digit. (Zie ook recursie.)

Hiermee is gedefinieerd wat men onder een letter en een cijfer moet verstaan en wat interessanter is, er staat wat een identifier is. Dat is een reeks van letters en cijfers, te beginnen met een letter.

BNF wordt veel gebruikt maar het wordt niet vaak exact beschreven. Er is ook veel variatie in: verschillende auteurs gebruiken hun eigen uitbreidingen, met toegevoegde symbolen, constructies, en semantiek (interpretatieregels). Men spreekt dan wel over Extended BNF (EBNF) of Augmented BNF (ABNF). Wel is er een ISO-standaard voor: ISO-EBNF.

Externe links[bewerken]