Грамматики предшествования Вирта

Отношения предшествования в грамматиках Вирта определяются между любыми символами: как терминальными, так и нетерминальными.

Алгоритм свёртки терминальных цепочек по Вирту:

1. Строится для любого нетерминального символа множество левых и правых символов.

2. Определяется отношение предшествования между символами, и заносятся в матрицу (таблицу предшествования).

3.Выполняя последовательные выделения основ для свёртки, осуществляется собственно свёртка цепочек.

4. Включается семантика в алгоритм свёртки цепочки.

Множество левых и правых символов для каждого нетерминала грамматики определяется следующим образом: L – множество левых символов:

L(u)={S|u®jÚu®AjÙSÎL(A)}, где uÎV_N,, SÎ(V_TÈV_N), jÎ(V_TÈV_N)^*

R – множество правых символов:

Отношения предшествования в грамматике по Вирту определяются следующим образом:

а) S₁ S₂, если существует правило вида: u®jS₁S₂h, где u – нетерминал, S₁,S₂Î(V_TÈV_N), j,hÎ(V_TÈV_N)^*.

б) S₁<·S₂, если существует правило вида: u®jS₁bh, S₂ÎL(B), S₁,S₂Î(V_TÈV_N), u,BÎV_N, j,hÎ(V_TÈV_N)^*

в) S₁·>S₂, если существует правило вида: u®jAS₂h, S₁ÎR(A), S₁,S₂Î(V_TÈV_N), u,AÎV_N, j,hÎ(V_TÈV_N)^* или u®jABh, S₁ÎR(A), S₂ÎL(B), A,B,uÎV_N

Пример 6.1.

S®^(AB)^, A®[A]|*, B®[B]|*

Строим множество левых и правых символов.

Рис. 6.1.

Матрица предшествования: S ^ ( A B ) [ ] * + S                     ^                   (           <·   <·   A           <·   <· B                 )                   [         <·   <· <· ]         ·> ·> ·> ·>   ·> *         ·>   ·> ·>   ·> +           ·>   ·>	S	^	(	A	B	)	[	]	*	+
S
^
(							<·		<·
A							<·			<·
B
)
[							<·		<·	<·
]					·>	·>	·>	·>		·>
*					·>		·>	·>		·>
+						·>		·>

Матрица предшествования:

Рис. 6.2.

Проверим принадлежность цепочки языку, выполнив свертку по Вирту:

-

S

Рис. 6.3.

Как видно, удалось свернуть цепочку до начального выделенного символа S, значит, цепочка принадлежит языку. Зато цепочка языку.

При выполнении свертки по Вирту возможны следующие ошибки:
1)между двумя символами не существует отношения предшествования;
2)выделена основа для свертки, а подходящего правила для замены нет.
Следует заметить, что не существует общего алгоритма, позволяющего преобразовать произвольную КС-грамматику к грамматике предшествования, хотя существует правило, позволяющее выполнить это для некоторых КС-грамматик, действие которого показано на следующем примере:

Включение семантики осуществляется следующим образом: в соответствии с любым правилом вывода ставится некоторое семантическое действие, которое выполняется при замене основы для свертки на это правило.