Использование матриц с предшествованием

	A	B	C	x	y	z	┤
A				=* ∙
B			=* ∙	<*∙
C							∙*>
x				=*∙	=*∙	=*∙	∙*>
y				∙*>
z				∙*>
├	<*∙	<*∙		<*∙

S ® BC

B ® Axz

C ® xx

A ® xy

Считаем, что она построена.

Использование матрицы:

xyxzxx - проставляем все значки

├ <* x =* y∙*> x =* z∙*> x =* x *> ┤

├ <* A ∙ x ∙ y ∙*> x ∙ x ∙ *> ┤

├ <* B <* x =* x *> ┤

├ <* B =* C *> ┤

├ S ┤

Алгоритм распознавания:

1. Между символами строки вставляются отношения предшествования.

5. Строка просматривается слева направо до первого символа ∙*>, после этого просмотр идет в обратном направлении до первого встречаемого символа *<∙ - между этими символами и находится свертка, то есть правая часть правила, которая заменяется левой.

3. Восстанавливаются отношения предшествования.

4. Возвращение к первому пункту. Процесс продолжается до получения начального нетерминального символа. Если этот процесс не завершиться успешно, строка не принадлежит данной грамматике.

У этого метода есть минусы:

1. Далеко не во всех случаях удается построить грамматику с предшествованиями.

2. На практике символов может быть много сотен сотни и в результате получается слабозаполненная матрица большой размерности.