From Wikipedia, the free encyclopedia
Indenfor datalogi er udvidet Backus-Naur form (engelsk extended Backus–Naur form (EBNF)) en familie af metasyntaksnotationer - og enhver af disse kan anvendes til at udtrykke en kontekstfri grammatik. EBNF anvendes til at lave en formel syntaksbeskrivelse af et formelt sprog såsom et programmeringssprog til computere. EBNF er udvidelser til Backus-Naur form (BNF) metasyntaksnotation.
De tidligste EBNF blev udviklet af Niklaus Wirth og indarbejdede nogle af begreberne (med en anden syntaks og notation) fra Wirth syntax notation. Men mange EBNF-varianter er i brug.[1] International Organization for Standardization vedtog en EBNF-standard (ISO/IEC 14977) i 1996.[2]
Ifølge Vadim Zaytsev bidrog standarden med citat only ended up adding yet another three dialects to the chaos og gjorde opmærksom på mangel på succes, og han gjorde opmærksom på at ISO EBNF ikke en gang blev anvendt i alle ISO standarder. David A. Wheeler argumenterer imod at anvende ISO-standarden når man skal anvende EBNF - og anbefaler at alternative EBNF-notationer overvejes såsom en af W3C Extensible Markup Language (XML) 1.0 (Fifth Edition).[3][4][5]
Denne artikel anvender EBNF som specificeret af ISO i eksempler, der gælder for alle EBNF'er. Andre EBNF-varianter anvender lidt andre syntaktiske konventioner.
EBNF kan både anvendes i den leksikalsk analyse og i parseren. (leksikalsk analyse splitter input-tekststrengen op i tokens ("sprogatomer", leksemer) og fjerner typisk whitespace og kodekommentarer.)
Selv EBNF kan beskrives ved at anvende EBNF. Betragt den skitserede grammatik herunder baseret på ASCII-tegnsættet (derfor ingen ÆØÅ).
Den leksikalske analyse gør følgende: Input (tegn) fås fra en tekstfil. Output-parsetræet er følge af tokens med metadata (whitespace og kommentarer smides typisk ud):
letter = "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" | "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" ;
digit = "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" ;
symbol_no_quotes_questionmark =
"[" | "]" | "{" | "}" | "(" | ")" | "<" | ">"
| "=" | "|" | "." | "," | ";" ;
visible_characters_no_quotes_questionmark =
letter | digit | symbol_no_quotes_questionmark | " " | "_" ;
visible_characters_no_quotes = visible_characters_no_quotes_questionmark | "?" ;
visible_characters_no_questionmark = visible_characters_no_quotes_questionmark | "'" | '"' ;
visible_characters = visible_characters_no_questionmark | "?" ;
white_space = "\t" | "\n" | "\r" | " " ;
identifier = letter , { letter | digit | "_" } ;
free-text-special-terminal =
"?" , visible_characters_no_questionmark
, { visible_characters_no_questionmark } , "?"
terminal = "'" , ( visible_characters_no_quotes | '"' )
, { ( visible_characters_no_quotes | '"' ) } , "'"
| '"' , ( visible_characters_no_quotes | "'" )
, { ( visible_characters_no_quotes | "'" ) } , '"'
| free-text-special-terminal ;
token = symbol_no_quotes_questionmark | identifier | terminal | free-text-special-terminal ;
comment = "(*" , visible_characters , { visible_characters } , "*)" ;
comment_or_whitespace = white_space | comment ;
grammar = { comment_or_whitespace } , { token , { comment_or_whitespace } } ;
Parser: Input (tokens) fås fra den ovenstående leksikalske analyse. Output er et parsetræ:
expression = identifier
| terminal
| "[" , expression , "]"
| "{" , expression , "}"
| "(" , expression , ")"
| expression , "|" , expression
| expression , "," , expression ;
lhs = identifier ;
rule = lhs , "=" , expression , ";" ;
grammar = { rule } ;
Et Pascal-lignende programmeringssprog, som kun tillader tildelinger, kan defineres i EBNF med ASCII-tegnsættet som følger.
Leksikalsk analyse: Input (tegn) fås fra en tekstfil. Output-parsetræet er en følge af tokens med metadata (whitespace smides typisk ud):
letter = "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" ;
digit = "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" ;
white_space = "\t" | "\n" | "\r" | " " ;
symbol_no_quotes = "[" | "]" | "{" | "}" | "(" | ")" | "<" | ">"
| "=" | "|" | "." | "," | ";" | ":=" ;
visible_characters_no_quotes = letter | digit | symbol_no_quotes | " " ;
identifier = letter , { letter | digit } ;
number = [ "-" ] , digit , { digit } ;
textstring = '"' , { visible_characters_no_quotes | "'" } , '"' ;
token = symbol_no_quotes | identifier | number | textstring ;
grammar = { white_space } , { token , { white_space } } ;
Parser: Input (tokens) fås fra den ovenstående leksikalske analyse. Output er et parsetræ:
assignment = identifier , ":=" , ( number | identifier | textstring ) ;
program = 'PROGRAM', identifier,
'BEGIN',
{ assignment, ";" } ,
'END.' ;
Fx kunne et syntaktisk korrekt program se således ud:
PROGRAM DEMO1
BEGIN
A:=3;
B:=45;
H:=-100023;
C:=A;
D123:=B34A;
BABOON:=GIRAFFE;
TEXT:="Hello world!";
END.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.