asyan.org
добавить свой файл
1
  1. Завдання GoTo.



Розв’язок. Безліч станів для кінцевого автомата, за допомогою якого легко здійснити рішення даної задачі складається з трьох елементів — відповідних коментарю, рядковій програмі і власне програмі (у програмній реалізації автомата вони позначаються константами типа com, str, prog, що перераховує. Алфавіт в даному випадку співпадає зі всіма символами кодової таблиці. Функція переходів для більшості символів з цього алфавіту залишає стан колишнім. Виняток становлять лише наступні пари: (‘, com) prog; (‘'’, str) prog; (‘,) com; (‘'’, prog) str. Початковим є стан prog. У цьому ж стані для символів ’g’, ’G’ слід застосувати процедуру обробки, перевіряючу наявність в даному місці програми оператора GOTO. Дану інформацію зручно записати у вигляді наступної таблиці:

Стан

Символ

Операція

Новий стан

com

}

Перейти до наступного символу

prog




решта символів

Перейти до наступного символу

com

str

'

Перейти до наступного символу

prog




решта символів

Перейти до наступного символу

str

prog

{

Перейти до наступного символу

com




'

Перейти до наступного символу

str




G

g

Перевірити наявність оператора GOTO

Перейти до наступного символу

prog




решта символів

Перейти до наступного символу

prog




кінець тексту

Вивести результат підрахунку і завершити роботу





^ 2. Перевірка арифметичного виразу на коректність

Для перевірки відповідності деякого виразу даній граматиці можна побудувати кінцевий автомат, що має три доступні стани (0, 1 і 2 в програмній реалізації) плюс стан виявлення помилки. У кожному з трьох станів допустимими є лише деякі символи. Наявність же на вході іншого символу говорить про помилку. Так стартовий нульовий стан говорить про те, що вираз може починатися з цифри, букви або символу '('. По-перше двох випадках слід пропустити число або ім'я цілком і перейти в стан 1, дужка, що відкривається ж, залишає автомат в тому ж стані. У першому стані допустимими є лише знаки бінарних арифметичних операцій і дужка, що закривається. Знак операції переводить автомат в стан 0, а дужка, що закривається, — залишає його в змозі 1. Якщо поточний символ — останній в аналізованому рядку, то автомат переводиться в стан 2, допустимими для якого є букви, цифри і дужка, що закривається. Залишається тільки перевірити, що загальне число дужок, що відкриваються, рівне числу дужок, що закриваються, а при зустрічі чергової дужки, що закривається, загальна їх кількість до цього моменту не може перевищувати кількість відкриваються дужок, що вже зустрілися. Для цього вводиться цілочисельна змінна — лічильник дужок (у програмі до), спочатку рівна 0. Якщо у виразі зустрілася дужка (стан 0), що відкривається, то до лічильника додається одиниця, якщо що закривається (стан 1), то одиниця віднімається. Дана змінна по ходу обчислень не повинна приймати негативних значень, а при завершенні перегляду (стан 2) повинна бути в точності рівна нулю.

Випишемо таблицю, яка задає описаний автомат.

Стан

Символ

Операція

Новий стан

0

останній символ




2




(

k:=k+1, перейти до наступного символу

0




буква або цифра

пропустити ім'я або число

перейти до наступного символу

1




решта символів

помилка, кінець роботи




1

останній символ




2




)

k := k - 1, перевірити, що k  0,

перейти до наступного символу

1




+, –, *, /

перейти до наступного символу

0




інші символи

помилка, кінець роботи




2

), буква або цифра

якщо k = 0, то вираз коректний,

інакше — помилка і кінець







інші символи

помилка і кінець