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

UptoLike

ВУЗ: 

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

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

Рубрика: 

48
Тогда определения отношений операторного предшествования будут вы-
глядеть так:
a =• b, если ∃ правило A→xaby ∈ Р или правило U→xaCby, где a,b∈VT,
A,C∈VN, x,y∈V*;
a <• b, если ∃ правило А→хаСу ∈ Р и b∈L
t
(C), где a,b∈VT, A,C∈VN, x,y∈V*;
a •> b, если ∃ правило A→xCby ∈ Р и a∈R
t
(C), где a,b∈VT, A,C∈VN, x,y∈V*.
В данных определениях цепочки символов x,y,z могут быть и пустыми.
Для нахождения множеств L
t
(A) и R
t
(A) предварительно необходимо вы-
полнить построение множеств L(A) и R(A), как это было рассмотрено ранее.
Далее для построения L
t
(A) и R
t
(A) используется следующий алгоритм:
Шаг 1. ∀ A∈VN:
R
t
0
(A) = {t | A→ytB или A→yt, t∈VT, B∈VN, y∈V*},
L
t
0
(A) = {t | A→Bty или A→ty, t∈VT, B∈VN, y∈V*}.
Для каждого нетерминального символа А ищем все правила, содержащие
А в левой части. Во множество L(А) включаем самый левый терминальный
символ из правой части правил, игнорируя нетерминальные символы, а во
множество R(A) – самый крайний правый терминальный символ из правой час-
ти правил. Переходим к шагу 2.
Шаг 2. ∀ A∈VN:
R
t
i
(A) = R
t
i-1
(A) ∪ R
t
i-1
(B), ∀ В ∈ (R(A) ∩ VN),
L
t
i
(A) = L
t
i-1
(A) ∪ L
t
i-1
(B), ∀ В ∈ (L(A) ∩ VN).
Для каждого нетерминального символа А: если множество L(A) содержит
нетерминальные символы грамматики А', А", …, то его надо дополнить симво-
лами, входящими в соответствующие множества L
t
(A’), L
t
(A’’), ... и не входя-
щими в L
t
(A). Ту же операцию надо выполнить для множеств R(A) и R
t
(A).
Шаг 3. Если ∃ A∈VN: R
t
i
(A) ≠ R
t
i-1
(A) или L
t
i
(A) ≠ L
t
i-1
(A), то i:=i+1 и вер-
нуться к шагу 2, иначе построение закончено: R(A) = R
t
i
(A) и L(A) = L
t
i
(A).
Если на предыдущем шаге хотя бы одно множество L
t
(A) или R
t
(A) для не-
которого символа грамматики изменилось, то надо вернуться к шагу 2, иначе
построение закончено.
Для практического использования матрицу предшествования дополняют
символами ⊥
H
и ⊥K (начало и конец цепочки). Для них определены следующие
отношения предшествования (S – целевой символ грамматики):
• ⊥
H
<• а, ∀ a∈VT, если ∃ S⇒*ax или ∃ S⇒*Cax, где S, C∈VN, x∈V* или
если a∈L
t
(S);
• ⊥
K
•> a, ∀ a∈VT, если ∃ S⇒*xa или ∃ S⇒*xaC, где S, C∈VN, x∈V* или
если a∈R
t
(S).
Алгоритм «сдвиг-свертка» для грамматик операторного
предшествования
Этот алгоритм в целом похож на алгоритм для грамматик простого пред-
шествования, рассмотренный выше. Он имеет те же условия завершения и об-
наружения ошибок. Основное отличие состоит в том, что при определении от-
ношения предшествования этот алгоритм не принимает во внимание находя-

Страницы