Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Вступ

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

Нотамція Бемкуса-Наумра (англ. Backus-Naur form, BNF) - це спосіб запису правил контекстно-вільної граматики, себто формою опису формальної мови. Саме її типово використовують для запису правил мов програмування та протоколів комунікації. У 50-х роках минулого сторіччя Джон Бекус створив цю нотацію розробляючи мову ALGOL. На першому Всесвітньому Комп'ютерному Конгресі, що відбувся у Парижі 1959-го він зробив доповідь на тему «Синтаксис та семантика пропонованої першої міжнародної алгебраїчної мови». Пізніше Наур Пітер спростив її та (за порадою Дональда Кнута) додав до назви своє ім'я.

З часу створення перших програмованих машин було створено понад дві з половиною тисячі мов програмування. Щороку їх кількість поповнюється новими. Деякими мовами вміє користуватись тільки невелике число їх власних розробників, інші стають відомі мільйонам людей. Професійні програмісти зазвичай застосовують в своїй роботі декілька мов програмування.



1. Огляд формальних способів опису мов програмування

1.1 Існуючі метамови опису мов програмування

Опис мови програмування здійснюється шляхом опису синтаксису та семантики. Найпростіший спосіб - просте перерахування всіх ланцюжків. Однак для складних мов цей спосіб неефективний. Тому використовуються спеціальні засоби. Вони ґрунтуються на описі граматичних мов програмування і називаються метамовами. Вони бувають трьох типів:

· вербальні

· графічні

· операційні

Описувати семантику мов програмування просто не вдається. Засоби опису семантики мов програмування ґрунтується на двох підходах:

1. Операційний - завдання семантики здійснюється шляхом опису деяких пристроїв, які володіють пам'яттю та структурованими станами.

2. Аксіоматичний - шляхом опису аксіом, правил висновку та теорії, що доводиться.

Формальній мові семантика необхідна тоді, коли будується реалізація мови (транслятор).

Вербальні метамови

Вербальні мови мають власний алфавіт.

Приклад - Векусові форми нормалі (NBF)

Алфавіт NBF

«<», «>» - нетермінальний ланцюжок з алфавіту W

«|» - «чи»

«:=» - відокремлення лівої частини від правої

«{»,»}» - повторення символів ланцюжка[1].

Приклад. Ідентифікатор задається наступним чином:

NBF: G: (ідентифікатор):

<ідентифікатор>:=<літера>

<ідентифікатор>:=<ідентифікатор><літера>

<ідентифікатор>:=<ідентифікатор><цифра>

<літера>:=A|B|C|…|Z

<цифра>:=1|2|…|9

Або

<ідентифікатор>:=<літера>{<літера>|<цифра>}

<літера>:=A|B|C|…|Z

<цифра>:=1|2|…|9

Графічні метамови

Графічні метамови використовують для опису синтаксису графічні позначення.

Приклад - графічні діаграми Вірта.

Нетермінальний ланцюжок:

Термінальний ланцюжок:

З'єднання ланцюжків:

Приклад - ідентифікатор задається наступними символами:

Літера та цифра:

Операційні метамови

Операційні метамови використовуються для опису процедури деякого пристрою.

Наприклад, кінцевий автомат.

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

Виразам мови, починаючи від найпростіших, ставиться у відповідність позначений ними зміст, що й є їхньою семантикою. Наприклад, у мовах програмування семантика числової сталої - це число, подане в комп'ютері, семантика імені змінної - це ділянка пам'яті, стани якої можна змінювати, семантика оператора - дії комп'ютера з виконання цього оператора.

Форма Бекуса-Наура

Синтаксичні правила, записані у вигляді <поняття>:= <метавираз>, називаються формами Бекуса-Наура, за прізвищами тих, хто їх придумав. Форми Бекуса-Наура скорочено називаються БНФ. Поняття, записане в БНФ ліворуч від»:=», називається її лівою частиною, а метавираз праворуч - правою. Знак»:=» не є символом мови й називається метасимволом. Мова БНФ була створена спеціально для описання синтаксису виразів мов програмування.

Сама по собі БНФ

<оператор присвоювання>:= <ім'я> ':=' <вираз>

задає лише загальну структуру кожного з представників поняття «оператор присвоювання», але не їх конкретний вигляд. Для цього треба описати структуру представників понять <ім'я> і <вираз>. Пригадаємо: «ім'я - це послідовність букв і цифр, що починається з букви». У цій фразі виникають одразу два нові поняття - <буква> і <послідовність букв і цифр>. Перепишемо її у вигляді БНФ

<ім'я>:=<буква><послідовність букв і цифр>.

Означимо тепер такі поняття, як послідовність терміналів, вивідна з початкового нетермінала, і формальна мова, задана сукупністю БНФ. Якщо замінити початковий нетермінал (позначимо його S) на праву частину правила, у якому S ліворуч, то одержимо послідовність символів (терміналів і нетерміналів), що називається вивідною з S. Означимо тепер такі поняття, як послідовність терміналів, вивідна з початкового нетермінала, і формальна мова, задана сукупністю БНФ. Якщо замінити початковий нетермінал (позначимо його S) на праву частину правила, у якому S ліворуч, то одержимо послідовність символів (терміналів і нетерміналів), що називається вивідною з S.

Підіб'ємо підсумок: БНФ - це вираз у алфавіті, що складається з терміналів, нетерміналів і спеціальних метасимволів. БНФ мають цілком визначений синтаксис (нетермінал, потім знак ':=' і метавираз). Їхньою семантикою є задання структури і множин представників понять, позначених нетерміналами. Таким чином, ми маємо мову БНФ. Вона призначена для описання інших мов і називається метамовою.

