Udvidet Backus-Naur form

Fra Wikipedia, den frie encyklopædi
(Omdirigeret fra EBNF)

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[redigér | rediger kildetekst]

Syntaksdiagrammer[redigér | rediger kildetekst]

Et muligt EBNF syntaksdiagram.

EBNF[redigér | rediger kildetekst]

Selv EBNF kan beskrives ved at anvende EBNF. Betragt den skitserede grammatik herunder baseret på ASCII-tegnsættet (derfor ingen ÆØÅ).

Leksikalsk analyse[redigér | rediger kildetekst]

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[redigér | rediger kildetekst]

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[redigér | rediger kildetekst]

Et Pascal-lignende programmeringssprog, som kun tillader tildelinger, kan defineres i EBNF med ASCII-tegnsættet som følger.

Leksikalsk analyse[redigér | rediger kildetekst]

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[redigér | rediger kildetekst]

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å[redigér | rediger kildetekst]

Referencer[redigér | rediger kildetekst]

  1. ^ 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. s. 1.{{cite conference}}: CS1-vedligeholdelse: Dato-format (link)
  2. ^ ISO/IEC 14977
  3. ^ Extensible Markup Language (XML) 1.0 (Fifth Edition): 6 Notation, backup
  4. ^ dwheeler.com: Don’t Use ISO/IEC 14977 Extended Backus-Naur Form (EBNF). David A. Wheeler, backup
  5. ^ grammarware.net: BNF WAS HERE: What Have We Done About the Unnecessary Diversity of Notation for Syntactic Definitions. Vadim Zaytsev, backup


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