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


АЛГОРИТМ СИНТАКСИЧЕСКОГО РАЗБОРА


yacc отображает файл спецификаций в процедуру на языке C, которая разбирает входной текст в соответствии с заданной спецификацией. Алгоритм, используемый для того, чтобы перейти от спецификации к C-процедуре, сложен и здесь обсуждаться не будет. Алгоритм же самого разбора относительно прост, знание его облегчит понимание механизма нейтрализации ошибок и обработки неоднозначностей.

yacc порождает алгоритм разбора, использующий конечный автомат со стеком. Кроме того, алгоритм разбора может прочесть и запомнить следующую входную лексему (которая называется предварительно просмотренной). Текущее состояние автомата всегда сохраняется на вершине стека. Состояния конечного автомата задаются небольшими целочисленными значениями. В начальный момент автомат находится в состоянии 0 (стек содержит единственное значение 0) и предварительно просмотренная лексема не прочитана.

В алгоритме имеется всего четыре типа действий - перенос

(shift), свертка (reduce), успех (accept), ошибка (error). Шаг работы алгоритма состоит в следующем:

  • Основываясь на текущем состоянии автомата, алгоритм выясняет, требуется ли для выбора очередного действия предварительно просмотренная лексема. Если требуется, но не прочитана, алгоритм запрашивает следующую лексему у функции yylex.
  • Используя текущее состояние и, если нужно, предварительно просмотренную лексему, алгоритм выбирает очередное действие и выполняет его. В результате состояния могут быть помещены в стек или извлечены из него, предварительно просмотренная лексема может быть обработана, а может быть и нет.

Действие перенос - наиболее частое действие алгоритма. В выполнении действия перенос всегда участвует предварительно просмотренная лексема. Например, для состояния 56 может быть определено действие

IF shift 34

что означает: в состоянии 56, если предварительно просмотренная лексема равна IF, текущее состояние (56) помещается в стек, текущим становится состояние 34 (заносится на вершину стека). Предварительно просмотренная лексема очищается.




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



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