У цій лабораторній роботі я реалізував скінченний автомат для простих регулярних виразів із застосуванням патерну об’єктно-орієнтованого програмування "State". Загальна ідея скінченних автоматів полягає в тому, що вони мають обмежену множину станів і визначені переходи між ними, які спрацьовують залежно від символів вхідного рядка. Під час обробки кожного символу автомат переходить у стан, що відповідає цьому символу, і продовжує роботу доти, доки не вичерпає вхідний рядок.
Патерн State робить код чистим і надає йому певну архітектуру: кожен стан автомата винесено в окремий клас, який відповідає за власну логіку перевірки символу та за перелік можливих наступних станів. Завдяки цьому додавання нових операторів або зміну поведінки переходів достатньо реалізувати в новому або існуючому класі без втручання в загальну структуру автомата.
Я імплементував лише базовий синтаксис регулярних виразів: точне порівняння ASCII-символів, універсальний оператор "." для будь-якого символу, квантори "*" (нуль або більше повторень) і "+" (одне або більше).
Реалізація починається з абстрактного класу State, який визначає методи ініціалізації стану, перевірки символу (check_self) та механізм переходу (check_next). Кожен підклас: StartState, TerminationState, DotState, AsciiState, StarState, PlusState — успадковує ці методи й реалізує власну поведінку. Наприклад, StartState і TerminationState завжди повертають False, бо не приймають ніяких символів, AsciiState зберігає символ і приймає тільки його, DotState завжди повертає true для будь-якого символу, а квантори StarState і PlusState організовують петлі повторювань попереднього стану.
Клас RegexFSM формує автомат у конструкторі: послідовно створює об’єкти станів для кожного символу вхідного шаблону та зв’язує їх через списки next_states. Після завершення обходу регулярного виразу додається TerminationState, який позначає коректний кінець шаблону. Така лінійна побудова НСА відображає структуру самого regex виразу.
Обробка вхідного рядка відбувається методом check_string, який перевіряє стрічку за допомогою допоміжної рекурсивної функції _match. Ця функція виконує backtracking: для кожного символу перевіряє відповідність поточному токену, враховуючи наявність кванторів. Якщо зустрічається *, спершу пробує нуль повторів (пропустити символ), потім забирати по одному символу до кінця стрічки поки вона не закінчиться або не знайдеться правильний прохід до кінця стрічки і regex виразу. Аналогічно для + спочатку вимагається один успішний збіг, а далі пробуються додаткові.
Код складається з чіткого розділення: стани займаються лише перевіркою символу, а клас RegexFSM — побудовою автомата і керуванням процесом backtracking. Це дозволяє просто адаптувати або розширювати функціональність регулярних виразів шляхом створення нових станів у рамках патерну State.