Курс Основы построения трансляторов


Восходящие методы анализа. Свертка-перенос - часть 2


Возможны два принципиально различных варианта свертки: правило единственное, либо возможен выбор одного из нескольких.

Для формального задания поведения МА необходимо задать таблицу его действий на полный абор сочетаний - входной терминальный символ и любой символ в стеке. В клетке таблицы могут быть указаны следующие действия:

Сообщение о синтаксической ошибке;

Сообщение об успешном завершении разбора;

Перенос символа из входной цепочки в стек;

Вызов процедуры для анализа правой части правила в стеке и замены ее на нетерминал.

Для грамматики арифметических выражений со скобками приведем пример такой таблицы.

.

       +-      */     (      )      F      #

+-     -       -      П      -      П      -

*/     -       -      П      -      П      -

(      -       -      П      -      П      -

)      С3      С3     С3     С3     С3     С3

F      С1      С1     -      С1     -      С1

T      С2      П      -      С2     -      С2

E      П       -      -      П      -      С4

#      -       -      П      -      П      +

.

# - начало/конец цепочки

Процедуры свертки правил:

С1 -> T::= T*F | T/F | F

C2 -> E::= E+T | E-T | T

C3 -> F::=(E)

С4 -> POP(M)

 

Как видно, для простых грамматик построение такой таблицы не выходит за рамки здравого смысла. Для каждой пары символов производится анализ ситуации (контекста цепочки), в которой она может встретиться, на основании чего и заполняется клетка таблицы. Если ситуация свидетельствует, что не вся правая часть правила в стеке, то необходимо сделать перенос, если вся - анализировать возможные правила. Заготовка программы, выполняющей синтаксический анализ для данной грамматики по методу "свертка-перенос" находится в файле lowtohigh.cpp.

 

Грамматика языка задана массивом указателей на строки - правила. Строками заданы множества терминальных символов грамматики (TS) и всех символов грамматики (NTS). Определены также стек и входная строка.

 

char      *GR[]={"Z:E","E:E+T","E:E-T","E:T","T:T*F","




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



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