Існують різні метамови; деякі з них задаються строго й точно засобами логіки і математики і тому називаються формальними. Мова БНФ, описана тут неформально, насправді є окремим випадком формальної метамови - мови формальних граматик.

Синтаксичні діаграми

Мова форм Бекуса-Наура - не єдина метамова для описання структури конструкцій мов програмування. Досить поширеною є також метамова синтаксичних діаграм. Синтаксичні діаграми - графічне правило визначення конструкції мови за допомогою спеціальних означень (елементів). В будь-якій мові є початкові базові поняття, які потребують не роз'ясненнь, а перерахування. В українській мові, наприклад, це літери кирилиці - вони просто є і не несуть особливого смислового навантаження. У Паскалі таку роль відіграють символи, які складають алфавіт мови, і службові слова.

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

Кожна діаграма має вхідну і вихідну стрілки, що означають початок та кінець синтаксичної конструкції і відображають процес її читання та аналізу. З кожного елемента виходить одна або кілька стрілок, що вказують на ті елементи, які можуть випливати безпосередньо за даними елементом. Будь-яке роздвоєння передається словом «або» і означає можливість рухатися по будь-якій гілці[3].



1.2 Використання контекстно-вільної граматики для опису синтаксичних стрктур мов програмування

Контекстно-вільною, або КВ-граматикою, називається граматика, в якій ліві частини всіх продукцій є нетерміналами. Зміст терміну «контекстно-вільна» полягає в тім, що застосування продукції A® w до ланцюжка uAv не залежить, тобто є вільним від сусідніх з A символів, які утворюють контекст uv. Зазначимо, що БНФ вигляду A:=w цілком аналогічна продукції A® w. Отже, сукупності БНФ є просто іншою формою КВ-граматик.

Контекстно-вільною мовою (КВ-мовою) називається мова, що може бути задана КВ-граматикою. Прикладами КВ-граматик та КВ-мов є граматики з прикладів 21.3, 21.5, 21.6 у попередньому параграфі й задані ними мови. Граматика з прикладу 21.7 не є КВ-граматикою. До речі, мова, задана нею, не є КВ-мовою, оскільки не існує КВ-граматики, яка б її задавала.

КВ-граматики відіграють особливу роль у програмуванні, оскільки ними описується синтаксис практично всіх конструкцій мов програмування. Більше того, він описується КВ-граматиками, продукції яких задовольняють певні структурні обмеження. З використанням цих обмежень було побудовано алгоритми синтаксичного аналізу, час виконання яких прямо пропорційний довжині аналізованого слова. А лінійна складність цих алгоритмів великою мірою зумовила ефективність сучасних систем програмування[7].

Заміна нетермінала з лівої частини продукції на її праву називається розгортанням нетермінала, а зворотна заміна - згортанням правої частини. Розглянемо дві стратегії аналізу, основані на згортаннях та на розгортаннях, за допомогою наступного прикладу.

Приклад 8. Нехай

G0 = ({a, +, *, (,)}, {E, T, F},

{E ® E + T | T, T ® T * F | F, F ® (E) | a},

E)

- граматика. Нетермінали E, T, F відповідно є скороченнями слів «Expression», «Term», «Factor», тобто «вираз», «доданок», «множник». Вони позначають вирази зі знаками операцій +, *, доданки та множники в них відповідно.

Виведення слова a+a*a в G0 з розгортанням нетерміналів, перших ліворуч у проміжних ланцюжках, має вигляд:

E Ю E+T Ю T+T Ю F+T Ю a+T Ю a+T*F Ю a+F*F Ю a+a*F Ю a+a*a

Тут нетермінали, що розгортаються, підкреслені. Аналіз ланцюжка, що відтворює такі розгортання від початкового символу до термінального слова, називається низхідним, або аналізом «від верху до низу». Тепер розглянемо виведення слова a+a*a з розгортанням нетерміналів, останніх праворуч:

E Ю E+TЮ E+T*F Ю E+T*a Ю E+F*a Ю E+a*a Ю T+a*a Ю F+a*aЮ a+a*a

Проміжні слова в цьому виведенні, записані у зворотному порядку, дістаються згортаннями правих частин продукцій, починаючи з термінального слова. Такі згортання від ланцюжка терміналів до початкового нетермінала граматики відтворюються в процесі висхідного аналізу, або аналізу «від низу до верху».з

Головною проблемою побудови алгоритмів аналізу в обох випадках є необхідність вибору продукції, застосованої для розгортання чи згортання. Чому, наприклад, у першому виведенні на першому кроці вибирається продукція E® E+T, а не E® T, а на другому, навпаки, E® T? Чому за оберненого виведення в слові E+T*F, в якому є дві праві частини продукцій E+T і T*F, саме ланцюжок T*F згортається в T, а не E+T в E? Тут необхідний вибір зроблено тому, що структура термінального слова була відома заздалегідь. Але, взагалі, структура слова до початку його аналізу невідома, і виникає необхідність перебирати продукції для застосування потрібної. Теоретично, можна розробити алгоритм аналізу на основі перебирання продукцій, але він буде практично неприйнятним внаслідок його оцінки складності. Один із шляхів до ефективних алгоритмів аналізу полягає в обмеженні структури продукцій і позбавленні від перебирання за рахунок звуження множини КВ-граматик. Далі розглядаються саме такі обмежені граматики та побудова алгоритму аналізу для них, складність якого лінійна.

LA(1) - граматики

