1 of 25

ЕЛЕМЕНТИ ТЕОРІЇ МОВ

лекція 12

2 of 25

План лекції

  • Опис синтаксису мов
    • БНФ, РБНФ, синтаксичні діаграми
  • Формальні граматики
  • Класифікація граматик за Хомським
  • Розпізнавання мов
    • Синтаксичний аналізатор, низ- і висхідний аналіз, повний перебір правил підстановки
    • Визначення мов за допомогою автоматів

​

3 of 25

Форма Бекуса-Наура опису синтаксису формальних мов

  • Джон Бекус(John Backus, 1924-2007)
    • Керував створенням першого компілятора для мови Фортран
  • Пітер Наур (Peter Naur, 1925)
    • Один із творців мови Алгол
    • "Backus Normal Form"

​

4 of 25

Форма Бекуса-Наура опису синтаксису формальних мов

  • Опис синтаксису мов програмування

​

  • Термінальні символи
  • Нетермінальні символи
  • Правила виду
    • <нетерм.символ> ::= <посл.симв.1>�| <посл.симв.2>�| . . .�| <посл.симв.n>

​

5 of 25

Приклад БНФ №1

  • <цифра>::='0'|'1'|'2'|'3'|'4'|'5'|'6'|'7'|'8'|'9'
  • <знак>::='+'|'-'|
  • <число без знаку>::=<цифра>|<цифра> <число без знаку>
  • <число>::=<знак> <число без знаку>

​

  • Багато рядків, які описує <число>:
    • 0, 1, ..., 9, +0, +1, ..., +9, -0, -1, ..., -9, 00, 01, ..., 09, +00, + 01, ..., +09, -00, -01, ..., -09, ...

​

6 of 25

Приклад БНФ №2

  • Яка кількість рядків описує <ппс>?

​

  • <ппс>::= |'('<ппс>')'|<ппс><ппс>

7 of 25

Приклад БНФ №3

  • Опишіть БНФ за допомогою БНФ

8 of 25

Розширена БНФ

  • [<остан.симв.>]
    • Необов'язкова послідовність символів
  • {<остан.симв.>}
    • Повторення послідовності символів

​

​

​

9 of 25

Граматики

  • Формальна мова – це довільна множина ланцюжків, складених із символів деякої скінченної абетки
    • Довільне - нескінченне, кінцеве чи порожнє

​

  • Граматика – це скінченний опис формальної мови

​

​

10 of 25

Визначення граматики

  • Граматика – це набір із чотирьох елементів
    • Множина термінальних символів
      • Алфавіт мови
    • Множина нетермінальних символів
      • Допоміжні символи, що не входять до описуваної мови
    • Множина правил виду ЛЧ-->ПЧ, де
      • ЛЧ – послід. терміналів та нетерміналів, що містить>=1 нетермінал
      • ПЛ – будь-яка послідовність нетерміналів
    • Стартовий нетермінал С

​

11 of 25

Застосування правил граматики

  • Ланцюжок Ц2 виходить із ланцюжка Ц1 застосуванням правила ЛЧ-->ПЧ, якщо Ц1 має вигляд х ЛЧ у, а Ц2 має вигляд х ПЧ у
  • Приклад
    • Ланцюжок ааАВвв виходить із аАВв застосуванням правила АВ-->аАВв

12 of 25

Висновок у граматиці

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

​

  • Мова, що описується граматикою, - це безліч ланцюжків термінальних символів, для яких є висновок

​

13 of 25

Приклади граматик

  • Мова {a+a,a+a+a,a+a+a+a, …}

​

  • T = {a, +}, N = {S, A}, стартовий символ S, правила
    1. S -->aA
    2. A --> +aA
    3. A -->+a
  • Приклад виведення а+а+a
    • Sп1 aAп2 a+aAп3 а+а+а

14 of 25

