Операционная система UNIX. Руководство программиста

Заказать электромонтажные услуги в квартире в Новокузнецке и пригороде. Русский электрик.

АЛГОРИТМ СИНТАКСИЧЕСКОГО РАЗБОРА - часть 2


Действие свертка препятствует неограниченному росту стека. Оно выполняется, когда алгоритм, просмотрев правую часть правила, обнаруживает в обрабатываемых данных ее вхождение, которое и заменяет левой частью. Может понадобиться проанализировать предварительно просмотренную лексему (обычно этого не требуется), чтобы решить, выполнять свертку или нет. Часто подразумеваемым действием (которое обозначается точкой) оказывается именно свертка.

Действия свертка ассоциируются с отдельными грамматическими правилами. Грамматические правила (как и состояния) нумеруются небольшими целыми числами, и это приводит к некоторой путанице. В действии

. reduce 18

имеется в виду грамматическое правило 18, тогда как в действии

IF shift 34

- состояние 34.

Предположим, выполняется свертка для правила

A : x y z ;

Действие свертка зависит от символа в левой части правила (в данном случае A) и числа символов в правой части (в данном случае три). При свертке сначала из стека извлекаются три верхних состояния. (В общем случае число извлекаемых состояний равно числу символов в правой части правила). В сущности, эти состояния были занесены в стек при распознавании x, y и z и больше не нужны. После того, как извлечены эти состояния, на вершине стека оказывается состояние автомата на момент перед началом применения данного правила. Для этого состояния и символа, стоящего в левой части правила, выполняется действие, имеющее результат, аналогичный переносу с аргументом A. Конечный автомат переходит в новое состояние, которое заносится в стек, и разбор продолжается. Имеются, однако, существенные отличия между обработкой символа из левой части правила и обычным переносом лексемы, поэтому это действие называется действием переход (goto). В частности, предварительно просмотренная лексема при переносе очищается, а при переходе не затрагивается. В любом случае, открывшееся на вершине стека состояние содержит действие

A goto 20

выполнение которого приводит к тому, что состояние 20 помещается на вершину стека и становится текущим.




Начало  Назад  Вперед



Книжный магазин