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

       

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


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

.

      Z

      |

      E

      |

      T

      -------------

      T     *     F

      |           --------

      F           (   E   )

                    -----

                    E + T

                    |   |

                    T   F

                    |



                    F

В данном дереве необходимо выполнить свертку по самому левому правилу T::=F в цепочке. Правая часть такого правила называется ОСНОВОЙ. Таким образом, основа - это полная правая часть первого правила при просмотре цепочки слева направо. Найденная в цепочке основа должна быть заменена на нетерминал из левой части соответствующего правила. Для более полного понимания принципа приведем последовательность основ цепочек при выполнении такого процесса свертки.

.

      F * (F + F)

      ---

      T * (F + F)

          ---

      T * (T + F)

          ---

      T * (E + F)

              ---

      T * (E + T)

           -----

       T * (E)

           ---

      T * F

      -----

        T

       ---

        E

       ---

        Z

       ---

Способ нахождения основы цепочки реализован в методе восходящего разбора "свертка-перенос":

В процессе анализа используется магазинный автомат (КА со стеком);

На каждом шаге работы автомата сравнивается пара символов - текущий символ входной цепочки (I) и текущий символ в стеке (М). По результату сравнения возможны два действия:

Перенос терминального символа из строки в стек: PUSH((I), NEXT(I) - в соответствии с принятыми для МА обозначениями.

Свертка правой части правила, которое в данный момент находится в стеке.
T:T/F","T:F","F:i","F:c","F:(E)",NULL };

char      TS[]= "+-*/()ic#" ;

char      NTS[]= "+-*/()ic#FTEZ" ;

char      s[100];      int      ns;

char      m[100];      int      sp;

Двумерный массив определяет действия МА на каждую пару сочетаний символа в стеке и во входной цепочке: 0 - ошибка, 1-перенос, 2-свертка, 3-успешный разбор.

int      TBL[14][10]={

/*             + - * / ( ) i c # err */

/* + */      { 0,0,0,0,1,0,1,1,0,0 },

/* - */      { 0,0,0,0,1,0,1,1,0,0 },

/* * */      { 0,0,0,0,1,0,1,1,0,0 },

/* / */      { 0,0,0,0,1,0,1,1,0,0 },

/* ( */      { 0,0,0,0,1,0,1,1,0,0 },

/* ) */      { 2,2,2,2,0,2,0,0,2,0 },

/* i */      { 2,2,2,2,0,2,0,0,2,0 },

/* c */      { 2,2,2,2,0,2,0,0,2,0 },

/* # */      { 0,0,0,0,1,0,1,1,0,0 },

/* F */      { 2,2,2,2,0,2,0,0,2,0 },

/* T */      { 2,2,1,1,0,2,0,0,2,0 },

/* E */      { 1,1,0,0,0,1,0,0,2,0 },

/* Z */      { 0,0,0,0,0,0,0,0,3,0 },

/*err*/      { 0,0,0,0,0,0,0,0,0,0 },

      };

Вспомогательная функция STS определяет номер символа в строке терминальных символов или всех символов грамматики

int      STS(char c,char T[]) {. . .}

Функция main буквально повторяет приведенный выше алгоритм разбора. Для каждой пары символов в строке и в вершине стека вызывает действие, определенное для них в таблице.

void      main()

{ int      i,j,stop;

printf("Строка:"); gets(s); strcat(s,"#");

ns=0; sp=0; m[0]='#'; m[1]='\0';

nts=strlen(TS); stop=0;

while(!stop)

      { i=TBL[ STS(m[sp],NTS) ][ STS(s[ns],TS) ];

      switch (i) {

case  1:  sp++; m[sp]=s[ns];      m[sp+1]='\0';

          ns++; break;            // Перенос

case  2:  if (TESTGR()==0)      // Свертка

          stop++; break;

case  3:  stop++; break;

default:  stop++; break;

          }}}

Функция TESTGR реализует самый общий принцип свертки: она просматривает список правил  и ищет первое из них, которое содержит в вершине стека свою правую часть, после чего заменяет его на левую.


То есть последовательность расположения правил с одинаковой правой частью в списке может влиять на правильность синтаксического разбора. А именно: если есть два правило с одинаковым окончанием правой части, то более длинное должно находиться в начале списка.

int      TESTGR()

{ char *ss,*q; int      n,j;

for (n=0; GR[n] !=NULL; n++)      // Поиск правила

      { for (q=ss=GR[n]+2; *ss !='\0'; ss++);

      ss--;

      for(j=sp; (ss>=q) && (m[j]==*ss); j--,ss--);

      if (q== ss+1)                  // Свертка

            { j++; sp=j; m[sp]=*GR[n];

m[sp+1]='\0'; return(1); }

      }

return (0);}

4. Семантический анализ

Семантический анализ является наименее формализуемой частью процесса трансляции,  поскольку касается “смысла” тех конструкций языка, которые анализируются на этапах лексического и синтаксического анализа. Если же подходить к этому процессу с точки зрения “здравого смысла”, то транслятор должен построить в процессе трансляции в памяти некоторую структуру данных, в которой зафиксировать все смысловые (семантические) взаимоотношения между объектами программы. Обычно объектами программы являются типы, переменные и функции (процедуры), которые обозначаются именами (идентификаторами). Для них уже на этапе лексического анализа может быть составлена таблица, которая на этапе семантического анализа дополняется данными о семантике объектов. Отсюда вырисовывается общая схема взаимодействия фаз транслятора:

-   Обычно транслятор создает несколько  семантических таблиц, по видам используемых в языке объектов, поскольку содержание их может быть в принципе различным. Например, в Си-компиляторе имеет смысл заводить таблицы типов, локальных и глобальных переменных, функций. Таблицы эти заполняются семантическими процедурами при свертывании соответствующих правил. Например, при свертывании определения переменной ее имя должно заноситься в таблицу локальных или глобальных имен;

-   на этапе лексического анализа при обнаружении очередного идентификатора его значение (строка символов, имя) либо непосредственно сопровождает распознанную лексему, либо помещается в таблицу со ссылкой на нее в той же лексеме.


В обоих случаях  значение лексемы (имя) сопровождает ее на этапе синтаксического анализа, где лексема выступает как терминальный символ и передается далее фазе семантического анализа.

-   в процессе синтаксического анализа, при “свертывании” правила, в котором в качестве терминалов фигурируют имена, вызывается семантическая процедура, соответствующая этому правилу. Она должна получить ссылки на эти имена из соответствующих лексем;

-   семантическая процедура по ссылкам на имена  определяет, является ли операция, заданная правилом, допустимой для семантики этих имен. Кроме того, семантическая процедура может создать новые записи в таблицах, изменить их содержание, произвести поиск и т.д.. Поскольку любое правило при свертывании приводится  к нетерминалу, стоящему в левой части, а он, в свою очередь, включается в другие, вышележащие правила, то семантическая процедура должна поставить ему в соответствие также некоторую семантику (смысл). Это делается также путем возвращения ссылки на элемент таблицы.

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

-   элементы семантических таблиц в свою очередь могут быть связаны с некоторыми динамическими структурами данных, которые отражают внутреннюю семантику хранимых объектов. Это могут быть списки, массивы, деревья. В целом образуется некоторая семантическая сеть, по структуре которой семантические процедуры и производят анализ тех или иных частей программы.


Содержание раздела