Побудова магазинного автомата

Для граматик, що задовольняють умовам LL(1) граматик, справедливо наступне твердження:

Для кожної LL(1) граматики можна побудувати детермінований магазинний автомат М, що допускає мова, породжувана даною граматикою: L ( Г ) = L ( М ).

Задача побудови магазинного автомата для заданої LL(1) граматики формулюється в такий спосіб.
Задано граматику Г = {V_т, V_a, I, R}, і потрібно визначити об'єкти, що визначають автомат М = { P , S , s₀ , F , H , h₀ , f }.
З огляду на те, що автомат повинний допускати ланцюжки мови, породжуваної заданою граматикою, приймемо P = V_т. Щоб спростити опис автомата, допустимо, що він має один стан s₀, що є і початковим і заключним, тобто - S = {s₀}і F = {s₀}.

Як магазинний алфавіт приймемо наступне об'єднання: H = {V_т È V_a È {h₀}}.
Побудову функції переходів виконаємо з використанням множин ВИБІР правил заданої граматики:
1) Для кожного правила граматики, що починається термінальним символом виду
A ® b a, побудуємо команду автомата

f ( s₀ , b , <A> ) = ( s₀ , a ' ) ,

де a ' є дзеркальним відображенням ланцюжка a .
2) Для кожного правила граматики, що починається нетермінальним символом виду
<A> ® <B>a,побудуємо команду автомата

f* ( s₀ , x , <A> ) = ( s₀ , <B> a ' )

деf* - команда автомата без зрушення вхідної голівки, а a ' є дзеркальним
відображенням ланцюжка a, х- елементи множини ВИБІР. Кількість команд, які необхідно побудувати для заданого правила, визначається числом елементів множини ВИБІР. Команди магазинного автомата, які працюють без зрушення вхідної голівки, виконують заміну нетермінала, що відповідає лівій частини правила, ланцюжком, що відповідає правій частини цього правила. У цьому випадку зіставлення термінального символу, одержуваного при виводі, і чергового символу вхідного ланцюжка не виробляється, тому для таких команд зрушення вхідної голівки не потрібне.
3) Для кожного правила граматики, що анулює,
виду A®$ побудуємо команди автомата

f* ( s₀ , x , A ) = ( s₀ , $ )

для кожного елемента x з множини ВИБІР(A ® $). Кількість таких команд визначається числом елементів множини ВИБІР.
4) Для кожного термінального символу b, розташованого в середині чи на кінці правих частин правил граматики, побудуємо команду

f ( s₀ , b , b ) = ( s₀ , $ ).

5) Для переходу в заключний стан побудуємо команду

f* ( s₀ , e , h₀ ) = ( s₀ , $ , $ ).

Як початкову конфігурацію автомата умовимося використовувати наступне вираження з заданим вхідним ланцюжком µ:

(s₀, µ, h₀I).

8. Приклади побудови спадного розпізнавача