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>::=, | .[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

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ż

Uwagi

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

Bibliografia

  • 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.

Content Disclaimer

Informasi ini disarikan dari Wikipedia dan disajikan kembali untuk tujuan edukasi. Konten tersedia di bawah lisensi CC BY-SA 3.0. Kami tidak bertanggung jawab atas ketidakakuratan data yang bersumber dari kontribusi publik tersebut.

  1. The information displayed on this website is sourced in part or in whole from Wikipedia and has been adapted for the purpose of restating it. We strive to provide accurate and relevant information, however:
  2. There is no guarantee of absolute accuracy. Wikipedia is an open, collaborative project that can be edited by anyone, so information is subject to change.
  3. It is not intended to constitute professional advice. The content displayed is for informational and educational purposes only. For important decisions (e.g., medical, legal, or financial), please consult a professional.
  4. Content copyright. Wikipedia is licensed under the Creative Commons Attribution-ShareAlike License (CC BY-SA). This means that content may be reused with appropriate attribution and shared under a similar license.
  5. Responsible use. Any risk arising from the use of information from this website is entirely the responsibility of the user.
Kembali kehalaman sebelumnya