Распознаватель

Основная идея алгоритма разбора следующая. Символы входной строки поочерёдно переписываются в стек до тех пор, пока между символами в вершине стека, обозначим его S_l - и очерёдным символом входной строки – S_i - не появится отношение , т.е. S_l S_i

Тогда стек просматривается в направлении от вершины к началу до тех пор пока, между двумя очередными символами S_k-1 и S_k не появится отношение S_k-1 S_{k .} Часть стека от символа S_k до символа в вершине S_l - основа. Теперь среди порождающих правил отыскивается правило вида: U->S_k…S_l – u, если нужно, вызывается семантическая подпрограмма, которая обрабатывает сроку S_k…S_l, переводя её на промежуточный или входной язык. После этого в стеке строка S_k…S_l заменяется символом U, и описанный выше процесс заполнения стека символами входной цепочки продолжается.

вершина стека ↓  

U

S_k-1

…

Si

Si+1

……

Sn

Если на некотором шаге процесса обнаруживается, что между соседними символами S_p и S_q отношения предшествования, то это свидетельствует об ошибке типа «символы S_p и S_q не могут не могут находиться рядом». Соответствующая информация заносится в таблицу ошибок.

Дата добавления: 2014-01-11