Notacja BNF

Notacja Backusa-Naura (ang. Backus-Naur Form, BNF) – metoda zapisu reguł gramatyki bezkontekstowej.

Definicja formalna

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 symbolu
• > – prawy ogranicznik symbolu
• ::= – 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łada się, ż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ł:

1. <zero>::= 0
   Przykład wartości: 0
2. <cyfra niezerowa>::= 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
   Przykład wartości: 1, 2, 3
3. <cyfra>::= <zero>| <cyfra niezerowa>
   Przykład wartości: 0, 1, 2, 3
4. <ciąg cyfr>::= <cyfra>| <cyfra><ciąg cyfr>
   Przykład wartości: 0, 1, 01, 23, 45, 99, 10023, 000001
5. <liczba naturalna>::= <cyfra>| <cyfra niezerowa><ciąg cyfr>
   Przykład wartości: 0, 1, 2, 34 56, 406, 556066

Wyjaśnienie: definicja ta jest rekurencyjna (w przeciwieństwie do iteracyjnej) – ciąg cyfr jest zdefiniowany przez odwołanie się do pojęcia ciągu cyfr. Jest to jednak poprawne określenie, bowiem produkcja 4 mówi, że ciągiem cyfr jest: cyfra lub cyfra i ciąg cyfr. Ostatecznie, pod pojęciem liczby naturalnej według powyższego określenia należy rozumieć dowolny ciąg cyfr, rozpoczynający się od cyfry niezerowej lub samo zero.

Na podobnej zasadzie, wykorzystując powyższe definicje, można zdefiniować liczbę zmiennoprzecinkową:

1. <przecinek>::=, | .
   Przykład wartości:,,.
2. <liczba zmiennoprzecinkowa>::= <liczba naturalna>| <liczba naturalna><przecinek><ciąg cyfr>
   Przykład wartości: 0, 12, 12.1, 12,09

Idąc tą drogą można zdefiniować punkt, wektor, liczbę zespoloną itd.

Zastosowanie

Notacja ta jest powszechnie używana w informatyce do zapisu składni (syntaktyki) języków programowania i protokołó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.

Zobacz też

• Notacja EBNF

Bibliografia

• Michał Iglewski, Jan Madey, Stanisław Matwin: Pascal – język wzorcowy. Pascal 360. WNT, 1979. ISBN 83-204-0597-1.brak strony w książce
• Alfred V. Aho, Ravi Sethi, Jeffrey D. Ullman: Kompilatory – reguły, metody i narzędzia. WNT, 1984. ISBN 83-204-2656-1.brak strony w książce