Необхідність створення формальних мов пов'язана з певними недоліками природної мови, які було виявлено при його використанні в теорії алгоритмів. Розглянемо деякі з них:
1. залежність способів побудови речень (синтаксису) від їхнього змісту (семантики). Наприклад, необхідно використовувати пропозицію "Лікар оглянув хворого" або "Лікар оглянула хворого" в залежності від приналежності лікаря до відповідного підлозі;
2. семантична неоднозначність пропозицій. Наприклад, пропозиція: «Зберігайте гроші в банку», може мати на увазі зберігання грошових коштів у фінансовій установі або в деякій ємності;
3. семантична неточність пропозицій. Наприклад, за пропозицією "Вчора була тепла погода" неможливо визначити температуру повітря, оскільки в різні пори року теплій погоді може відповідати різна температура;
4. наявність парадоксів, розглянутих в попередньому параграфі.
Формальна мова, зручний для теорії алгоритмів, не повинен мати цих недоліків. При цьому для опису формального мови (мови - об'єкта) будемо користуватися іншою мовою (метамовою), наприклад, природним українською мовою.
Правила побудови слів з букв і пропозицій з слів формального мови будемо називати формальною граматикою. Для опису синтаксису формального мови використовують запропоновану американським лінгвістом і математиком Хомским стандартну форму, яку можна представити у вигляді:
де Х - алфавіт термінальних символів формального мови;
Y - допоміжний алфавіт нетермінальних символів;
R - кінцевий набір синтаксичних правил;
S - початковий допоміжний символ з безлічі нетермінальних символів (термінальний символ - найменший значущий елемент формального мови).
Кожне синтаксичне правило з R являє собою підстановку А → В, в якій А і В - деякі слова, утворені з символів алфавітів Х і Y. Пропозиції формального мови почнемо отримувати, якщо можна застосувати до нетермінальному символу S деяку підстановку з R. Така підстановка, ліва частина якої відповідає нетермінальному символу S, повинна знаходитися в R. Якщо отриманий результат містить тільки термінальні символи, то це означає, що пропозиція мови вже отримано. Якщо в отриманій ланцюжку присутні нетермінальні символи, то починаємо знову застосовувати до цієї ланцюжку одну з підстановок з R, причому будь-яку з них. Якщо отримана ланцюжок має кілька входжень слова А, то відповідна підстановка допускає заміну будь-якого з цих входжень А на В.
Розглянемо приклад формальної граматики, в якій X =, Y =, а система підстановок має вигляд:
Така граматика породжує формальну мову, що містить двійкові числа, які зліва направо Новомосковскются так само, як справа наліво. Наприклад, застосування підстановок 3, 4, 1 призведе до отримання числа 01010; підстановок 4, 3, 3, 2 - до отримання числа 1001001 і т.д.
Нормальна форма Бекуса-Наура.
Нормальна форма Бекуса-Наура (БНФ) - це ще один спосіб опису формальної мови.
Для опису формальної мови за допомогою БНФ будемо використовувати синтаксичні правила (продукції), в яких будемо використовувати такі символи:
1. = - це символ, який відокремлює ліву частину продукції, що є нетермінальним символом, від правої частини, яка є непорожній, кінцевою ланцюжком термінальних і нетермінальних символів. Символ. = Новомосковскется як по визначенню є або як може складатися з;
2. | - це роздільник, який поміщається між різними формами одного і того ж нетермінального поняття. Символ Новомосковскется як або;
3. <> - кутові дужки використовуються для виділення нетермінального символу, тобто такого поняття, яке не може зустрічатися в пропозиціях описуваного мови і застосовується для того, щоб допомогти описати ці пропозиції.
Розглянемо приклади опису десяткових цифр і констант цілого типу за допомогою БНФ.
Той факт, що 1 є цифрою, виражається за допомогою БНФ наступним чином:
При цьому кутові дужки <> використовуються для того, щоб виділити нетермінальний символ, який не може зустрічатися в пропозиціях описуваного формального мови, і призначений для опису синтаксичного правила. Символ 1 може зустрічатися в пропозиціях описуваного формального мови і є термінальним символом.
Для того щоб показати, що нетермінальний символ <цифра> може бути 0 або 1, можна скористатися наступним синтаксичним правилом:
Таким чином, для опису десяткових цифр можна написати правило:
<цифра>:: = 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9.
Константи цілого типу можуть бути рекурсивно визначені в такий спосіб:
- <константа>:: =<цифра>;
- <константа>:: =<константа> <цифра>;
- <цифра>:: = 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9.
Перше з правил Новомосковскется: <константа> може складатися з <цифры>. Друге правило Новомосковскется: <константа> може складатися з іншого <константы>, за якої слід <цифра>.
Наведені синтаксичні правила утворюють граматику для мови <констант>. Пропозиціями цієї мови є послідовності термінальних символів, які можуть бути виведені з нетермінального символу <константа>. Розглянемо приклад отримання константи 673 за допомогою використання синтаксичних правил, записаних за допомогою БНФ:
- використовуємо друге правило: нетермінальний символ <константа> замінюємо на ланцюжок <константа> <цифра>;
- використовуємо третє правило: нетермінальний символ <цифра> замінюємо на термінальний символ 3;
- використовуємо знову друге правило і отримуємо <константа> <цифра>3;
- використовуємо третє правило і отримуємо <константа> 73;
- використовуємо перше правило: нетермінальний символ <константа> замінюємо на нетермінальний символ <цифра>, в результаті отримуємо ланцюжок <цифра> 73;
- використовуємо третє правило і отримуємо 673.
БНФ і її модифікації є в даний час стандартним засобом опису синтаксису мов програмування.