КС-языки и магазинные автоматы

Эквивалентные преобразования КС-грамматик

Пример 16

Следующая грамматика решает проблему "кочующего else":

stmt à if expr then stmt | if expr then stmt else stmt | a

expr à b (5.13)

Будучи левофакторизованной, эта грамматика принимает следующий вид:

stmt à if expr then stmt S' | а

S' à else stmt | λ (5.14)

E à b

Таким образом, при получении на входе if используется продукция if expr then stmtS' и, только когда будет просмотрена if expr then stmt, можно решить, расширять ли S' до else stmt или λ. Однако, и грамматика (5.13), и грамматика (5.14) неоднозначны, и при входном символе else неясно, какая из альтернатив для S' должна быть выбрана.

Цель преобразования грамматик: упрощение правил грамматики и облегчение создания распознавателя. При создании компиляторов вторая цель наиболее важная, поэтому иногда упрощением грамматик пренебрегают.

Грамматики, к которым применены преобразования в определенном порядке, называется приведенными.

Последовательность правил преобразований грамматик должна быть следующей:

1) удаление всех бесполезных символов; (Нетерминальный символ грамматики является бесполезным, если он не играет никакой роли в построении правильных цепочек языка)

2) удаление всех недостижимых символов; (Нетерминальный символ грамматики является недостижимым, если он никогда не появляется в выводимых цепочках)

3) удаление λ-продукций; (Грамматика является λ-свободной, если множество продукций не содержит λ -продукций, или есть ровно одно λ -правило S–> λ и S не встречается в правых частях остальных продукций)

4) удаление цепных правил (Грамматика является грамматикой без циклов, если в ней нет выводов вида А=*>А).

Описание КС-языка с помощью порождающей КС-грамматики не является описанием алгоритма порождения предложений этого языка. Правила подста­новки грамматики — это не последовательность предписаний, а совокупность разрешений, причем порядок применения правил в грамматике произволен, тогда как в алгоритме должен быть задан жесткий порядок применения от­дельных инструкций.

Получение алгоритмического описания процесса распознавания языка яв­ляется одной из первоочередных задач при разработке блока синтаксического анализа транслятора.

Одним из способов описания алгоритма распознавания языка является за­дание его в виде некоторого распознающего устройства. Для КС-языков таки­ми устройствами являются магазинные автоматы (автоматы с магазинной памятью, МП-автоматы).

Формальное определение и содержательное описание функциониро­вания МП-автомата.

Недетерминированным МП-автоматом называется семерка вида:

М = <А, Q, Г, δ, q₀, Z₀, F>,

где А — конечное множество входных символов (входной алфавит);

Q — конечное множество внутренних состояний (алфавит состояний);

Г — конечное множество магазинных символов;

q₀∈ Q — начальное состояние автомата;

F⊆Q — множество заключительных состояний;

δ — отображение QxAxГ в множество подмножеств QxГ*,

т.е. отображение вида δ: QxAxГ → (QxГ*).

Схема МП-автомата показана на рис. 26. Автомат имеет конечное множе­ство состояний, конечное множество входных символов и неограниченную ленту, называемую лентой магазинной памяти или магазинной памятью. «Дно» магазина (самый нижний символ) отмечается специальным символом, называемым маркером дна (например, символом #). Магазинная память определяется свойством «первым пришел — последним ушел». При записи символа в магазин, его содержимое сдвигается на одну ячейку «вниз», а на освободившееся место записывается требуемый символ. В этом случае говорят, что символ «вталкивается» в магазин.

Рис. 26 Схема автомата с магазинной памятью

Для чтения доступен только самый верхний символ магази­на. Этот символ после чтения может либо остаться в магазине, либо быть уда­лен из него, т.е. «вытолкнут» из магазина. За один такт работы МП-автомата из магазина можно удалять не более одного символа.

Каждый шаг работы МП-автомата задается множеством правил перехода ав­томата из одних состояний в другие. Переходы в общем случае определяются:

· состоянием МП-автомата;

· верхним символом магазина;

· текущим входным символом.

Множество правил перехода называется управляющим устройством. В за­висимости от получаемой информации, управляющее устройство реализует один такт работы МП-автомата, который включает в себя три операции:

1) операции над магазином:

· втолкнуть в магазин определенный символ;

· вытолкнуть верхний символ из магазина;

· оставить содержимое магазина без изменений;

2) операции над состоянием:

· перейти в заданное новое состояние S;

· остаться в прежнем состоянии;

3) операции над входом:

· перейти к следующему входному символу и сделать его текущим;

· оставить данный входной символ текущим, т.е. держать его до

следующего шага.

