Udvidet Backus Form - Naura

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 20. februar 2015; checks kræver 12 redigeringer .

The Extended Backus – Naur Form ( EBNF ) er et formelt syntaksdefinitionssystem, hvor nogle syntaktiske kategorier er sekventielt defineret gennem andre . Bruges til at beskrive kontekstfri formelle grammatikker . Foreslået af Niklaus Wirth . Det er en udvidet bearbejdning af Backus-Naur formerne , adskiller sig fra BNF i mere "rummelige" konstruktioner, som med samme udtryksevne gør det muligt at forenkle og reducere beskrivelsen i volumen.

Der anvendes dog mange forskellige varianter af RBNF. Den Internationale Standardiseringsorganisation har vedtaget RBNF-standarden: ISO/IEC 14977 [1] .

Beskrivelse

Terminaler og ikke-terminaler

Som i BNF er en grammatikbeskrivelse i RBNF et sæt regler, der definerer relationer mellem terminalsymboler (terminaler) og ikke-terminale symboler (ikke-terminaler).

Terminalsymboler er minimale grammatikelementer, der ikke har deres egen grammatiske struktur. I RBNF er terminaltegn enten foruddefinerede identifikatorer (navne, der anses for at være givet for en given grammatikbeskrivelse) eller strenge, sekvenser af tegn omgivet af anførselstegn eller apostrof.
Ikke-terminale symboler er grammatikelementer, der har deres egne navne og struktur. Hvert ikke-terminalsymbol består af et eller flere terminal- og/eller ikke-terminalsymboler, hvis kombination er bestemt af grammatikreglerne. I RBNF har hvert ikke-terminal symbol et navn, som er en streng af tegn.

Regler

Reglen i RBNF er:

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

hvor identifikatoren er navnet på et ikke-terminalt symbol, og udtrykket er en kombination af terminal- og ikke-terminalsymboler og specialtegn, der overholder RBNF-reglerne. Prikken i slutningen er et specialtegn, der angiver slutningen af reglen.

RBNF-reglens semantik er, at det ikke-terminale tegn angivet af identifikatoren til venstre for lighedstegnet er en kombination af terminale og ikke-terminale tegn defineret af et udtryk .

En komplet grammatikbeskrivelse er et sæt regler, der sekventielt definerer alle ikke-terminale symboler i grammatikken, således at hvert ikke-terminalsymbol kan reduceres til en kombination af terminalsymboler ved successiv (rekursiv) anvendelse af reglerne. Der er ingen særlige regler i definitionen af RBNF vedrørende den rækkefølge, reglerne er skrevet i, selvom sådanne forskrifter kan indføres ved brug af RBNF af softwareværktøjer, der giver automatisk generering af parsere fra en grammatikbeskrivelse.

Udtryk

Sættet af mulige RBNF-konstruktioner er meget lille. Disse er sammenkædning, selektion, betinget forekomst og gentagelse.

Sammenkædning. Defineret af symbolet "," (komma). Formreglen A = B,C.betyder, at det ikke-terminale A består af to tegn - B og C. Sammenkædningselementer kaldes også syntaktiske faktorer, eller blot faktorer. I dette eksempel er B og C syntaktiske faktorer.
Valg. Angivet med en lodret streg. Formreglen A = B|C|D.betyder, at den ikke-terminale A kan bestå af enten B, eller C eller D. Valgelementer kaldes også syntaktiske termer eller blot termer. I dette eksempel er B, C, D syntaktiske udtryk.
Betinget adgang. Firkantede parenteser markerer et valgfrit element i udtrykket, som kan være til stede eller ikke. Formreglen A = [B].betyder, at den ikke-terminale A enten er tom eller består af tegnet B.
Gentagelse. Krøllede parenteser angiver sammenkædningen af et hvilket som helst tal (inklusive nul) af elementerne skrevet i det. Formreglen A = {B}.betyder, at A enten er tom eller er en sammenkædning af et vilkårligt antal B-tegn (det vil sige, at A enten er et tomt element, eller B, eller BB, eller BBB, og så videre). Hvis du ønsker, at A skal være enten B eller et vilkårligt tal B, men ikke kan være tomt, skal du bruge notationenA = B{B}.
Ud over de grundlæggende operationer kan RBNF bruge almindelige parenteser. De bruges til at gruppere elementer, når de danner komplekse udtryk. For eksempel reglen A = (B|C)(D|E). angiver, at A består af to tegn, hvoraf det første er enten B eller C, det andet er enten D eller E, det vil sige, A kan være en af strengene BD, BE, CD, CE.
ikke almindelig! Det giver også nogle gange mening at bruge negation. For eksempel betyder A = (B|D)!C, at A kan være B eller D, men ikke BC eller DC. Denne mulighed giver os mulighed for klart at skelne A fra G = (B|D)C og forenkle parsingproceduren.
ikke almindelig! Definitionen af et ciffer omfatter 10 tegn - fra '0' til '9'. Det er ret logisk at beskrive begrebet "cifre" ved opregning Digit = '0' | '1' | '2' | ... | '9':. Du kan også definere begrebet "symbol".

