Notacja EBNF

Rozszerzona notacja Backusa-Naura (ang. Extended Backus-Naur Form) – sposób wyrażenia gramatyki bezkontekstowej, czyli opisem języków formalnych. Jest rozszerzeniem notacji BNF.

Początkowo rozwijana przez Niklausa Wirtha, obecnie jest w użyciu wiele jej wariantów.

Międzynarodowa Organizacja Normalizacyjna (ISO) przyjęła standard ISO/IEC 14977.

Podstawy

Słowo opisywanego języka składa się z symboli terminalnych, czyli widocznych znaków, w tym cyfr, znaków interpunkcyjnych czy spacji.

EBNF określa reguły produkcji gdzie do symboli nieterminalnych przypisane są sekwencje symboli:

 cyfra bez zera = "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" ;
 cyfra          = "0" | cyfra bez zera ;

Ta reguła produkcji definiuje symbol nieterminalny cyfra, Znak "|" oddziela alternatywy, którymi są symbole terminalne w cudzysłowach a średnik kończy definicję.

Reguła może także zawierać sekwencję symboli terminalnych lub nieterminalnych, oddzielonych przecinkami:

 dwanaście                        = "1" , "2" ;
 dwieście jeden                   = "2" , "0" , "1" ;
 trzysta dwanaście                = "3" , dwanaście ;
 dwanaście tysięcy dwieście jeden = dwanaście , dwieście jeden ;

Wyrażenia które mogą być pomijane lub powtarzane można reprezentować biorąc je w nawiasy klamrowe { ... }:

 liczba naturalna = cyfra bez zera , { cyfra } ;

W tym wypadku ciągi 1, 2, ...,10,...,12345,... są poprawnymi wyrażeniami. Cokolwiek znajduje się w nawiasach klamrowych może być powtarzane dowolną liczbę razy, w tym ani razu (występuje zero lub wiele razy).

Wyrażenie opcjonalne (występuje jeden raz, lub nie występuje) reprezentujemy przez wzięcie je w nawiasy kwadratowe [ ... ]:

 liczba całkowita = "0" | [ "-" ] , liczba naturalna ;

Stąd liczba całkowita może być cyfrą zero lub ciągiem określonym przez liczba naturalna opcjonalnie poprzedzony znakiem minus.

Rozszerzenia zgodnie z normą ISO

Zgodnie z normą ISO 14977 standard EBNF ma być rozszerzalny. Wspomniano o dwóch udogodnieniach. Pierwsze jest częścią gramatyki EBNF, specjalną sekwencja, którą jest dowolny tekst ograniczony znakami zapytania, którego interpretacja jest poza zakresem standardu EBNF. Na przykład spacja może być zdefiniowana za pomocą następującej reguły:

 spacja = ? US-ASCII character 32 ?;

Drugim jest wykorzystanie faktu, że nawiasy nie mogą występować za identyfikatorem. Następująca definicja nie ma poprawnej składni EBNF:

 something = foo ( bar );

Więc ta notacja może być użyta do rozszerzenia EBNF. Na przykład w gramatyce Lispa funkcja application może być definiowana następująco:

 function application = list( symbol , [ { wyrażenie } ] );

Motywacja rozszerzenia BNF

Problemem BNF jest to, że nie można wyrazić bezpośrednio powtórzeń i wystąpień opcjonalnych. Zamiast tego mamy pośrednie reguły i rekurencyjny sposób definiowania powtórzeń i opcji. Możliwość takiego sposobu definicji mamy również w EBNF.

Opcja:

 liczba ze znakiem = [ znak , ] liczba ;

może być zdefiniowana w stylu BNF:

 liczba ze znakiem = znak , liczba | liczba ;

lub

 liczba ze znakiem = znak warunkowy , liczba ;
 znak warunkowy = ε | znak ; (* epsilon jest tu użyty do zaznaczenia pustej produkcji *)

Powtórzenia:

 liczba = { cyfra } ;

mogą być zdefiniowane w stylu BNF:

 liczba = cyfra | liczba cyfra;

Tabela symboli

Poniżej przedstawiono symbole użyte w standardzie.

Użycie	Zapis
definicja	=
złączenie	,
zakończenie	;
alternatywa	|
zawartość opcjonalna	[ ... ]
powtórzenie	{ ... }
grupowanie	( ... )
tekst dosłowny	" ... "
tekst dosłowny	' ... '
komentarz	(* ... *)
wyrażenie specjalne	? ... ?
wyjątek	-
wielokrotność	*

Dodatki i modyfikacje

Notacja EBNF eliminuje kilka wad BNF:

• BNF używa symboli (<, >, |, ::=) dla siebie; gdy pojawią się one w języku, który ma być definiowany, notacja BNF nie może być użyta bez modyfikacji i objaśnień.
• Składnia BNF może reprezentować wyłącznie jedną regułę w jednej linii.

EBNF rozwiązuje te problemy:

• Symbole terminalne są zamknięte pomiędzy znakami cudzysłowu ("..." lub '...'), a symbole w sekwencji rozdzielane przecinkami. Ostre nawiasy ("<...>") dla symboli nieterminalnych mogą zostać pominięte.
• Każdą regułę kończy znak ograniczający – według normy średnik.

Ponadto istnieją mechanizmy ulepszenia definiujące liczbę powtórzeń, wyłączanie (np. wszystkie znaki bez cudzysłowów), komentarze.

Pomimo ulepszeń EBNF nie jest "silniejszy" w rozumieniu języka, który może definiować. Gramatyka zdefiniowana w EBNF może być również reprezentowana w BNF.

Przykład

Prosty język programowania, który pozwala jedynie na przypisywanie, może być zdefiniowany w EBNF następująco:

 (* a simple program in EBNF − Wikipedia *)
 program = 'PROGRAM' , white space , identifier , white space ,
            'BEGIN' , white space ,
            { assignment , ";" , white space } ,
            'END.' ;
 identifier = alphabetic character , { alphabetic character | digit } ;
 number = [ "-" ] , digit , { digit } ;
 string = '"' , { all characters − '"' } , '"' ;
 assignment = identifier , ":=" , ( number | identifier | string ) ;
 alphabetic character = "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 = ? white space characters ? ;
 all characters = ? all visible characters ? ;

Syntaktycznie poprawnym programem będzie:

PROGRAM DEMO1
BEGIN
  A0:=3;
  B:=45;
  H:=-100023;
  C:=A;
  D123:=B34A;
  BABOON:=GIRAFFE;
  TEXT:="Hello world!";
END.