Extended Backus Form - Naura

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 20 februari 2015; kontroller kräver 12 redigeringar .

The Extended Backus – Naur Form ( EBNF ) är ett formellt syntaxdefinitionssystem där vissa syntaktiska kategorier definieras sekventiellt genom andra . Används för att beskriva kontextfria formella grammatiker . Föreslagen av Niklaus Wirth . Det är en utökad bearbetning av Backus-Naur-formerna , skiljer sig från BNF i mer "rymliga" konstruktioner, som med samma uttrycksförmåga gör det möjligt att förenkla och reducera beskrivningen i volym.

Men många olika varianter av RBNF används. International Organization for Standardization har antagit RBNF-standarden: ISO/IEC 14977 [1] .

Beskrivning

Terminaler och icke-terminaler

Liksom i BNF är en grammatikbeskrivning i RBNF en uppsättning regler som definierar relationer mellan terminalsymboler (terminaler) och icke-terminala symboler (icke-terminaler).

Terminalsymboler är minimala grammatikelement som inte har sin egen grammatiska struktur. I RBNF är terminaltecken antingen fördefinierade identifierare (namn som anses vara givna för en given grammatikbeskrivning) eller strängar, sekvenser av tecken omslutna av citattecken eller apostrof.
Icke-terminala symboler är grammatikelement som har sina egna namn och struktur. Varje icke-terminalsymbol består av en eller flera terminal- och/eller icke-terminalsymboler, vars kombination bestäms av grammatikreglerna. I RBNF har varje icke-terminal symbol ett namn, vilket är en teckensträng.

Regler

Regeln i RBNF är:

идентификатор = выражение.

där identifieraren är namnet på en icke-terminal symbol, och uttrycket är en kombination av terminala och icke-terminala symboler och specialtecken som överensstämmer med RBNF-reglerna. Punkten i slutet är ett specialtecken som indikerar slutet på regeln.

Semantiken för RBNF-regeln är att det icke-terminala tecknet som anges av identifieraren till vänster om likhetstecknet är en kombination av terminala och icke-terminala tecken som definieras av ett uttryck .

En fullständig grammatikbeskrivning är en uppsättning regler som sekventiellt definierar alla icke-terminala symboler i grammatiken så att varje icke-terminal symbol kan reduceras till en kombination av terminalsymboler genom successiv (rekursiv) tillämpning av reglerna. Det finns inga särskilda regler i definitionen av RBNF angående i vilken ordning reglerna skrivs, även om sådana föreskrifter kan införas när man använder RBNF av mjukvaruverktyg som ger automatisk generering av parsers från en grammatikbeskrivning.

Uttryck

Uppsättningen av möjliga RBNF-konstruktioner är mycket liten. Dessa är sammanlänkning, urval, villkorad förekomst och upprepning.

Sammankoppling. Definieras av symbolen "," (komma). Formregeln A = B,C.innebär att det icke-terminala A består av två tecken - B och C. Sammankopplingselement kallas också för syntaktiska faktorer, eller helt enkelt faktorer. I detta exempel är B och C syntaktiska faktorer.
Val. Indikeras med en vertikal stapel. Formregeln A = B|C|D.innebär att det icke-terminala A kan bestå av antingen B, eller C eller D. Valelement kallas också syntaktiska termer, eller helt enkelt termer. I detta exempel är B, C, D syntaktiska termer.
Villkorligt inträde. Hakparenteser markerar ett valfritt element i uttrycket, som kanske finns eller inte. Formregeln A = [B].innebär att icke-terminal A antingen är tom eller består av tecknet B.
Upprepning. Lockiga parenteser betecknar sammanlänkningen av ett valfritt antal (inklusive noll) av elementen som skrivits i den. Formregeln A = {B}.betyder att A antingen är tom eller är en sammanlänkning av valfritt antal B-tecken (det vill säga, A är antingen ett tomt element, eller B, eller BB, eller BBB, och så vidare). Om du vill att A ska vara antingen B eller ett godtyckligt tal B, men inte kan vara tomt, använd notationenA = B{B}.
Utöver de grundläggande operationerna kan RBNF använda vanliga parenteser. De används för att gruppera element när man formar komplexa uttryck. Till exempel regeln A = (B|C)(D|E). anger att A består av två tecken, varav det första är antingen B eller C, det andra är antingen D eller E, det vill säga A kan vara en av strängarna BD, BE, CD, CE.
inte vanlig! Ibland är det också meningsfullt att använda negation. Till exempel betyder A = (B|D)!C att A kan vara B eller D, men inte BC eller DC. Det här alternativet tillåter oss att tydligt skilja A från G = (B|D)C och förenkla analysproceduren.
inte vanlig! Definitionen av en siffra innehåller 10 tecken - från '0' till '9'. Det är ganska logiskt att beskriva begreppet "siffra" genom uppräkning Digit = '0' | '1' | '2' | ... | '9':. Du kan också definiera begreppet "symbol".

Eller allt ovanstående kort och gott:

