Notacja BNF

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacji, wyszukiwania

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

Definicja[edytuj | 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 | 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 | 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.

Uwagi

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

Zobacz też[edytuj | edytuj kod]

Bibliografia[edytuj | edytuj kod]

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