Eller alt ovenstående kort sagt:

lexeme "::=" dens beskrivelse (eller "=")
'...' - tekstelement - tegn eller gruppe af tegn
A, B - element A efterfulgt af element B (sammenkædning)
A | B - enten element A eller B (valg)
[A] — element A er inkluderet eller ikke inkluderet (betinget forekomst)
{A} - nul eller flere elementer af A (gentagende)
(AB) - gruppering af elementer

Syntaksindstillinger

Nogle værker indeholder modificerede varianter af RBNF-syntaksen.

Du kan finde brugen af symbolet " ::=" i stedet for " =" i reglerne (i analogi med BNF).
Nogle gange angives sammenkædning i udtryk ikke med en simpel sekvens af tegn efter hinanden, men med et komma. I dette tilfælde skal flere ord adskilt af mellemrum forstås som ét flerordsnavn på et ikke-terminalt symbol. For eksempel:

Betinget sætning = "HVIS" , boolsk udtryk , "SÅ" , erklæringsgruppe , { "ELSIF" , boolsk udtryk , " THEN" , erklæringsgruppe }, [ " ELSE" , erklæringsgruppe ] , " ENDIF "

— en regel, der specificerer grammatikken for den betingede operator af Modula-2 sproget , hvor "Betinget operator" og "Group of operators" er ikke-terminale symboler med sammensatte navne.

BSI standard. EBNF-standarden, der blev vedtaget i 1981 af British Standards Institution (BSI), adskiller sig fra versionen foreslået af Wirth på følgende måder:
- sammenkædning er angivet med et komma;
- slutningen af regeldefinitionen er angivet med et semikolon;
- Mellemrum i en regel, bortset fra dem, der er anført i anførselstegn, anses for at være uvæsentlige.

Konstruktionseksempler

Formel selvbestemmelse af RBNF

Den generelle form for en EBNF-beskrivelsesgrammatik kan beskrives som EBNF som følger:

Syntaks = { SynthOperator }. SynthOperator = Identifikator "=" SynthExpression "." . SyntExpression = SynTerm { "|" SinTerm }. SynTerm = SyntFactor { SyntFactor }. SynthFactor = identifikator | kæde | "(" SynthExpression ")" | "[" SynthExpression "]" | "{" SynthExpression "}" .

Denne beskrivelse antager, at identifikator og streng er foruddefinerede termer. Hvis det ønskes, er det ikke svært at skrive deres definition i RBNF, for dette behøver du kun at angive et bestemt alfabet og om nødvendigt yderligere begrænsninger for typen af identifikator.

Nummer og identifikator i RBNF

Følgende grammatikker definerer notationen af et generelt decimaltal (med et fortegn, en mulig brøkdel og en eksponent) og en typisk programmeringssprogsidentifikator (en sekvens af bogstaver, tal og understregninger, der starter med et bogstav).

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

Definitionen af det ikke-terminale bogstav er ikke givet her på grund af åbenhed og besværlighed - det repræsenterer et valg fra det accepterede alfabet.

RBNF og andre måder at beskrive formelle grammatikker på

RBNF og BNF

Lighederne og forskellene mellem BNF og RBNF er indlysende fra beskrivelsen. Forskellen består stort set i to hovedpunkter:

I RBNF er syntaksen for skriveregler blevet forenklet: Definitionstegnet “ ::=” er blevet erstattet med “ =”, og brugen af vinkelparenteser til at skelne mellem ikke-terminaler er blevet afskaffet. Som et resultat er muligheden for at navngive ikke-terminaler med verbose identifikatorer forsvundet, men posten er blevet kortere. I en modifikation af RBNF-syntaksen, der angiver sammenkædning med et komma, kan multiord-identifikatorer bruges.
RBNF introducerer to nye syntaktiske elementer: betinget forekomst (udtryk i firkantede parenteser) og gentagelse (udtryk i krøllede parenteser).

Der kan være forskellige meninger om succesen eller fiaskoen af den første ændring, men under alle omstændigheder påvirker det ikke formens udtryksmuligheder. Men den anden innovation er meget vigtig. Det tilføjer heller ikke fundamentalt nye udtryksmuligheder (alt, der er skrevet i RBNF, kan skrives tilstrækkeligt i almindelig BNF), men det reducerer og forenkler notationen markant.

Den største fordel ved RBNF frem for BNF er evnen til at beskrive simple gentagne konstruktioner af ubestemt længde (lister, strenge, sekvenser og så videre) uden rekursive regler. Fraværet af gentagelseskonstruktionen i BNF fører til, at enhver gentagelse skal defineres ved at indføre yderligere mellemliggende ikke-terminale symboler og rekursive regler, hvilket gør definitionen for stor og uklar. Beskrivelsen af gentagelser i EBNF viser sig at være både kortere og mere bekvem for menneskelig perception.

