ТПТ_Лекція_3_Формальні_мови_та_грамматики

Визначення формальних мов і граматик
Математичні моделі, що використовують подання текстів у вигляді послідовності символів, називають формальними мовами і граматиками.
Кінцева множина символів, неподільних у даному розгляді, називається словником чи алфавітом, а символи, що входять у множину, –буквами алфавіту.
Наприклад, алфавіт A = {2, b, c, +, !} містить 5 букв, а алфавіт B = {00, 01, 10, 11} містить 4 букви, кожна з яких складається з двох символів.
Послідовність букв алфавіту називається словом чи ланцюжком у цьому алфавіті. Число букв, що входять у слово, називається його довжиною.
Наприклад, слово в алфавіті A а= 2bc має довжину l(a) = 3, а слово в алфавіті B b = 0000110010 має довжину l (b) = 5.
Теорія побудови трансляторів

Визначення формальних мов і граматик
Формальною граматикою Г, що породжує множину символів, називається наступна сукупність чотирьох об'єктів: Г = { Vт, VA, I ∈ VA, R }, де VТ – термінальний алфавіт (словник); букви цього алфавіту називаються термінальними символами; з них будуються ланцюжки породжувані граматикою; VА – нетермінальний, допоміжний алфавіт (словник); букви цього алфавіту використовуються при побудові ланцюжків; вони можуть входити в проміжні ланцюжки, але не повинні входити в результат породження; I - початковий символ граматики I ∈ Vа; R - множина правил чи виводу правил вигляду, що α→ β , де α і β - ланцюжки, побудовані з букв алфавіту Vт∪ VА, що називають повним алфавітом (словником) граматики Г.
До множини правил граматики можуть також входити правила з порожньою правою частиною вигляду Е → $.
Теорія побудови трансляторів

Визначення формальних мов і граматик
Нехай τ→ γ – правило граматики Г і α → χ'τ χ" – ланцюжок символів, причому χ', χ" ∈ (Vт ∪ VA) *. Тоді ланцюжок β→ χ' γ χ " може бути отриманий з ланцюжка α шляхом застосування правила τ → γ . У цьому випадку говорять, що ланцюжок β безпосередньо виведений з ланцюжка α і позначають α ⇒ β .
Множина кінцевих ланцюжків термінального алфавіту VТ граматики Г, виведених з початкового символу I, називається мовою, породжуваною граматикою Г, і позначається L( Г):
L( Г ) = {ϖ ∈ VТ* |
⇒*ϖ }.
Теорія побудови трансляторів

Приклад 1
Задана граматика Г.1. Потрібно визначити мову, породжувану цією граматикою:
Г1: VТ = {a, b, c, d}, VА = {I, B, C}
R = { I → aB
B → Cd
B → dc
C → $}.
Побудуємо всі виводи в цій граматиці:
I ⇒ aB ⇒ aCd ⇒ ad,
I ⇒ aB ⇒ adc.
Отже мова L(Г .1) = {adc, ad}.
Теорія побудови трансляторів

ПОРОЖНЯ МОВА
Задано граматику Г2. Потрібно визначити мову, породжувану цією граматикою .
Г2 : VТ = {a, b}, VА = {I, A},R = { I → aA, A → bA}.
Спроба побудови виведення в цій граматиці призводить нас до ланцюжка:
I ⇒ aA ⇒ abA ⇒ abbA ⇒ ... ,
який виявляється нескінченним. Іншими словами, Г2 породжує порожню мову. Якщо мова, породжувана граматикою Г, не містить жодного кінцевого ланцюжка (кінцевого слова), то вона називається порожньою.
Для того, щоб мова L(Г) не була порожньою, у множині R повинне бути хоча б одне правило вигляду r = χ → ψ, де ψ ∈ Vт* і повинен існувати вивід I ⇒* χ.
Теорія побудови трансляторів

Типи формальних мов і граматик. Граматики типу 0.
Граматики типу 0, які називаються граматиками загального вигляду, не мають ніяких обмежень на правила породження. Будь-яке правило:
r = η → ψ
може бути побудоване з використанням довільних ланцюжків η, ψ ∈ (VТ ∪ VА)*. Наприклад, ССLW → WT xSAb → xrtHD.
Теорія побудови трансляторів

