Udvidet Backus-Naur form
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.)
Eksempler
Syntaksdiagrammer
EBNF
Selv EBNF kan beskrives ved at anvende EBNF. Betragt den skitserede grammatik herunder baseret på ASCII-tegnsættet (derfor ingen ÆØÅ).
Leksikalsk analyse
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
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 } ;
Pascal
Et Pascal-lignende programmeringssprog, som kun tillader tildelinger, kan defineres i EBNF med ASCII-tegnsættet som følger.
Leksikalsk analyse
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
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.
Se også
- Attributgrammatik - formelt sprog med semantisk databehandling
Referencer
- ^ Zaytsev, Vadim (marts 26-30, 2012). "BNF Was Here: What Have We Done About the Unnecessary Diversity of Notation for Syntactic Definitions?" (PDF). Proceedings of the 27th Annual ACM Symposium on Applied Computing (SAC '12). Riva del Garda, Italy. p. 1.CS1-vedligeholdelse: Dato-format (link)
- ^ ISO/IEC 14977
- ^ Extensible Markup Language (XML) 1.0 (Fifth Edition): 6 Notation, backup
- ^ dwheeler.com: Don’t Use ISO/IEC 14977 Extended Backus-Naur Form (EBNF). David A. Wheeler, backup
- ^ grammarware.net: BNF WAS HERE: What Have We Done About the Unnecessary Diversity of Notation for Syntactic Definitions. Vadim Zaytsev, backup
 | Spire Denne artikel om datalogi eller et datalogi-relateret emne er en spire som bør udbygges. Du er velkommen til at hjælpe Wikipedia ved at udvide den. |
Medier brugt på denne side