Backus - Naur-notasjon , også kjent under sine engelske navn Backus-Naur-form ( BNF ), Backus-Naur-formalisme eller Backus-normalform , er et metaspråk som brukes for å uttrykke kontekstfrie grammatikker : det vil si en formell måte å beskrive språk formelle på .
BNF brukes mye som en notasjon for grammatikkene til programmeringsspråk , kommandosystemer og kommunikasjonsprotokoller , samt en notasjon for å representere deler av naturlig språkgrammatikk (for eksempel meteren i poesi til Venpa). De fleste lærebøker for programmeringsspråkteori eller semantikk dokumenterer programmeringsspråket i BNF.
Noen varianter, som Augmented Backus-Naur Form (ABNF) og Extended Backus-Naur Form (EBNF), har sin egen dokumentasjon.
Ideen om å transkribere språkstruktur med omskrivingsregler går tilbake til i det minste arbeidet til den indiske grammatikeren Panini (cirka 460 f.Kr. ), som brukte det i sin beskrivelse av ordstrukturen til sanskritspråket (noen har til og med foreslått å gi nytt navn til BNF til Panini-Backus Form). Amerikanske lingvister som Leonard Bloomfield og Zellig Harris tok denne ideen et skritt videre ved å forsøke å formalisere språket og dets studie i form av formelle definisjoner og prosedyrer (1920-1960).
Noam Chomsky , MITs lærer i informasjonsteoretisk studentlingvistikk , kombinerte lingvistikk og matematikk, og tok i hovedsak Axel Thues formalisme som grunnlag for hans beskrivelse av naturlig språksyntaks. Han introduserte også et klart skille mellom generative regler (fra kontekstfri grammatikk) og transformative regler (1956).
John Backus , en designer av programmeringsspråk hos IBM , tok i bruk Chomskys generative regler for å beskrive syntaksen til det nye IAL-programmeringsspråket, nå kjent som ALGOL 58 (1959), og presenterte på den første World Computer Congress ( World Computer Congress ) artikkel «Syntaksen og semantikken til det foreslåtte internasjonale algebraiske språket til Zürich ACM-GAMM-konferansen».
Peter Naur identifiserte i sin rapport fra 1963 om ALGOL 60 Backus-notasjon som Backus Normal Form, og forenklet den til å bruke et mindre sett med symboler, men etter forslag fra Donald Knuth ble etternavnet hans lagt til som en anerkjennelse for hans bidrag, og erstattet ordet "Normal" med Naur, siden det ikke er en normalform på noen måte, i motsetning til for eksempel Chomskys Normalform. [ 1 ]
En BNF-spesifikasjon er et system med avledningsregler, skrevet som:
< symbol > ::= <uttrykk med symboler>der < symbol > er en ikke- terminal , og uttrykket består av sekvenser av symboler eller sekvenser atskilt med den vertikale linjen , '|', som indikerer et alternativ , er settet en mulig erstatning for symbolet til venstre. Symboler som aldri vises på venstre side er terminaler .
Som et eksempel kan du vurdere denne BNF for en amerikansk postadresse .
<postadresse> ::= < navn > <adresse> < postboks > < navn > ::= < personlig > < etternavn > [ < behandling > ] < EOL > | < ansatte > < navn > <personlig> ::= <fornavn> | <initial> "." < adresse > ::= [ < leilighet > ] < husnummer > < gatenavn > < EOL > < P.O.-boks > ::= < by > "," <delstatskode> <postnummer> < EOL >Dette oversettes til spansk som:
Merk at mange ting (som formatet til en personlig del, en leilighetsspesifikasjon eller postnummer) er uspesifisert her. Om nødvendig kan de beskrives ved hjelp av ytterligere BNF-regler, eller stå som en abstraksjon hvis det ikke er anvendelig for det aktuelle formålet.
Interessant nok kan BNF-syntaksen representeres i BNF som følger:
< syntaks > ::= < regel > [ < syntaks > ] < regel > ::= < mellomrom > "<" < regelnavn > ">" < mellomrom > " ::= " < uttrykk > < mellomrom > < uttrykk > ")" | "[" < uttrykk > "]") [ < liste-uttrykk > ] < mellomrom > ::= [" " < mellomrom > ] < linjeslutt > ::= [ < mellomrom > ] < EOL > [ < linje- slutt > ]Dette forutsetter at det ikke er noe mellomrom som er nødvendig for riktig tolkning av regelen. <QUOTE> antas å være tegnet ", og <EOL> å være den riktige end-of-line spesifisert (i ASCII , vognretur eller nylinje, avhengig av operativsystemet ). <regelnavn> og <tekst> må erstattes med henholdsvis navn/etikett eller den bokstavelige teksten til en erklært regel.
Det er mange varianter og utvidelser av BNF, som muligens inneholder noen eller alle jokertegnene for regulære uttrykk , for eksempel "*" eller "+". Den utvidede Backus-Naur-formen (EBNF) er en vanlig variant. Eksemplet ovenfor er faktisk ikke den rene formen som ble oppfunnet for ALGOL 60-rapporten. Klammebetegnelsen "[ ]" ble introdusert noen år senere i IBMs definisjon av PL/I, men er nå universelt anerkjent. ABNF er en annen vanlig utvidelse for å beskrive IETF - protokoller .
Parser grammatikkuttrykk bygget på BNF og regulære uttrykksnotasjoner for å danne en alternativ klasse av formell grammatikk , som i hovedsak er analytisk snarere enn generativ karakter.
Mange BNF-spesifikasjoner tilgjengelig på nettet er ment å kunne leses med det blotte øye og er ikke formelle spesifikasjoner. Disse inkluderer ofte noen av disse syntaksreglene og utvidelsene: