Статьи

Самостійна робота 13: кінцеві автомати

  1. Детермінований кінцевий автомат
  2. приклад 1
  3. Приклад 2. Символьний літерал
  4. приклад 3
  5. Кінцевий автомат з виходом
  6. Приклад 4. CRLF
  7. Приклад 5. Коментарі C ++
  8. 1
  9. 2
  10. 3
  11. 4
  12. 5
  13. 6
  14. 7
  15. 8
  16. 9

Загальна зміст

11 балів

Цілі: набуття навичок конструювання і програмної реалізації простих детермінованих кінцевих автоматів.

критерії повноти

  1. Складено схему кінцевого автомата (якщо поставлено конкретне кінцевий автомат).
  2. Реалізована окрема функція або об'єкт, що реалізують кінцевий автомат.
  3. Знайти або створити приклад вхідної послідовності, досить повно демонструє поведінку автомата ( "досить повно" = автомат відвідує все свої статки в процесі обробки цієї послідовності).

Область застосування кінцевих автоматів: транслятори (синтаксичний аналіз, "регулярні вирази"), системи управління (апаратні контролери, мережеві протоколи), моделювання систем об'єктів, включаючи фізичні пристрої.

Поняття кінцевого автомата вже вводилося в " основах обчислень ". Нижче воно розглянуто більш докладно і дано в традиційній формулюванні. На вхід автоматів будемо відправляти "символи".

Кінцевий автомат (КА; автомат з кінцевим безліччю станів) finite automaton (FA), finite state machine (FSM) - абстрактна машина, яка:

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


Отже, математично кінцевий автомат задається п'ятіркою (A, Σ, s 0, a, ρ), де:

  • A - алфавіт символів введення (непорожнє кінцеве безліч);
  • Σ - непорожня скінченна множина можливих станів автомата;
  • s 0 ∈ Σ - початковий стан;
  • a: Σ → {0,1} - предикат, який визначає чи є заданий кінцевий стан приймають, коли їхня мета автомата - розпізнавання певних ланцюжків вхідних символів. Замість довільного предиката може використовуватися фіксоване безліч станів F ⊆ Σ, для яких a повертає істину. Конкретне приймає стан може служити результатом розпізнавання (вказувати, що саме було розпізнано);
  • ρ: A × Σ → Σ - правила переходу, на кожному кроці визначають наступний стан автомата по вхідному символу і попереднього стану. Зазвичай перераховується лише частина всіх можливих вихідних комбінацій пар символ - стан. У цьому випадку передбачається, що якщо трапляється незазначена комбінація, то автомат зупиняється. В "Основах обчислень" ця функція була позначена g, а її табличне представлення - G. Використання списку правил замість таблиці зазвичай дозволяє представити автомат набагато більш компактно. У загальному випадку правила переходу можуть не бути "звичайної" функцією в математичному сенсі.

Часто кінцеві автомати зображуються у вигляді діаграм, на яких стану зображені у вигляді гуртків або овалів, які з'єднані позначають переходи стрілками, позначеними відповідними вхідними символами. Непомічені стрілки відповідають переходу "при всіх інших (невказаних) вхідних символах". При цьому беруть стану позначають подвійний або ширшої кордоном гуртка, а вхідний стан стрілкою, яка не має прив'язки до стану результату.

Детермінований кінцевий автомат

Детермінований кінцевий автомат (ДКА) deterministic finite automaton (DFA) - кінцевий автомат, для якого правило ρ є функцією тільки поточного стану і вхідного символу. Замість функції ρ можна використовувати кінцеве безліч правил виду A × Σ → Σ (трійок), при цьому необхідно, щоб для кожного елемента A × Σ існувало не більше одного правила.

Діаграми зручні при складанні та аналізі кінцевих автоматів. Побудовану діаграму легко "механічно" перевести в програмний код, що моделює (який реалізує) відповідний ДКА. Однак, зробити це можна різними способами. Вибір конкретного способу залежить від:

  1. Зручності інтеграції в зовнішній програмний код.
  2. Простоти внесення змін до отриманий код (зміни поведінки автомата).
  3. Вимог до швидкодії.

З точки зору п.1 потрібно визначити:

  • як автомат буде отримувати вхідні символи: чи буде його викликати зовнішній код, передаючи кожен наступний символ, або ж автомат, будучи запущений, буде читати символи самостійно з деякого джерела (потоку, рядки, масиву і т.п.);
  • чи повинен автомат явно представляти стан, в якому знаходиться (чи є необхідність його передавати зовні або зберігати для подальшого відновлення), і в якій формі його слід представляти;
  • чи є необхідність явно сигналізувати застопорення або прийняття рядки або взагалі будь-яка зміна стану;
  • чи є необхідність змінювати набір правил під час виконання програмного коду, або ж вони можуть бути зафіксовані в програмі.

Існують окремі бібліотеки, що дозволяють будувати довільні кінцеві автомати і вирішальні все або багато зі згаданих питань. Тут же ми обмежимося "ручним" кодуванням досить простих випадків.

приклад 1

Нехай дано:

  • A = {a, b, c} (три можливих вхідних символу);
  • Σ = {0, 1, 2, 3, 4} (п'ять можливих станів автомата);
  • s 0 = 0;
  • F = {4} (одне приймає стан);
  • ρ = {(a, 0) → 1, (b, 1) → 2, (b, 2) → 4, (c, 2) → 3, (b, 4) → 1, (будь-який символ, 3) → 0}.
Загальна зміст   11 балів   Цілі: набуття навичок конструювання і програмної реалізації простих детермінованих кінцевих автоматів

Діаграма кінцевого автомата

Які рядки приймає цей автомат?

  • Дивимося: послідовність станів 0-1-2-3-0- ... відповідає пропуску будь-якої кількості повторень abc s, де s - будь-який символ. Якщо ж після цього зустрінеться abb, то такий рядок буде прийнята.
  • Те ж саме можна сказати про abbbb (послідовність 0-1-2-4-1-2-4). Взагалі, завдяки циклу 1-2-4 автомат приймає "хвіст" виду abb (bbb) *. Зірочкою позначено довільне число повторень послідовності в дужках, тобто a і (3 i -1) поспіль b (для будь-якого натурального i).
  • Завдяки цьому ж циклу автомат може пропускати рядки, складені не тільки з abc s, але з ab (bbb) * c s, тобто з групами по (3 i -2) поспіль b.

Отже, закодируем розглянутий вище автомат в класичній формі "цикл + switch станом".

Цикл буде зчитувати символи з потоку введення, поки це можливо, або не відбудеться застопорення. Ознака відсутності застопорення будемо зберігати в явній формі в змінної running. Результат функції - відповідь на питання "чи прийшов в кінці роботи автомат до приймаючої стан".

Для зручності продублюємо схему.

Для зручності продублюємо схему

Діаграма кінцевого автомата // Повертає істину, якщо автомат зупинився в приймаючому стані. bool dfa_example (std :: istream & is) {int state = 0; bool running = true; for (char input; is.get (input) && running;) switch (state) {case 0: if (input == 'a') state = 1; else running = false; break; case 1: if (input == 'b') state = 2; else running = false; break; case 2: if (input == 'c') state = 3; else if (input == 'b') state = 4; else running = false; break; case 3: state = 0; break; case 4: if (input == 'b') state = 1; else running = false; break; } // Стан 4 - приймає. return state == 4; }

C ++ , HTML

Той же автомат можна представити в об'єктної формі. Об'єкт автомата буде обробляти по одному символу, який передається йому ззовні. Тобто в даному прикладі цикл for винесено в код, який використовує автомат.

// Кінцевий автомат в об'єктної оболонці, відв'язав від istream - приймає по одному символу. class Dfa_example {int state; public: // Конструктор за замовчуванням встановлює початковий стан. Dfa_example (): state (0) {} // список ініціалізації: тут той же, що state = 0 // Перевірити, чи знаходиться автомат в приймаючому стані. bool accepts () const // const каже, що виклик даної функції не змінює стан об'єкта {return state == 4; } // Повертає брехня, якщо автомат застопорився (можна проігнорувати). // Повертає істину, якщо автомат не застопорився і чекає наступний символ. bool operator () (char input) {switch (state) {case 0: if (input == 'a') state = 1; else return false; break; case 1: if (input == 'b') state = 2; else return false; break; case 2: if (input == 'c') state = 3; else if (input == 'b') state = 4; else return false; break; case 3: state = 0; break; case 4: if (input == 'b') state = 1; else return false; break; default: assert (false); // сюди має бути неможливо потрапити} return true; // нет застопорення}};

C ++ , HTML

Приклад 2. Символьний літерал

розпізнавання символьного литерала C ++ . Розглянемо спрощений синтаксис символьного литерала: непорожній послідовність символів, укладена в одинарні лапки ', можливо екранування лапки символом \.

Розглянемо спрощений синтаксис символьного литерала: непорожній послідовність символів, укладена в одинарні лапки ', можливо екранування лапки символом \

Діаграма автомата-розпізнавача литерала

Дану діаграму легко "перевести" на C ++.

/// Переглядає діапазон масиву символів [from, to). /// Повертає покажчик на символ, наступний за останнім прийнятим (тобто за літералом). /// Повертає nullptr, якщо буквальний ні успішно розпізнано. const char * char_lit (const char * from, const char * to) {// Можливі стану автомата. enum {open_quote, // очікується відкриває 'close_quote, // очікується закриває' not_quote, // перший символ литерала, не може бути 'escape, // після \ accepted, // літерал закінчився stuck // застопорення: чи не буквальний} state = open_quote; while (from! = to) {const char ch = * from ++; switch (state) {case open_quote: state = ch == '\' '? not_quote: stuck; break; case not_quote: switch (ch) {case '\\': state = escape; break; case '\' ': state = stuck; break; default: state = close_quote; } Break; case close_quote: switch (ch) {case '\\': state = escape; break; case '\' ': state = accepted; return from; default:; / * Нічого не змінювати * /} break; case escape: / * просто пропустити символ * / state = close_quote; break; case stuck: return nullptr; default: assert (! "impossible FSM state occured"); }} Return nullptr; // занадто рано скінчилася рядок}

C ++ , HTML

Не важко буде помітити, що отриманий код кілька надмірний. Ми можемо прибрати деякі стану автомата: досить перевірити, що перший символ - лапки до входу в цикл, і тоді стан open_quote не потрібно. Стану stuck і accepted можна прибрати, тому що перехід в них відповідає поверненню значення з функції.

/// Переглядає діапазон масиву символів [from, to). /// Повертає покажчик на символ, наступний за останнім прийнятим (тобто за літералом). /// Повертає nullptr, якщо буквальний ні успішно розпізнано. const char * char_lit (const char * from, const char * to) {// Витягнемо open_quote: даний стан має сенс тільки на першому символі. if (from == to || * from ++! = '\' ') return nullptr; // Можливі стану автомата. enum {close_quote, // очікується закриває 'not_quote, // перший символ литерала, не може бути' escape // після \} state = not_quote; while (from! = to) {const char ch = * from ++; switch (state) {case not_quote: if (ch == '\' ') return nullptr; state = ch == '\\'? escape: close_quote; break; case close_quote: if (ch == '\' ') return from; if (ch == '\\') state = escape; break; case escape: / * просто пропустити символ * / state = close_quote; break; default: assert (! "impossible FSM state occured"); }} Return nullptr; // занадто рано скінчилася рядок}

C ++ , HTML

Втім, аналогічно стану open_quote можна прибрати і стан not_quote, виконавши перевірку другого символу послідовності на нерівність 'також перед циклом.

/// Переглядає діапазон масиву символів [from, to). /// Повертає покажчик на символ, наступний за останнім прийнятим (тобто за літералом). /// Повертає nullptr, якщо буквальний ні успішно розпізнано. const char * char_lit (const char * from, const char * to) {// Витягнемо open_quote: даний стан має сенс тільки на першому символі. if (from == to || * from ++! = '\' ') return nullptr; // Витягнемо not_quote: даний стан має сенс тільки на другому символі. if (from == to || * from == '\' ') return nullptr; // Можливі стану автомата. enum {close_quote, // очікується закриває 'escape // після \} state = * from ++ ==' \\ '? escape: close_quote; while (from! = to) {const char ch = * from ++; switch (state) {case close_quote: if (ch == '\' ') return from; if (ch == '\\') state = escape; break; case escape: / * просто пропустити символ * / state = close_quote; break; default: assert (! "impossible FSM state occured"); }} Return nullptr; // занадто рано скінчилася рядок}

C ++ , HTML

Тепер усередині циклу залишилося всього два можливих стани: close_quote і escape. Замінимо state на булевскому змінну await_quote (її значення відповідає умові state == close_quote). Заодно сумісний перевірки перед циклом в один if.

const char * char_lit (const char * from, const char * to) {// Не менш трьох символів. // Перший символ повинен бути лапками, другий символ не повинен бути лапками. if (to - from <3 || from [0]! = '\' '|| from [1] ==' \ '') return nullptr; bool await_quote = from [1]! = '\\'; for (from + = 2; from! = to;) {const char ch = * from ++; if (await_quote) {if (ch == '\' ') return from; if (ch == '\\') await_quote = false; } Else await_quote = true; } Return nullptr; // занадто рано скінчилася рядок}

C ++ , HTML

Втім, через те, що варіанту await_quote == false відповідає просто пропуск чергового символу з переходом в стан await_quote == true, ми можемо взагалі позбутися від явного стану автомата: в ситуації await_quote == false слід просто пропустити ще один символ.

const char * char_lit (const char * from, const char * to) {// Не менш трьох символів. // Перший символ повинен бути лапками, другий символ не повинен бути лапками. if (to - from <3 || from [0]! = '\' '|| from [1] ==' \ '') return nullptr; for (++ from; from! = to;) {switch (* from ++) {case '\\': if (from ++ == to) return nullptr; break; case '\' ': return from; default:; / * Do nothing * /}} return nullptr; }

C ++ , HTML

Той же самий цикл можна переписати без switch-case компактніше.

const char * char_lit (const char * from, const char * to) {// Не менш трьох символів. // Перший символ повинен бути лапками, другий символ не повинен бути лапками. if (to - from <3 || from [0]! = '\' '|| from [1] ==' \ '') return nullptr; for (++ from ;;) {if (from == to) return nullptr; const char ch = * from ++; if (ch == '\\' && from ++ == to) return nullptr; if (ch == '\' ') return from; }}

C ++ , HTML

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

Подальша оптимізація швидкодії подібного коду може проводитися шляхом обробки декількох символів (байт) за одну ітерацію.

Даний приклад показує, що від схеми КА ми можемо прийти до досить компактному і ефективному коду. Таким чином, КА надає нам інструмент, що дозволяє в ряді випадків "отримувати" ефективні лінійні алгоритми-обробники послідовностей даних, які може бути складно придумати відразу. Що ще важливіше, аналізувати коректність автомата простіше, ніж деякого "начебто правильного" коду. Тому отримати коректний і близький до оптимального код з автомата також може бути простіше.

Додатковий приклад: розпізнавання (і зчитування значення) записи (литерала) цілого числа в форматі, прийнятому в стандартному C ++ 14:

C ++ , HTML

приклад 3

Рішення варіанти 4 з роботи 6 . Потрібно класифікувати послідовність як (-1) монотонно (нестрого) спадну, (+1) монотонно (нестрого) зростаючу, (0) складається з однакових елементів або як (2) містить як зростаючі, так і спадні підпослідовності. Зазначені номери будемо використовувати в якості станів автомата. Всі стану вважатимемо приймають. На вхід автомата будемо подавати числа: (-1), якщо в черговий парі сусідніх елементів другої менше першого, (0), якщо вони рівні, і (+1), якщо другий більше першого.

Шаблон функції порівняння:

template <class Val> inline int compare (const Val & a, const Val & b) {return a <b? 1: b <a? -1: 0; } template <class Val> inline int compare (const Val & a, const Val & b) {return a <b Діаграма КА, классифицирующего послідовність

Перепишемо дану діаграму на C ++.

enum Sequence_type {monotone_decreasing = -1, empty_or_constant = 0, monotone_increasing = 1, not_monotone = 2}; /// ValIt - итератор (узагальнення покажчика), /// послідовність належить напівінтервалів [from, to). template <class ValIt> Sequence_type sequence_type (ValIt from, ValIt to) {Sequence_type state = empty_or_constant; if (from! = to) {for (ValIt a = from, b = std :: next (from); b! = to; a = b ++) {const int relation = compare (* a * b); switch (state) {case monotone_decreasing: if (relation == 1) state = not_monotone; break; case empty_or_constant: if (relation == -1) state = monotone_decreasing; else if (relation == 1) state = monotone_increasing; break; case monotone_increasing: if (relation == -1) state = not_monotone; break; case not_monotone: break; / * Do nothing * / default: assert (! "Sequence_type: impossible Sequence_type"); }}} Return state; }

C ++ , HTML


Спробуйте перетворити (скоротити) даний код аналогічно тому, як це було зроблено в прикладі 2 вище.

Кінцевий автомат з виходом

Кінцевий автомат з виходом finite state transducer (FST) - кінцевий автомат, розширений можливістю виведення. Задається шісткою (A, Σ, s 0, a, ρ, B), де B - алфавіт символів виведення, а ρ зіставляє парі з A × Σ пару з Σ × B *. Тут B * є безліч всіх рядків (включаючи порожню) на алфавіті B. Цей другий елемент (рядок) йде на висновок автомата на відповідному кроці.

Детермінований автомат з виходом обмежений щодо довільного кінцевого автомата з виходом аналогічно "простому" кінцевого автомату (розпізнавачів) тим, що ρ: A × Σ → Σ × B * є математична функція в звичайному сенсі і може бути представлена у вигляді кінцевого безлічі правил з різними лівими частинами.


зауваження 1

Описаний вище автомат з виходом також називається автоматом Мілі Mealy machine. В автоматах Мілі своя вихідна рядок ототожнюється з кожним переходом (стрілкою на діаграмі).

Існує більш вузький клас автоматів, званих автоматами Мура Moore machine, в яких вихід формується тільки в залежності від стану, в яке приходить автомат. Тобто можна вважати, що в автоматі Мура відображення ρ має вигляд A × Σ → Σ, і задано додаткове відображення β: Σ → B *. При кожному переході, автомат виводить β від поточного стану. Таким чином, в автоматі Мура вихідна рядок ототожнюється з кожним станом.


зауваження 2

Слід розуміти, що "перетворення вхідного тексту у вихідний" - це абстрактне формулювання. Елементами B можуть бути якісь "події" або "дії", тоді B * - безліч всіх можливих послідовностей подій або застосування дій з безлічі B. Такий автомат може бути керуючим пристроєм, що посилає сигнали керованій системі.


зауваження 3

Нарешті, автомат-распознаватель ( "автомат без виходу") можна вважати окремим випадком автомата з виходом, в якому (в найпростішому випадку) B = {очікує, застопорився, прийняв} - набір подій, які можуть відбуватися при розпізнаванні рядки.

Приклад 4. CRLF

Як приклад розглянемо кінцевій автомат, что вірішує завдання нормалізації перекладів рядків. Серед керуючих символів кодування ASCII є два символи, які традиційно використовуються для оформлення перекладів рядків: код 10 (LF line feed, зрушити каретку на рядок вниз, \ n в C) і код 13 (CR carriage return, повернути каретку в початок рядка, \ r в C). Є чотири варіанти їх використання: LF (Unix-подібні системи), CR LF (Windows, а також текстові мережеві протоколи, наприклад, HTTP ), А також CR і LF CR, які не використовуються на сучасних системах. Всі ці чотири варіанти будемо "переводити" в \ n. Діаграма автомата приведена нижче.

Діаграма автомата приведена нижче

автомат CRLF

Позначення на стрілках мають вигляд символ на вході (опціонально) / символ на виході, де символ на виході може бути "nl" (переклад рядка, '\ n'), "*" (символ на вході, тобто вивести прочитаний символ ) або "-" (нічого не виводити).

Отже, наш кінцевий автомат буде замінювати у вхідному тексті всі чотири варіанти перекладів на '\ n', а інші символи залишати незмінними. Переведемо цю схему на C ++.

// Повертає покажчик на символ, наступний за останнім записаним символом. char * crlf_normalize (const char * from, const char * end, char * to) {enum {Other, LF, CR} state = Other; while (from! = end) {const char input = * from ++; switch (state) {case Other: switch (input) {case '\ n': * to ++ = '\ n'; state = LF; break; case '\ r': * to ++ = '\ n'; state = CR; break; default: * to ++ = input; } Break; case LF: switch (input) {case '\ n': * to ++ = '\ n'; break; case '\ r': state = Other; break; default: * to ++ = input; state = Other; } Break; case CR: switch (input) {case '\ n': state = Other; break; case '\ r': * to ++ = '\ n'; break; default: * to ++ = input; state = Other; } Break; default: assert (! "crlf_normalize: impossible state"); }} Return to; }

C ++ , HTML

При реалізації кінцевих автоматів замість явно виписаного циклу і switch станом нерідко застосовується простий перехід по мітках (що відповідає станам) за допомогою інструкції goto. Такий код також безпосередньо відповідає схемі автомата і може породжуватися автоматично (програмою за схемою автомата). Його переваги перед використанням switch складаються в потенційно більшої продуктивності отриманого машинного коду (роль змінної, що зберігає поточний стан автомата, грає спеціальний регістр процесора - покажчик інструкції), що може бути помітно якраз при прямій обробці масивів символів в пам'яті. Його недолік - менша гнучкість.

char * crlf_normalize (const char * from, const char * end, char * to) {char input; Other: if (from == end) return to; input = * from ++; if (input == '\ n') goto LF; if (input == '\ r') goto CR; * To ++ = input; goto Other; LF: * to ++ = '\ n'; if (from == end) return to; input = * from ++; if (input == '\ r') goto Other; if (input == '\ n') goto LF; * To ++ = input; goto Other; CR: * to ++ = '\ n'; if (from == end) return to; input = * from ++; if (input == '\ n') goto Other; if (input == '\ r') goto CR; * To ++ = input; goto Other; }

C ++ , HTML

Звичайно, даний код можна трохи модифікувати, щоб прибрати goto, що організують явні цикли. Можна взагалі прибрати все goto, не вводячи додаткових змінних, але код від цього не стане простіше, коротше і зрозуміліше.

Тепер уявімо, що автомат обробляє блок даних заздалегідь невідомої довжини, отримуючи їх блоками обмеженого розміру (має буфер введення і буфер виведення). Таким чином, іноді необхідно припиняти автомат, щоб завантажити або передати наступну порцію даних. Якщо взяти варіант на основі switch, то завдяки явно зберігається станом нескладно модифікувати код так, щоб можна було продовжити обробку наступної порції даних з того стану, в якому автомат закінчив обробку попередньої порції. Для зберігання змінної стану можна організувати об'єкт-обгортку як в прикладі 1 . Однак, на жаль, те ж саме можна сказати про варіант на основі goto: в ньому стан не зберігається в змінної.

Наступний приклад є синтезом цих двох варіантів, що дозволяє обробляти дані в потоці з завантаженням в проміжні буфери. Інструкція switch забезпечує "відновлення" автомата з місця зупинки. Мітки case могли б бути розташовані відразу після інструкцій return, відображаючи логіку роботи (продовження після повернення), але в прикладі вони "підняті", щоб вхідний діапазон обов'язково перевірявся на порожнечу.

// Автомат, що запам'ятовує стан між викликами. class Crlf_normalizer {enum {Other, LF, CR} state; public: // Конструктор встановлює початковий стан. Crlf_normalizer (): state (Other) {} // Оператор "дужки" дозволяє викликати об'єкт даного класу як функцію. // Повертає покажчик на символ, наступний за останнім записаним символом. char * operator () (const char * from, const char * end, char * to) {char input; switch (state) {Other_: case Other: if (from == end) // вихід return state = Other, to; input = * from ++; if (input == '\ n') goto LF_; if (input == '\ r') goto CR_; * To ++ = input; goto Other_; LF_: * to ++ = '\ n'; case LF: if (from == end) // вихід return state = LF, to; input = * from ++; if (input == '\ r') goto Other_; if (input == '\ n') goto LF_; * To ++ = input; goto Other_; CR_: * to ++ = '\ n'; case CR: if (from == end) // вихід return state = CR, to; input = * from ++; if (input == '\ n') goto Other_; if (input == '\ r') goto CR_; * To ++ = input; goto Other_; default: assert (false); return to; }}};

C ++ , HTML

Об'єкт Crlf_normalizer є функтором - його можна використовувати як функцію crlf_normalize з попередніх варіантів, однак, на відміну від них, можна застосовувати його повторно, передаючи дані по частинах, "розриваючи" потік даних в довільній позиції.

Приклад 5. Коментарі C ++

Нехай дано файл з вихідним кодом на мові C ++. Потрібно видалити з нього всі коментарі. Будемо вирішувати цю задачу за допомогою кінцевого автомата, що одержує на вхід вихідний файл і видає на вихід той же файл, але вже без коментарів. На схемі вказані такі стани:

  • Normal mode - початковий стан, "йде звичайний текст програми".
  • Char literal - йде символьний літерал (зустрілася одинарна лапка).
  • Char escape - в символьному літералі зустрівся escape-символ (зворотна коса риска).
  • String literal - йде строковий літерал (зустрілися подвійні лапки).
  • String escape - в строковому літералі зустрівся escape-символ (зворотна коса риска).
  • Possible comment - в коді зустрілася коса риска, можливий початок коментаря.
  • Oneliner - йде однорядковий коментар (зустрілися дві поспіль йдуть косі риси).
  • Comment concat - в кінці однострочного коментаря зустрівся символ \, можливо, приєднує наступний рядок до коментарю.
  • Multiliner - йде багатостроковий коментар (зустрілася комбінація / *).
  • Possible end - можливе завершення многострочного коментаря (зустрілася зірочка), на діаграмі / sp позначає висновок пробілу.

Схема дещо спрощена в порівнянні з сучасним синтаксисом C ++ (не підтримуються 'всередині числових літералів, а також raw-літерали символів і рядків).

Схема дещо спрощена в порівнянні з сучасним синтаксисом C ++ (не підтримуються 'всередині числових літералів, а також raw-літерали символів і рядків)

Автомат C ++ decomment

Наведений нижче код, який реалізує даний автомат, розрахований на обробку одного файлу вихідного коду, цілком розміщеного в оперативній пам'яті. Для виконання цього завдання в пам'ять (об'єкт string) зчитується весь вміст потоку введення. Потім дані обробляє автомат, і результат записується в потік виводу.

// Автомат читає блок символів з діапазону [from, to) // і записує результат обробки в масив за адресою out. char * cpp_decomment (const char * from, const char * to, char * out) {Normal_mode: while (from! = to) {switch (const char in = * from ++) {case '\' ': * out ++ = in; goto Char_literal; case '\ "': * out ++ = in; goto String_literal; case '/': goto Possible_comment; default: * out ++ = in;}} return out; Char_literal: while (from! = to) {switch (const char in = * from ++) {case '\\': // Char_escape * out ++ = in; if (from! = to) * out ++ = * from ++; break; case '\' ': * out ++ = in; goto Normal_mode; default: * out ++ = in;}} return out; String_literal: while (from! = to) {switch (const char in = * from ++) {case '\\': // String_escape * out ++ = in; if (from! = to) * out ++ = * from ++; break; case '\ "': * out ++ = in; goto Normal_mode; default: * out ++ = in; }} Return out; Possible_comment: if (from == to) return * out ++ = '/', out; switch (const char in = * from ++) {case '/': goto Oneliner; case '*': goto Multiliner; default: out [0] = '/'; out [1] = in; out + = 2; goto Normal_mode; } Oneliner: while (from! = To) {switch (const char in = * from ++) {case '\ n': * out ++ = in; goto Normal_mode; case '\\': // Comment_concat if (from! = to) ++ from; // just skip the next char break; default:; // skip}} return out; Multiliner: while (from! = To) {if (* from ++ == '*') goto Possible_end; } Return out; Possible_end: if (from! = To && * from ++ == '/') {* out ++ = ''; goto Normal_mode; } Goto Multiliner; }

C ++ , HTML

Замість мітки в коді, кожному стану можна зіставити власну функцію. Тоді goto замінюються на виклик функції. Однак, це має практичний сенс тільки в тому випадку, якщо компілятор гарантовано виконує оптимізацію хвостового виклику (тобто фактично замінює виклики функцій на ті ж самі goto).

Ряд варіантів нижче пропонують виконати аналогічне завдання (видалення коментарів) для інших мов програмування. Її можна вирішувати шляхом заміни автомата в коді вищенаведеного прикладу на автомат для заданого мови програмування.

1

Видалення коментарів з вихідних файлів на мові MATLAB .

синтаксис :

  • Коментарі
    1. Однорядкові: (варіант 1) починаються з% або (варіант 2) с ....
    2. Багаторядкові: починаються з% {, закінчуються%}.
  • Рядкові літерали: в одинарних лапках: 'the simplest'. Escape-послідовності як в C.

2

Видалення коментарів з вихідних файлів на мові Pascal (передбачається діалект Free Pascal ).

синтаксис :

  • Коментарі
    1. Однорядкові: починаються з //.
    2. Багаторядкові, варіант 1: починаються з {, закінчуються}.
    3. Багаторядкові, варіант 2: починаються з (*, закінчуються *).
  • Рядкові літерали: в одинарних лапках 'no abstract escape-seqs'. Escape-послідовності не передбачені.

3

Видалення коментарів з вихідних файлів на мові Python .

спрощений синтаксис :

  • Коментарі - тільки однорядкові: починаються з #.
  • рядкові літералі
    1. "Короткі" (однорядкові): в одинарних лапках 'left' або в подвійних лапках "right". Escape-послідовності як в C.
    2. "Довгі" (багаторядкові): в потроєних одинарних лапках '' 'too' much 'nuisance' '' або в потроєних подвійних лапках "" "let me speak" Abracadabra "!" "".

4

Видалення коментарів з вихідних файлів на мові Lua .

спрощений синтаксис :

  • Коментарі
    1. Однорядкові: починаються з -.
    2. Багаторядкові: починаються - [[, закінчуються]].
  • рядкові літералі
    1. В одинарних лапках: 'say "Hello!" \ N'. Escape-послідовності як в C.
    2. У подвійних лапках: "I do not say \" Hello! \ "\ 0". Escape-послідовності як в C.
    3. Від [[до]] без escape-послідовностей.
    4. Від [= [до] =] без escape-послідовностей. Строго кажучи, може бути довільне число знаків = в відкриває скобці (п.3 - окремий випадок), стільки ж знаків = повинно бути в закриває дужки. Коректна поведінка в такій ситуації можна реалізувати за допомогою додаткового стану: целочисленного лічильника знаків =.

5

Видалення коментарів з вихідних файлів на мові Julia .

спрощений синтаксис

  • Коментарі
    1. Однорядкові: починаються з #.
    2. Багаторядкові: починаються з # =, закінчуються = #. Строго кажучи, вони поводяться як дужки, тобто скільки було відкривають # =, стільки потім повинно бути і закривають = #. Коректна поведінка в такій ситуації можна реалізувати за допомогою додаткового стану: целочисленного лічильника поточної глибини укладення (кількості зустрінутих до моменту відкритих # =).
  • Символьні та рядкові літерали
    1. В одинарних лапках: '\\'. Escape-послідовності як в C.
    2. У подвійних лапках: "This is a \" quote \ "". Escape-послідовності як в C.
    3. У потроєних подвійних лапках: "" "Contains" quote "characters" "".
    4. Призначені для користувача рядкові літерали: буква, за якою відразу слід строковий літерал в подвійних лапках, але вже без escape-послідовностей. Приклад: r "^ \ s * (?: # | $)".

6

Видалення коментарів з вихідних файлів на мові Haskell .

спрощений синтаксис

  • Коментарі
    1. Однорядкові: починаються з -, після яких йде або -, або символ пробілу, або буква (це важливо, тому що в коді на Haskell можливі операції на кшталт ->, які не повинні випадково відкривати коментар).
    2. Багаторядкові: починаються з {-, закінчуються -}. Можуть бути вкладеними як дужки, тобто на кожну відкриває пару {- має припадати своя закриває пара -}. Коректна поведінка в такій ситуації можна реалізувати за допомогою додаткового стану: целочисленного лічильника поточної глибини укладення (кількості зустрінутих до моменту відкритих {-).
  • Символьні та рядкові літерали
    1. В одинарних лапках: '\ t'. Escape-послідовності як в C.
    2. У подвійних лапках: "Hello, \ n". Escape-послідовності як в C.

7

Замінити маленькі букви, початківці пропозиції, на великі. Визначити кількість пропозицій (додаткове стан: лічильник пропозицій). Вважати, що кожне речення закінчується принаймні однією літерою, за якою слідує послідовність точок, знаки оклику та знаки, а потім або закінчується вхідна послідовність, або йде послідовність символів пробілів.

8

Виконати розпізнавання записи (литерала) числа з плаваючою точкою в форматі, прийнятому в мові C. Автомат повинен визначати праву межу записи і зберігати розпізнане число по переданої посиланням на змінну.

Приклади літералів: .10, 1., 2e2, 1.05E-50, 500.e + 100.

9

Побудувати кінцевий автомат, що розпізнає послідовності з нулів і одиниць, що містять парне число одиниць і не містять одиниць, що йдуть підряд один за одним.

приклади

00000 - прийняти

01000 - не брати (непарне число одиниць)

00011 - не брати (дві одиниці підряд)

10100 - прийняти

10110 - не брати (непарне число одиниць і дві одиниці підряд)

Загальна зміст

Кувшинов Д.Р. © 2016

Enum {close_quote, // очікується закриває 'escape // після \} state = * from ++ ==' \\ '?
B <a?

Новости