lexem "::=" dess beskrivning (eller "=")
'...' - textelement - tecken eller grupp av tecken
A, B - element A följt av element B (sammansättning)
A | B - antingen element A eller B (val)
[A] — element A ingår eller ingår inte (villkorlig förekomst)
{A} - noll eller fler element av A (upprepande)
(AB) - gruppering av element

Syntaxalternativ

Vissa verk innehåller modifierade varianter av RBNF-syntaxen.

Du kan hitta användningen av symbolen " ::=" istället för " =" i reglerna (i analogi med BNF).
Ibland indikeras sammanlänkning i uttryck inte med en enkel sekvens av tecken efter varandra, utan med ett kommatecken. I det här fallet bör flera ord separerade med mellanslag förstås som ett flerordsnamn på en icke-terminal symbol. Till exempel:

Villkorlig sats = "IF" , booleskt uttryck , "THEN" , satsgrupp , { "ELSIF" , booleskt uttryck , " DÅ" , satsgrupp }, [ "ANSÅ" , satsgrupp ] , " ENDIF "

— En regel som specificerar grammatiken för den villkorliga operatorn för Modula-2- språket , där "Villkorlig operator" och "Group of operators" är icke-terminala symboler med sammansatta namn.

BSI standard. EBNF-standarden, som antogs 1981 av British Standards Institution (BSI), skiljer sig från versionen som föreslagits av Wirth på följande sätt:
- sammanlänkning indikeras med kommatecken;
- slutet av regeldefinitionen indikeras med semikolon;
- mellanslag i en regel, andra än de inom citattecken, anses vara oviktiga.

Konstruktionsexempel

Formell självbestämmande av RBNF

Den allmänna formen av en EBNF-beskrivningsgrammatik kan beskrivas som EBNF enligt följande:

Syntax = { SynthOperator }. SynthOperator = Identifier "=" SynthExpression "." . SyntExpression = SynTerm { "|" SinTerm }. SynTerm = SyntFactor { SyntFactor }. SynthFactor = identifierare | kedja | "(" SynthExpression ")" | "[" SynthExpression "]" | "{" SynthExpression "}" .

Denna beskrivning förutsätter att identifierare och sträng är fördefinierade termer. Om så önskas är det inte svårt att skriva deras definition i RBNF, för detta behöver du bara ange ett visst alfabet och, om nödvändigt, ytterligare begränsningar för typen av identifierare.

Nummer och identifierare i RBNF

Följande grammatiker definierar notationen av ett allmänt decimaltal (med ett inledande tecken, en möjlig bråkdel och en exponent) och en typisk programmeringsspråksidentifierare (en sekvens av bokstäver, siffror och understreck som börjar med en bokstav).

Tal = [ "+" | "-" ] NatNumber [ "." [ NatNumber ]][( "e" | "E" )[ "+" | "-" ] NatNumber ]. NatNumber = Siffra { Siffra }. Siffra = "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" . Ident = Bokstav { Bokstav | Siffra | "_" }.

Definitionen av den icke-terminala bokstaven ges inte här på grund av självklarhet och krånglighet - den representerar ett val från det accepterade alfabetet.

RBNF och andra sätt att beskriva formella grammatiker

RBNF och BNF

Likheterna och skillnaderna mellan BNF och RBNF framgår av beskrivningen. Skillnaden består i stort sett i två huvudpunkter:

I RBNF har syntaxen för skrivregler förenklats: definitionstecknet " ::=" har ersatts med " =", och användningen av vinkelparenteser för att särskilja icke-terminaler har avskaffats. Som ett resultat har möjligheten att namnge icke-terminaler med utförliga identifierare försvunnit, men posten har blivit kortare. I en modifiering av RBNF-syntaxen som betecknar sammanlänkning med ett kommatecken, kan flerordsidentifierare användas.
RBNF introducerar två nya syntaktiska element: villkorlig förekomst (uttryck inom hakparenteser) och upprepning (uttryck inom hakparenteser).

Det kan finnas olika åsikter om framgången eller misslyckandet med den första förändringen, men i vilket fall som helst påverkar det inte formens uttrycksmöjligheter. Men den andra innovationen är mycket betydelsefull. Det tillför inte heller i grunden nya uttrycksmöjligheter (allt som skrivs i RBNF kan skrivas adekvat i vanlig BNF), men det minskar och förenklar notationen avsevärt.

Den största fördelen med RBNF framför BNF är förmågan att beskriva enkla upprepande konstruktioner av obestämd längd (listor, strängar, sekvenser, och så vidare) utan rekursiva regler. Frånvaron av upprepningskonstruktionen i BNF leder till det faktum att varje upprepning måste definieras genom att införa ytterligare mellanliggande icke-terminala symboler och rekursiva regler, vilket gör definitionen för stor och oklar. Beskrivningen av upprepningar i EBNF visar sig vara både kortare och mer bekväm för människans uppfattning.

Som ett exempel, betrakta reglerna som definierar den icke-terminala "listan", som är en uppsättning av noll till valfritt antal identifierare separerade med kommatecken (förutsatt att tecknen "RightBracket", "LeftBracket", "Comma" och "Ident " är redan definierade).

Definitionen i RBNF innehåller bara en regel:

