Формальні мови та граматики - студопедія

Необхідність створення формальних мов пов'язана з певними недоліками природної мови, які було виявлено при його використанні в теорії алгоритмів. Розглянемо деякі з них:

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.

Константи цілого типу можуть бути рекурсивно визначені в такий спосіб:

  1. <константа>:: =<цифра>;
  2. <константа>:: =<константа> <цифра>;
  3. <цифра>:: = 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9.

Перше з правил Новомосковскется: <константа> може складатися з <цифры>. Друге правило Новомосковскется: <константа> може складатися з іншого <константы>, за якої слід <цифра>.

Наведені синтаксичні правила утворюють граматику для мови <констант>. Пропозиціями цієї мови є послідовності термінальних символів, які можуть бути виведені з нетермінального символу <константа>. Розглянемо приклад отримання константи 673 за допомогою використання синтаксичних правил, записаних за допомогою БНФ:

  1. використовуємо друге правило: нетермінальний символ <константа> замінюємо на ланцюжок <константа> <цифра>;
  2. використовуємо третє правило: нетермінальний символ <цифра> замінюємо на термінальний символ 3;
  3. використовуємо знову друге правило і отримуємо <константа> <цифра>3;
  4. використовуємо третє правило і отримуємо <константа> 73;
  5. використовуємо перше правило: нетермінальний символ <константа> замінюємо на нетермінальний символ <цифра>, в результаті отримуємо ланцюжок <цифра> 73;
  6. використовуємо третє правило і отримуємо 673.

БНФ і її модифікації є в даний час стандартним засобом опису синтаксису мов програмування.

Схожі статті