Приклади граматик

  • Мова {a,aaaa,aaaaaaaaa, …} –рядки з n^2 символів а
  • T = {a}, N = {S, S', A, B, C, L, R}, стартовий символ S, правила
    1. S --> LS'R
    2. S' --> AS'B
    3. S' --> AB
    4. AB --> BAC
    5. AC --> CA
    6. CB --> BC
    7. LB --> L
    8. AR --> R
    9. LC -->aL
    10. LR -->
  • Приклад виведення ааaa
  • породжуємоLAnBnR
    • SLS'R LAS'BR LAABBR
  • НесемоBліворуч і породжуємоCпри переходіBчерезA –число С дорівнюєn^2
    • LABACBR LBACACBR LBACABCR LBACBACCR LBABCACCRLBBACCACCR
  • Видаляємо А та В
    • LBACCACCR LACCACCR LCACACCR LCCAACCR LCCACACR LCCCACARLCCCACR LCCCCAR LCCCCR
  • Замінюємо З а, видаляємоLіR
    • aLCCCR aaLCCR aaaLCR aaaaLR aaaa

​

15 of 25

Класифікація граматик за Хомським

  • Ноам Хомскі (Ноум Чомскі, Noam Chomsky), 1928

​

  • Класифікація (ієрархія) граматик за складністю розпізнавання�описуваних ними мов

16 of 25

Класифікація граматик за Хомським – тип 0

  • Тип 0 – довільні граматики
    • Будь-яке рекурсивно перелічену множину можна описати як мову з граматикою типу 0
      • Нетривіальний результат
    • Будь-яка мова з граматикою типу 0 є рекурсивно переліченою множиною
      • Чому?
    • Є мови з граматикою типу 0, для яких перевірка належності алгоритмічно нерозв'язна

17 of 25

Класифікація граматик за Хомським – тип 1

  • Тип 1 - контекстно-залежні граматики
    • αAβ→αγβ, де α, β довільні ланцюжки, γ непустий ланцюжок, A нетермінал
  • Правила можна привести до виду α→β, де α, β непусті ланцюжки та 1≤|α|≤|β|
    • Гратики, що не скорочують.
  • Приналежність будь-якого ланцюжка мови м.б. перевірена алгоритмом
    • Аналог рекурсивних множин

18 of 25

Класифікація граматик за Хомським – тип 2

  • Тип 2 – контекстно-вільні граматики
    • A→β, де β ланцюжок терміналів та нетерміналів, A нетермінал
    • Опис мов програмування
    • Еквівалентні БНФ
    • Автоматична генерація алгоритмів розпізнавання
      • Рекурсивний спуск
      • ШвидкіLLіLRпарсери для мов зі спеціальними КС граматиками

​

​

19 of 25

LLаналізатор мови з КС граматикою

  • Стрічка
    • Вхідний буфер, він же аналізований ланцюжок
  • Стек
    • Проміжні дані синтаксичного аналізу
  • Таблиця синтаксичного аналізу
    • Або правило граматики для символу на вершині стека та поточного символу на стрічці
    • Або позначка про відсутність правила для такої пари символів

​

​

​

20 of 25

LLаналізатор мови з КС граматикою

  • ГраматикаT={+,(,),1}, N={S,F},правила
    1. S --> F
    2. S --> (S+F)
    3. F -->1
  • Таблиця ($ --допоміжний термінал "кінець стеку")

​

​

​

(

)

1

+

$

S

п2

-

п1

-

-

F

-

-

п3

-

-

21 of 25

LLаналізатор мови з КС граматикою-приклад

​

​

Стек

Стрічка

S$

(1+1)$

(S+F)$

(1+1)$

S+F)$

1+1)$

F+F)$

1+1)$

1+F)$

1+1)$

+F)$

+1)$

F)$

1) $

1) $

1) $

)$

)$

$

$

​

(

)

1

+

$

S

п2

-

п1

-

-

F

-

-

п3

-

-

22 of 25

LLаналізатор мови з КС граматикою

  • Поки що не кінець
    • Вершина стеку нетермінал
      • У таблиці знаходимо правило граматики на перетині стовпця та рядки, що відповідають нетерміналу на вершині стека та поточному символу на стрічці, і кладемо у стек ланцюжок з правої частини правила
      • Якщо у зазначеному осередку таблиці правило відсутнє, то повідомляємо про помилку
    • Вершина стеку термінал
      • Порівнюємо його з поточним символом на стрічці
      • Якщо вони рівні, то видаляємо символ зі стрічки та зі стека
      • Інакше помилка
    • Вершина $
      • Поточний символ на стрічці $, то кінець
      • Інакше помилка

​

23 of 25

LLаналізатор мови з КС граматикою – побудова таблиці

  • Не встиг :(
  • A -->aX
  • A -->zAat

24 of 25

Класифікація граматик за Хомським – тип 3

  • Тип 3 – регулярні граматики
    • A→ γB або A→γ, де γ ланцюжок терміналів, А та В нетермінали
    • Правила можна привести до виду A→Bγ
    • Для будь-якої мови з регулярною граматикою можна побудувати кінцевий автомат, що розпізнає цю мову
    • Будь-який кінцевий автомат задає мову з регулярною граматикою

​

​

25 of 25

Висновок

  • Опис синтаксису мов
    • БНФ, РБНФ, синтаксичні діаграми
  • Формальні граматики
  • Класифікація граматик за Хомським
  • Розпізнавання мов
    • Нис-і висхідний розбір, повний перебір правил підстановки
    • Визначення мов за допомогою автоматів

​