Backus–Naur form

Ej att förväxla med Boyce–Codds normala form .

Inom datavetenskap är Backus–Naur-formen ( / ˌ b æ k ə s ˈ n aʊər / ) eller Backus normalform ( BNF ) en metasyntaxnotation för kontextfria grammatiker , som ofta används för att beskriva syntaxen för språk som används i datorer , såsom datorprogrammeringsspråk , dokumentformat , instruktionsuppsättningar och kommunikationsprotokoll . Den används överallt där exakta beskrivningar av språk behövs: till exempel i officiella språkspecifikationer, i manualer och i läroböcker om programmeringsspråksteori.

Många tillägg och varianter av den ursprungliga Backus-Naur-notationen används; vissa är exakt definierade, inklusive utökad Backus-Naur-form (EBNF) och utökad Backus-Naur-form (ABNF).

Översikt

En BNF-specifikation är en uppsättning härledningsregler, skrivna som

   <  symbol  >  ::=  __uttryck__

var:

  • < symbol > är en icke-terminal (variabel) och __uttrycket__ består av en eller flera sekvenser av antingen terminala eller icke-terminala symboler;
  • ::= betyder att symbolen till vänster måste ersättas med uttrycket till höger.
  • fler sekvenser [av symboler] är åtskilda av den vertikala stapeln "|", vilket indikerar ett val , hela är en möjlig ersättning för symbolen till vänster.

Symboler som aldrig visas på vänster sida är terminaler . Å andra sidan är symboler som visas på vänster sida icke-terminaler och är alltid inneslutna mellan paret <>.

Exempel

Som ett exempel, överväg detta möjliga BNF för en amerikansk postadress : 

     

            

    

      

           

    <  postadress  >  ::=  <  namndel  >  <  gatuadress  >  <  zip-del  >  <  namndel  >  ::=  <  personlig del  >  <  efternamn  >  <  opt-suffix-del  >  <  EOL  >  |  <  personal-part  >  <  name-part  >  <  personal-part  >  ::=  <  initial  >  "." |   <  förnamn  >  <  gatuadress  >  ::=  <  hus-nummer  >  <  gatunamn  >  <  opt-apt-num  >  <  EOL  >  <  zip-del  >  ::=  <  ortsnamn  >  ","  <  tillståndskod  >  <  Postnummer  >  <  EOL  >  <  opt-suffix-del  >  ::=  "Sr." |  "Jr."  |   <  romerska siffror  >  | ""   <  opt-apt-num  >  ::=  <  apt-num  >  | ""

Detta översätts till engelska som:

  • En postadress består av en namndel, följt av en gatuadressdel , följt av en postnummerdel .
  • En namndel består av antingen: en personlig del följt av ett efternamn följt av ett valfritt suffix (Jr., Sr. eller dynastiskt nummer) och radslut , eller en personlig del följt av en namndel ( denna regel illustrerar användningen av rekursion i BNF, och täcker fallet med personer som använder flera för- och mellannamn och initialer).
  • En personlig del består av antingen ett förnamn eller en initial följt av en prick.
  • En gatuadress består av ett husnummer, följt av ett gatunamn, följt av en valfri lägenhetsspecifikation , följt av en radslut.
  • En zip-del består av ett stad -namn, följt av ett kommatecken, följt av en tillståndskod , följt av ett postnummer följt av ett radslut.
  • En opt-suffix-del består av ett suffix, såsom "Sr.", "Jr." eller en romersk siffra , eller en tom sträng (dvs ingenting).
  • Ett opt-apt-num består av ett lägenhetsnummer eller en tom sträng (dvs ingenting).

Observera att många saker (som formatet på ett förnamn, lägenhetsnummer, postnummer och romerska siffror) lämnas ospecificerade här. Vid behov kan de beskrivas med hjälp av ytterligare BNF-regler.

Historia

Idén om att beskriva språkets struktur med hjälp av omskrivningsregler kan spåras tillbaka till åtminstone Pāṇinis arbete, en forntida indisk sanskrit-grammatiker och en vördad forskare inom hinduismen som levde någon gång mellan 600- och 400-talet f.Kr. Hans notation för att beskriva sanskritordstrukturen är likvärdig i kraft med Backus och har många liknande egenskaper.

