Notacja Backusa-Naura jest sposobem zapisu reguł gramatyki bezkontekstowej, czyli sposobem opisu języków formalnych.
Notacja ta jest powszechnie używana w informatyce do zapisu składni języków programowania iprotokołów komunikacyjnych. Została wymyślona przez Johna Backusa w latach 50. w czasie prac nad językiem Fortran, a następnie zmodyfikowana przez Petera Naura i użyta do zdefiniowania składni języka Algol.
Notacja BNF jest zestawem reguł produkcji o następującej postaci:
- <symbol> ::= <wyrażenie zawierające symbole>
Znaczenie użytych tu symboli jest następujące:
- < – lewy ogranicznik wyrażenia
- > – prawy ogranicznik wyrażenia
- ::= – jest zdefiniowane jako
- | – lub
Cztery powyższe symbole to symbole metajęzyka – ich znaczenie nie jest określone w języku, który określają.
O innych symbolach występujących w regułach produkcji zakładamy, że należą do alfabetu języka lub samego języka.
Przykład
Aby przy pomocy notacji BNF określić liczbę naturalną, można użyć następujących reguł:
- <zero>::= 0
- <cyfra niezerowa>::= 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
- <cyfra>::= <zero> | <cyfra niezerowa>
- <liczba naturalna>::= <zero> | <cyfra niezerowa> | <cyfra niezerowa><liczba naturalna>
Wyjaśnienie: definicja ta jest rekurencyjna – liczba naturalna jest zdefiniowana przez odwołanie się do pojęcia liczby naturalnej. Jest to jednak poprawne określenie, albowiem produkcja 4 mówi, że liczbą naturalną jest: zero lub cyfra niezerowa lub (uprzednio zdefiniowana) liczba naturalna poprzedzona cyfrą niezerową. Ostatecznie, pod pojęciem liczby naturalnej wg powyższego określenia należy rozumieć dowolny ciąg cyfr, rozpoczynający się od cyfry niezerowej.
Notacja dla języka PASCAL (interpretowanego w projekcie)
OZNACZENIA:
::= - przypisanie
[] - element może wystąpić 0 lub 1 raz (co najwyżej 1 raz)
{} - wybierz jeden z elementów występujących (dokładnie 1 raz)
{}+ - element musi wystąpić co najmniej 1 raz (1 lub więcej razy)
{}* - element może wystąpić 0 lub więcej razy (0 lub więcej razy)
<> - zostało zdefiniowane wcześniej
NOTACJA:
1. Podstawy
cyfra::={0|1|2|3|4|5|6|7|8|9}
liczba_calk::=< cyfra >{< cyfra >}*
liczba_rzecz::={< cyfra >}+< separator_dzies >{< cyfra >}*
liczba::={< liczba_calk >|< liczba_rzecz >}
mala_litera::={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}
duza_litera::={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}
litera::={< mala_litera >|< duza_litera >}
inny_symbol::={~|!|@|#|$|%|^|&|*|(|)|_|+|=|-|:|'|.|,|>|<|?|/|\}
znak::={< cyfra >|< litera >| _}
tekst::={ < znak > | < inny_symbol > }*
separator_dzies::={ .}
przecinek::= { ,}
srednik::= { ;}
dwukropek::= { :}
czudzyslow::= { "}
klamra_l::= { :}
klamra_p::={ :}
spacja::={ }
2. Operatory
operator_arytmetyczny::={ +|-|*|/ }
operator_relacji::={ <|>|=|>=|<=|<> }
operator_przypisania::={:=}
3. Słowa kluczowe
s_and::={and}
s_begin::={begin}
s_const::={const}
s_do::={do}
s_else::={else}
s_end::={end}
s_for::={for}
s_if::={if}
s_or::={or}
s_program::={program}
s_then={then}
s_to::={to}
s_var::={var}
4. Operacje
zmienna::=< litera >{< znak >}*
typ::={integer|real}
deklaracja_zmiennych::=< zmienna >{< przecinek >< zmienna >}* < dwukropek >< typ >< srednik >
wartosc::={< liczba >|< zmienna >}
operacja_arytmetyczna::=< wartosc >{< operator_arytmetyczny >< wartosc >}*
operacja_relacji::=< wartosc >< operator_relacji >< wartosc >
operacja_przypisania::=< zmienna >< operator_przypisania >{< liczba >|< zmienna >|< wyrazenie_arytmetyczne >}
wynik::=< zmienna >< operator >< zmienna >< srednik >
warunek::={{< wartosc >< operator_relacji >< wartosc >}|{< zmienna >< s_and >< zmienna >}|{< zmienna >< s_or >< zmienna >}|{< zmienna >< s_not >< zmienna >}}
petla_for::=< s_for >< zmienna >< operator_przypisania >{< liczba_calk >|< zmienna >|< operacja_arytmetyczna >}< s_to >{< liczba_calk >|< zmienna >|< operacja_arytmetyczna >}< s_do >< instrukcja_zlozona >
instrukcja_prosta::={< zmienna >< przypisanie >< zmienna >< separator > |< zmienna >< wynik >< srednik >}
instrukcja_warunkowa::={ < s_if > < s_then >< instrukcja_zlozona > | < instrukcja_prosta >)
instrukcja_zlozona::=< s_begin >{< instrukcja_prosta >}* |{< petla_for >}* {< instrukcja warkunkowa >}*
komentarz::= < klamra_l >{ < tekst >< spacja >}*< klamra_p >
4. WE/WY
o_read::={read}
o_readln::={readln}
o_write::={write}
o_writeln::={writeln}
wczytywanie_zmiennych::={< o_read >< zmienna >< srednik > |< o_readln >< zmienna >< srednik >}
wypisywanie::={< o_write >< cudzyslow >< tekst >< cudzyslow >< srednik >|< cudzyslow >< teks >< cudzyslow >< srednik >}
4. program
def_programu::= {< s_program >< nazwa >< srednik >} [< s_const >{< nazwa >< operator_przypisania >{< liczba >|< tekst >< separator >}}+] [< s_var >{< zmienna >}+] {< operacja_przypisania >|< wypisywanie >|< wczytywanie_zmiennych >|< instrukcja_prosta >|< instrukcja_zlozona >}* < s_end >'.'