Notacja BNF


Notacja BNF w encyklopedii

Z Wikipedii, wolnej encyklopedii Przejdź do nawigacji Przejdź do wyszukiwania

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

Spis treści

Definicja formalna | edytuj kod

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 | edytuj kod

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>::=, | .[a]
    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 | edytuj kod

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ż | edytuj kod

Uwagi | edytuj kod

  1. Jako przecinek należy tu rozumieć znak przecinka lub kropki.

Bibliografia | edytuj kod

  • Michał Iglewski, Jan Madey, Stanisław Matwin: Pascal – język wzorcowy. Pascal 360. WNT, 1979. ISBN 83-204-0597-1.
  • Alfred V. Aho, Ravi Sethi, Jeffrey D. Ullman: Kompilatory – reguły, metody i narzędzia. WNT, 1984. ISBN 83-204-2656-1.
Na podstawie artykułu: "Notacja BNF" pochodzącego z Wikipedii
OryginałEdytujHistoria i autorzy