List = LeftBracket [ Ident { Comma Ident }] HögerBracket .

Definitionen i BNF ser ut så här:

Redan från detta exempel är skillnaderna mellan formerna synliga:

I BNF, i regeln som definierar listan, finns det två alternativ - för en tom lista och för vilken som helst annan. I RBNF har, på grund av konstruktionen av villkorad förekomst, behovet av en uttrycklig beskrivning av de två alternativen försvunnit.
I BNF krävdes det att införa en artificiell rekursiv regel IdentList för att beskriva en sekvens av identifierare separerade med kommatecken. I RBNF, på grund av konstruktionen av upprepning, skrivs detta syntaxfragment direkt i huvudregeln och i en enklare form.
Eftersom det bara finns en RBNF-regel, dess längd är kortare, och den innehåller inga varianter och rekursion, är det mycket lättare att förstå. För att återställa listans form enligt de givna beskrivningarna, i fallet med en RBNF-beskrivning, räcker det att sekventiellt skriva ner symbolernas värden, och för en BNF-beskrivning måste du bestämma ordningen i vilka reglerna tillämpas och bygga listor för varje alternativ (och det finns två av dem i varje regel).

Naturligtvis är priset för fördelarna med RBNF framför BNF den större komplexiteten i automatisk tolkning av RBNF-beskrivningar. Formella grammatikparsergeneratorer som använder BNF är enklare än de som använder RBNF.

RBNF och syntaxdiagram

RBNF är ekvivalenta med en underklass av syntaxdiagram som används allmänt för att beskriva grammatik. Vilken RBNF-grammatik som helst kan representeras på ett adekvat sätt av ett syntaxdiagram, men i allmänhet låter syntaxdiagram dig skapa beskrivningar som inte kan representeras i RBNF (eller i alla fall inte kan översättas till RBNF direkt utan att först konvertera den grafiska beskrivningen) .

Tillämpningar, fördelar och nackdelar med RBNF

RBNF, liksom sin föregångare, BNF, används extremt flitigt som ett sätt att beskriva konstgjorda språk, främst programmeringsspråk och relaterade notationssystem. I synnerhet använde uppfinnaren av RBNF, Niklaus Wirth, denna formalism i sina böcker för att beskriva alla programmeringsspråk som övervägdes där.

Den högre komplexiteten hos RBNF jämfört med BNF leder till att det finns betydligt färre parsergeneratorer baserade på RBNF än de baserade på BNF. Men de finns och gäller. RBNF är grunden för Spirit C++ Parser Framework, Coco/R, SLK Parser Generator och några andra. För användning i sådana system utökas RBNF-syntaxen i samma riktning som BNF-syntaxen när man använder yacc- eller bison -parsergeneratorerna - koden som bearbetar den infogas direkt i grammatikbeskrivningen, och interaktionen med den lexikala analysatorn är på något sätt organiserad . Ytterligare restriktioner kan också läggas på reglernas struktur - inte alla regler som kan beskrivas i RBNF kan effektivt omvandlas till kod.

De absoluta fördelarna med RBNF inkluderar enkelhet (RBNF-språket i sig innehåller endast 10 specialtecken - tre typer av parenteser, en vertikal stapel, ett likhetstecken och citattecken, eventuellt ett kommatecken; dess syntax bestäms av fem regler), tillräcklig kraft och synlighet, vilket gör det bekvämt att göra beskrivningar avsedda inte bara för automatisk tolkning, utan också för mänsklig läsning. RBNF-konstruktionernas närhet till syntaktiska diagram gör det möjligt att dra de senare direkt från RBNF-beskrivningen.

Nackdelarna med RBNF, liksom för BNF, inkluderar det faktum att de beskriver den grammatiska strukturen i ett formellt språk utan att ta hänsyn till kontextuella beroenden, vilket innebär att i närvaro av sådana beroenden visar sig RBNF-beskrivningen vara ofullständig. , och vissa syntaxregler för det beskrivna språket måste anges i normal textform. Detta leder till att text som exakt matchar RBNF-grammatiken fortfarande kan vara syntaktisk felaktig. Till exempel, i en RBNF-grammatik är det inte möjligt att naturligt representera det faktum att en operation kräver operander av samma typ. Sådana kontroller måste utföras med handskriven grammatikanalyskod. Å andra sidan visar sig grammatikbeskrivningssystem som inkluderar definitionen av kontextberoenden, till exempel van Wiingaardens grammatik , vara mycket mer komplicerade, och deras användning för automatisk generering av parsers visar sig vara svår.

Anteckningar

↑ ISO/ IEC 14977 . ISO / IEC (15 december 1996). Hämtad 20 februari 2015. Arkiverad från originalet 11 mars 2007.

Länkar

ISO/IEC 14977 (engelska) . Computer Laboratory . University of Cambridge (15 december 1996). Hämtad: 20 februari 2015.
Andrew Bushman. ISO/IEC 14977 (inofficiell översättning) . Lokalisering av ISO/IEC 14977:1996(E) (Utökad BNF) . Google Groups (21 juli 2013). Hämtad: 20 februari 2015. (obestämd)