Грамматики с операторным предшествованием. Определение
отношений
Другим типом грамматик, в которых могут быть определены отношения между символами, являются грамматики с операторным предшествованием.
Операторной грамматикой называется грамматика, не содержащая правил вида A → xBCy, где x, y – произвольные строки, B, C – нетерминалы.
Пусть U, C, D – нетерминалы. Грамматикой с операторным предшествованием называется операторная грамматика, в которой все правые части правил различны и между двумя любыми терминальными символами p, q выполняется не более чем одно из следующих отношений предшествования:
p=q, если существует правило U → xpqy или U→xpСqy;
p qz или CDqz;
p>q, если существует правило U → xCqy и вывод Czp или CzpD.
Для определения отношений строятся множества:
LT(U) – множество левых терминалов в разложениях U, т.е. множество таких терминалов q, что существует вывод Uqz или UDqz;
RT(U) – множество правых терминалов в разложениях U, т.е. множество таких терминалов p, что существует вывод Uzp или UzpD.
С этой целью:
строятся множества левых и правых символов – L(U), R(U) (см. п.4.2);
для правил вида U → qz, U → Cqz терминал q заносится в LT(U); для правил вида U → zp, U → zpC терминал p заносится в RT(U);
для каждого нетерминала U', принадлежащего L(U), LT(U) дополняется терминалами из LT(U'). Аналогично дополняется RT(U).
Пример:
S → T | S+T Грамматика для выражений, состоящих из
T → ид | T*ид идентификаторов и знаков +, *.
Построение множеств левых и правых терминалов для нетерминальных символов:
L(U), R(U) после первого шага окончательно
U
|
L(U)
|
R(U)
|
|
U
|
L(U)
|
R(U)
|
S
|
T, S
|
T
|
|
S
|
T, S, ид
|
T, ид
|
T
|
Ид, T
|
ид
|
|
T
|
ид, T
|
ид
| |
Скачать 0.64 Mb.