ВУЗ:
Составители:
46
символами ⊥
H
и ⊥
K
(начало и конец цепочки). Для них определены следующие
отношения предшествования (S – целевой символ грамматики):
• ⊥
H
<• X, ∀ a∈V, если ∃ S⇒*Xy, где S∈VN, y∈V* или если X∈L(S);
• ⊥
K
•> X, ∀ a∈V, если ∃ S⇒*yX, где S∈VN, y∈V* или если X∈R(S).
Матрица предшествования служит основой для работы распознавателя
языка, заданного грамматикой простого предшествования.
Алгоритм «сдвиг-свертка» для грамматик простого
предшествования
Отношения предшествования служат для того, чтобы определить в процес-
се выполнения алгоритма, какое действие – сдвиг или свертка – должно выпол-
няться на каждом шаге алгоритма, и однозначно выбрать цепочку для свертки.
Однозначный выбор правила при свертке обеспечивается за счет различия пра-
вых частей всех правил грамматики.
Алгоритм состоит из следующих шагов:
Шаг 1. Поместить в верхушку стека символ ⊥
H
, считывающий элемент – в
начало входной цепочки символов.
Шаг 2. Сравнить с помощью отношения предшествования символ, нахо-
дящийся на вершине стека (левый символ отношения), с текущим символом
входной цепочки, обозреваемым считывающим элементом (правый символ от-
ношения).
Шаг 3. Если имеет место отношение <• или =•, то произвести сдвиг (пере-
нос текущего символа из входной цепочки в стек и сдвиг считывающего эле-
мента на один шаг вправо) и вернуться к шагу 2. Иначе перейти к шагу 4.
Шаг 4. Если имеет место отношение •>, то произвести свертку. Для этого
надо найти на вершине стека все символы, связанные отношением =• («осно-
ву»), удалить эти символы из стека. Затем выбрать из грамматики правило,
имеющее правую часть, совпадающую с основой, и поместить в стек левую
часть выбранного правила (если символов, связанных отношением =•, на вер-
хушке стека нет, то в качестве основы используется один, самый верхний сим-
вол стека). Если правило, совпадающее с основой, найти не удалось, то необхо-
димо прервать выполнение алгоритма и сообщить об ошибке, иначе, если раз-
бор не закончен, то вернуться к шагу 2.
Шаг 5. Если не установлено ни одно отношение предшествования между
текущим символом входной цепочки и символом на верхушке стека, то надо
прервать выполнение алгоритма и сообщить об ошибке.
Разбор считается законченным, если считывающий элемент обозревает
символ ⊥
K
и при этом больше не может быть выполнена свертка. Решение о
принятии цепочки зависит от содержимого стека. Цепочка принимается, если в
результате завершения алгоритма в стеке находятся начальный символ грамма-
тики S и символ ⊥
H
.
Грамматики операторного предшествования
Операторной грамматикой называется КС-грамматика без λ-правил, в ко-
торой правые части всех правил не содержат смежных нетерминальных
Страницы
- « первая
- ‹ предыдущая
- …
- 42
- 43
- 44
- 45
- 46
- …
- следующая ›
- последняя »
