Backus-Naur form

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. 

 Oppbygning 
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>           ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
 <tall>             ::= <siffer> | <siffer> <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:
 <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å 
SDF er en alternativ metasyntakser for samme formål, men som har sitt opphav i universell algebra.

 Referanser 
Report on the Algorithmic Language ALGOL 60. 1960.

Kategori:Formelle språk
Kategori:Kompilatorer