I det västerländska samhället ansågs grammatik länge vara ett ämne för undervisning, snarare än vetenskapliga studier; beskrivningarna var informella och inriktade på praktisk användning. Under första hälften av 1900-talet lingvister som Leonard Bloomfield och Zellig Harris försök att formalisera beskrivningen av språk, inklusive frasstruktur .

Samtidigt introducerades och studerades regler för omskrivning av strängar som formella logiska system av matematiker som Axel Thue (1914), Emil Post (1920-40-talet) och Alan Turing (1936). Noam Chomsky , som undervisade i lingvistik för studenter i informationsteori vid MIT , kombinerade lingvistik och matematik genom att ta vad som i huvudsak är Thues formalism som grund för beskrivningen av syntaxen i naturligt språk . Han införde också en tydlig distinktion mellan generativa regler (de av sammanhangsfria grammatiker ) och transformationsregler (1956).

John Backus , en programmeringsspråksdesigner på IBM , föreslog ett metaspråk av "metalinguistiska formler" för att beskriva syntaxen för det nya programmeringsspråket IAL, idag känt som ALGOL 58 (1959). Hans notation användes först i ALGOL 60-rapporten.

BNF är en notation för Chomskys kontextfria grammatiker. Backus var bekant med Chomskys arbete.

Som föreslagits av Backus definierade formeln "klasser" vars namn är omgivna av vinkelparenteser. Till exempel, <ab> . Vart och ett av dessa namn betecknar en klass av grundläggande symboler.

Ytterligare utveckling av ALGOL ledde till ALGOL 60 . I kommitténs betänkande från 1963 Peter Naur Backus notation Backus normalform . Donald Knuth hävdade att BNF snarare borde läsas som Backus-Naur form , eftersom det inte är "en normal form i konventionell mening", till skillnad från till exempel Chomsky normalform . Namnet Pāṇini Backus-formen föreslogs också en gång med tanke på att expansionen Backus normalform kanske inte är korrekt, och att Pāṇini självständigt hade utvecklat en liknande notation tidigare.

BNF beskrivs av Peter Naur i ALGOL 60-rapporten som metallspråklig formel :

Sekvenser av tecken inom parentes <> representerar metaspråkliga variabler vars värden är sekvenser av symboler. Märkena "::=" och "|" (de senare med betydelsen av "eller") är metallspråkliga bindemedel. Varje märke i en formel, som inte är en variabel eller ett bindemedel, anger sig själv. Juxtaposition av märken eller variabler i en formel betyder juxtaposition av den angivna sekvensen.

Ett annat exempel från ALGOL 60-rapporten illustrerar en stor skillnad mellan BNF-metaspråket och en kontextfri grammatik från Chomsky. Metalinguistiska variabler kräver ingen regel som definierar deras bildande. Deras bildande kan enkelt beskrivas i naturligt språk inom <> parentes. Följande ALGOL 60 rapport avsnitt 2.3 kommenterar specifikation, exemplifierar hur detta fungerar:

För att inkludera text bland symbolerna i ett program gäller följande "kommentar"-konventioner:

Sekvensen av grundläggande symboler: är ekvivalent med
; kommentera <valfri sekvens som inte innehåller ';'>; ;
börja kommentera <valfri sekvens som inte innehåller ';'>; Börja
end <valfri sekvens som inte innehåller 'end' eller ';' eller 'annat'> slutet

Ekvivalens betyder här att vilken som helst av de tre strukturerna som visas i den vänstra kolumnen kan ersättas, i vilken som helst förekomst utanför strängar, av symbolen som visas på samma rad i den högra kolumnen utan någon effekt på programmets åtgärd.

Naur ändrade två av Backus symboler till vanliga tecken. ::=- symbolen var ursprungligen en :≡ . Den | symbolen var ursprungligen ordet " eller " (med ett streck över).

BNF är mycket likt booleska algebra- ekvationer i kanonform som används och användes vid den tiden i logikkretsdesign. Backus var matematiker och designern av programmeringsspråket FORTRAN. Studier av boolesk algebra är vanligtvis en del av en matematikläroplan. Varken Backus eller Naur beskrev namnen inneslutna i < > som icke-terminaler. Chomskys terminologi användes ursprungligen inte för att beskriva BNF. Naur beskrev dem senare som klasser i ALGOL-kursmaterial. I ALGOL 60-rapporten kallades de för metaspråkliga variabler. Allt annat än metasymbolerna ::= , | , och klassnamn inneslutna i < > är symboler för språket som definieras. Metasymbolen ::= ska tolkas som "definieras som". Den | används för att separera alternativa definitioner och tolkas som "eller". Metasymbolerna < > är avgränsare som omsluter ett klassnamn. BNF beskrivs som ett metaspråk för att prata om ALGOL av Peter Naur och Saul Rosen .

