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

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

1

2

4

5

6

8

7 9

в)

■

Деякі важливі алгоритми на бінарних деревах розглядаються в підрозд. 4.3.

Скінченні автомати. Скінченні X -автомати – це спеціальний клас обчислювальних процедур (див. підрозд. 1.3.4), призначений для синтаксичного аналізу регулярних мов. Обчислення в таких процеду-

91

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

рах відбуваються в натуральному часовому просторі, а стани мають структуру пар (q,u), де q належить певній скінченній сукупності Q

внутрішніх станів, а u – слово в певному вхідному алфавіті X . Пере- буваючи в стані (qt ,ut ) і читаючи першу літеру слова ut , незалежно

від моменту часу t автомат переходить у новий стан (qt +1,ut +1 ), в якому друга компонента або збігається зі словом ut , або є його закін-

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

пускається автоматом. Заключний стан вигляду (qt ,ε) і обчислення,

яке закінчується таким станом, будемо називати термінальними. Для префікса v , що допускається автоматом, завжди існує результативне

термінальне обчислення зі вхідним станом (q0,v ). Таким чином, су- купності всіх префіксів і слів, які допускаються автоматом A , збіга- ються й називаються мовою L (A), що допускається цим автоматом. Подібні мови називають скінченно-автоматними.

Формально скінченний X -автомат – це п'ятірка A = (Q,X,δ,q0,F ), де: Q – скінченна множина внутрішніх станів;

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

δ: Q ×(X ε) → B (Q ) – функція переходів, керує роботою автомата;

q0 Q – початковий внутрішній стан; F Q – множина заключних станів.

Перехід δ(q,ε) = p означає, що автомат у процесі обчислення пере-

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

92

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

більше ніж в один внутрішній стан і при цьому не має ε-переходу, то він називається детермінованим.

Скінченні автомати зручно задавати у вигляді орієнтованих зва-

Шлях у графі автомата називається повним, якщо він розпочина- ється в початковій вершині й закінчується в одній із заключних. Ко- жному повному шляху в автоматному графі відповідає певне резуль- тативне термінальне обчислення автомата, і навпаки. Слово в алфа- віті Х, побудоване в результаті конкатенації символів, якими зважені стрілки в повному шляху, є таким, що допускається автоматом. На- приклад, для вищенаведеного автомата слово 100 допускається, а 11

δ = {q0a → q*;q*b → q*;q*c → q0}. Очевидно, що L (A2 )= ab* (cab* )* .

Введемо відношення безпосереднього переходу на конфігураціях скінченного автомата A : (q,aw)|−(p,w), якщо в автоматі є команда

qa → p . Нехай |−* – рефлексивно-транзитивне замикання цього від-

93

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

b

Рис. 1.8

Теорема 1.5 (Кліні). Класи регулярних і скінченно-автоматних мов збігаються.

Доведення. Покажемо, як побудувати скінченний автомат A , що розпізнає регулярну мову, задану даним виразом R . Автомат A буду- ється відповідно до структури виразу R , має строго один заключний стан, у ньому немає переходів у початковий стан та із заключного стану в інші. Нехай B та C – недетерміновані скінченні автомати для регулярних виразів T та S , відповідно.

1. Для виразу R = ε A має вигляд :

рис. 1.9. Тут i – новий початковий стан, f – новий заключний стан.

Автомат A спочатку по ε переходить у початкові стани автоматів B та C , а закінчує роботу ε -переходом із заключних станів автоматів B та C у стан f . Початковий і заключний стани автоматів B та C

не є такими для нового автомата A .

94

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

C

Рис. 1.9

4. Для виразу R = TS автомат A будується, як показано на рис. 1.10:

Рис. 1.10

Початковий стан автомата B стає початковим, а заключний стан автомата C – заключним для нового автомата. Початковий стан C і заключний стан B ототожнюються.

5. Для виразу R = S* автомат A будується таким чином (рис. 1.11):

i

Рис. 1.11

Тут i та f – нові початковий і заключний стани. Автомат B зацикле- ний – у ньому з'явився ε -перехід від заключного до початкового стану.

95

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

Отже, усі випадки для регулярного виразу R розглянуто. Зворотне доведення можна знайти в [23, 52] (вправа 39) ■ Як показує наступна теорема, розпізнавальні можливості недетер-

мінованих і детермінованих скінченних автоматів однакові. Автомати A та B називаються еквівалентними, якщо L (A) = L (B ).

Теорема 1.6 (детермінізація скінченних автоматів). Для довільного недетермінованого скінченного автомата A = (Q,X,δ,q0,F ) існує екві-

валентний йому детермінований автомат B .

Доведення. Побудуємо детермінований скінченний автомат B = {2Q ,X,δ1,Q0,F1 } . Станами його є підмножини станів недетерміно-

ваного автомата. Щоб одержати стан детермінованого автомата, в який здійснюється перехід по даному символу з даного стану M Q ,

потрібно об'єднати всі стани недетермінованого скінченного автома- та, в які існують переходи по даному символу з усіх вершин множини M , а потім приєднати до них усі вершини, досяжні зі станів M , за допомогою серій ε -переходів. Початковий стан Q0 містить стан q0 і

всі стани, досяжні з нього за допомогою всіх можливих серій ε - переходів. Покладемо сукупність заключних станів F1 = {Q′ Q : Q′ ∩ F ≠ } . За побудовою кожному обчисленню в авто-

маті A з довільним вхідним словом відповідає аналогічне обчислення в детермінованому автоматі, і навпаки ■

Насправді в детермінованому еквіваленті автомата A досяжними

будуть не всі стани булеана 2Q , а значно менше. Саме їх можна взяти за сукупності станів автомата B , а не весь булеан. Наприклад, з восьми

станів булеана 2Q автомата з рис. 1.7 досяжними будуть лише два: {q0} та {q1,q*}. Зведений детермінований еквівалент зображено на рис. 1.12. Він спростився за рахунок усунення ε -переходу.

0

Рис. 1.12

96

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

Контекстно-вільні граматики та МП-автомати. Як і скінченні

X -автомати, контекстно-вільні граматики (КВ-граматики) та МП- автомати – це спеціальні класи недетермінованих обчислювальних процедур, призначені для математичного опису синтаксису формаль- них мов та їхнього синтаксичного аналізу. КВ-граматики вперше були застосовані при описі мови програмування Алгол-60 у вигляді так званих форм Бекуса – Наура (БНФ). Розглянемо ці формалізми й про- блему ефективного синтаксичного аналізу мов, заданих ними.

S – аксіома з множини N . Кажуть, що слово uwv безпосередньо ви-

водиться зі слова uXv у граматиці G (позначається uXv → uwu ), як- що X → w P . Ланцюжок слів вигляду u1 → u2 → ... → un називається

виведенням (обчисленням) слова un зі слова u1 у граматиці G . Позна-

чимо рефлексивно-транзитивне замкнення відношення безпосере- днього виведення в граматиці G . Контекстно-вільною мовою (КВ- мовою), породженою граматикою G , називається множина

L(G ) = {x T * : S x } .

Дві КВ-граматики називають еквівалентними, якщо вони поро- джують одну й ту саму мову.

Приклад 1.24. Побудуємо КВ-граматику для мови L2 = {anbn : n ≥ 0} .

КВ-граматика G1 = (T,N,P,S), де T = {a,b} , N = {S } , P = {S → aSb,S → ε} , породжує мову L2 . Дійсно, для будь-якого натурального n ≥ 0 у грама-

тиціG1 є виведення вигляду S anSbn anbn . Таким чином, D L(G1). Однак інших виведень у граматиці G1 не існує. Отже, D = L(G1) ■

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

розширених (РКВ-граматик). Їх також називають розширеними БНФ

(РБНФ). В останніх стрілочка в правилах замінена метасимволом ::=. У правилах РКВ-граматик використовуються метасимволи |,(,),[,],{,},+,*,-,\,<,>. Символ | читається як "або". Пара круглих дужок об'єднує кілька конструкцій в одну загальну. Конструкція у квадрат-

97

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

них дужках може бути відсутньою. Конструкція у фігурних дужках означає ітерацію записаного в них виразу (див. підрозд. 1.4.3). За нею може йти один із модифікаторів: *,+ або (n,m). Модифікатор іте-

рації означає, що вираз у дужках може повторюватися: 1) нуль або будь-яку кількість разів; 2) не менше одного разу; 3) від n до m разів.

Наприклад, розширені правила S →a{S}*b та S → a{S } +b еквівале-

S → a{S }(2,3)b еквівалентне правилу S → aSSb|aSSSb .

Діапазон символів кодової таблиці скорочено записується з вико- ристанням метасимволу – : наприклад, A–Z означає сукупність усіх великих латинських літер від A до Z. Дужки <,> використовуються для йменування нетерміналів.

Увага! Щоб метасимвол можна було використовувати як терміна- льний, перед ним необхідно вжити бек-слеш \. Бек-слеш \ також за- стосовують для перенесення правила на наступний рядок тексту ►

тне правилу S →ABCDEFGHEIJKLMNOPQRSTUVWXYZ.

Іншим прикладом РКВ-граматики є граматика G2 , яка породжує

сукупність арифметичних виразів. Її нетерміналами є <вираз>, <дода-

нок> ,<операція1>, <множник> , <операція2>, <змінна> та <число>,

аксіомою – <вираз>, а правилами –

<вираз> → <доданок> [<операція1> <доданок>] <доданок> → <множник>[<операція2> <множник>] <множник> → \(<вираз>\)|<змінна> | <число> <операція1> →\ + | \-

<операція2> →\* | / <число> → {<цифра>} <цифра> → 0 – 9

<змінна> → A – Z | a – z

Граматику G2 буде використано в підрозд. 4.5. Побудуємо в ній виведення виразу (a +12):

<вираз>→<доданок> →<множник> →(<вираз>) →(<доданок> <опера- ція1> <доданок>) →(<множник> <операція1> <доданок>) →(<змінна> <операція1> <доданок>) →(a <операція1> <доданок>) →(a + <дода-

98

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

нок>) → (a + <число>) →(a + {<цифра>}) →(a + <цифра><цифра>) →( a +

1<цифра>) → (a + 12 ).

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

Для аналізу виведень у КВ-граматиках застосовують дерева виве-

день. Нехай G = (T ,N ,P,S ) – довільна КВ-граматика. Зважене упоряд-

коване дерево D називається деревом виведення граматики G , якщо виконуються умови:

1)Корінь дерева зважений аксіомою S .

2)Якщо D1...,Dk – усі піддерева дерева з коренем, зваженим нете-

рміналом X , а корені піддерева Di зважені символом Xi T N {ε} , то правило X → X1...Xk належить P . Якщо при цьому Xi T , то ко- рінь піддерева Di є листком дерева D .

Кожному виведенню з аксіоми граматики G відповідає певне де- рево виведення, і навпаки, – за деревом виведення можна побудува- ти саме виведення (напр., лівостороннє) слова в граматиці. На рис. 1.13 зображені два дерева виведень граматики G1 :

S S

99

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

З усього комплексу задач, що розглядаються в теорії КВ-граматик, зупинимось тільки на проблемі ефективного синтаксичного аналізу мов, які породжуються цими граматиками. Відомо, що алгоритм перевірки існування виведення даного слова у КВ-граматиці має складність, бли-

зьку до O(n3 ) , де n – довжина слова, що є неприйнятним із практично-

го погляду []. Тому було докладено значних зусиль для пошуку класів КВ- граматик, які були б, з одного боку, достатньо потужними, а з іншого – допускали б лінійну оцінку алгоритму синтаксичного аналізу. Одним із найпростіших таких класів є клас LL(k) -граматик.

Для КВ- (РКВ)-граматики G і ланцюжка w , що складається з тер-

не число. Множина FIRSTk (w) складається з термінальних префіксів

довжиною k усіх слів, що виводяться з w .

Граматика G називається LL(k)-граматикою, якщо для кожного її нетермінала X N , пари продукцій X →v , X → w і кожного лівосто-

побудови лівостороннього виведення для даного термінального слова на кожному кроці за k наступними його символами однозначно виб- рати праву частину продукції для продовження виведення (звісно, якщо така взагалі існує).

Якщо взяти граматику G1 для мови L2 , то вона є LL (1)- граматикою. Дійсно, довільне лівостороннє виведення в граматиці G1 має вигляд S anSbn ,n ≥1 і для нього виконується LL (1)- властивість FIRST1 (aSbn +1 )(= {a})∩ FIRST1 (εbn )(= {b})= .

З'ясуємо, чи виводиться в граматиці G1 слово aabbb . Слово розпо- чинається з термінала a FIRST1 (aSb), тому на першому кроці застосо-

вується продукція S → aSb . Далі в слові знову йде літера a , тому й на другому кроці виведення має застосовуватись та сама продукція. Маємо виведення S → aSb → aaSbb . Далі в слові йде літера b . Оскільки

b FIRST1 (aSb), то продукція S → aSb застосована бути не може. За-

лишається продукція S → ε , що приводить до виведення S → aSb → aaSbb → aabb , яке вже не може бути продовженим. Отже, слово aabbb не може бути породженим у граматиці G1 .

100