Лекция: Использование матриц с предшествованием.
| 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. На практике символов может быть много сотен сотни и в результате получается слабозаполненная матрица большой размерности.