Типи формальних мов і граматик. Граматики типу 1.
Граматики типу 1, що називаються контекстно-залежними граматиками, не допускають використання будь-яких правил. Правила виводу в таких граматиках повинні мати вигляд:
χ1Aχ2 → χ1ω χ2,
де χ1, χ2 – ланцюжки, можливо порожні, з множини (Vт ∪ VА)*, символ А ∈ VА і ланцюжок w ∈ (Vт ∪ VА)*. Ланцюжки χ1 і χ2 залишаються незмінними при застосуванні правила, тому їх називають контекстом (відповідно лівим і правим), а граматику – контекстно-залежною.
Теорія побудови трансляторів

Типи формальних мов і граматик. Граматики типу 2.
Граматики типу 2 називають контектно-вільними (КВ) граматиками, або бесконтекстними граматиками.
Правила виводу таких граматик мають вигляд:
A → α,
де A ∈ VА і α ∈ (Vт ∪ VА)*.
Очевидно, що ці правила виходять із правил граматики типу 1 за умови χ1 = χ2 = $. Оскільки контекстні умови відсутні, то правила КВ- граматик виходять простіші, ніж правила граматик типу 1. Саме такі граматики використовують для опису мов програмування.
Теорія побудови трансляторів

Типи формальних мов і граматик. Граматики типу 3.
Граматики типу 3 називають автоматними граматиками (А - граматиками). Правила виводу в таких граматиках мають вигляд:
A → a, або A → aB, або A → B a,
де a ∈ Vт, A, B ∈ VА, причому граматика може мати тільки правила вигляду A → aB – правосторонні правила, або тільки вигляду A → Ba – лівосторонні правила.
Теорія побудови трансляторів

Виведення у КВ- граматиках і правила побудови дерева виведення
Правила побудови дерева виведення можна сформулювати так:
1) Як початок чи вершину кореня дерева візьмемо вершину, яку позначимо початковим символом граматики I; ця вершина утворить нульовий ярус дерева;
2) Якщо при виведенні ланцюжка на черговому кроці використовується правило граматики A → α і вершина, позначена нетерміналом A, розташована на ярусі з номером k-1, то до побудованого дерева потрібно додати стільки вершин, скільки міститься символів у ланцюжку α, розташувати ці вершини на ярусі k , позначити їх символами ланцюжка α і з'єднати ці вершини дугами з вершиною A. Результатом виведення є множина кінцевих вузлів – листів, що виписуються при обході дерева ліворуч – униз – праворуч – нагору.
Теорія побудови трансляторів

Приклад 2
Задано граматику Г 3:
Vт = {a, b}, Va = {I},
R = {I → aIb,
I → ab },
яка породжує мову L(Г3) = {aa...abb...b}, де а і b повторюються по n разів (n=1,2,...).
Теорія побудови трансляторів
Виведення ланцюжка aaabbb

Синтаксичний розбір
Послідовність номерів правил граматики Г, застосування яких дозволяє побудувати вивід розглянутого ланцюжка σ з початкового символу граматики, називається синтаксичним розбором σ.
Наприклад, у граматиці Г4:
Vт = { i, +, * , (, ) }, Va = {I, T, P}
R ={ (1) I → I + T
(2) I → T (3) T → T *P (4) T → P (5) P → (I) (6) P → i },
правила якої пронумеровані, вивід
I ⇒ I +T ⇒ T +T ⇒ T *P +T ⇒ P *P +T ⇒ i * P +T ⇒ i * i +T ⇒
i * i +P ⇒ i * i + i
має синтаксичний розбір [1, 2, 3, 4, 6, 6, 4, 6].
Теорія побудови трансляторів

Ліве і праве виведення
Якщо при побудові виведення ланцюжка α при кожнім застосуванні правила заміняється самий лівий нетермінальний символ, то такий виведення називається лівим, або лівостороннім виведенням α. Якщо при побудові виведення α, завжди заміняється самий правий нетермінальний символ проміжного ланцюжка, то виведення називається правим, або правостороннім виведенням α.
Теорія побудови трансляторів

