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

26 Содержание
ИНФОРМАЦИОННЫЕ СТРУКТУРЫ И ИХ ПРЕОБРАЗОВАНИЕ
1. Все правые части правил единственны.
2. Для любой пары цепочек xy таких, что |x| = m; |y| = n, выполняется
не более одного из трех рассмотренных выше отношений.
3.6. Способ представления грамматики в ОП
Одномерный массив
EE+T|T$TT*F|F$F(E)|а#, где
$ – символ, не принадлежащий грамматике, - разделитель между
правилами;
# – конец массива;
| – промежуточный мета-символ.
Построение легкое, но работать с ним неудобно.
Имеет более удобную структуру двумерный массив.
Каждая вершина – это символ из правой части и содержит 4
компоненты:
1. Имя в некоторой внутренней форме.
2. Определение: 0, если терминал; в противном случае указывает
на первый символ правой части первого правила. Предположение, что
рассматриваемый находится в левой.
3. Альтернатива: указывает на первый символ правой части
правила, который может быть использован вместо правила, где стоит
рассматриваемый символ; 0 в противном случае.
4. Приемник: указывает на символ, который следует
непосредственно за рассматриваемым, а если такового нет, то 0.
Рассматриваются все символы для правой части.
Е
Определение Альтернатива Приёмник
E:=E<АОП>T|T;
T:=T<МОП>F|F;
F:=(E)|а;
АОП - аддитивный оператор: <АОП>:=+|-;
МОП - мультипликативный оператор: <МОП>:=*|/.