LA(1) - граматики дозволяють вибирати необхідну для розгортання продукцію при низхідному аналізі за першим символом ще не розпізнаної частини слова. «LA(1)» позначає речення «Look Ahead 1 symbol», тобто «подивитися спереду на 1 символ».

Нехай G=(X, N, P, S) - КВ-граматика, і за словом w треба визначити, чи належить воно до L(G). Нехай S® v1|…|vp - усі продукції з нетерміналом S ліворуч. Потрібну для розгортання S продукцію S® vi можна визначити безпосередньо за першим символом слова w, якщо множини перших символів ланцюжків, вивідних із v1, v2, …, vp, не перетинаються. Взагалі, нехай am…an - нерозпізнана частина слова, початок якої має виводитися з нетермінала A, і A® w1|…|wk - усі продукції з A ліворуч. Тоді потрібна для розгортання A продукція A® wi визначається за першим символом am, якщо множини перших символів ланцюжків, вивідних з w1, w2, …, wk, не перетинаються.

Отже, для кожного нетермінала A та кожної правої частини wi продукцій A ® w1 | w2 | … | wk означимо множини

first (wi) = {a | a О X* і wi Ю az для деякого слова z}, first (A) = first (wi).

Граматика може мати так звані e - продукції вигляду A® e. У такому разі, якщо AvЮ *b1…bn, то b1 може починати слово, вивідне як з A, так і з v. Визначити за символом b1, з чого саме виводиться слово, можна за умови, що first(A) не містить перших символів слів, вивідних із v. Множину цих перших символів ланцюжків, що виводяться з усіх можливих правих контекстів нетермінала A, позначимо follow (A):

follow (A) = {a | S Ю * uAv, a О first (v)}.

Граматика називається LA(1) - граматикою, якщо:

(1) для кожного нетермінала A з продукціями A® w1|…|wk, де wi№ e для всіх i=1,…, k, справджується умова

first (wi) З first (wj) = Ж при i, j = 1, …, k, i № j;

(2) для кожного нетермінала A такого, що в P є продукція A ® e, справджується

first (A) З follow (A) = Ж.

Умови (1), (2) називаються LA(1) - умовами.

Не кожна КВ-мова породжується LA(1) - граматикою, але синтаксис практично всіх конструкцій сучасних мов програмування можна задати LA(1) - граматиками. Досить часто мова «природно» задається не LA(1) - граматикою, але таку граматику для неї можна побудувати.

Приклад 9. За продукціями E® E+T|T, T® T*F|F, F® (E)|a граматики G0 маємо

