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. International Organization for Standardization vedtog en EBNF-standard (ISO/IEC 14977) i 1996.

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).

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

Et muligt EBNF syntaksdiagram.

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

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.