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

UptoLike

ВУЗ: 

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

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

Рубрика: 

45
Матрицу предшествования грамматики сложно построить, опираясь непо-
средственно на определения отношений предшествования. Удобнее воспользо-
ваться двумя дополнительными множествами – множеством крайних левых и
множеством крайних правых символов относительно нетерминальных симво-
лов грамматики. Эти множества определяются следующим образом:
• L(A) = {X | ∃ A⇒*Xz}, A∈VN, X∈V, z∈V* – множество крайних левых
символов относительно нетерминального символа А (цепочка z может
быть и пустой цепочкой);
•
R(A) = {X | ∃ A⇒*zX}, A∈VN, X∈V, z∈V* – множество крайних правых
символов относительно нетерминального символа А.
Иными словами, множество крайних левых символов относительно нетер-
минального символа А – это множество всех крайних левых символов в цепоч-
ках, которые могут быть выведены из символа А. Аналогично определяется и
множество крайних правых символов относительно нетерминального символа
А. Тогда отношения предшествования можно определить так:
• В
i
=• B
j
(∀ B
i
, B
j
∈ V), если ∃ правило A→xB
i
B
j
y ∈ Р, где A ∈ VN, x,y∈V*;
• В
i
<• B
j
(∀ B
i
, B
j
∈ V), если ∃ правило A→xB
i
Dy ∈ Р и B
j
∈ L(D), где
A,D∈VN, x,y∈V*;
•
В
i
•> Bj (∀ B
i
, B
j
∈ V), если ∃ правило A→xCB
j
y ∈ Р и B
i
∈R(C) или ∃ пра-
вило A→xCDy ∈ Р и B
i
∈R(C), B
j
∈L(D), где A,C,D∈VN, x,y∈V*.
Такое определение отношений удобнее на практике, так как не требует по-
строения выводов, а множества L(A) и R(A) могут быть построены для каждого
нетерминального символа A∈VN грамматики G(VN,VT,P,S), V = VT∪VN по
следующему алгоритму:
Шаг 1. ∀ A∈VN:
R
o
(A) = {X | А→уХ, X∈V, y∈V*}, L
0
(A) = {X | A→Xy, X∈V, y∈V*}, i:= 1.
Для каждого нетерминального символа А ищем все правила, содержащие
А в левой части. Во множество L(A) включаем самый левый символ из правой
части правил, а во множество R(A) — самый крайний правый символ из правой
части. Переходим к шагу 2.
Шаг 2. ∀ A∈VN:
R
i
(A) = R
i-1
(A) ∪ R
i-1
(B), ∀ В ∈ (R
i-1
(A) ∩ VN),
L
i
(А) = L
i-1
(A) ∪ L
i-1
(B), ∀ В ∈ (L
i-1
(A) ∩ VN).
Для каждого нетерминального символа А: если множество L(A) содержит
нетерминальные символы грамматики А', А", …, то его надо дополнить симво-
лами, входящими в соответствующие множества L(A'), L(A"), ... и не входящи-
ми в L(A). Ту же операцию надо выполнить для R(A).
Шаг 3. Если ∃ A∈VN: R
i
(A) ≠ R
i-1
(A) или L
i
(A) ≠ L
i-1
(A), то i:=i+l и вер-
нуться к шагу 2, иначе построение закончено: R(A) = R
i
(A) и L(A) = L
i
(A).
Если на предыдущем шаге хотя бы одно множество L(A) или R(A) для не-
которого символа грамматики изменилось, то надо вернуться к шагу 2, иначе
построение закончено.
После построения множеств L(A) и R(A) по правилам грамматики создает-
ся матрица предшествования. Матрицу предшествования дополняют

Страницы