first ((E)) = {(}, first (a) = {a}, звідки

first (F) = {a, (}; first (T*F) = first (F), звідки

first (T*F) З first (F) № Ж,

тобто G0 не є LA(1) - граматикою. Проте мова виразів L(G0) задається еквівалентною LA(1) - граматикою. Побудуємо її. Із T виводяться слова F, F*F, F*F*F, …. Додамо нетермінал B та правила B® e |*FB, T® FB замість правил T® F|T*F. Маємо

first (T) = first (F) = {a, (}, first (*FB) = {*},

first (B) = {*}, follow (B) = follow (T) =

= follow (E) = (+,)}.

Отже, продукції T® FB і B® e |*FB не порушують LA(1) - умови. Аналогічно, додавши нетермінал A, а замість правил E® E+T|T правила E® TA, A® e |+EA, одержимо LA(1) - граматику.з

Ліворекурсивні та розширені продукції[1]

Правило вигляду A® Av називається ліворекурсивним. Якщо в граматиці є продукції A® Av|u, де u№ e, то first(Av)=first(u)№ Ж, і граматика не є LA(1) - граматикою. Але за допомогою цих правил виводяться слова з множини {u, uv, uvv, …}, яка задається регулярним виразом uv* або u{v}. Замість продукцій A® Av|u запишемо A® u{v}. Продукції з регулярними виразами в правій частині називаються розширеними, як і граматики з такими продукціями. Неважко переконатися, що розширені правила не збагачують множину мов, породжених КВ-граматиками[8].

1.3 Використання регулярних мов для опису синтаксиса мов програмування

Мова називається регулярною, якщо вона кінцева (у тому числі і Ж) або утворюється з кінцевих мов за допомогою операцій об'єднання, добутку та ітерації. Безліч всіх регулярних мов над алфавітом A позначається Reg(A).

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

Приклади 2.1.

а. Прикладами регулярних мов над алфавітом e = Ж ^*, A и A^*.

b. Окремі конструкції в мовах програмування є регулярними мовами. Як правило, це лексичні одиниці - ідентифікатори, числа, рядки, ключові слова і тому подібне. Наприклад, безліч ідентифікаторів I = L (L І D), де L = {а,…, z}, D = {0,1,2…, 9}, або безліч чисел R = SNFP, де S = {+,-, e}, N = Dd*, F =.N І e, P = esn І e.

Складніші конструкції (наприклад, вирази), вже не є регулярними мовами. Для доказу того, що якась мова нерегулярна, корисно наступна властивість.

Теорема 2.2. Для будь-якої регулярної мови L існує таке число m > 0, що всякий ланцюжок а О L, довжина якої більше m, представіма у такому вигляді а = gbd, що b №e і для будь-якого n > 0 ланцюжок gb ^nd О L.

Доказ (індукцією по побудові регулярної мови).

а. Якщо L - кінцева мова, то m рівне максимальній довжині його ланцюжків.

b. Якщо L = M*, то m = 0, оскільки разом з непорожнім ланцюжком а мова L містить і всі ланцюжки а n, n > 0.

с. Якщо m1, m2 - необхідні числа для мов M і N, відповідно, то для L = M І N можна узяти m = max {m1, m2}, а для L = MN - m = m1 + m2. Дійсно, якщо |a | > max{m₁, m₂}, то |a | > m₁ и |a | > m₂, так що і при а О M, і при а О N ланцюжок а представіма в необхідному вигляді. А якщо a О MN и a = a₁a₂, где a₁О M, а a₂О N, и |a | > m₁ + m₂, то либо |a₁| > m₁, либо |a₂| > m₂ і, отже, а представлена в необхідному вигляді.

Приклад 2.2. Як приклад використання цієї теореми доведемо нерегулярність мови L = {aⁿbⁿ | n > 0}. Довільний ланцюжок а О L представимо у вигляді а = gbd, де b №e. Якщо b = am або b = bm, то в gbbd буде нерівна кількість символів а і b. Якщо b = a^mb^m, то в gbbd входитиме підланцюжок ba. У цих випадках gbbd П L, а інших варіантів розбиття а, потрібного в теоремі 1.2, немає. Отже, мова L нерегулярна.

Регулярний вираз (в програмуванні) - це рядок що описує або збігається з множиною рядків, відповідно до набору спеціальних синтаксичних правил. Вони використовуються в багатьох текстових редакторах та допоміжних інструментах для пошуку та зміни тексту на основі заданих шаблонів. Багато мов програмування підтримують регулярні вирази для роботи з рядками. Наприклад, Perl та Tcl мають потужний механізм для роботи, вбудований безпосередньо в їх синтаксис. Завдяки набору утиліт (включаючи редактор sed та фільтр grep), що входили до складу дистрибутивів Юнікс регулярні вирази стали відомими та поширеними[10].

Регулярні вирази базуються на теорії автоматів та теорії формальних мов. Ці розділи теоретичної кібернетики займаються дослідженням моделей обчислення (автомати) та способами описання та класифікації формальних мов. Регулярний вираз (часто називається шаблон) є послідовністю, що описує множину рядків. Ці послідовності використовуються для того, аби дати точне описання множини, не перелічуючи всі її елементи. Наприклад, множина, що складається із слів «грати» та «ґрати» може бути описана регулярним виразом «[гґ] рати». В більшості формалізмів, якщо існує регулярний вираз, що описує задану множину, тоді існує нескінченна кількість варіантів, які описують цю множину.

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

Більшість символів у регулярному виразі представляють самі себе за винятком спеціальних символів (метасимволів) [] \ ^ $. |? * + () {}, яким може передувати символ \ (зворотна коса риса) («екрановані», «захищені») для представлення їх самих як символів тексту. Можна екранувати деяку послідовність символів, розмістивши її між \Q і \E.

Приклад	Відповідність
a\.?	a. або a
a\\\\b	a\\b
a\[F\]	a[F]
\Q+-*/\ E	+-*/

Рисунок. 1.1 Послідовність символів

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

Залежно від інтерпретатора регулярних виразів, метасимволи «?», «+», «{», «|», «(», та «)» можуть втрачати своє спеціальне значення, замість цього слід вживати «\?», «\+», «\{», «\|», «\(», та «\)».

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

Два регулярних вирази можна об'єднати. У цьому разі отриманий складний вираз буде рядком, що є об'єднанням двох рядків, які відповідають цим простим виразам.

Символьні класи (набори символів)

Набір символів у квадратних дужках [] іменується символьним класом і дозволяє вказати інтерпретаторові регулярних виразів, що на даному місці в рядку може стояти один із перерахованих символів. Зокрема, [абв] задає можливість появи в тексті одного із трьох зазначених символів, а [1234567890] задає відповідність одній із цифр. Можливе зазначення діапазонів символів: наприклад, [А-Яа-Я] відповідає всім літерам російського алфавіту, за винятком літер «Ё» і «ё».^[1]

Якщо потрібно вказати символи, які не входять у зазначений набір, то використовують символ ^ усередині квадратних дужок, наприклад, [^0-9] означає будь-який символ, крім цифр. Додавання в набір спеціальних символів шляхом екранування - найпростіший спосіб. Однак сучасні регулярні вирази успадковують також і традиційний підхід - див. Традиційні регулярні вирази.

Деякі символьні класи можна замінити спеціальними метасимволами:

\d		Відповідає цифрі. Еквівалентно [0-9]
\D		Відповідає нецифровому символу. Еквівалентно [^0-9]
\s		Відповідає будь-якому пробільному символу. Еквівалентно [\f\n\r\t\v]
\S		Відповідає будь-якому непробільному символу. Еквівалентно [^ \f\n\r\t\v]
\w		Відповідає будь-якому літерному символу, цифровому й знаку підкреслення. Еквівалентно [[:word:]]
\W		Відповідає будь-якому символу, крім літерного символу, цифрового або підкреслення. Еквівалентно [^[:word:]]

Рисунок. 1.2 Спеціальні метасимволи

Два регулярних вирази можна з'єднати інфіксним оператором «|»; у цьому разі складний вираз буде відповідатиме рядкам, що відповідають або першому, або другому простому регулярному виразу.

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



2. Використання теорії автоматів для роботи з формальними мовами

2.1 Використання формальних мов для формалізації синтаксиса

Систематичне використання математичних методів для опису мов програмування започатковане у 1960 р. Тоді виявилось, що БНФ, які використовувались для опису синтаксису мови Алгол-60, мають строге формальне обґрунтування за допомогою засобів математичної лінгвістики. З цього часу і почалась історія розвитку і застосування формального математичного апарату? теорії формальних мов і граматик? для проектування і конструювання трансляторів.

Спочатку наука про мови? лінгвістика? зводилась до вивчення конкретних природних мов, їх класифікації, з'ясуванню подібності і відмінностей між ними. Виникнення і розвиток метаматематики, що вивчала мову математики, проведення робіт з вивчення засобів комунікації тварин та інші дослідження привели у 30-х роках ХХ століття до значно ширшого поняття про мову, коли під мовою розуміють всякий засіб спілкування, що складається з:

знакової системи, тобто множини допустимих послідовностей знаків;

змістовних множини цієї системи;

відповідності між послідовностями знаків і змістом, який ставиться у відповідність допустимим послідовностям.

Знаками можуть бути букви абетки, математичні позначення, звуки тощо. Математична лінгвістика розглядає тільки такі знакові системи, які складаються з символів деякого алфавіту[4].

Алфавітом називається скінченна множина символів. Позначатимемо його X. Словом (фразою, або ланцюжком) у алфавіті X називається послідовність символів із X. Множина всіх скінченних слів у алфавіті X позначається X^*. Зауважимо, що вона нескінченна. Вона містить порожнє слово - послідовність довжиною 0, позначену буквою e. Множину X^*\{e} позначимо X⁺, а слово вигляду wwј w, де слово w із X⁺ записано n разів - wⁿ. Вважатимемо, що w⁰ = e.

Довільна підмножина множини X^* називається формальною мовою. Далі в цьому розділі вона буде називатися просто мовою. Задача перевірки, чи належить слово w мові L, називається задачею належності, або проблемою слів. Як правило, множина L задається певним скінченним описанням, що визначає не тільки її саму, а й структуру її елементів.

Задача належності розв'язується найчастіше шляхом перевірки, чи має слово відповідну структуру, тобто шляхом синтаксичного аналізу, або розпізнавання. Наприклад, структура всіх можливих синтаксично правильних Паскаль-програм визначається скінченною та відносно невеликою сукупністю БНФ. Саме на її основі будуються синтаксичні аналізатори в трансляторах, тобто програми аналізу синтаксичної правильності вхідних програм.

Формальні мови розглядатимуться далі як мови, задані саме скінченним описом. Отже, головним у вивченні формальних мов стає засіб їх задання. У розділі 10 ми вже познайомилися з одним із них - це були БНФ та їх сукупності. Розглянемо ще деякі.

Регулярні операції, вирази та мови

Регулярні вирази й задані ними регулярні мови означимо індуктивно. Вирази Ж, e та a при aО X є регулярними в алфавіті X і задають відповідно регулярні мови Ж, {e}, {a}. Якщо r₁ і r₂ - регулярні вирази, що задають регулярні мови L₁ і L₂, то вирази (r₁), r₁+r₂, r₁r₂, r₁^* є регулярними й задають відповідно регулярні мови L₁, L_1? L₂, L₁L₂, L₁^*.

Очевидно, що кожна скінченна мова є регулярною, оскільки задається регулярним виразом як скінченне об'єднання одноелементних регулярних мов.

Множина регулярних мов, заданих усіма можливими регулярними виразами в алфавіті X, називається класом регулярних мов над X. Регулярні операції застосовні до будь-яких мов, а не тільки до регулярних. За означенням, застосування їх до регулярних мов породжує регулярні мови.

Не всі мови є регулярними. Наприклад, «мова вкладених дужок», задана БНФ

<вкл-дуж>:= () | (<вкл-дуж>),

є множиною {(ⁿ)ⁿ|n>0}, яка не задається жодним скінченним регулярним виразом. Отже, розглянемо інші, потужніші засоби задання мов.

Класифікація граматик і мов за Хомським

Граматика G = (T, N, P, S) називається граматикою типу 0, якщо на правила виводу не накладається ніяких обмежень (крім тих, котрі зазначені в означенні граматики).

Граматика G = (T, N, P, S) називається граматикою, що не укорочує, якщо кожне правило з P має вид (a, b), де a О (T И N)⁺, b О (T И N)⁺ і | a | <= | b |.

Граматика G = (T, N, P, S) називається контекстно-залежною (КЗ), якщо кожне правило з P має вид a ® b, де a = x ₁Ax ₂; b = x ₁g x ₂; A О N; g О (T И N)⁺; x ₁, x ₂ О (T И N)^*. Граматику типу 1 можна означити як таку, що не укорочує, або як контекстно-залежну.

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

Граматика G = (T, N, P, S) називається контекстно-вільною, якщо кожне правило з Р має вид A ® b, де A О N, b О (T И N)^*. Граматику типу 2 можна визначити як контекстно-вільну.

Граматика G = (T, N, P, S) називається праволінійною, якщо кожне правило з Р має вид A ® t або A ® t, де A О N, B О N, t О T.

Граматика G = (T, N, P, S) називається ліволінійною, якщо кожне правило з Р має вид A ® Bt або A ® t, де A О N, B О N, t О T. Граматику типу 3 (регулярну, A-граматику) можна визначити як праволінійну або як ліволінійну.

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

Співвідношення між типами граматик:

1) будь-яка регулярна граматика є КВ - граматикою;

2) будь-яка КВ - граматика є КЗ - граматикою (з точністю до порожнього слова);

3) будь-яка КЗ - граматика є граматикою типу 0.

4) будь-яка граматика, що не укорочує, є граматикою типу 0.

