й, на практиці неможливо реалізувати, тому що в загальному випадку безліч ланцюжків мови нескінченно і перерахувати їх неможливо).
вказівку способу породження ланцюжків мови (завдання граматики мови) - застосування т.зв. генератора.
завдання методу розпізнавання ланцюжків мови - використання распознавателя.
Генератори і розпізнавачі є основними інструментами завдання нескінченного мови кінцевими засобами. Існує певна класифікація мов за їх типом, і для кожного класу мов є еквівалентні способи завдання за допомогою генераторів і распознавателей. Нижче розглянемо ці способи більш докладно.
У будь-якій мові можна виділити його синтаксис і семантику. Крім того, транслятори мають справу також з лексичними конструкціями (лексемами), які задаються лексикою мови. Дамо визначення цих понять.
Синтаксис мови - це набір правил, що визначає допустимі конструкції мови. Найчастіше синтаксис мови можна задати у вигляді суворого набору правил, але повністю це справедливо тільки для формальних мов.
Семантика мови - це розділ, що визначає значення пропозицій мови. Семантика визначає «зміст мови», тобто задає значення всіх допустимих ланцюжків мови. Для більшості мов семантика визначається неформальними методами.
Лексика - це словниковий запас мови. Лексична одиниця (лексема) - конструкція, яка складається з елементів алфавіту мови і не містить в собі інших конструкцій. Тобто лексема може містити в собі тільки елементарні символи алфавіту і не може містити інших лексем. Наприклад, лексемами російської мови є слова, а пропуски і розділові знаки являють собою роздільники. Лексемами алгебри є числа, знаки математичних операцій, позначення функцій і т.п. У мовах програмування лексеми - це ключові слова, ідентифікатори, константи, мітки, знаки операцій.
4.3 Поняття граматики. Форма Бекуса-Наура
Граматика, загалом, являє собою опис способу побудови ланцюжків мови. Наприклад, для природних мов це набір правил побудови різних виразів і пропозицій. Для багатьох мов (у тому числі для мов програмування) можливо, використовувати формалізований опис, тобто якусь математичну систему, що описує мову. Граматика задає правила породження ланцюжків мови, отже, є генератором - реалізує другий спосіб завдання мови.
Формальний опис граматики побудовано на основі системи правил, або продукцій. Правило являє собою упорядковану пару ланцюжків символів, яку зазвичай записують, як і читають як «породжує».
Граматика мови програмування містить правила двох типів: перші (визначальні синтаксичні конструкції мови) легко піддаються формальному опису; другий (визначальні семантичні обмеження мови) звичайно викладаються у неформальному вигляді. Тому будь-яке опис мови програмування зазвичай складається з двох частин: спочатку формально викладаються правила побудови синтаксичних конструкцій, потім природною мовою дається опис семантичних правил. Для компілятора семантичні обмеження повинні бути представлені у вигляді алгоритмів перевірки правильності програми.
Говорячи далі про граматиках мов програмування, будемо мати на увазі тільки правила побудови синтаксичних конструкцій мови.
Формально граматика визначається як четвірка
де - множина термінальних символів (символи алфавіту);- Безліч нетермінальних символів (слова, поняття, конструкції мови);
повний алфавіт граматики;- Безліч правил виду
де;- Початковий (цільової) символ граматики, з якого починається процес породження ланцюжків мови.
Кожен нетермінальний символ може зустрічатися в ланцюжках як лівої, так і правої частин правил, але він зобов'язаний бути хоча б один раз в лівій частині хоча б одного правила. Правила граматики будуються таким чином, що в лівій частині кожного з них є хоча б один нетермінальний символ.
У безлічі правил граматики може бути кілька правил, що мають однакові ліві частини, наприклад
,, ...,
Тоді ці правила записуються в один рядок
.
Розглянута форма запису правил граматики називається формою Бекуса-Наура. У ній, як правило, нетермінальні символи полягають в кутові дужки.
Наприклад, граматика для породження цілих десяткових чисел зі знаком
. :; ;
У даній граматиці безліч нетермінальних символів містить три елементи (символи,,), безліч термінальних символів - 12 елементів (10 цифр і два знаки), безліч P - 15 прави...
