.doc ».
Чи не коректна форма запису обмежень, може призвести до не коректні результатами роботи інтерпретатора.
Висновки
У даному розділі була розроблена структура програми, розроблені програмні інтерфейси класів для роботи з даними, файлами і користувача інтерфейсом, розроблені схеми алгоритмів файлових операції, розроблена підтримка виконання користувальницьких інтерфейсів.
4 Теорія формальних мов
При обробці текстів виникає ряд завдань. Це завдання, пов'язані з проблемою завдання мови, або генерації його ланцюжків, завдання визначення приналежності деякого безлічі слів заданому мови, задачі ідентифікації ланцюжків. Для їх вирішення розроблено безліч методів, причому деякі з них працюють, тільки з певним класом мов (наприклад, з мовами програмування), інші ж є універсальними.
4.1 Ланцюжки символів і операції над ними
Алфавітом називається непорожнє кінцеве безліч символів.
Ланцюжок, або рядок - це послідовність символів деякого алфавіту, при цьому символи в рядку можуть повторюватися. Для ланцюжка важливий її склад, порядок символів і їх кількість.
Довжиною ланцюжка є кількість символів в ній. Наприклад, ланцюжок має довжину.
Два ланцюжки і збігаються (рівні):, якщо вони мають один і той же склад і порядок символів, і їх кількість.
Ланцюжок, що не містить символів, називається порожньою ланцюжком, позначається через або.
Будь-яка послідовно узята частина ланцюжка є її подцепочкой, власний суфікс - це частина рядка, що містить її останній символ і не містить перший, власний префікс - це частина рядка, що містить перший символ і не містить останнього.
Над ланцюжками можна виділити наступні операції:
конкатенацію, або зчепленням (складанням) ланцюжків, називається рядок, отримана їх об'єднанням, наприклад
,
тоді конкатенація ланцюжків і буде мати вигляд. Так як в ланцюжку важливий порядок символів, очевидно, що операція додавання НЕ коммутативна, тобто в загальному випадку. Конкатенація асоціативна, тобто.
Звернення ланцюжка - це запис її символів у зворотному порядку, позначається. Наприклад, для ланцюжка її звернення. Властивість операції звернення
.
Ітерація ланцюжка раз - це її зчеплення (повторення) разів, позначається.
Для порожній ланцюжка справедливі наступні рівності:
;
;
;
;
.
4.2 Поняття мови. Способи завдання мов
У загальному випадку мова - це заданий набір символів і правил, що встановлюють способи комбінації цих символів між собою для запису осмислених текстів. Основою будь-якої мови є алфавіт, визначальний набір допустимих символів.
Ланцюжок символів є ланцюжком над алфавітом, якщо до неї входять тільки символи цього алфавіту.
Якщо - деякий алфавіт, то - безліч всіх ланцюжків над алфавітом без, - безліч всіх ланцюжків над алфавітом, включаючи.
Мовою над алфавітом - називають деякий рахункове підмножина ланцюжків кінцевої довжини з безлічі всіх ланцюжків над цим алфавітом. Безліч ланцюжків мови не повинно бути кінцевим, і кожна ланцюжок може мати як завгодно велику довжину.
Для будь-якої мови справедливо.
Мова включає в себе мову
, якщо.
Дві мови еквівалентні
, якщо і.
конкатенацію (об'єднанням) мов і називають мову, що складається зі всіляких зчеплень ланцюжків мов і:
.
Замикання Кліні, або ітерація мови, позначається і визначається рекурсивно
, для, для всіх..
Мова має суффіксним (префіксним) властивістю, якщо ніяка ланцюжок мови не є суфіксом (префіксом) другий ланцюжка.
Мова складається з нескінченної кількості ланцюжків символів над деяким алфавітом, або слів. Але не будь ланцюжок символів над цим алфавітом належить мові, тому існують правила побудови допустимих ланцюжків для кожної конкретної мови. Вказати ці правила - значить задати мову. Існують три основні способи завдання мови:
перерахування всіх допустимих ланцюжків мови (спосіб формальни...