Означення: мова L(G) є мовою типу k, якщо її можна описати граматикою типу k.

Співвідношення між типами мов:

1) кожна регулярна мова є КВ-мовою, але існують КВ - мови, що не є регулярними (наприклад, L = {aⁿbⁿ | n>0}).

2) кожна КВ - мова є КЗ - мовою, але існують КЗ-мови, що не є КВ-мовами (наприклад, L = {aⁿbⁿcⁿ | n>0}).

3) кожна КЗ-мова є мовою типу 0.

Варто підкреслити, що якщо мова задана граматикою типу k, то це не означає, що не існує граматики типу k' (k'>k), що описує ту ж мову. Тому, коли говорять про мову типу k, звичайно мають на увазі максимально можливе k.

Наприклад, КЗ-граматика G₁ = ({0,1}, {A, S}, P₁, S) та КВ-граматика G₂ = ({0,1}, {S}, P₂, S),

де P₁: S ® 0A1 P₂: S ® 0S1 | 01

0A ® 00A1

A ® e

описують ту ж саму мову L = L(G₁) = L(G₂) = {0ⁿ1ⁿ | n>0}. Мову L називають КВ-мовою, тому що існує КВ-граматика, що її описує. Але вона не є регулярною мовою, тому що не існує регулярної граматики, що її описує[1].