Неоднозначні й еквівалентні граматики
Існують граматики, в яких один и той самий ланцюжок може бути отриманий за допомогою різного виведення.
Наприклад, у граматиці Г5: VТ = {a, b, c, d}, VА = {I, A, B},
R = {1. I → AB,
2. A → a,
3. A → ac,
4. B → b,
5. B → cb}.
Перше виведення цього ланцюжка має вигляд:
I ⇒ AB ⇒ Ab ⇒ acb,
а друге можна отримати так: I ⇒ AB ⇒ Acb ⇒ acb.
Цим виведенням відповідають різні синтаксичні дерева і розбори.
Теорія побудови трансляторів
Синтаксичні дерева і розбори виразу acb

Побудова граматик і граматики, що описують основні конструкції мов програмування
Основою створення правил граматики є спосіб виділення структури заданої множини ланцюжків. Цей спосіб передбачає розчленування ланцюжків, що входять у задану множину, на їх частини таким чином, щоб виявити частини ланцюжків, які повторюються і частини, що входять у всі ланцюжки в незмінному вигляді. Таке розчленування на частини являє собою виявлення структури ланцюжків заданої множини.
Для кожного виявленого елемента структури вводиться позначення. Множина таких позначень складає основу словника нетермінальних символів деякої граматики. Наступним кроком побудови є виявлення послідовностей, у яких елементи структури можуть входити в задані ланцюжки. Такі послідовності є основою для побудови правил граматики.
Теорія побудови трансляторів

Рекомендації з побудови граматик
1. Ланцюжку, що складається з заданих символів abc, відповідає правило:
I → abc.
2. Ланцюжку, що починається з заданого символу a, відповідає правило:
I → aA.
3. Ланцюжку, що закінчується заданим символом a, відповідає правило:
I → Aa.
4. Ланцюжку, що починається і закінчується заданими символами a, b, відповідає правило:
I → aAb.
5. Ланцюжку, що містить у середині символ a, відповідає правило:
I → AaB.
6. Ланцюжку заданої довжини l =2 відповідають правила:
A → aB і B → a.
7. Ланцюжку, що складається з повторюваних символів a, відповідають правила:
A → aA і A → a.
8. Ланцюжку, що складається із символів, що чергуються, a і b, відповідають правила:
A → aB і B → bA.
Теорія побудови трансляторів

Опис списків
Послідовності символів і послідовності символів з роздільниками часто називають списками.
1. Позначимо елемент послідовності a. Найпростіша послідовність може складатися з одного елемента a. Всі інші послідовності можуть бути отримані шляхом приписування до вже побудованої послідовності ще одного елемента. Якщо позначити побудовану частину послідовності нетермінальним символом R, а послідовність символом L, то одержимо правила граматики у вигляді:
Г6: L → aR,
R → aR,
R → $,
Теорія побудови трансляторів

Опис списків
2. У попередній задачі передбачалося, що список L повинен містити хоча б один елемент. Якщо ж допустити, що множина ланцюжків, породжених правилами граматики, може включати порожній символ, то до побудованих правил потрібно додати ще одне правило L → $. У цьому випадку набір правил має вигляд :
Г7: L → aR,
R → aR,
R → $,
L→ $.
Теорія побудови трансляторів

Опис списків
3. Розглянемо побудову списку, між елементами якого повинні стояти роздільники. Виберемо як роздільник кому. Найпростіший список, як і в попередньому випадку, складається з одного елемента, а побудова списку з декількох елементів може бути виконана приписуванням до вже побудованої частини списку роздільника з елементом списку. Правила, що відповідають цій побудові, мають вигляд:
Г8: L → aR,
R → ,aR,
R → $.
Теорія побудови трансляторів

Опис списків
4. Якщо список з роздільниками може бути порожнім, то наведений вище набір правил потрібно доповнити ще одним правилом з порожньою правою частиною. У результаті одержимо:
Г9: L → aR,
R → ,aR,
R → $,
L → $.
Теорія побудови трансляторів

