Зубенко, Омельчук - Програмування. Поглиблений курс

Розділ І. ЛОГІКО-АЛГЕБРИЧНІ УНІВЕРСАЛІЇ

Для практичного застосування LL (k )-граматик необхідно вміти зна- ходити множину значення функції FIRST . Нехай маємо КВ-граматику G = (N ,T ,P,S ) і ланцюжок w термінальних і нетермінальних символів. Розглянемо один із методів побудови множини FIRSTk (w) для КВ- граматик. Нехай x /k означає префікс слова x довжиною k . За озна- ченням x /k = x , якщо k ≥|x |. Для мови L і натурального k покладемо, що L /k – сукупність префіксів довжиною k усіх її слів. Нехай w = X1X2...Xn , Xi T N , i =1,n . Нескладно впевнитись, що

FIRSTk (w)= (FIRSTk (X1 )FIRSTk (X2 )KFIRSTk (Xn ))/k .

Тому, щоб знайти сукупність FIRSTk (w), достатньо вміти знаходити сукупності FIRSTk (X ) для X N . Зазначимо, що для Xi T {ε}

FIRSTk (Xi )= {Xi }.

Для i ≥ 0 і кожного X T N визначимо такі мови Fi (X ):

1.Fi (a )= {a}, a T ;

2.F0 (X )= {x : x T * & X → xu P (x = k x < k & u = ε)};

3.Нехай Fi −1 (X ) уже визначені для всіх X N , тоді Fi (X ) = Fi −1(X )

{x : X →Y1Y2...Ym P & x Fi −1 (Y1 )Fi −1 (Y2 )...Fi −1 (Ym )/k}.

Ураховуючи, що число k фіксоване та Fi −1 (X ) Fi (X ), на певному кроці l для всіх X N сукупності Fl −1(X ) та Fl (X ) будуть збігатися. За побудовою FIRSTk (X )= Fl (X ).

101

ПРОГРАМУВАННЯ

Очевидно, граматика G 2 є LL (1)-граматикою. Це випливає з того, що значення функції FIRST1 для всіх альтернативних правих частин

продукцій попарно не перетинаються ■ Звернемось тепер до автоматів із магазинною23 пам'яттю (МП-

автоматів) – класу процедур, призначених для розпізнавання й син- таксичного аналізу КВ-мов. Від скінченного автомата МП-автомат ві- дрізняється наявністю в загальній структурі його станів третього компонента – стеку символів. Перші два компоненти функція перехо- ду МП-автомата перетворює так, як і у випадку скінченних автома- тів, а третю – за допомогою стекових операцій pop (зняти) і push

(покласти елемент у стек).

МП-автомат – це сімка A = (Q,X,Y ,δ,q0,Z0,F ), де:

1)Q – скінченна множина внутрішніх станів;

2)Σ – скінченна множина вхідних символів (вхідний алфавіт);

3)H – скінченна множина магазинних символів;

4)δ : Q ×(Σ ε)× H → B (Q × H * ) – функція переходів, керує роботою

автомата;

5)q0 Q – початковий внутрішній стан керуючого пристрою;

6)Z0 H – початковий стан стеку;

7)F Q × Σ* × H * – множина заключних станів.

Зазвичай множина заключних станів має вигляд F = Qfin × Σ* × H * ,

або F = Qfin × Σ* ×{ε}, для певної підмножини Qfin Q заключних вну-

трішніх станів МП-автомата. За означенням із порожнім стеком ав- томат продовжувати обчислення не може.

Обчислення за МП-автоматом – це послідовність станів, в які він переходить, читаючи або не читаючи літери вхідного слова. Перебу-

ваючи в стані (q,au,vZ ) і читаючи першу літеру a вхідного слова, не-

внутрішній стан qt +1 = p , друга компонента ut +1 = u . Якщо ж автомат не читає літеру на вході й реалізує ε -перехід δ(q,ε,Z ) = (p,ω), то qt +1 = p , ut +1 = au . В обох випадках нове значення стеку vt +1 = vω .

23 Магазин – це синонім слова "стек".

102

Розділ І. ЛОГІКО-АЛГЕБРИЧНІ УНІВЕРСАЛІЇ

При цьому ω = ε означає, що зі стеку знімається верхній елемент (операція pop ), ω ≠ ε – що зі стеку знімається верхній елемент і в ньо-

го послідовно вносяться символи слова ω (серією операцій push ).

МП-автомат називається недетермінованим, якщо, перебуваючи в деякому стані й читаючи поточний символ, він може перейти в один із кількох можливих станів або здійснити ε -перехід. Якщо, перебува- ючи в будь-якому стані й читаючи поточний символ, автомат може перейти не більше ніж в один стан і при цьому не має ε -переходу, то він, як і cкінченний автомат, називається детермінованим.

Введемо відношення├ безпосереднього переходу на конфігураціях МП-автомата. Оскільки значення функції переходу не залежить від часової компоненти, то останню можна не показувати в конфігураці-

δ(q,ε,Z ) = (p,ω). Нехай├* – рефлексивно-транзитивне замикання ві- дношення безпосереднього переходу.

Слово w розпізнається автоматом A , якщо (q,w,Z0 )├* (p,ε,v ), де q0 – початковий стан, а p F . Позначимо L (A)-мову, що розпізна-

ється МП-автоматом A .

A3 = (Q,Σ,H,δ,q0,Z0,F ) із даними компонентами задає мову L2 . На-

На першому, другому, третьому й четвертому кроках обчислення були застосовані перше, друге, третє й четверте за порядком правила переходу функції δ, після чого обчислення перейшло в заключний стан. Узагалі, перебуваючи в початковому внутрішньому стані q0 і

читаючи на вході літери a , автомат A3 щоразу кладе в стек символ 1 (тим самим запам'ятовується кількість підряд прочитаних літер а),

103

ПРОГРАМУВАННЯ

доки не зустріне першу літеру b і не перейде в заключний внутрішній стан q* . Перебуваючи далі в стані q* і читаючи символи b , A3 знімає зі стеку щоразу один символ 1. Перехід у єдиний заключний стан (q*,ε,ε) свідчить, що літер b було прочитано поспіль рівно стільки,

скільки спочатку літер a ■ Має місце

Теорема 1.7. Клас КВ-мов збігається з класом мов, що розпізна- ються МП-автоматами.

Доведення. Нехай G = (N ,T ,P,S ) – КВ-граматика. Побудуємо для неї МП-автомат A = (Q,Σ,H,δ,q0,Z0,F ), який буде моделювати всі її ліво- сторонні виведення й розпізнавати тільки ті слова, що належать мові L (G ). Подібні МП-автомати для КВ-граматик називаються МП-

аналізаторами типу розгортки. Покладемо Q = {q}, Σ = T , H = N T , q0 = q , Z0 = S , F = {(q,ε,ε)}, а функція δ визначається так: 1) для ко-

S u T * (q,u,S├) * (qε,ε), тобто A є МП-аналізатором типу розгор-

тки для граматики G (вправа 27).

Для доведення зворотної теореми можна обмежитися МП- автоматами зі спустошенням. МП-автоматом зі спустошенням нази-

ний МП-автомат і F = Qfin × Σ* ×{ε} для певної підмножини Qfin Q . Побудуємо для A КВ-граматику G = (N,T ,P,S ), що породжує мову L(A), таким чином, щоб будь-яке лівостороннє виведення слова u Σ* у граматиці G відповідало обчисленню автомата А зі словом u

на отримати так:

104

Нескладно перевірити, що для будь-яких q,r Q та Z H викону- ється (*) (вправа 28). Звідси випливає, що L(G ) = L(A) ■

МП-аналізатор типу розгортки для LL(k) -граматик досить просто

детермінізувати. Для цього достатньо, щоб він: а) мав можливість перед вибором продукції забігти наперед і прочитати наступні k нерозпізнаних вхідних символів; б) умів побудувати значення функції FIRSTk для відповідних альтернатив поточного виведення. Обидві

можливості реалізуються в межах скінченно-автоматного керування. Синтаксичні діаграми. Запропоновані Н. Віртом. Можуть розгля-

датися як графічний варіант РКВ-граматик, орієнтований на корис- тувача. Синтаксична діаграма (СД) є сукупністю певних орієнтова- них графів (піддіаграм) на площині з вершинами, що мають вигляд:

НЕТЕРМІНАЛ

Лексема

і відповідають правим частинам усіх правил РКВ-граматики. Кожно- му входженню лексеми чи нетермінального символу в праву частину правила відповідає окрема вершина піддіаграми. Вершини з'єдну- ються стрілками в тій самій послідовності, в якій зустрічаються в правилі. Кожна піддіаграма має рівно одну вхідну й вихідну стрілки. При цьому, якщо права частина є альтернативною, то піддіаграма складається з піддіаграм альтернатив, об'єднаних спільними входом і виходом. Якщо це конструкція:

1)у квадратних дужках, то до її піддіаграми додається стрілка, що з'єднує вхід і вихід;

2)у фігурних дужках, то вихід її піддіаграми зациклюється на свій же вхід і додається стрілка, що з'єднує вхід і вихід. Якщо при цьому вона має модифікатор: а) *, то піддіаграма не змінюється; б) +, то остання стрілка не додається; в) (n,m ), то піддіаграма будується про-

сто як відповідна кількість альтернатив.

Конструкція-діапазон замінюється відповідною кількістю альтернатив. Піддіаграма, що відповідає аксіомі граматики, називається головною.

105

ПРОГРАМУВАННЯ

На рис. 1.14 наведено СД для РКВ-граматики G3 із сукупністю не-

терміналів N ={<ідентифікатор>, <літера> ,<цифра>}, аксіомою <іде- нтифікатор> і правилами:

<ідентифікатор> → <літера> {<літера> | <цифра>} <цифра> → 0 – 9

<літера> → A – Z.

Граматика G3 задає клас лексем-ідентифікаторів – слів, що розпо-

чинаються з латинської літери або літери _ (знак підкреслювання) і складаються з них і десяткових цифр.

<ідентифікатор>

Рис. 1.14

Кожному виведенню слова з аксіоми в граматиці відповідає його виведення (шлях) у СД. Виведення в СД – це проходження в ній за стрілками піддіаграм, що розпочинається з головної діаграми з одно- часною конкатенацією символів-лексем, розташованих у вершинах.

106

Розділ І. ЛОГІКО-АЛГЕБРИЧНІ УНІВЕРСАЛІЇ

При цьому проходження вершини-нетермінала означає негайний тимчасовий перехід до її піддіаграми й повернення назад після вихо- ду з неї. Виведення закінчується на виході з головної піддіаграми. Ре- зультатом його є конкатенація пройдених символів-лексем. Напри- клад, ідентифікатору K_16 відповідає такий шлях: (літера,1) → K →К

(літера,2) →К_ → К_(цифра, 1) → К_1 →К_1(цифра, 1) →К_15.

*Література для CР: алгебричні системи – [62, 79, 97]; узагальнені (неокласичні) алгебричні системи й логіки для них [39, 62, 94, 105, 150]; регулярні вирази, скінченні автомати [7, 23, 52, 97]; КВ-граматики та МП-автомати – [7, 20, 23]; САА та їхні застосування – [23, 24, 32, 52].

Контрольні запитання та вправи

1.Що таке алгебрична система, алгебра й реляційна система? Навести власні приклади таких систем.

2.Що таке замкнена підмножина й підсистема алгебричної системи?

3.Що таке множина твірних алгебри? Навести приклади твірних множин алгебр.

4.Що таке незалежна система твірних алгебри? Навести приклади таких множин.

5.Чим відрізняються ізоморфізм, автоморфізм і гомоморфізм систем?

6.Що таке півгрупа й підпівгрупа? Навести власні приклади півгруп, їхніх підпівгруп і твірних множин.

7.Що означає: одна система моделює іншу?

8.Дати означення наближеної, сильної й точної моделей системи.

9.Які системи називаються еквівалентними?

10.Дати означення конгуенції системи.

11.Що таке ядерна еквівалентність системи?

12.Що означає: узгодженість операцій і предикатів двох систем?

13.Нехай – довільна сукупність непорожніх власних

підсистем системи А . Довести, що перетин B = ∩ D або

D

порожній, або замкнений.

14. Нехай – сукупність усіх підсистем системи А , що містять

B . Довести, що перетин B* усіх систем із є найменшою

підсистемою А , що містить усі елементи B .

15. Сформулювати лему про ядерну еквівалентність гомоморфізму.

107

ПРОГРАМУВАННЯ

16. Довести, що ядерна еквівалентність гомоморфізму φ: A → B системи А в систему B є конгруенцією.

17.Довести, що класи лишків за модулем p задають

конгруенцію на Z.

18.Навести інші нетривіальні конгруенції цілих чисел. Що можна сказати взагалі про їхню кількість?

19.Знайти всі конгруенції алгебри A = ({a,b,c,d},F ), де унарна

20.Що таке типізована операція?

21.Дати визначення багатосортної Ω -системи.

22.Що таке вільна Ω-система?

23.Сформулюйте теорему про вільні Ω -системи.

24.Дати визначення Ω-алгебри слів, регулярної Ω -системи мов

ісистеми алгоритмічних алгебр.

25.Довести, що система дійсних квадратних матриць розміром n ×n є півгрупою відносно додавання та множення (у

першому випадку – комутативною, у другому – ні). Що можна сказати про систему твірних у цих півгрупах?

26.Що таке список і лінійний список?

27.Сформулювати основні операції для лінійних списків.

28.Що таке стек і черга?

29.Сформулювати основні операції для стеків і черг.

30.Дати визначення графа, зваженого графа, мультиграфа й мережі.

31.Що таке дерево?

32.Що таке піддерево й листок дерева?

33.Довести лему 1.5 про дерево.

34.Що таке висота дерева?

35.Що таке дерево пошуку та збалансоване дерево?

36.Навести визначення скінченного, детермінованого й недетермінованого автоматів.

37.Дати визначення ізоморфізму й гомоморфізму скінченних автоматів.

38.Зобразити графічно автомат Q ={q0,q1,q*}, {q1,q*},F =

108

Розділ І. ЛОГІКО-АЛГЕБРИЧНІ УНІВЕРСАЛІЇ

таких рівнянь. Показати, що кожна скінченно-автоматна мова є найменшим розв'язком певної системи лінійних рівнянь із б) [23, 52].

41.Побудувати регулярний вираз і детермінований автомат для множини десяткових скінченних дробів вигляду

xx...x.yy...y , де x,y – довільні десяткові цифри.

42.Побудувати регулярний вираз і за ним детермінований автомат, які описують: 1) сукупність ідентифікаторів – слів, що складаються з латинських літер і цифр і розпочинаються

злітери; 2) сукупність адрес електронної пошти; 3) сукупність Інтернет-адрес.

43.Те саме, що й у вправах 37-38, але застосувати: а) розширену БНФ; б) синтаксичну діаграму.

44.Детермінізувати автомат Q із вправи 15.

45.* Довести, що мова L2 ={anbn : n ≥ 0} не є регулярною.

46.Наведіть визначення КВ-граматики.

47.Побудувати за даною КВ-граматикою відповідну до неї обчислювальну процедуру.

48.Що таке еквівалентні КВ-граматики? Навести кілька прикладів таких граматик.

49.Символ X об'єднаного алфавіту N T називається

недосяжним у граматиці G = (N,Σ,P,S ), якщо в ній немає

жодного виведення вигляду S uXv,u,v (N T )* . Якщо в

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

50.Довести, що для будь-якого виведення слова в граматиці G існує його лівостороннє виведення.

51.Показати, що для будь-якої РКВ-граматики існує еквівалентна КВ-граматика.

52.Наведіть визначення LL (k )-граматик. Які переваги мають

LL (k )-граматикою для деякого k > 0 ?

54.Побудувати LL (1)-граматику для сукупності ідентифікаторів.

55.Наведіть приклад не LL (1)-, а LL (2)-граматики.

109

ПРОГРАМУВАННЯ

граматики.

60.Довести, що МП-автомат A з доведення теореми 1.4 за побудовою є МП-аналізатором типу розгортки для граматики G.

61.Довести твердження (*) з доведення теореми 1.4.

62.Довести, що для будь-якого МП-автомата A з множиною

L ={uuR : u {a,b}*}, де uR – дзеркальне обернення слова u .

64.Побудувати МП-аналізатори типу розгортки для граматик із правилами: а) S →AB|b , A →SA|a ; б) S →SS|A , A →(A)|( ).

65.Побудувати МП-аналізатор для мови Діка (див. вправу 53).

66.Що таке БНФ та РБНФ?

67.Що таке синтаксична діаграма?

68.Побудувати синтаксичну діаграму та РБНФ для мови Діка в алфавіті (,),[,],{,}.

69.Побудувати синтаксичну діаграму та РБНФ для понять мови

С(див. підрозд. 3.2.2):

а) <ціле_число>; б) <дійсне_ число>; в) <літерал >; г) <коментар>;

д) <шістнадцяткова_константа>; е) <вісімкова_константа>.

110