2.2 Синтаксичні аналізатори

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

В основі синтаксичного аналізатора лежить распознаватель тексту вхідної програми на основі граматики вхідної мови. Як правило, синтаксичні конструкції мов програмування можуть бути описані за допомогою КС-граматик, рідше зустрічаються мови, які, можуть бути описані за допомогою регулярних граматик. Найчастіше регулярні граматики застосовні до мов асемблера, а мови високого рівня побудовані па основі синтаксису КС-мов. Розпізнавач дає відповідь на питання про те, належить чи ні ланцюжок вхідних символів заданому мови. Однак, як і у випадку лексичного аналізу, завдання синтаксичного розбору не обмежишся лише перевіркою приналежності ланцюжка заданому мови. Необхідно виконати всі перераховані вище завдання, які повинен вирішити синтаксичний аналізатор. У такому варіанті аналізатор вже не є різновидом МП-автомата - його функції можна трактувати ширше. Синтаксичний аналізатор повинен мати якийсь вихідний мову, за допомогою якого він передає наступним фазам компіляції не тільки інформацію про знайдені і розібраних синтаксичних структурах. У такому випадку він вже є перетворювачем з магазинною пам'яттю - МП-перетворювачем. Синтаксичний розбір - це основна частина компілятора на етапі аналізу. Без виконання синтаксичного розбору робота компілятора безглузда, у той час як лексичний розбір в принципі є необов'язковою фазою. Усі завдання з перевірки синтаксису вхідного мови можуть бути вирішені на етапі синтаксичного розбору. Сканер тільки дозволяє позбавити складний за структурою синтаксичний аналізатор від рішення примітивних завдань з виявлення та запам'ятовування лексем вихідної програми.

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

Синтаксичний аналізатор сприймає вихід лексичного аналізатора і розбирає його відповідно до граматикою вхідної мови. Однак у граматиці вхідної мови програмування звичайно не уточнюється, які конструкції слід вважати лексемами. Прикладами конструкцій, які зазвичай розпізнаються під час лексичного аналізу, служать ключові слова, константи і ідентифікатори. Але ці ж конструкції можуть розпізнаватися і синтаксичним аналізатором. На практиці не існує жорсткого правила, що визначає, які конструкції повинні розпізнаватися на лексичному рівні, а які треба залишати синтаксичному аналізатору. Зазвичай це визначає розробник компілятора виходячи з технологічних аспектів програмування, а також синтаксису та семантики вхідної мови Далі розглянуті технічні аспекти, пов'язані з реалізацією синтаксичних аналізаторів для використання результатів їхньої роботи на етан генерації коду. Тим не менш, основу будь-якого синтаксичного аналізатора завжди складає распознаватель, побудований на основі якого-небудь класу КС-граматик. Тому головну роль і те, як функціонує синтаксичний аналізатор і який алгоритм лежить в його основі, відіграють принципи побудови розпізнавачів КС-мов. Без застосування цих принципів неможливо виконати ефективний синтаксичний розбір пропозицій вхідного мови[2].

Автоматизація побудови синтаксичних аналізаторів

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

Автоматизована побудова синтаксичних аналізаторів може бути виконано за допомогою програми YACC. Програма YACC (Yet Another Compiler Compiler) призначена для побудови синтаксичного аналізатора контекстно-вільного мови. Аналізований мова описується за допомогою граматики до пилки, близькому формі Бекуса-Наура (нормальна форма Бекуса-Наура - НФБН). Результатом роботи YACC є вихідний текст програми синтаксичного аналізатора. Аналізатор, який породжується YACC, реалізує висхідний LALR (l) распознаватель.

Як і програма LEX, що служить дли автоматизації побудові лексичних аналізаторів, програма YACC тісно пов'язана з історією операційних систем типу UNIX. Ця програма входить в постачання багатьох версій ОС UNIX або Linux. Тому найчастіше результатом роботи YACC є вихідний текст синтаксичного розпізнавача на мові С, Однак існують версії YACC, що виконуються під управлінням ОС, відмінних від UNIX, і породжують вихідний код на інших мовах програмування (наприклад, Pascal). Принцип роботи YACC схожий на принцип роботи LEX: на вхід надходить файл, що містить опис граматики заданого КС-мови, а на виході отримуємо текст програми синтаксичного розпізнавача, який, природно, можна доповнювати і редагувати, як і будь-яку іншу програму на заданому мовою програмування.

