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

UptoLike

ВУЗ: 

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

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

Рубрика: 

44
− В
i
<• В
j
(∀ B
i
, B
j
∈ V), если и только если ∃ правило A→xB
i
Dy ∈ P и вывод
D⇒*S
j
z, где A,D∈VN, x,y,z∈V*;
− В
i
•> B
j
(∀ B
i
, B
j
∈ V), если и только если ∃ правило А→хСВ
j
у ∈ P и вывод
C⇒*zB
i
или ∃ правило A→xCDy ∈ P и выводы C⇒*zB
i
и D⇒*B
j
w, где
A,C,D∈VN, x,y,z,w∈V*.
2. Различные правила в грамматике имеют разные правые части.
Отношения =•, <• и •> называют отношениями предшествования для сим-
волов. Отношение предшествования единственно для каждой упорядоченной
пары символов. При этом между какими-либо двумя символами может и не
быть отношения предшествования – это значит, что они не могут находиться
рядом ни в одном элементе разбора синтаксически правильной цепочки. Отно-
шения предшествования зависят от порядка, в котором стоят символы, и в этом
смысле их нельзя путать со знаками математических операций – они не обла-
дают ни свойством коммутативности, ни свойством ассоциативности. Напри-
мер, если известно, что В
i
•> B
j
, то не обязательно выполняется B
j
<• В
i
.
Для грамматик простого предшествования известны следующие свойства:
• всякая грамматика простого предшествования является однозначной;
•
легко проверить, является или нет произвольная КС-грамматика граммати-
кой простого предшествования (для этого достаточно проверить рассмот-
ренные выше свойства грамматик простого предшествования или восполь-
зоваться алгоритмом построения матрицы предшествования, который бу-
дет рассмотрен далее).
Как и для многих других классов грамматик, для грамматик простого
предшествования не существует алгоритма, который бы мог преобразовать
произвольную КС-грамматику в грамматику простого предшествования (или
доказать, что преобразование невозможно).
Метод предшествования основан на том факте, что отношения предшест-
вования между двумя соседними символами распознаваемой строки соответст-
вуют трем следующим вариантам:
• B
i
<• B
i+1
, если символ B
i+1
– крайний левый символ некоторой основы (это
отношение между символами можно назвать «предшествует основе» или
просто «предшествует»);
• В
i
•> B
i+1
, если символ В
i
– крайний правый символ некоторой основы (это
отношение между символами можно назвать «следует за основой» или
просто «следует»);
• В
i
=• B
i+1
, если символы В
i
и B
i+1
принадлежат одной основе (это отноше-
ние между символами можно назвать «составляют основу»).
На основании отношений предшествования строят матрицу предшествова-
ния грамматики. Строки матрицы предшествования помечаются первыми (ле-
выми) символами, столбцы – вторыми (правыми) символами отношений пред-
шествования. В клетки матрицы на пересечении соответствующих столбца и
строки помещаются знаки отношений. При этом пустые клетки матрицы гово-
рят о том, что между данными символами нет ни одного отношения предшест-
вования.

Страницы