BNF

Notacja BNF - (równania normalne Backusa) - system zapisywania produkcji gramatyki zaproponowany przez J. Backusa i P. Naura przy okazji prac prowadzonych nad językiem Algol 60. Symbole metajęzykowe (alfabetu pomocniczego), służące do nazywania jednostek składniowych definiowanego języka umieszcza się w nawiasach kątowych.

Symbol :: =, czytany “jest równe z definicji”, łączy strony produkcji. Po nim następuje (po prawej stronie) skończony ciąg symboli nieterminalnych i terminalnych. Symbol nieterminalny, który jest po lewej stronie symbolu produkcji, może się również powtarzać po jego prawej stronie, umożliwia to definiowanie reguł rekursywnych.

Pionowa kreska (|) oznacza w produkcjach spójnik logiczny “albo” i pozwala na zmniejszenie ich liczby. Symbole alfabetu końcowego pisze się w BNF bez żadnych zaznaczeń.

Składnia - zasady budowy poprawnych wypowiedzi w języku.

Przykład:(notacja BNF)

<zdanie> :: = <grupa_podmiotu> <grupa_orzeczenia>

<grupa_podmiotu> :: = <fraza_rzeczownikowa>

<grupa_orzeczenia> :: = <fraza_czasownikowa>

<fraza_rzeczownikowa> :: = <przymiotnik> <faza_rzeczownikowa> | <rzeczownik>

<fraza_czasownikowa> :: = <czasownik> <fraza_przysłówkowa>

| <czasownik> <fraza_rzeczownikowa> | <czasownik>

<fraza_przysłówkowa> :: = <przyimek> <fraza_rzeczownikowa> | <przysłówek>

| <przysłówek> <przyimek> <fraza_rzeczownikowa>

<przymiotnik> :: = szybki | rudy | omszały | głęboki | mądry

<rzeczownik> :: = lis | pień | dół

<przyimek> :: = przez

<czasownik> :: = przeskoczył | polubił

Poprawne zdania:

szybki rudy lis przeskoczył przez omszały pień
mądry lis polubił głęboki omszały pień
głęboki lis przeskoczył przez mądry dół
szybki głęboki pień polubił przez mądry rudy dół
lis przeskoczył zgrabnie przez głęboki dół

Niepoprawne zdania:

lis przeskoczył bardzo zgrabnie przez głęboki dół (nie można użyć dwóch przysłówków w jednym zdaniu)
szybki rudy wilk przeskoczył przez omszały pień (rzeczownik wilk nie występuje w definicji języka)
polubił głęboki omszały dół ( w zdaniu musi wystąpić <grupa_podmiotu)

Do opisu języka trzeba używać metajęzyka. W zapisie wg. notacji BNF elementami

metajęzyka są:

<zdanie>, <grupa_podmiotu>, ... zwane symbolami nieterminalnymi, symbolami pomocniczymi lub zmiennymi językowymi,
:: = <-- operator podstawienia metajęzykowego,
| <-- symbol metajęzykowy "lub",

Elementami języka są zaś symbole terminalne (końcowe) jak np.: szybki, rudy, lis.

Zapis typu <....> :: = .... nazywa się produkcją lub regułą syntaktyczną.

Zapis typu:

<AAA> :: = aaa | bbb

jest równoważny dwóm regułom syntaktycznym:

<AAA> :: = aaa

<AAA> :: = bbb

Do pełnej definicji języka należy określić:

N - zbiór symboli nieterminalnych np.: N={<zdanie>, <grupa_podmiotu>, ...}

T - zbiór symboli terminalnych np.: T={szybki, rudy, lis, ...}

P - zbiór reguł syntaktycznych np.: P={<zdanie> :: = <grupa_podmiotu> <grupa_orzeczenia>, ...}

Z Î N - symbol początkowy, od którego rozpoczyna się wprowadzanie napisów języka np.: Z=<zdanie>

Te cztery kategorie łącznie noszą nazwę gramatyki języka formalnego.

Poniżej przedstawiono prosty przykład gramatyki bezkontekstowej, zapisanej w notacji BNF, generującej liczby binarne :

<liczba_binarna> ::= <liczba_binarna> <cyfra>
<liczba_binarna> ::= <cyfra>
<cyfra> ::= 0 | 1

Gramatyka ta ma więc postać ogólną:

G = { N, V, P, S } Gramatyka
N = { <liczba_binarna>, <cyfra> } Alfabet nieterminalny
V = { 0, 1 } Alfabet terminalny
P = { <liczba_binarna> ::= <liczba_binarna> <cyfra> ;
<liczba_binarna> ::= <cyfra> ;
<cyfra> ::= { 0 | 1 } Zbiór reguł produkcji

Opis podzbioru języka Pascal, który jest interpretowany przez zaimplementowany interpreter.

1. Akceptowane znaki

::= - 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

cyfra::={0|1|2|3|4|5|6|7|8|9}

liczba_calk::=<cyfra>{<cyfra>}*

liczba_nat::={0|1|2|3|4|5|6|7|8|9}+

liczba_zmiennop::={<cyfra>}+< separator_dzies>{<cyfra>}*

liczba::={< liczba_calk>|< liczba_zmiennop>}

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>}

znak::={<cyfra>|<litera>|_}

nazwa::=<litera>{<znak>}*

spacja::={" "}

cudzyslow::={"}

ciapek::={'}

znak_inny::={~|!|@|#|$|%|^|&|*|(|)|-|+|=|[|]|{|}|;|:|<|>|,|.|/|?|\|"|"|<spacja>}

wszystkie::={<znak>|{<znak_inny>}*}

2. Operatory i symbole

operator::={ +|-|*|/ }

operator_relacji::={ <|>|=|>=|<=|<> }

nawias::={ (|)|[|] }

klamra_l::={ { }

klamra_p::={ } }

separator_dzies::={ .}

inne_symbole::= { ,| : }

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. Deklaracje zmiennych i operacji

nazwa::=<litera>{<znak>}*

nazwa_zmiennej::=<nazwa>

typ::={string|integer|real|boolean}

separator::={ ; } zmienna::=<nazwa_zmiennej>{','[<nazwa_zmiennej>]}*':'<typ><separator>

wartosc::={<liczba>|<zmienna>}

operacja_matem::=<wartosc>{<operator><wartosc>}*

operacja_matem_w_nawias::={<operacja_matem>|'('<operacja_matem>')'}

operacja_matem_z_nawias::=<operacja_matem_w_nawias>{<operator><operacja_matem_w_nawias>}*

wyrazenie_mat::={'('{<operacja_mat_z_nawias>|<wyrazenie_mat>}{<operator_matematyczny><wyrazenie_mat>}*')'|{<operacja_mat_z_nawias>|<wyrazenie_mat>}{<operator_matematyczny><wyrazenie_mat>}*}

przypisanie::={:=}

operacja_przypisania::=<zmienna><przypisanie>{<liczba>|<zmienna>|<tekst>|<wyrazenie_mat>}

wynik::=<zmienna><operator><zmienna><separator>

instrukcja_prosta::={<zmienna><przypisanie><zmienna><separator> |<zmienna><przypisanie><wynik><separator>}

instrukcja_zlozona::=<s_begin>{<instrukcja_prosta>}*<s_end><separator>

warunek::= {{<wartosc><operator_relacji><wartosc>}|{<zmienna><s_and><zmienna>}|{<zmienna><s_or><zmienna>}|{<zmienna><s_not><zmienna>}}

petla_for::=<s_for><zmienna>':='{<liczba_nat>|<zmienna>|<wyrazenie_mat>}<s_to>{<liczba_nat>|<zmienna>|<wyrazenie_mat>}<s_do>< instrukcja_zlozona>

komentarz::= <klamra_l>{ <nazwa><spacja>}*<klamra_p>

5. Operacje we/wy

o_read::={read} o_readln::={readln} o_write::={write} o_writeln::={writeln} tekst::={<ciapek><wszystkie><ciapek>}

output::={<liczba>|<zmienna>|<tekst>|<wyrazenie_mat>}

wczytywanie_zmiennych::={<o_read><nazwa_zmiennej><separator>|<o_readln><nazwa_zmiennej><separator>}

wypisywanie::={<o_write><wszystkie><separator>|<o_writeln><wszystkie><separator>}

6. Struktura programu

def_programu::= {<s_program><nazwa><separator>} [<s_const>{<nazwa><przypisanie>{<liczba>|<tekst><separator>}}+] [<s_var>{<zmienna>}+] <s_begin> {<operacja_przypisania>|<wypisywanie>|<wczytywanie_zmiennych>|<instrukcja_prosta>|<instrukcja_zlozona>}* <s_end>'.'