Задачи по программированию по курсу ЯПиМТ. Родионова Т.Е. - 30 стр.

UptoLike

ВУЗ: 

УлГТУ | Ульяновск

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

Рубрика: 

30
чен. Множество ситуаций конечно, так как получаемые в дальнейшем с помощью сдвига активные префик-
сы будут повторять уже описанные ситуации.
Построенное множество ситуаций называется канонической LR(0) –системой. В ней нет конфликтов
типа сдвиг-свертка и свертка-свертка. По данным состояниям можно осуществлять разбор предложений язы-
ка и ,следовательно, грамматика обладает свойством LR(0).
Составим управляющую таблицу для LR(0) разбора. Количество строк в таблице равно числу со-
стояний, количество столбцов – число терминалов и нетерминалов в грамматике плюс три. Первый столбец –
номер состояния, далее столбец с активным префиксом, затем столбец действия по данному состоянию. Да-
лее следует несколько столбцов для задания переходов по символам правил. Для вышеуказанного примера
таблица имеет следующий вид:
Переход
Префикс Действие
abS
0eсдвиг 123
1aсдвиг 124
2bсвертка (1)
rrr
3Sдопуск
rrr
4aSсдвиг 125
5aSSсвертка (2)
rrr
В начале работы в стеке содержится фиктивный элемент с состоянием V(0). В процессе работы по
текущему состоянию (вершине стека) выбирается действие. Если действие “сдвиг”, то очередной символ из
входной строки помещается в стек. По текущему состоянию и этому символу вычисляется новое состояние,
которое записывается на вершину стека. Если действие “свертка”, то из стека извлекается нужное количест-
во символов. По состоянию на новой вершине стека и полученному при свертке нетерминалу вычисляется
новое состояние, которое вместе с нетерминалом записывается на вершину стека.
Грамматики предшествования являются подклассами LR(k) – грамматик. При разборе данного типа
грамматик используется понятие “основа цепочки”. Основа правовыводимой цепочки – это ее любая подце-
почка, которая является правой частью некоторого правила, причем после замены ее левой частью этого пра-
вила, тоже получается правовыводимая цепочка. Таким образом, если цепочку
αβω
можно свернуть в цепоч-
ку
α
A
ω
с помощью правила A
→β
, то
β
- основа цепочки
αβω
.
Для грамматики предшествования границы основы правовыводимой цепочки можно определить с
помощью некоторых отношений между символами, входящими в эту цепочку. Используются три отношения
предшествования:
•> - конец основы, выполняется между последним символом цепочки β ипервымсимволомце-
почки
ω
;
<•
- начало основы, выполняется между последним символом цепочки
α
и первым символом цепоч-
ки β;
=
•
- выполняется между смежными символами основы.
Итак, основу правовыводимой цепочки грамматики простого предшествования можно выделить,
просматривая эту цепочку слева направо до тех пор, пока впервые не встретится отношение конца цепочки.
Для нахождения левого конца основы надо возвращаться назад, пока не встретится отношение начала осно-

Страницы