Backus-Naur form

Fra Wikipedia, den frie encyklopedi
Gå til: navigasjon, søk

Backus–Naur Form (BNF) er et formelt metaspråk for å uttrykke kontekstfrie grammatikker som for eksempel syntaksen til høynivåspråk. Formen er oppkalt etter John Backus og Peter Naur, som utviklet BNF for å kunne bruke kontekstfrie grammatikker til å beskrive syntaksen til programmeringsspråk, den ble brukt for første gang i Algol 60 Report 1960.[1]

Oppbygning[rediger | rediger kilde]

Et program består vanligvis av synlige tegn som finnes på et tastatur, disse kalles terminalsymboler. BNF anvender avledningsregler for å danne syntaktiske variable. Her blir tegnfølgen ::= brukt for å notere en definisjon, | (pipe) for å notere alternativer og spisse parenteser < og > for å betegne en syntaktisk variabel. Terminalsymbolene utgjør grunnelementene i BNF, alle definisjonene baserer på disse. Eksempler på definisjoner:

<siffer ikke null> ::= 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
<siffer>           ::= 0 | <siffer ikke null>
<tall>             ::= <siffer> | <siffer ikke null> <tall> 

Her er den første linjen en enkel definisjon med terminalsymboler som alternativer, den andre en kjededefinisjon som bygger på den første og den tredje er en rekursiv definisjon. De første defisjonene i Algol 60:[1]

<empty>            ::=
<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
<logical value>    ::= true|false

I definisjonen av <logical value> er terminalsymbolene ikke tastaturtegn men hele ord, i BNF-notasjonen kjennetegnet med fet skrift. I praktiske implemetasjoner kunne slike symboler kjennetegnes for eksempel ved at de ble skrevet understreket som true og false.

Se også[rediger | rediger kilde]

SDF er en alternativ metasyntakser for samme formål, men som har sitt opphav i universell algebra.

Referanser[rediger | rediger kilde]

InformatikkstubbDenne Informatikkrelaterte artikkelen er dessverre kort eller mangelfull, og du kan hjelpe Wikipedia ved å utvide den.