Представлення опису заданої мови в БНФ та графічній формі з використанням токенів

Кожна мова програмування має правила, які визначають синтаксичну структуру коректних програм. В Pascal, наприклад, програма створюється із блоків, блок – з інструкцій, інструкції – з виразів, вирази – з токенів і т.д. Синтаксис конструкцій мови програмування може бути описаний за допомогою контекстно-вільних граматик або нотації БНФ (Backus-Naur Form, форм Бекуса-Наура).

Формально граматика визначається четвіркою G=(Vn,Vt,S,P), де:

Vn і Vt - відповідно множини нетермінальних, і термінальних символів, що не перетинаються;

S - виділений символ у Vn, що звичайно називають вихідним або початковим символом;

P - кінцева множина продукцій (правил), за якими нетермінальні символи визначаються як упорядкована послідовність термінальних та/або нетермінальних символів. Ця послідовність може складатися із одного термінального або нетермінального символа. В останьому випадку це буде просте перевизначення нетермінального символа лівої частини правила.

Для завдання продукцій частіше усього використовуються метамова (мова для опису мов) нормальних форм Бекуса-Наура або Бекусовых нормальних форм (скорочено - БНФ), яка була запропонована і вжита у 1955 р. для опису однєї з перших і на той час найбільш поширеної універсальної мови програмування АЛГОЛ. У цій метамові використовуються наступні метасинтаксичні символи або сполучення символів:

< > – кутні дужки для визначення в них імені нетермінального символу;

::= – аналог оператора присвоєння в мовах програмування. Він читається як "це є" і розділяє ліву і праву частини граматичного правила.

| – роздільник алтернативных правил у правій частині металингвістичої формули.

У лівій частині формули завжди повинний бути присутнім нетермінальний символ. Якщо в лівій частині будь-якої формули якоїсь граматики є не більш одного нетермінального символу, то така граматика є контекстно незалежною, у протилежному випадку - контекстно залежною. Далі будемо розглядати тільки контекстно незалежні граматики.

У правій частині формули записується одне або декілька (якщо вони існують) правил, розділених символом “|”, кожне з яких представляє собою, як наводилося, послідовність термінальних та/або нетермінальних символів.

Кожний нетермінальный символ повинний зустрітися в лівій частині якогось правила, тобто не може бути жодного невизначеного нетермінального символа.

Наведемо приклад граматики визначення змінних мовою Pascal.

(1) <оператор_опису_змінних>::= var <список_імен_змінних>: <тип_змінних>;

(2) <список_імен_змінних>::= іd

(3) <список_імен_змінних>::= <список_імен_змінних>, id

(4) <тип_змінних>::= char

(5) <тип_змінних>::= real

(6) <тип_змінних>::= int

(7) <тип_змінних>::= integer

Графічне представлення граматики

Поиск по сайту: