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

Содержание 59
ИНФОРМАЦИОННЫЕ СТРУКТУРЫ И ИХ ПРЕОБРАЗОВАНИЕ
выбрала первую альтернативу и, столкнувшись с неудачей
вернулась и выбрала бы
Т2 |→ $)a,FТE aFTE,,q(
122 121 3 + |→ ,$)aFТE aFTE,,q(
122 121 4 +
сравниваем удачно
4 3 2 1
#a a
↑
+
Гомоморфизм 123123 )aFTE aFTE(h
122 121 = + .
Восходящий разбор
Должно быть понятно, что каким бы методом («сверху вниз» или
«снизу вверх») мы ни воспользовались для синтаксического разбора строки
) (
1 GL x ∈ , где G — контекстно свободная грамматика, результат должен быть
один (это утверждение справедливо при условии допустимости
использования обоих методов), так как эти методы отличаются лишь спо-
собами построения деревьев.
Если метод синтаксического разбора «сверху вниз» рекомендует
построение указанных деревьев начиная с корня, то метод «снизу вверх»
рекомендует строить их наоборот, начиная с листьев и кончая корнем дерева.
Введенные входные строки в последнем случае анализируются слева
направо; получаемые в процессе подстроки сравниваются с правыми частями
продукции грамматики, а при совпадении заменяются или приводятся к
нетерминальному символу, стоящему в левой части таких продукций. В
результате такой замены может быть получена сентенциальная форма
грамматики, а затем вся процедура повторяется до тех пор, пока полученная
сентенциальная форма не примет вид S, где символом S помечен корень
дерева вывода. В результате будет получена последовательность схем вывода
и соответствующих им приведений, позволяющая построить дерево вывода
от листьев до корня. Каждому элементу этой последовательности, очевидно,
соответствует один родительский узел дерева вывода.
Рассмотрим грамматику G 1, имеющую следующие продукции:
b aBB B
a bAA A
bA bAC aB aBC C
C S
|
|
, | | |
$,
→
→
→
→