Обработку входной цепочки МП-автомат начинает в некотором выделен­ном состоянии при определенном содержимом магазина. Затем автомат вы­полняет операции, задаваемые его управляющим устройством. При этом выполняется либо завершение обработки, либо переход в новое состояние. Если выполняется переход, то он дает новый верхний символ магазина, новый теку­щий символ, автомат переходит в новое состояние и цикл работы автомата повторяется.

МП-автомат называется МП-распознавателем, если у него два выхода ДОПУСТИТЬ и ОТВЕРГНУТЬ.

Работа МП-автомата при распознавании конкретной цепочки описывается обычно в виде последовательности конфигураций МП-автомата. Конфигурация МП-автомата содержит (содержимое стека; состояние; необработанная часть входной цепочки).

Более формальный способ описания МП-автомата — в виде последовательности ко­манд. Команда записывается в виде:

(q,a,z)→{(q₁,γ₁),...,(q_m,γ_m)},

где q, q₁,..., q_m ∈ Q; a ∈ A; z ∈ Г, γ ₁ γ_{2 …}γ_m ∈ Г*.

Команда интерпретируется следующим образом: МП-автомат находится в состоя­нии q, считывает входной символ а и верхний символ магазина z, переходит в состояние q_i, заменяя в магазине символ z на символ γ_i, l≤i≤m и продвигает входную головку на один символ.

Если же при выполнении команды сдвига входной ленты не выполняется, то команда записывается в виде:

(q,λ,z)→{(q₁,γ1),...,(q_m,γ_m)}.

и используется лишь для изменения содержимого магазина.

Различают детерминированные и недетерминированные МП-автоматы. Если среди команд МП-автомата нет двух, у которых совпадают левые части и не совпадают части, стоящие справа от стрелки, то МП-авто­мат называют детерминированным. В противном случае, т.е. когда для заданно­го состояния и текущих входном и магазинном символах, возможны переходы автомата в различные состояния, его называют недетерминированным.

Связь между КС-языками и недетерминированными автоматами выража­ется теоремами, которые показывают, что класс языков, допускаемых мага­зинными автоматами при пустом магазине, есть в точности класс КС-языков.

Теорема: Пусть L(G) — КС-язык, порождаемый грамматикой G = <N, T, P, S> в нормальной форме Грейбах (правила вывода которой имеют вид A->bα). Тогда существует недетерминиро­ванный нисходящий МП-автомат М, допускающий все слова языка L(G). Автомат М = <А, Q, Г, δ, q₀, Z₀, F> строится следую­щим образом:

1)А = Т;

2)Q={q,};

3)T = N;

4)q₀=q_q;

5)Z₀ = S;

6) F = ∅;

7) δ: (q, а, В)–> (q_p γ), когда подстановка В →aγ принадлежит множеству правил Р грамматики G, здесь В ∈N, а ∈Т, γ ∈ {N U T} * [5].

Пример 14

Дана КС-грамматика G = <N, T, P, S>, у которой

N={S,D,B},T={a,b},

Р= {S→aB | bD

D→aS | a | bDD

В → аВВ | bS | b}

В соответствии с теоремой МП-автомат М = <А, Q, Г, δ, q₀, Z₀, F>, допускающий данный КС-язык, будет включать в себя компоненты А = {а, Ь}, Q={q,}, Г = {S, D, В}, q₀ = q₁, z₀ = S и отображение δ, заданное в виде:

l.(q₁,a, S)→(q₁,B), т.к. (S → аВ) ∈ Р;

2.(q₁,b, S)→ (q₁, D); т.к. (S→bD)∈ P;

3.(q₁, a, D) → {(q₁, S), (q₁, λ)}, т.к. (D → aS) и (D → a)

входят в множество Р;

4. (q₁, b, D) → (q₁, DD), т.к. (D → bDD) ∈ P;

5. (q_­1, a, B) →(q₁, BB), т.к. (В → аВВ) ∈Р;

6. (q₁, b, B) → {(q₁, S), (q₁ λ)}, т.к. (B → bS) и (В → b)

входят в множество Р.

Построенный МП-автомат является недетерминированным, т.к. в нем в правилах 3 и 6 допускается неоднозначность перехода для одной и той же комбинации состояния входного и магазинного символов. В общем случае классы языков, допускаемых детерминированными и недетерминирован­ными МП-автоматами не совпадают. На практике же получили наибольшее применение детерминированные методы разбора для, так называемых, детер­минированных КС-языков, которые хотя и уже всего класса КС-языков, но боль­шинство языков программирования можно отнести к классу этих языков.

Дата добавления: 2014-12-27