1947 blev Saul Rosen involverad i verksamheten i den nystartade Association for Computing Machinery , först i språkkommittén som blev IAL-gruppen och så småningom ledde till ALGOL. Han var den första chefredaktören för ACM:s kommunikation. [ förtydligande behövs ] BNF användes först som ett metaspråk för att tala om ALGOL-språket i ALGOL 60-rapporten. Det är så det förklaras i ALGOL programmeringskursmaterial utvecklat av Peter Naur 1962. Tidiga ALGOL-manualer av IBM, Honeywell, Burroughs och Digital Equipment Corporation följde efter ALGOL 60-rapporten och använde det som ett metaspråk. Saul Rosen beskriver i sin bok BNF som ett metaspråk för att prata om ALGOL. Ett exempel på dess användning som ett metaspråk skulle vara att definiera ett aritmetiskt uttryck: 

   <  expr  >  ::=  <  term  >  |  <  expr  ><  addop  ><  term  >

Den första symbolen för ett alternativ kan vara klassen som definieras, upprepningen, som förklaras av Naur, har funktionen att specificera att den alternativa sekvensen rekursivt kan börja med ett tidigare alternativ och kan upprepas hur många gånger som helst. Till exempel, ovan definieras <expr> som en <term> följt av valfritt antal <addop> <term> .

I vissa senare metaspråk, såsom Schorres META II , ersätts BNF:s rekursiva upprepningskonstruktion med en sekvensoperator och målspråkssymboler definierade med hjälp av citattecken. < och > parenteserna togs bort. Parenteser ( ) för matematisk gruppering lades till. Regeln <expr> skulle visas i META II som 

EXPR = TERM $('+' TERM .OUT('ADD') | '-' TERM .OUT('SUB'));

Dessa ändringar gjorde det möjligt för META II och dess härledda programmeringsspråk att definiera och utöka sitt eget metaspråk, på bekostnad av möjligheten att använda en naturlig språkbeskrivning, metaspråklig variabel, språkkonstruktionsbeskrivning. Många spin-off-metaspråk var inspirerade av BNF. [ citat behövs ] Se META II , TREE-META och Metacompiler .

En BNF-klass beskriver en språkkonstruktionsbildning, med formation definierad som ett mönster eller handlingen att bilda mönstret. Klassnamnet expr beskrivs på ett naturligt språk som en <term> följt av en sekvens <addop> <term> . En klass är en abstraktion; vi kan prata om det oberoende av dess bildande. Vi kan tala om term, oberoende av dess definition, som adderad eller subtraherad i expr. Vi kan prata om att en term är en specifik datatyp och hur en expr ska utvärderas med specifika kombinationer av datatyper, eller till och med omordna ett uttryck för att gruppera datatyper och utvärderingsresultat av blandade typer. Tillägget för naturligt språk gav specifika detaljer om språkklassens semantik som ska användas av en kompilatorimplementering och en programmerare som skriver ett ALGOL-program. Beskrivningen på naturligt språk kompletterade syntaxen ytterligare. Heltalsregeln är ett bra exempel på naturligt språk och metaspråk som används för att beskriva syntax: 

   <  heltal  >  ::=  <  siffra  >  |  <  heltal  ><  siffra  >

Det finns inga detaljer om vitt utrymme i ovanstående. Såvitt regeln anger kan vi ha mellanrum mellan siffrorna. I det naturliga språket kompletterar vi BNF-metaspråket genom att förklara att siffersekvensen inte kan ha något blanksteg mellan siffrorna. Engelska är bara ett av de möjliga naturliga språken. Översättningar av ALGOL-rapporterna fanns tillgängliga på många naturliga språk.

Ursprunget till BNF är inte lika viktigt som dess inverkan på utvecklingen av programmeringsspråk. [ citat behövs ] Under perioden omedelbart efter publiceringen av ALGOL 60-rapporten var BNF grunden för många kompilator-kompilatorsystem .

