Стр. 62 - Информационные структуры и их преобразование

60 Содержание
ИНФОРМАЦИОННЫЕ СТРУКТУРЫ И ИХ ПРЕОБРАЗОВАНИЕ
G 1 - однозначная грамматика, и, следовательно, любой строке
) (
1 GL x ∈ соответствует единственное дерево вывода.
Например, дерево вывода для строки $ bbaa x = приведено на рис. 2, д.
b b a a $
A
b b a a $
A A
b b a a $
A A
A
а) б) в)
b b a a $
A A
A
C
b b a a $
A A
A
C
S
г) д)
Рис. 2. Дерево вывода для строки $ bbaa x =
Далее каждому дереву вывода соответствует единственная
правосторонняя схема вывода, т. е. такая схема вывода, в которой всегда
выводится самый правый нетерминальный символ. Так, дереву вывода,
рассмотренному в вышеприведенном примере, соответствует правосторонняя
схема вывода:
$ $ $ $ $ bbaa bbAa bbAA bA C S ⇒ ⇒ ⇒⇒⇒.
Рассматриваемый метод синтаксического разбора «снизу вверх»,
позволит построить такую схему вывода справа налево. Пример построения
дерева вывода для строки bbaa$ показан на рис.1. Подстроку, которая
приводится, называют основой правосторонней сентенциальной формы,
или правосторонней простой фразой. Процесс построения дерева вывода
для нашего примера иллюстрируется табл.1.
Таблица1
Правосторонняя сентенциальная
форма
Основа Замещающий
символ
bbaa$ а (левый символ) А
bbАа$ а А
bbАА$ bАА А
bА$ bА С
С$ С$ S