Utökad Backus-Naur-form
Inom datavetenskap är utökad Backus-Naur-form ( EBNF ) en familj av metasyntaxnotationer , varav vilken som helst kan användas för att uttrycka en kontextfri grammatik . EBNF används för att göra en formell beskrivning av ett formellt språk såsom ett datorprogrammeringsspråk . De är förlängningar av den grundläggande Backus-Naur-formens ( BNF) metasyntaxnotation.
Den tidigaste EBNF utvecklades av Niklaus Wirth och inkorporerade några av begreppen (med en annan syntax och notation) från Wirth-syntaxnotation . Idag används många varianter av EBNF. Den internationella standardiseringsorganisationen antog en EBNF- standard , ISO/IEC 14977, 1996. Enligt Zaytsev slutade emellertid denna standard "endast med att lägga till ytterligare tre dialekter till kaoset" och noterar också, efter att ha noterat sin brist på framgång, att ISO EBNF inte ens används i alla ISO-standarder. Wheeler argumenterar mot att använda ISO-standarden när man använder en EBNF och rekommenderar att man överväger alternativa EBNF-notationer som den från W3C Extensible Markup Language (XML) 1.0 (femte upplagan).
Den här artikeln använder EBNF som specificerats av ISO för exempel som gäller alla EBNF. Andra EBNF-varianter använder något annorlunda syntaktiska konventioner.
Grunderna
EBNF är en kod som uttrycker syntaxen för ett formellt språk. En EBNF består av terminalsymboler och icke-terminalproduktionsregler som är de begränsningar som styr hur terminalsymboler kan kombineras till en legal sekvens. Exempel på terminalsymboler inkluderar alfanumeriska tecken , skiljetecken och blanksteg .
EBNF definierar produktionsregler där sekvenser av symboler respektive tilldelas en icke-terminal :
siffra exklusive noll = "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" ; siffra = "0" | siffra exklusive noll ;
0 Denna produktionsregel definierar den icke-terminala siffran som finns till vänster om tilldelningen. Den vertikala stapeln representerar ett alternativ och terminalsymbolerna är omgivna av citattecken följt av ett semikolon som avslutande tecken. Därför är en siffra en eller en siffra exklusive noll som kan vara 1 eller 2 eller 3 och så vidare tills 9 .
En produktionsregel kan också inkludera en sekvens av terminaler eller icke-terminaler, var och en separerad med ett kommatecken:
tolv = "1" , "2" ; tvåhundra ett = "2" , "0" , "1" ; tre hundra tolv = "3" , tolv ; tolv tusen två hundra ett = tolv , två hundra ett ;
Uttryck som kan utelämnas eller upprepas kan representeras med hängslen { ... }:
naturligt tal = siffra exklusive noll , { siffra } ;
I det här fallet är strängarna 1 , 2 , ..., 10 , ..., 10000 , ... korrekta uttryck. För att representera detta kan allt som är satt inom de lockiga hängslen upprepas godtyckligt ofta, inklusive inte alls.
Ett alternativ kan representeras med hakparenteser [ ... ]. Det vill säga, allt som ställs inom hakparenteserna kan vara närvarande bara en gång, eller inte alls:
heltal = "0" | [ "-" ], naturligt tal ;
0 Därför är ett heltal en noll ( ) eller ett naturligt tal som kan föregås av ett valfritt minustecken .
EBNF tillhandahåller också, bland annat, syntaxen för att beskriva upprepningar (av ett specificerat antal gånger), att utesluta någon del av en produktion och att infoga kommentarer i en EBNF-grammatik.
Tabell över symboler
Följande representerar en föreslagen ISO/IEC 14977-standard, av RS Scowen, sidan 7, tabell 1.
| Användande | Notation |
|---|---|
| definition | = |
| sammanlänkning | , |
| uppsägning | ; |
| alternering | | |
| frivillig | [ ... ] |
| upprepning | { ... } |
| gruppering | (...) |
| terminalsträng | "..." |
| terminalsträng | '...' |
| kommentar | (* ... *) |
| speciell sekvens | ? ... ? |
| undantag | - |
Exempel
Syntaxdiagram
EBNF
Även EBNF kan beskrivas med EBNF. Överväg nedanstående grammatik (använd konventioner som "-" för att indikera uppsättningsdisjunktion, "+" för att indikera en eller flera matchningar och "?" för valmöjligheter):
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 = "[" | "]" | "{" | "}" | "(" | ")" | "<" | ">" | "'" | '"' | "=" | "|" | "." | "," | ";" | "-" | "+" | "*" | "?" | "\n" | "\t" | "\r" | "\f" | "\b" ; tecken = bokstav | siffra | symbol | "_" | " " ; identifierare = bokstav , { bokstav | siffra | "_" } ; S = { " " | "\n" | "\t" | "\r" | "\f" | "\b" } ; terminal = "'" , tecken - "'" , { tecken - "'" } , "'" | '"' , character - '"' , { character - '"' } , '"" ; terminator = ";" | "." ; term = "(" , S , rhs , S , ")" | "[ " , S , rhs , S , "]" | "{" , S , rhs , S , "}" | terminal | identifierare ; faktor = term , S , "?" | term , S , "*" | term , S , "+" | term , S , "-" , S , term | term , S ; sammanlänkning = ( S , faktor , S , "," ? ) + ; alternering = ( S , sammanlänkning , S , "|" ? ) + ; rhs = alternering ; lhs = identifierare ; regel = lhs , S , "=" , S , rhs , S , terminator ; grammatik = ( S , regel , S ) * ;
Pascal
Ett Pascal -liknande programmeringsspråk som endast tillåter tilldelningar kan definieras i EBNF enligt följande:
(* en enkel programsyntax i EBNF - Wikipedia *) program = 'PROGRAM' , blanksteg , identifierare , blanksteg , 'BEGIN' , blanksteg , { tilldelning , ";" , blanksteg }, 'END.' ; identifierare = alfabetiskt tecken , { alfabetiskt tecken | siffra } ; nummer = [ "-" ], siffra , { siffra } ; string = '"' , { alla tecken - '"' }, '"' ; tilldelning = identifierare , ":=" , ( nummer | identifierare | sträng ) ; alfabetiskt tecken = "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" ; siffra = "0" | " 1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" ; blanksteg = ? blanktecken ? ; alla tecken = ? alla synliga tecken ?;
Till exempel kan ett syntaktiskt korrekt program då vara:
PROGRAM DEMO1 BÖRJA A := 3 ; B := 45 ; H :=- 100023 ; C := A ; D123 := B34A ; BABUON := GIRAFF ; TEXT := " Hej världen !" ; SLUT .
Språket kan enkelt utökas med kontrollflöden , aritmetiska uttryck och Input/Output-instruktioner. Sedan skulle ett litet, användbart programmeringsspråk utvecklas.
Fördelar jämfört med BNF
Vilken grammatik som helst som definieras i EBNF kan också representeras i BNF, även om representationer i den senare i allmänhet är längre. Till exempel kan alternativ och upprepningar inte uttryckas direkt i BNF och kräver användning av en mellanregel eller alternativ produktion definierad som antingen ingenting eller valfri produktion för alternativ, eller antingen den upprepade produktionen av sig själv, rekursivt, för upprepning. Samma konstruktioner kan fortfarande användas i EBNF.
BNF använder symbolerna ( < , > , | , ::= ) för sig själv, men inkluderar inte citattecken runt terminalsträngar. Detta förhindrar att dessa tecken används i språken och kräver en speciell symbol för den tomma strängen. I EBNF terminaler strikt omgivna av citattecken ( " ... " eller ' ... ' ). Vinkelparenteserna (" < … > ") för icke-terminaler kan utelämnas.
BNF-syntax kan bara representera en regel på en rad, medan i EBNF ett avslutande tecken, semikolontecknet “ ; ” markerar slutet på en regel.
Dessutom inkluderar EBNF mekanismer för förbättringar, definiera antalet repetitioner, utesluta alternativ, kommentarer etc.
Konventioner
- Enligt avsnitt 4 i ISO/IEC 14977-standarden används följande konventioner:
- Varje meta-identifierare av Extended BNF skrivs som ett eller flera ord sammanfogade med bindestreck . Men att förena orden verkar endast gälla för hänvisningar till meta-identifierare utanför själva metaspråket, vilket framgår av exemplen på standarden.
- En meta-identifierare som slutar med -symbol är namnet på en terminalsymbol för Extended BNF.
- Det normala tecknet som representerar varje operatör av Extended BNF och dess underförstådda prioritet är (högsta prioritet överst):
* upprepningssymbol - utom-symbol , sammanfoga-symbol | definition-separator-symbol = definierande symbol ; terminator-symbol . terminator-symbol
- Den normala företrädet åsidosätts av följande paren av parentes:Det första citattecken är apostrof som definieras av ISO/IEC 646:1991, det vill säga Unicode U+0027 (
(* start-kommentar-symbol slutkommentar-symbol *) ' första-citat-symbol första-citat-symbol ' ( start-grupp-symbol slut-grupp-symbol ) [ start-alternativ-symbol slut-alternativ-symbol ] { start-repeat-symbol end-repeat-symbol } ? special-sekvens-symbol special-sekvens-symbol ? " andra-citat-symbol andra-citat-symbol "
'); teckensnittet som används i ISO/IEC 14977:1996(E) gör det väldigt likt det akuta, Unicode U+00B4 ( ´ ),såförvirring uppstår ibland. ISO Extended BNF-standarden åberopar dock ISO/IEC 646:1991, "ISO 7-bitars kodad teckenuppsättning för informationsutbyte", som en normativ referens och nämner inte några andra teckenuppsättningar, så formellt finns det ingen förväxling med Unicode-tecken utanför 7-bitars ASCII-intervallet.
Som exempel illustrerar följande syntaxregler möjligheterna för att uttrycka upprepning:
aa = "A" ; bb = 3 * aa , "B" ; cc = 3 * [ aa ], "C" ; dd = { aa }, "D" ; ee = aa , { aa }, "E" ; ff = 3 * aa , 3 * [ aa ], "F" ; gg = { 3 * aa }, "G" ;
Terminalsträngar som definieras av dessa regler är följande:
aa: A bb: AAAB cc: C AC AAC AAAC dd: D AD AAD AAAD AAAAD etc. ee: AE AAE AAAE AAAAE AAAAAE etc. ff: AAAF AAAAF AAAAAF AAAAAAF gg: G AAAG AAAAAAG osv.
Sträckbarhet
Enligt ISO 14977-standarden är EBNF tänkt att vara utbyggbar och två anläggningar nämns. Den första är en del av EBNF grammatik, den speciella sekvensen, som är godtycklig text omsluten av frågetecken. Tolkningen av texten i en speciell sekvens ligger utanför ramen för EBNF-standarden. Till exempel kan mellanslagstecknet definieras av följande regel:
mellanslag = ? ASCII-tecken 32 ? ;
Den andra möjligheten för förlängning använder det faktum att parenteser i EBNF inte kan placeras bredvid identifierare (de måste sammanfogas med dem). Följande är giltigt EBNF:
något = foo , ( bar );
Följande är inte giltigt EBNF:
något = foo ( bar );
Därför skulle en förlängning av EBNF kunna använda den notationen. Till exempel, i en Lisp grammatik, kan funktionsapplikation definieras av följande regel:
funktion applikation = lista ( symbol , { uttryck } );
Relaterat arbete
- W3C publicerar en EBNF - notation .
- W3C använde en annan EBNF för att specificera XML- syntaxen .
- British Standards Institution publicerade en standard för en EBNF: BS 6154 1981.
- IETF använder förstärkt BNF ( ABNF), specificerat i RFC 5234 .
Se även
- Meta-II – Ett tidigt kompilatorskrivverktyg och notation
- Frasstrukturregler – Den direkta motsvarigheten till EBNF i naturliga språk
- Vanligt uttryck
- Spirit Parser Framework
externa länkar
- ISO/IEC 14977: 1996(E)
- BNF/EBNF-varianter – En tabell av Pete Jinks som jämför flera syntaxer