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

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

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

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

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

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

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

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

L(u)={S|uuASL(A)}, где uV_N,, S(V_TV_N), (V_TV_N)^*

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

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

а) S₁S₂, если существует правило вида: uS₁S₂, где u – нетерминал, S₁,S₂(V_TV_N), ,(V_TV_N)^*.

б) S₁<·S₂, если существует правило вида: uS₁, S₂L(B), S₁,S₂(V_TV_N), u,BV_N, ,(V_TV_N)^*

в) S₁·>S₂, если существует правило вида: uAS₂, S₁R(A), S₁,S₂(V_TV_N), u,AV_N, ,(V_TV_N)^* или uAB, S₁R(A), S₂L(B), A,B,uV_N

Пример 6.1.

S(AB), A[A]|, B[B]|

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

U	L(u)	R(u)
S		
A	[	]
B	[+	]+

Рис. 6.1.

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

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

Рис. 6.2.

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

-

S

Рис. 6.3.

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

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

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