Вихідна граматика для YACC складається з трьох секцій, розділених символом%%, - секції описів, секції правил, у якій описується граматика, і секції програм, вміст якої просто копіюється у вихідний файл. Наприклад, нижче наведено опис найпростішої граматики для YACC, яка відповідає граматиці арифметичних виразів:

% Token a

% Start e

%

e: e '+' m | e '-' m | m

m: m '*' t | m '/' t | t

a: a | ' (' e ')':

%%

Секція описів містить інформацію про тому, що ідентифікатор а є лексемою (термінальним символом) гpамматікі, а символ е - її початковим нетермінальним символом.

Граматика, записана звичайним чином - ідентифікатори позначають термінальні та нетермінальні символи; символьні константи типу '+' і '-' вважаються термінальними символами. Символи:, |,; належать до метамови YACC і читаються згідно НФБН «є за визначенням», «або» та «кінець правила» відповідно[10].

На відміну від LEX, який завжди здатний скорчити лексичний распознаватель, якщо вхідний файл містить правильне регулярний вираз, YACC не завжди може побудувати распознаватель, навіть якщо вхідна мова заданий правильної КС-граматикою. Адже задана граматика може і не належати до класу LALR (l). У цьому випадку YACC видасть повідомлення про помилку (наявності нерозв'язного LALR (t) конфлікту в граматиці) при побудові синтаксичного аналізатора. Тоді користувач повинен або перетворити граматику, або задати YACC деякі додаткові правила, які можуть полегшити побудову аналізатора. Наприклад, YACC дозволяє вказати правила, явно задають пріоритет операцій та порядок їх виконання (зліва направо або справа наліво).

З кожним правилом граматики може бути пов'язана дія, яка буде виконана при згортку по даному правилу. Воно записується у вигляді укладеної у фігурні дужки послідовності операторів мови, на якому породжується вихідний текст програми розпізнавача (зазвичай це мова С). Послідовність має розташовуватися після правій частині відповідного правила. Також YACC дозволяє керувати діями, які будуть виконуватися розпізнавачем в тому випадку, якщо вхідні ланцюжок не належить заданому мови. Розпізнавач має можливість видати повідомлення про помилку, зупинитися або ж продовжити розбір, зробив деякі дії, пов'язані зі спробою локалізувати або усунути помилку у вхідний ланцюжку[6].

2.3 Кінцеві автомати та автомати із магазинною пам'яттю

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

Класифікація

Існує дві різних групи автоматів: Акцептори/Розпізнавачі і Перетворювачі(Трансдуктори).

Акцептори і розпізнавачі. Акцептори і розпізнавачі (також виявлювачі послідовностей) продукують двійковий вихід, кажучи або так або ні на питання прийняті автоматом вхідні дані чи ні. Всі стани КА можуть бути або допустими або ні. Коли всі вхідні дані оброблені, якщо поточний стан є допустимим, значить вхід прийнятий; інакше відхилений. Як правило на вхід подаються символи (літери); дії не використовуються. Приклад на зображенні показує КА який приймає слово «nice». В цьому КА єдиний допустимий стан це 7.

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

Початковий стан зазвичай показується зі стрілкою «звідкись».

Допустимі (або кінцеві) стани. Приклад скінченного автомата; цей приклад показує автомат, який визначає чи двійкове число має непарну кількість 0, де це допустимий стан.

Допустимі стани (також відомі як кінцеві стани) це такі, що якщо автомат знаходиться в них це означає, що вхідний рядок, наскільки він опрацьований, належить мові що розпізнається. Зазвичай позначається двома колами. Приклад допустимого стану з'являється в діаграмі праворуч: a детермінований кінцевий автомат (ДКА), що визначає чи двійковий вхідний рядок містить парну кількість 0. S₁ (який є початковим станом) показує стан в якому парна кількість 0 була введена. Цей автомат опиниться в допустимому стані, якщо двійковий рядок містить парну кількість 0 (включно з рядком, що не містить 0 взагалі). Приклади рядків розпізнаваних цим ДКА це порожній рядок, 1, 11, 11…, 00, 010, 1010, 10110, і подібні.

Перетворювачі (Трансдуктори)

Перетворювачі виробляють вихід, що базується на даному вході і/або на станах з використанням дій. Вони використовуються для керування і в галузі математичної лінгвістики. Тут вирізняють два типи:

Автомат Мура

КА використовує тільки вхідні дії, тобто, вихід базується тільки на стані. Перевагою моделі Мура є спрощення поведінки. Уявімо двері підйомника. Автомат розпізнає дві команди: «відчинити» і «зачинити», які викликають зміну стану. Вхідна дія (E:) в стані «Відчиняються» змушує двигун відчиняти двері, вхідна дія в стані «Зачиняються» змушує двигун зачиняти двері. Стани Відчинено і Зачинено зупиняють мотор коли двері повністю відчинені або зачинені. Вони повідомляють зовнішній світ (наприклад, інші автомати) ситуація: «двері відчинені» або «двері зачинені». КА перетворювач: приклад моделі Мілі

Автомат Мілі

КА, що використовує тільки вхідні дії, тобто, вихід базується на вході і стані. Використання КА Мілі часто призводить до зменшення кількості станів. Приклад на малюнці показує КА Мілі реалізуючий однакову поведінку із прикладом автомата Мура. Присутні дві вхідні дії (I:): «запустити двигун для закриття дверей якщо прийшла команда зачинити» і «запустити мотор в іншому напрямку якщо для відчинення дверей якщо прийшла команда відчинити». Проміжні стани «Відчинення» і «Зачинення» не показані. На практиці часто використовується суміш моделей. Більше подробиць по відмінностям і використанню моделей Мура і Мілі із виконанними прикладами можна знайти на «Moore or Mealy model? (Модель Мура або Мілі?)»

Детермінованість

Подальша відмінність між Детермінованими (ДКА) і недетермінованими (НКА) автоматами. В детермінованих автоматах, кожен стан має лише один перехід для кожного входу. В недетермінованих автоматах вхід може призвести до одного, більше ніж одного або зовсім без переходу для даного стану. Ця різниця важлива на практиці, але не в теорії, через існування алгоритму трансформації будь-якого НКА в більш складний ДКА з однаковою функціональністю[4].

Математична модель

Згідно із загальною класифікацією, дані наступні визначення:

· детермінований кінцевий автомат або детермінований кінцевий автомат акцептор є п'ятіркою, де:

o вхідна абетка (кінцевий, не порожній набір символів).

o - кінцевий, не порожній набір станів.

o - початковий стан, елемент з.

o - функція переходу: (в недетермінованих кінцевих автоматах це буде, тобто, повертає набір станів).

o набір кінцевих станів, (можливо порожня) підмножина.

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

· кінцевий перетворювач це шістка, де:

o - вхідна абетка (кінцевий, не порожній набір символів).

o - вихідна абетка (кінцевий, не порожній набір символів).

o - кінцевий, не порожній набір станів.

o - початковий стан, елемент з (в недетермінованих кінцевих автоматах, це набір початкових станів).

o - функція переходу:.

o функція виходу.

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

Автомамт з магазимнною памм'яттю (МП автомат) - в теорії автоматів це кінцевий автомат, що використовує стек для зберігання станів. На відміну від кінцевих автоматів, автомат з магазинною пам'яттю є набором, де

· K - кінцева множина станів автомата

· - єдиний допустимий початковий стан автомата

· - множина кінцевих станів, причому допускається F=Ш, і F=K

· У - скінченна множина символів вхідного алфавіту, з якого формуються строки, що зчитуються автоматом

· S - алфавіт пам'яті (магазину)

· - нульовий символ пам'яті.

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

У чистому вигляді автомати з магазинною пам'яттю використовуються вкрай рідко. Зазвичай ця модель використовується для наочного подання відмінності звичайних скінченних автоматів від синтаксичних граматик. Реалізація автоматів з магазинною пам'яттю відрізняється від кінцевих автоматів тим, що поточний стан автомата сильно залежить від будь-якого попереднього.

Види автоматів з магазинної пам'яттю

Існують детерміновані та недетерміновані автомати з магазинною пам'яттю. Для недетермінованих автоматів (на відміну від детермінованих) існує два еквівалентні критерії завершення роботи:

· порожній магазин

· досягнення кінцевого стану

Детермінований автомат завершує роботу лише тоді, коли досягає кінцевого стану.



2.4 Використання автомата із магазинною пам'яттю для розпізнання мови, яка породжується контекстно-вільною граматикою

граматика формальний автомати програмування

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

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

1. визначати рівність дужок, тобто кількість дужок, що відкриваються і кількість дужок, що закриваються має бути однаковою;

2. стежити за правильністю їх вкладення, тобто, щоб будь-якій дужці, що закривається, передувала відповідна відкриваюча.

У цій ситуації кінцевий автомат може успішно справитися тільки з першою частиною задачі. Однак, забезпечити розпізнавання вкладеності він не зможе. Неможливість використання кінцевого автомата підтверджується і тим, що граматику, що породжує розглянуті ланцюжки, не можна звести до праволінійної, що є еквівалентною кінцевому автомату. Її також не можна представити тільки ітеративними діаграмами Вірта, безпосередньо відповідному кінцевому автоматові. Це пов'язане з тим, що граматика містить рекурсію в середині правила, а така рекурсія не може бути зведена до ітерації. Граматика G може бути означена так: G= ({A, S}, {(,)}, P, S),

де P визначається як:

1. S ® (A) A

2. A ® S

3. A ®e

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

Організація автомата з магазинною пам'яттю

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

1. Кінцевою множиною вхідних символів, що включає маркер кінця (+).

2. Кінцевою множиною магазинних символів, що включають маркер дна (С).

3. Кінцевою множиною станів, що включає початковий стан

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

5. Початковим умістом магазина, що містить маркер дна і ланцюжок магазинних символів (можливо порожній).

Автомат з магазинною пам'яттю називається розпізнавачем, якщо він має ще й два виходи: «Допустити» та «Відкинути».

Операції автомата

Динамічна поведінка АМП описується його операціями над вхідним ланцюжком і стеком, а також переходами з одного стану в інший. До операцій над стеком відносяться:

1. «Виштовхнути» - виштовхує зі стека верхній символ (будемо також використовувати скорочене позначення «^»).

2. «Заштовхнути А» - вштовхує в стек магазинний символ А (будемо також використовувати скорочене позначення «vА»).

3. «Замінити XYZ» - використовується для скорочення запису, коли необхідно виштовхнути верхній символ і замість нього вштовхнути кілька інших (у даному випадку X, Y, Z). Еквівалент:

4. ^vXvYvZ (скорочено позначимо: ¦ XYZ).

Перехід АМП з одного стану в інший вказується явно операцією «Стан t», де t - новий стан автомата (будемо скорочувати текст даної операції до «[t]»). Зсув вхідної голівки на один символ вправо щодо вхідної стрічки задається операцією «Зсув» (скоротимо до «>»). Після її виконання поточним символом стає наступний символ на вхідній стрічці. Іншою операцією над вхідною голівкою є «Тримати», яка не змінює становище вхідної голівки до наступного кроку (можна просто не писати, якщо немає зсуву) [11].