Языки и трансляции. Мартыненко Б.К. - 166 стр.

UptoLike

ВУЗ: 

СПбГУ | Санкт-Петербург

Составители: 

Рубрика: 

164
символов на входе и не имеет внутренних состояний управления. В начальный
момент на входе находится анализируемая цепочка, в магазине — начальный
символ магазина и маркер “дна”, на выходе пусто. Читающая головка
сканирует начало входной ленты. На каждом такте работы алгоритм адресуется
к своей управляющей таблице с двумя входами: верхним символом магазина и
текущей аванцепочкой. Управляющий элемент диктует одно движение из двух,
которое и выполняется. Этот цикл повторяется до тех пор, пока управляющий
элемент не просигнализирует о приёме входной цепочки, и в этом случае на
выходе образуется её левосторонний анализ, или управляющий элемент
диагностирует ошибку на входе, и тогда алгоритм останавливается, не
принимая входной цепочки.
На рис. 2.1 входная цепочка, представлена как wx, причём w обозначает
просмотренную, а x — не просмотренную её часть, которая начинается с
аванцепочки u и заканчивается цепочкой y. Магазинная цепочка представлена
в виде Xα$, где X обозначает верхний символ магазина, α — символы
магазина, располагающиеся ниже его вершины, а $ — маркер “дна”. Выходная
цепочка представлена как πi, где π обозначает часть цепочки, образованную
перед последним движением алгоритма, а i — последнюю произведенную
запись на выходную ленту.
2.3.2. Формальное определение.
Сначала дадим несколько определений.
Определение 2.9. k-Предсказывающим алгоритмом анализа называется
формальная система A =(Σ, Γ∪{$}, ∆, M, X
0
, $), где Σ — входной алфавит,
Γ∪{$} — магазинный алфавит, $ ∉Γ— маркер “дна” магазина, ∆ — выходной
алфавит, X
0
∈Γ— начальный символ магазина, M: (Γ∪{$}) ×Σ
*
k
→ { (β, i), pop,
accept, error} — управляющая таблица, причём β ∈ Γ
*
, i ∈ ∆ — номер правила
грамматики.
Работу k-предсказывающего алгоритма анализа проще всего описать в
терминах отношения на множестве конфигураций.
Определение 2.10. Под конфигурацией k-предсказывающего алгоритма
анализа будем подразумевать тройку (x, α, π), где x ∈Σ
*
— непросмотренная
часть входной цепочки, причём
*
FIRST ( ),
Gk
k
uxu
∈
∈Σ — аванцепочка, α∈Γ
*
{$}
— магазинная цепочка, π∈∆
*
— выходная цепочка.
Начальная
конфигурация есть (w, X
0
$, ε), где w ∈Σ
*
— вся входная цепочка.
Пусть (x, Xα, π) — текущая конфигурация, где x ∈Σ
*
— непросмотренная
часть входной цепочки, X ∈Γ∪{ε} — верхний символ магазина или пустая
цепочка, α∈Γ
*
{$} — остальная часть магазинной цепочки.
Определим следующую конфигурацию в зависимости от значения
элемента управляющей таблицы M(X, u).
__
1. Если (, )(, ), то (, , ) (, ).
M
Xu i xX x i=β απ βα,π
2.
Если ( , ) pop, MXu=
и в этом случае всегда X = a, a∈Σ, x = ax
’,
x
’
∈Σ
*
, то
(, , ( , , ( , , ).xX ax a x
__
′′
απ)= απ) απ
−−

Страницы