Som et eksempel kan du overveje reglerne, der definerer den ikke-terminale "liste", som er et sæt nul til et vilkårligt antal identifikatorer adskilt af kommaer (forudsat at tegnene "Højre parentes", "Venstre parentes", "Komma" og "Ident" "er allerede defineret).

Definitionen i RBNF omfatter kun én regel:

Liste = Venstre parentes [ Ident { Comma Ident }] Højre parentes .

Definitionen i BNF ser sådan ud:

Allerede fra dette eksempel er forskellene mellem formerne synlige:

I BNF, i reglen, der definerer listen, er der to muligheder - for en tom liste og for enhver anden. I RBNF er behovet for en eksplicit beskrivelse af de to muligheder på grund af konstruktionen af betinget forekomst forsvundet.
I BNF var det nødvendigt at indføre en kunstig rekursiv regel IdentList for at beskrive en sekvens af identifikatorer adskilt af kommaer. I RBNF, på grund af konstruktionen af gentagelse, er dette fragment af syntaks skrevet direkte i hovedreglen og i en enklere form.
Da der kun er én RBNF-regel, dens længde er kortere, og den indeholder ikke varianter og rekursion, er den meget lettere at forstå. For at gendanne listens form i henhold til de givne beskrivelser, i tilfælde af en RBNF-beskrivelse, er det nok at sekventielt nedskrive værdierne af symbolerne, og for en BNF-beskrivelse skal du bestemme rækkefølgen i hvilke reglerne anvendes, og opbyg lister for hver mulighed (og der er to af dem i hver regel).

Naturligvis er prisen for fordelene ved RBNF frem for BNF den større kompleksitet ved automatisk fortolkning af RBNF-beskrivelser. Formelle grammatikparsergeneratorer, der bruger BNF, er enklere end dem, der bruger RBNF.

RBNF og syntaksdiagrammer

RBNF svarer til en underklasse af syntaksdiagrammer, der er meget brugt til at beskrive grammatikker. Enhver RBNF-grammatik kan repræsenteres tilstrækkeligt af et syntaksdiagram, men generelt giver syntaksdiagrammer dig mulighed for at oprette beskrivelser, der ikke kan repræsenteres i RBNF (eller under alle omstændigheder ikke kan oversættes direkte til RBNF uden først at konvertere den grafiske beskrivelse) .

Anvendelser, fordele og ulemper ved RBNF

RBNF er ligesom sin forgænger, BNF, ekstremt udbredt som et middel til at beskrive kunstige sprog, primært programmeringssprog og relaterede notationssystemer. Især opfinderen af RBNF, Niklaus Wirth, brugte denne formalisme i sine bøger til at beskrive alle de programmeringssprog, der betragtes der.

Den højere kompleksitet af RBNF sammenlignet med BNF fører til, at der er signifikant færre parser-generatorer baseret på RBNF end dem, der er baseret på BNF. Men de eksisterer og gælder. RBNF er grundlaget for Spirit C++ Parser Framework, Coco/R, SLK Parser Generator og nogle andre. Til brug i sådanne systemer udvides RBNF-syntaksen i samme retning som BNF-syntaksen, når du bruger yacc- eller bison -parser-generatorerne - koden, der behandler den, indsættes direkte i grammatikbeskrivelsen, og interaktion med den leksikale analysator er på en eller anden måde organiseret . Yderligere begrænsninger kan også blive pålagt reglernes opbygning - ikke alle regler, der kan beskrives i RBNF, kan effektivt konverteres til kode.

De absolutte fordele ved RBNF omfatter enkelhed (selve RBNF-sproget indeholder kun 10 specialtegn - tre typer parenteser, en lodret streg, et lighedstegn og anførselstegn, muligvis et komma; dets syntaks bestemmes af fem regler), tilstrækkelig styrke og synlighed, hvilket gør det bekvemt at lave beskrivelser, der ikke kun er beregnet til automatisk fortolkning, men også til menneskelig læsning. RBNF-konstruktionernes nærhed til syntaktiske diagrammer gør det muligt at trække sidstnævnte direkte fra RBNF-beskrivelsen.

Ulemperne ved RBNF, som faktisk ved BNF, omfatter det faktum, at de beskriver den grammatiske struktur af et formelt sprog uden at tage hensyn til kontekstuelle afhængigheder, hvilket betyder, at RBNF-beskrivelsen viser sig at være ufuldstændig i nærvær af sådanne afhængigheder. , og nogle syntaksregler for det beskrevne sprog skal angives i normal tekstform. Dette fører til, at tekst, der nøjagtigt matcher RBNF-grammatikken, stadig kan være syntaktisk forkert. For eksempel, i en RBNF grammatik, er det ikke muligt naturligt at repræsentere det faktum, at en operation kræver operander af samme type. Sådanne kontroller skal udføres ved hjælp af håndskrevet grammatikanalysatorkode. På den anden side viser grammatikbeskrivelsessystemer, der omfatter definitionen af kontekstafhængigheder, for eksempel van Wiingaardens grammatik , at være meget mere komplicerede, og deres anvendelse til automatisk generering af parsere viser sig at være vanskelig.

Noter

↑ ISO/ IEC 14977 . ISO / IEC (15. december 1996). Hentet 20. februar 2015. Arkiveret fra originalen 11. marts 2007.