Vissa, som "A Syntax Directed Compiler for ALGOL 60" utvecklad av Edgar T. Irons och "A Compiler Building System" som utvecklats av Brooker och Morris, använde direkt BNF. Andra, som Schorre Metacompilers, gjorde det till ett programmeringsspråk med bara några få ändringar. <klassnamn> blev symbolidentifierare, släppte det omslutande <,> och använde citattecken för symboler för målspråket. Aritmetikliknande gruppering gav en förenkling som tog bort klasser där gruppering var dess enda värde. META II aritmetiska uttrycksregeln visar grupperingsanvändning. Utmatningsuttryck placerade i en META II-regel används för att mata ut kod och etiketter i ett assemblerspråk. Regler i META II är likvärdiga med klassdefinitioner i BNF. Unix-verktyget yacc är baserat på BNF med kodproduktion som liknar META II. yacc används oftast som en parsergenerator , och dess rötter är uppenbarligen BNF.

BNF är idag ett av de äldsta datorrelaterade språken som fortfarande används. [ citat behövs ]

Ytterligare exempel

BNF syntax diagram
BNF syntaxdiagram

BNF:s syntax i sig kan representeras med en BNF enligt följande:

            
               
          
           
               
                                
            
        
                                                 
         <  syntax  >  ::=  <  regel  >  |  <  regel  >  <  syntax  >  <  regel  >  ::=  <  opt-whitespace  >  "<"  <  regelnamn  >  ">"  <  opt-whitespace  >  "  ::=  "  <  opt-whitespace  >  <  uttryck  >  <  radslut  >  <  opt-whitespace  >  ::=  " "  <  opt-whitespace  >  | ""   <  uttryck  >  ::=  <  lista  >  |  <  lista  >  <  opt-whitespace  >  "|"  <  opt-whitespace  >  <  expression  >  <  line-end  >  ::=  <  opt-whitespace  >  <  EOL  >  |  <  radslut  >  <  radslut  >  <  lista  >  ::=  <  term  >  |  <  term  >  <  opt-whitespace  >  <  lista  >  <  term  >  ::=  <  bokstavlig  >  | "<"   <  regelnamn  >  ">"  <  bokstavligt  >  ::=  '"'  <  text1  >  '"' | "'"   <  text2  >  "'"  <  text1  >  ::=  "" |  <  tecken1  >  <  text1  >  <  text2  >  ::=  "" |  <  tecken2  >  <  text2  >  <  tecken  >  ::=  <  bokstav  >  |  <  siffra  >  |  <  symbol  >  <  bokstav  >  ::=  "A" | "B" |  "C" |  "D" |  "E" |  "F" |  "G" |  "H" |  "Jag" |  "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" |  "jag" |  "j" |  "k" |  "l" |  "m" |  "n" |  "o" |  "p" |  "q" |  "r" |  "s" |  "t" |  "u" |  "v" |  "w" |  "x" |  "y" |  "z"   <  siffra  >  ::=  "0" | "1" |  "2" |  "3" |  "4" |  "5" |  "6" |  "7" |  "8" |  "9"   <  symbol  >  ::=  "|" |  " " |  "!"  |  "#" |  "$" |  "%" |  "&" |  "(" | ")" |  "*" |  "+" |  "," |  "-" |  "."  |  "/" |  ":" |  ";"  |  ">" |  "=" |  "<" |  "?"  |  "@" |  "[" |  "\" |  "]" |  "^" |  "_" |  "`" |  "{" |  "}" |  "~"   <  tecken1  >  ::=  <  tecken  >  | "'"   <  tecken2  >  ::=  <  tecken  >  | '"'   <  regelnamn  >  ::=  <  bokstav  >  |  <  regelnamn  >  <  regel-tecken  >  <  regel-tecken  >  ::=  <  bokstav  >  |  <  siffra  >  | "-"

Observera att "" är den tomma strängen .

Den ursprungliga BNF använde inte citattecken som visas i regeln <literal> . Detta förutsätter att inget blanksteg är nödvändigt för korrekt tolkning av regeln.

<EOL> representerar lämplig linjeslutsspecifikator (i ASCII , vagnretur, radmatning eller båda beroende på operativsystem ) . <regelnamn> och <text> ska ersättas med en deklarerad regels namn/etikett eller bokstavstext.

I exemplet med postadresser i USA ovan är hela blockcitatet en syntax. Varje linje eller obruten gruppering av linjer är en regel; till exempel börjar en regel med <namndel> ::= . Den andra delen av den regeln (bortsett från en linjeände) är ett uttryck, som består av två listor åtskilda av ett rör | . Dessa två listor består av några termer (tre termer respektive två termer). Varje term i denna speciella regel är ett regelnamn.

Varianter

EBNF

Huvudartikel: Extended Backus–Naur form

Det finns många varianter och förlängningar av BNF, i allmänhet antingen för enkelhetens och korthetens skull eller för att anpassa den till en specifik tillämpning. En vanlig egenskap hos många varianter är användningen av reguljära uttrycksrepetitionsoperatorer som * och + . Den utökade Backus-Naur-formen (EBNF) är vanlig.

En annan vanlig förlängning är användningen av hakparenteser runt valfria föremål. Även om den inte finns i den ursprungliga ALGOL 60-rapporten (istället introducerad några år senare i IBM :s PL/I -definition), är notationen nu allmänt erkänd.

ABNF

Huvudartikel: ABNF

Augmented Backus–Naur form (ABNF) och Routing Backus–Naur form (RBNF) är tillägg som vanligtvis används för att beskriva Internet Engineering Task Force (IETF) protokoll .

Att analysera uttrycksgrammatik bygger på BNF och reguljära uttrycksnotationer för att bilda en alternativ klass av formell grammatik , som i huvudsak är analytisk snarare än generativ till sin karaktär.

Andra

Många BNF-specifikationer som finns online idag är avsedda att vara läsbara för människor och är icke-formella. Dessa inkluderar ofta många av följande syntaxregler och tillägg:

  • Valfria objekt inom hakparenteser: [<artikel-x>] .
  • Objekt som finns 0 eller fler gånger omges av parenteser eller suffixas med en asterisk ( * ) såsom <ord> ::= <bokstav> {<bokstav>} eller <ord> ::= <bokstav> <bokstav>* respektive .
  • Objekt som existerar 1 eller flera gånger suffixas med en tilläggssymbol (plus), + , såsom <ord> ::= <bokstav>+ .
  • Terminaler kan visas i fetstil snarare än kursiv, och icke-terminaler i vanlig text snarare än vinkelparenteser.
  • Där objekt är grupperade är de inneslutna inom enkla parenteser.

Programvara som använder BNF

  • ANTLR , en annan parsergenerator skriven i Java
  • Qlik Sense, ett BI-verktyg, använder en variant av BNF för skript
  • BNF Converter (BNFC), som fungerar på en variant som kallas "märkt Backus–Naur form" (LBNF). I denna variant ges varje produktion för en given icke-terminal en etikett, som kan användas som en konstruktor av en algebraisk datatyp som representerar den icke-terminalen. Konverteraren kan producera typer och parsers för abstrakt syntax på flera språk, inklusive Haskell och Java.
  • Coco/R , kompilatorgenerator som accepterar en tillskriven grammatik i EBNF
  • DMS Software Reengineering Toolkit , programanalys och transformationssystem för godtyckliga språk
  • GULD BNF-parser
  • GNU bison , GNU-version av yacc
  • RPA BNF-parser. Online (PHP) demoanalys: JavaScript, XML
  • XACT X4MR System, ett regelbaserat expertsystem för översättning av programmeringsspråk
  • XPL Analyzer, ett verktyg som accepterar förenklad BNF för ett språk och producerar en parser för det språket i XPL; det kan integreras i det medföljande SKELETON-programmet, med vilket språket kan felsökas (ett SHARE- bidragsprogram, som föregicks av A Compiler Generator )
  • Yacc , parsergenerator (används oftast med Lex- förprocessorn)
  • bnfparser 2 , ett universellt verktyg för syntaxverifiering
  • bnf2xml, Markup-ingång med XML-taggar med avancerad BNF-matchning.
  • JavaCC, Java Compiler Compiler tm (JavaCC tm) - Java Parser Generator.
  • Rackets parserverktyg , lex och yacc-liknande parsing (Beautiful Racket edition)

Se även

externa länkar

Språkgrammatik

Hämtad från " https://en.wikipedia.org/w/index.php?title=Backus–Naur_form&oldid=1141508412 "