Порядок побудови правил граматики
1) виписати кілька прикладів із заданої множини ланцюжків;
2) проаналізувати структуру ланцюжків, виділяючи початок, кінець, що повторюються, або символи з групи символів;
3) ввести позначення для складних структур, що складаються з груп символів; такі позначення є нетермінальними символами шуканої граматики;
4) побудувати правила для кожної з виділених структур, використовуючи для завдання повторюваних структур рекурсивні правила;
5) об’єднати всі правила;
6) перевірити за допомогою виведення можливість одержання ланцюжків з різною структурою.
Теорія побудови трансляторів

Приклад 3
Побудувати граматику для мови L ,термінальний словник якого Vm = {*, |}, а ланцюжки, що утворюють мову, мають наступну структуру:
а) кожен ланцюжок починається буквою * і закінчується двома буквами **.
б) між початком і кінцем ланцюжків можуть бути або непорожня послідовність паличок, або кілька таких послідовностей, розділених символами *.
1. Спочатку побудуємо кілька ланцюжків заданої мови, що можуть бути подані в наступному вигляді:
* |||**,
* |*|*|**,
* ||*||||*|||||** ,
* |||*|*||*||||||** .
Теорія побудови трансляторів

Приклад 3
2. Розглядаючи наведені ланцюжки, можна виділити наступні їх структурні компоненти:
початок ланцюжка (символ * );
кінець ланцюжка (символи ** );
непорожня група паличок;
послідовність груп паличок, розділених зірочками.
3. Позначимо групу паличок символом A, а послідовність груп паличок символом B.
Теорія побудови трансляторів

Приклад 3
4. Виділені структури можна розглядати як списки. Так послідовність паличок являє собою список без роздільників, елементом якого є паличка. Правила граматики, що задає такий список, мають такий вигляд:
1.A → | R,
2.R → | R,
3.R → $.
Теорія побудови трансляторів

Приклад 3
5. Послідовність груп паличок, розділених зірочкою, являє собою список з роздільником. Елементом такого списку є група паличок A, а роздільником – зірочка. Правила граматики, що задає такий список, можна записати так:
B → AR1,
R1 → *AR1,
R1 → $.
З огляду на те, що кожен ланцюжок мови повинен мати початок і кінець, і , вибираючи як початковий символ граматики I, одержуємо правило, що визначає загальний вигляд ланцюжка:
I → *B**.
Теорія побудови трансляторів

Приклад 3
6. Поєднуючи побудовані правила, остаточно одержимо схему шуканої граматики у вигляді:
Г10: R = { I → *B**,
B→ AR1,
R1→ *AR1,
R1 → $,
A → | R,
R→ | R,
R → $ }
Теорія побудови трансляторів

Приклад 3
7. За допомогою правил побудованої граматики:
Г10: R = { 1. I → *B**, 2. B→ AR1, 3.R1 → *AR1, 4. R1 → $, 5.A → | R, 6.R→ | R, 7. R → $ }
можна отримати, наприклад, ланцюжок: * | * | * | **.
Теорія побудови трансляторів

Приклад 4
Побудувати правила граматики для опису цілих чисел.
Г11:1. N → DR, 2. R → DR |0R
3. R → $,
4. D → 1 | ... | 9.
Виведення для числа 127.
N → DR → 1R → 1DR → 12R → 12DR → 127R → 127
Синтаксичний розбір: [1, 4.2, 2, 4.3, 3, 4.8, 3].
Теорія побудови трансляторів

Приклад 5
Побудувати правила граматики для опису ідентифікатора.
Г12: R ={ 1. I → CA,
2. A → CA|DA,
3. A → C|D,
4. A → $,
5. D → 0 | 1 | ... | 9,
6. C → a | b | c | ... | z | _ }.
Виведення для ідентифікатора a0_d:
I → CA → aA → aDA → a0A → → a0CA → a0_A → a0_CA → a0_dA → a0A
Синтаксичний розбір: [6.1, 2.2, 5.1, 2.2,6.28, 2.2, 6.4, 4].
Теорія побудови трансляторів