Включение -правил в lr(0)- и slr (1)-грамматики

г) если А   – правило вывода с номером i и множество

СЛЕД (A) ={aj  1j  m , где m – количество символов в T  { } },

то f(aj) = (СВЕРТКА, i) в тех строках управляющей таблицы, для которых g(A) ОШИБКА.

Алгоритм построения анализатора типа “перенос –свертка” для грамматик простого предшествования

Вход

Грамматика простого предшествования G = < T, N, S, R >, в которой правила вывода занумерованы натуральными чис­лами 1, 2, ... , р.

Выход

Алгоритм A = (f, g) типа “перенос – свертка” для грамматики G.

1. Функция переноса f зависит только от верхнего символа магазина и самого левого необработанного символа входной це­почки. Поэтому f определяется на множестве (V  {  })  (T  {  }) ( за исключением правила с), которое имеет приоритет над правила­ми а) и b), когда Х = S и a =  ):

1. f(X, а) = ПЕРЕНОС, если Х <• а или Х  а ;

2. f(X, а) = СВЕРТКА, если Х •> а ;

3. f(S, ) = ДОПУСК;

4. f(X, а) = ОШИБКА в остальных случаях.

2) Функция свертки g зависит от верхней части магазинной цепочки, включающей основу и еще один символ ниже нее. Необ­работанная часть входной цепочки на g не влияет, поэтому g задается только на (V  {  })^*:

1. g(X_k+1X_kX_k-1 … X₁, ) = i, если X_k+1 <• X_k, X_j+1  X_j для k>j1 и

A  Х_kХ_k-₁ ... Х₁ – правило вывода с номером i. Заметим, что функция g определяется только тогда, когда Х₁ •> a – текущий входной символ;

b) g(, ) = ОШИБКА в остальных случаях.

Для КС-грамматики G = < T, N, S, R >отношения простого предшествования <• и  определя­ются на (V  {  })(V  {  }), где –маркер дна магазина, следующим образом:

X  Y,если вRесть правилоA  XY.

a) X <• Y,если вRесть правилоA  XB иB +Y;

б)  <• Yдля всехY, для которыхS + Y;

Отношение • определяется на(V  {  })(T  {  }), так как непосредственно справа от правовыводимой цепочки может стоять только терминал.

a)X • a,если вRесть правилоA  BY иB +X и Y a;

б) X •  для всех, для которыхS + X.

пример

S  aSSb

S  c

f(X,a)	a	b	c	
S	П	П	П
a	П		П
b	С	С	С	С
c	С	С	С	С
	П		П
S				Д

		g()
S	aSSb	1
a	aSSb	1
	aSSb	1
S	c	2
a	c	2
	c	2

	S	a	b	c	
S		<•		<•
a		<•		<•
b		•	•	•	•
c		•	•	•	•
		<•		<•

грамматики слабого предшествования.

Определение.

Пусть G = < T, N, S, R > – приве­денная грамматика без -правил. Назовем G грамматикой сла­бого предшествования, если

1)отношение •> не пересекается с объединением отношений <• и  ;

2)для AX и В   из R, где XV, не выполняется ни Х <• В, ни Х  В.

Вход

Обратимая грамматика слабого предшествования G = < T, N, S, R >, правила которой занумерованы натуральными числами от 1 до р.

Выход

Алгоритм A = (f, g) типа “перенос – свертка” для грамматики G.