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

Содержание 11
ИНФОРМАЦИОННЫЕ СТРУКТУРЫ И ИХ ПРЕОБРАЗОВАНИЕ
Пример: Выведем предложение (i+i)i.
Левосторонний вывод – это такой вывод, при котором на каждом
шаге заменяется самый левый символ.
Используем правила из примера:
E=>T=>T∗F=>F∗F=>(E)∗F=>(E+T)F=>(T+T)F=>(F+T)F=>(i+T)F=>(i+F)F
=>(i+i)F=>(i+i)i .
Правосторонний вывод:
E=>T=>T∗F=>F∗F=>(E)F=>(E+T)F=>(T+T)F=>(F+T)F=>(i+T)F=>(i+F)F=
>(i+i)F=>(i+i)i .
Рассмотрим грамматику : E:=E+E|E ∗E; E:=i.
Нужно вывести предложение i+i∗i . Рассмотрим 2 дерева:
+ *
* +
Из обоих этих деревьев выделяется нужная цепочка. В этом случае для
построения цепочки есть альтернатива, в отличие от предыдущего примера.
Эта грамматика неоднозначная. Критерием неоднозначности являются
различные деревья.
Если какое-либо предложение, генерированное грамматикой, имеет
более 1-го дерева разбора, то говорят, что грамматика неоднозначна. Задача
установления неоднозначности в какой-либо грамматике неразрешима, т.е.
не существует алгоритма, который бы за конечное число шагов, рассмотрев
предложение, ответил бы – однозначна грамматика его породившая, или нет.
Задачи разбора заключаются в том, чтобы распознать: принадлежит ли
предложение языка программирования рассматриваемой грамматике.
Различают 2 категории алгоритмов: нисходящий (развертка) и восходящий
(свертка).
Итеративная форма задания грамматик
Цель: создание бесконечного числа цепочек конечным (минимальным)
количеством правил. Вводится мета-символ { }, который означает: элемент,
находящийся внутри { }, может повторяться многократно.
Е
Е
Е Е
Е
Е
i i
Е
i i
i
Е
Е
Е i