Реферат: Проектирование трансляторов

ли u C Vt*. Вывод w=>v канонический, если все непосредственные

выводы в нем канонические.

Сентенциальная форма, имеющая канонический вывод - канони-

ческая сентенциальная форма.

Свертывание будем называть проходом или анализом. В дальней-

шем будем считать, что в процессе анализа считывание входного

текста происходит слева направо, а свертывание начинается с той

самой левой части строки, которая может быть свернута без допол-

нительного анализа последующего текста. Такое свертывание будем

называть каноническим.

Отношения

->, => - символы отношений между цепочками.

Пара цепочек (c,d) принадлежит отношению R, если выполняет-

ся cRd.

Отношение P включает R, если из (c,d) C R следует (c,d) C Р.

Отношение, обратное R - R^(-1).

Рефлексивное отношение - при справедливости сRc.

Например: i <= i - рефлексивное, а i < i - не рефлексивное

отношение.

Транзитивное отношение R - если выполняется aRb, bRc => aRc.

Произведение R,P: cRPd - если существует е, такое что cRe и ePd.

Итерация R - (обозначается R*): aR*b - когда a=b или aR+b.

Ограничения, накладываемые на грамматику G:

- нет правил вида U ::= U;

- S=>xUy, U=>t, t C Vt* - приведенная грамматика;

Пример. G - язык арифметических выражений.

S ::= E

E ::= T

E ::= E+T