Системное программное обеспечение: Основы трансляции. Карпушин А.Н - 45 стр.

UptoLike

ВУЗ: 

УлГТУ | Ульяновск

Составители: 

Рубрика: 

47
символов. Для операторной грамматики отношения предшествования можно
задать на множестве терминальных символов (включая символы ⊥
H
и ⊥
K
).
Грамматикой операторного предшествования называется операторная
КС-грамматика G(VN,VT,P,S), V = VT∪VN, для которой выполняются сле-
дующие условия:
1. Для каждой упорядоченной пары терминальных символов выполняется не
более, чем одно из трех отношений предшествования:
• а =• b, если и только если существует правило A→xaby ∈ Р или правило
А→хаСbу, где a,b∈VT, A,C∈VN, x,y∈V*;
• а <• b, если и только если существует правило А→хаСу ∈ Р и вывод
C⇒*bz или вывод C⇒*Dbz, где a,b∈VT, A,C,D∈VN, x,y,z∈V*;
• а •> b, если и только если существует правило А→хСЬу ∈
P
и вывод
C⇒*za или вывод C⇒*zaD, где a,b∈VT, A,C,D∈VN, x,y,z∈V*.
2. Различные порождающие правила имеют разные правые части, λ-правила
отсутствуют.
Отношения предшествования для грамматик операторного предшествова-
ния определены таким образом, что для них выполняется еще одна особенность
– правила грамматики операторного предшествования не могут содержать двух
смежных нетерминальных символов в правой части. То есть в грамматике опе-
раторного предшествования G(VN,VT,P,S), V = VT∪VN не может быть ни од-
ного правила вида: А→хВСу, где A,B,C∈VN, x.y∈V* (здесь х и у – это произ-
вольные цепочки символов, могут быть и пустыми).
Грамматики операторного предшествования имеют следующие свойства:
• всякая грамматика операторного предшествования задает детерминирован-
ный КС-язык (но не всякая грамматика операторного предшествования при
этом является однозначной);
• легко проверить, является или нет произвольная КС-грамматика граммати-
кой операторного предшествования.
Как и для многих других классов грамматик, для грамматик операторного
предшествования не существует алгоритма, который бы мог преобразовать
произвольную КС-грамматику в грамматику операторного предшествования
(или доказать, что преобразование невозможно).
Принцип работы распознавателя для грамматики операторного предшест-
вования аналогичен грамматике простого предшествования, но отношения
предшествования проверяются в процессе разбора только между терминальны-
ми символами.
Для грамматики данного вида на основе установленных отношений пред-
шествования также строится матрица предшествования, но она содержит толь-
ко терминальные символы грамматики. Для построения этой матрицы удобно
ввести множества крайних левых и крайних правых терминальных символов
относительно нетерминального символа А – L
t
(A) или R
t
(A):
L
t
(А) = {t | ∃ A⇒*tz или ∃ A⇒*Ctz }, где t∈VT, A,C∈VN, z∈V*;
R
t
(A) = {t | ∃ A⇒*zt или ∃ A⇒*ztC }, где t∈VT, A,C∈VN, z∈V*.

Страницы