Синтаксически управляемая трансляция на основе атрибутных грамматик

Программирование Технология и методы программирования Спортивное программирование Теория трансляторов Синтаксически управляемая трансляция на основе атрибутных грамматик

Помечено: ,

  • В этой теме 0 ответов, 1 участник, последнее обновление 1 неделя, 1 день назад сделано Васильев Владимир Сергеевич.
Просмотр 0 веток ответов
  • Автор
    Сообщения
    • #6305
      @admin

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

      В зависимости от направления последовательности вычисления атрибутов, приписанных символам правила КС-грамматики, различают синтезируемые и наследуемые атрибуты. Синтезируемым является атрибут, приписанный символу левой части правила и вычисляемый по известным атрибутам символов правой части правила КС-грамматики. Наследуемым является атрибут, приписанный какому-либо символу правой части правила и вычисляемый по известным атрибутам символов, стоящих в правиле левее него, в том числе – символа левой части правила КС-грамматики. Так, например, для правила грамматики

      A ::= B C D

      символу A можно приписать синтезируемый атрибут As, который будет вычисляться как функция атрибутов символов B, C и D:

      $$A_s = f(B_b, C_c, D_d)$$

      Индекс s будем использовать в обозначениях синтезируемых (synthesized) атрибутов, а в обозначениях наследуемых (inherited) – индекс i. Для атрибутов символов B, C и D выбраны произвольные обозначения, так как при записи функции для As не делалось никаких предположений о способах их вычисления. В соответствии с этим же правилом для B, C и D могут быть определены только наследуемые атрибуты:

      $$
      B_i = g(A_a), \\
      C_i = h(A_a, B_b), \\
      D_i = q(A_a, B_b, C_c ).
      $$

      Обобщение КС-грамматики, в котором с каждым грамматическим правилом связано множество атрибутов, называется синтаксически управляемым определением.

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

      Практическую реализацию вычисления атрибутов рассмотрим на примере языка строк круглых скобок, расставленных в соответствии с правилами их расстановки в арифметических выражениях: количества открывающих и закрывающих скобок должны быть равны, а при просмотре строки слева направо количество закрывающих скобок не должно превышать количества открывающих. Пусть в процессе синтаксического анализа строки скобок требуется решить задачу определения длины префикса этой строки, состоящего только из открывающих скобок. Или, в терминологии обсуждаемой темы, требуется организовать подсчёт длины префикса строки скобок, состоящего только из открывающих скобок, под управлением синтаксического анализа этой строки. Формально эта длина и должна рассматриваться как результат трансляции строки скобок, сколь бы странным это ни казалось. Так, для строки ( ( ( ) ( ) ) ) ( ) результатом трансляции должно быть число 3, а для строки ( ( ) ) ) ( трансляция не может быть выполнена, поскольку эта строка синтаксически неверна.

      Наиболее удобочитаемым вариантом грамматики для такого языка можно считать следующий:

      $$A ::= ( ) | ( A ) | A A.$$

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

      $$
      A ::= ( )\hspace{10mm} \{ A_s = 1 \} \\
      A ::= ( A )\hspace{10mm} \{ A_s = 1 + A_a \} \\
      A ::= A A\hspace{10mm} \{ A_s = A_{a1} \}
      $$

      , где Aa1 – атрибут первого символа A из двух, стоящих в правой части правила. Атрибут левой части правила в этом случае равен атрибуту первого символа A, поскольку любая подстановка вместо этого символа приведёт к появлению хотя бы одной закрывающей скобки перед вторым символом A, и атрибут второго символа A, таким образом, не сможет повлиять на длину префикса из открывающих скобок.

      Однако такая грамматика не годится для построения синтаксических анализаторов детерминированного типа, и по этой причине далее будем пользоваться другим описанием синтаксиса того же языка скобок:

      A ::= T Z
      Z ::= T Z
      Z ::= Λ
      T ::= ( A )
      T ::= ( )

      Аксиомой здесь является символ A, а символ Λ является условным обозначением пустой строки.

      Вычисления синтезируемых атрибутов в этом варианте грамматики аналогичны предыдущим:
      $$
      A ::= T Z\hspace{10mm} \{ A_s = T_t \} \\
      Z ::= T Z\hspace{10mm} \{ Z_s = T_t \} \\
      Z ::= Λ\hspace{10mm} \{ Z_s = 0 \} \\
      T ::= ( A )\hspace{10mm} \{ T_s = 1 + A_a \} \\
      T ::= ( )\hspace{10mm} \{ T_s = 1 \}
      $$

      Для вычислений атрибутов в первых двух правилах справедливо то же замечание, что и для вычисления в последнем правиле первого варианта грамматики: синтезируемый атрибут левой части правила не зависит от атрибута символа Z и равен атрибуту символа T, поскольку любая подстановка вместо символа T помещает, как минимум, одну закрывающую скобку перед символом Z. Строго говоря, вычисление синтезируемого атрибута для символа Z в рассматриваемой задаче не имеет смысла; он не влияет на значение атрибута аксиомы, что нетрудно проследить по приведённым формулам вычислений атрибутов.

      Синтаксически управляемая трансляция как вычисление синтезируемых атрибутов

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

      Текущая Сентенциальная форма  Применяемое правило грамматики  Атрибуты символов правой части правила  Синтезируемый атрибут левой части правила
      ( ( ( ) ( ) ) ) ( )  T ::= ( )  — — 1
       ( ( T ( ) ) ) ( ) T ::= ( )  — — 
       ( ( T T ) ) ( ) Z ::= Λ  0
       ( ( T T Z ) ) ( ) Z ::= T Z  1 0 1
       ( ( T Z ) ) ( )  A ::= T Z  1 1  1
       ( ( A ) ) ( )  T ::= ( A )  — 1 — 2
       ( T ) ( ) Z ::= Λ   — 0
       ( T Z ) ( )  A ::= T Z 2 0 2
       ( A ) ( ) T ::= ( A )   — 2 — 3
       T ( ) T ::= ( )   — — 1
       T T  Z ::= Λ 0
      T T Z Z ::= T Z 1 0 1
      T Z A ::= T Z 3 1 3
      A      

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

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

      Текущая Сентенциальная форма  Применяемое правило грамматики  Атрибуты символов правой части правила  Синтезируемый атрибут левой части правила
      ( ( ) ) ) ( T ::= ( )  — — 1
      ( T ) ) ( Z ::= Λ 0
      ( T Z ) ) ( A ::= T Z 1 0 1
      ( A ) ) ( T ::= ( A ) — 1 — 2
      T ) (      

      К полученной форме, казалось бы, ещё можно применить правило Z ::= Λ, а затем к получившейся T Z ) ( – правило A ::= T Z, в результате чего форма приобретёт вид: A ) ( , и к ней уже невозможно применить ни одно из правил грамматики (Z ::= Λ – не в счёт), поскольку никакая из её подстрок не является правой частью никакого из этих правил. Но о том, что эти два преобразования бесполезны, нетрудно догадаться по присутствию в форме T ) ( закрывающей скобки без предшествующих открывающих. Строго говоря, ни одна из форм, записанных в столбце «Текущая сентенциальная форма» таблицы, не является сентенциальной, поскольку в конечном итоге не сворачивается в аксиому. Но алгоритму восходящего разбора об этом становится известно, как минимум, только на 5-м шаге работы, который и становится заключительным с выводом об ошибочности исходной строки.

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

      В таблице используются обозначения внутренних состояний автомата-анализатора числами 1 – 9. Состояние 1 считается начальным. В командах, изображённых целыми числами, указаны состояния соответствующих переходов автомата. Команды, представленные правилами грамматики, предписывают замены в сентенциальных формах правых частей правил на соответствующие левые. Пустые ячейки таблицы считаются содержащими команду «ошибка». Следуя указаниям такой таблицы, детерминированный автомат всегда знает, какое единственно правильное действие должно быть выполнено на каждом шаге его работы: это указание выбирается из таблицы по текущему внутреннему состоянию автомата (координата строки таблицы) и текущему сканируемому символу сентенциальной формы (координата столбца таблицы). Так, например, нетрудно видеть, что сканируя префикс исходной строки, состоящий только из открывающих скобок, автомат будет оставаться во внутреннем состоянии 6. Как только такой префикс закончится, т.е. будет обнаружена первая закрывающая скобка, следует применить правило T ::= ( ), т.к. закрывающая скобка инициирует переход автомата из состояния 6 в состояние 9, а 9-я строка таблицы предписывает выполнение команды T ::= ( ). В соответствии с этим правилом обнаруженная пара скобок заменяется в сентенциальной форме нетерминальным символом T, как это и показано в таблицах.

      Восходящий разбор, сопровождаемый вычислением синтезируемых атрибутов, удобно реализуется с помощью утилиты Bison. Её интерфейс предлагает специальные обозначения для переменных, содержащих значения синтезируемых атрибутов: $$ – для атрибута нетерминала левой части правила и $n – для атрибутов символов правой части правила (n – номер позиции символа в правой части правила). При этом атрибуты терминальных символов считаются синтезируемыми на этапе лексического анализа, а наличие доступа к ним через переменные $n обеспечивается нахождением их в yylval. Если тип значений атрибутов отличен от int, его следует указать в директиве %union и упомянуть имя этого типа в директиве %token перед перечнем символьных обозначений токенов. Например, если атрибутами должны быть строки, то соответствующие директивы могут быть такими: %union{char *string;} и %token<string> Omega. Подчеркнём, что описание string относится только к типу атрибута; токен, представленный символьным обозначением Omega, должен быть целочисленным.

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

      %{
      #include <iostream>
      #include <string>
      
      using namespace std;
      
      void yyerror(char const* msg);
      
      int yylex();
      int yyparse();
      %}
      
      %%
      A:T Z {$$=$1;cout<<$$<<'\n';} // As = Tt и вывод атрибута As , связанного с аксиомой
      ;
      Z:{$$=0;}                     // Z s = 0
      |
      T Z {$$=$1;}                  // Zs = Tt
      ; 
      T:'('A')' {$$=$2+1;}          // Ts = Aa + 1
      | 
      '('')' {$$=1;} // Ts = 1
      
      ;
      %%
      void yyerror(char const* msg) {
        cerr << msg << endl;
      }
      
      // ввод символов исходного текста
      int yylex() {
        
        char c;
        cin >> c;
        return c;
      }
      
      int main() {
        if (yyparse() != 0) {
          // вывод результатов синтаксического анализа
          cout << "Syntax error " << endl;
        } 
        else {
          cout << "Success" << endl;
        }
      }

      Синтаксически управляемая нисходящая трансляция как вычисление наследуемых и синтезируемых атрибутов

      При решении задачи синтаксического анализа нисходящим алгоритмом трансляция может быть выполнена в виде схемы вычислений наследуемых и синтезируемых атрибутов. Применение правила грамматики в процессе нисходящего разбора означает замену в текущей сентенциальной форме нетерминального символа левой части этого правила на правую часть этого правила. При этом символы правой части правила могут получить «в наследство» информацию из атрибутов символа левой части правила, если таковая на данный момент имеется. Иными словами, для символов правой части правила могут быть вычислены наследуемые атрибуты. Причём при распространении этого наследства по символам правой части правила в направлении слева направо оно «обогащается» информацией вычисляемых атрибутов. Так символ, занимающий крайнюю правую позицию, получает максимум информации для вычисления наследуемого атрибута: значения атрибутов символа левой части правила и всех символов правой части правила, расположенных левее него. По окончании всех вычислений для символов правой части правила появляется возможность пополнить информацию о нетерминальном символе левой части правила путём вычисления для него синтезируемого атрибута.

      Рассмотрим эту схему на примере того же языка скобок, предварительно преобразовав грамматику к виду, удобному нисходящему разбору:

      $$
      A ::= T Z \hspace{10mm} \{ T_i = A_a ; A_s = T_t \} \\
      Z ::= T Z \\
      Z ::= Λ \\
      T ::= ( Y \hspace{10mm} \{ Y_i = T_t + 1 ; T_s = Y_y \} \\
      Y ::= A ) \hspace{10mm} \{ A_i = Y_y ; Y_s = A_a \} \\
      Y ::= ) \hspace{10mm} \{ Y_s = Y_i \}
      $$

      Аксиомой здесь, по-прежнему, является символ A. Обозначения
      $$A_a, T_t, Y_y$$
      относятся к атрибутам соответствующих нетерминальных символов, значения которых были вычислены по наследуемой и синтезируемой информации и известны на момент применения формулы. Впрочем, в описаниях вычислений синтезируемых атрибутов индексы в этих обозначениях могут быть заменены на индекс s, поскольку к моментам использования значений этих атрибутов полностью завершаются построения выводов из соответствующих нетерминалов и, следовательно, эти атрибуты относятся к синтезируемым. То же можно сказать и о вычислениях атрибутов, наследуемых символами от своих соседей слева в правых частях правил (такой ситуации нет в рассматриваемой грамматике, поскольку символ Z в части правила T Z, по-прежнему, не участвует в вычислении итогового результата). В вычислениях же атрибутов, наследуемых от символов левых частей правил, индексы в вышеупомянутых обозначениях заменены индексом i, т.к. у символа левой части правила в этот момент разбора имеется только наследуемая информация, синтезируемая будет вычислена позже, когда будет обработана вся правая часть этого правила.

      Следует заметить, что с точки зрения последовательности действий синтаксического разбора и вычислений атрибутов приведённая схема не вполне корректна, поскольку описания всех вычислений, относящихся к правилу грамматики, собраны в единые фигурные скобки. С учётом того, что наследуемые атрибуты вычисляются до синтаксического разбора нетерминального символа, а синтезируемые – после него, схему имеет смысл переписать в следующем виде:
      $$
      \textbf{A ::=} \{ T_i = A_i \} \hspace{10mm} \textbf{T Z} \hspace{10mm} \{ A_s = T_s \} \\
      \textbf{Z ::=} \{ T_i = 0 \} \hspace{10mm} \textbf{T Z} \\
      \textbf{Z ::=} \hspace{10mm} \textbf{Λ} \\
      \textbf{T ::=} ( \{ Y_i = T_i + 1 \} \hspace{10mm} \textbf{Y} \hspace{10mm} \{ T_s = Y_s \} \\
      \textbf{Y ::=} \{ A_i = Y_i \} \hspace{10mm} \textbf{A )} \hspace{10mm} \{Y_s = A_s \} \\
      \textbf{Y ::=} \hspace{10mm} \textbf{)} \hspace{10mm} \{ Y_s = Y_i \}
      $$

      Для примера разбора нисходящим алгоритмом возьмём всё ту же строку ( ( ( ) ( ) ) ) ( ). Её левый (полученный заменами самых левых нетерминалов на каждом шаге) вывод выглядит так:

      A => T Z => ( Y Z => ( A ) Z => ( T Z ) Z => ( ( Y Z ) Z => ( ( A ) Z ) Z => ( ( T Z ) Z ) Z => ( ( ( Y Z ) Z ) Z =>
      => ( ( ( ) Z ) Z ) Z => ( ( ( ) T Z ) Z ) Z => ( ( ( ) ( Y Z ) Z ) Z => ( ( ( ) ( Y Z ) Z ) Z => ( ( ( ) ( ) Z ) Z ) Z =>
      => ( ( ( ) ( ) ) Z ) Z => ( ( ( ) ( ) ) ) Z => ( ( ( ) ( ) ) ) T Z => ( ( ( ) ( ) ) ) ( Y Z => ( ( ( ) ( ) ) ) ( ) Z => ( ( ( ) ( ) ) ) ( )

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

      Правила грамматики в этой схеме указаны явно и размещены так, что символ левой части правила занимает ту же вертикаль, какую он же занимает в вышестоящей строке, где он должен быть заменён на правую часть этого правила. Так в первых двух строках схемы символы T размещены по одной вертикали, поскольку именно этот символ в форме T Z подлежит замене на ( Y, правую часть его правила. Слева от правил в фигурных скобках выписаны значения наследуемых атрибутов. Значения синтезируемых атрибутов выписаны справа от правил и также заключены в фигурные скобки.

      Перед началом нисходящего разбора с аксиомой грамматики, символом A, следует связать значение атрибута, которое могло бы быть передано в качестве «наследства» при первой подстановке вместо A. Очевидно, что таким значением должен быть 0, поскольку в момент первой подстановки ничего неизвестно об искомой длине префикса открывающих скобок. Во второй строке схемы этот факт указан в виде { Ti = 0 }, что соответствует получению наследуемого атрибута, равного 0, символом T,занимающим первую позицию в применяемом правиле A ::= T Z. В дальнейшем применению каждого правила предшествует вычисление наследуемого атрибута для левой части этого правила в соответствии с указаниями синтаксически управляемого определения. Так, например, перед применением правила Y ::= A ) (третья строка схемы) вычисляется наследуемый атрибут для Y, который этот символ получил «в наследство» от символа T (вторая строка схемы). Вычисление выполняется в соответствии с указанием синтаксически управляемого определения { Yi = Ti + 1 } и с учётом того, что в текущий момент Ti = 0. По завершении разбора правой части какого-либо правила и, следовательно, по завершении вычисления атрибутов всех символов правой части этого правила появляется возможность вычисления синтезируемого атрибута для символа левой части правила. Простейшим примером такого вычисления является последняя строка схемы с правилом Y ::= ). С единственным символом правой части этого правила не связаны никакие атрибуты, а синтезируемый атрибут символа Y, в соответствии с указанием синтаксически управляемого определения { Ys = Yi }, совпадает с его наследуемым атрибутом, равным в текущий момент разбора единице. В схеме это указано так: { Ys = 1 }. Впрочем, эти вычисления, приведённые в последних двух строках схемы, никак не влияют на значение синтезируемого атрибута аксиомы, поскольку они относятся к разбору правой части правила для символа Z, атрибуты которого, как это уже неоднократно отмечалось, не могут участвовать в вычислении итогового результата, а потому и не вычисляются вовсе. Итоговый результат представлен в первой строке схемы синтезируемым атрибутом аксиомы: { As = 3 }. Такое его размещение объясняется тем, что он связан с левой частью первого применяемого правила, символом A. Однако вычисление этого атрибута происходит на последнем шаге алгоритма разбора, после того, как полностью разобрана правая часть этого правила, A ::= T Z. Вычисления синтезируемых атрибутов, можно сказать, происходят в направлении снизу вверх по схеме.

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

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

      Одна из программных реализаций нисходящего разбора, использующего свойство LL(1) грамматики, известна под названием: «Метод рекурсивного спуска». Структура такой программы фактически повторяет структуру грамматики, описывая каждый нетерминальный символ грамматики программной компонентой – функцией. Содержание такой функции – изображение средствами языка программирования соответствующей правой части правила грамматики, т.е. последовательность вызовов функций нетерминальных символов, находящихся в правой части правила. Терминальные символы правой части правила проверяются на совпадение с текущими сканируемыми символами анализируемой строки (своеобразная реализация исполнения команды «выброс», упомянутой в LL(1)-таблице). Разветвление на несколько правил грамматики внутри функции выполняется по одному терминальному символу, который является текущим сканируе- мым в анализируемой строке (это и позволяет считать метод реализацией LL(1)-разбора).

      Реализация нисходящего разбора методом рекурсивного спуска для рассматриваемого примера LL(1)-грамматики может быть следующей.

      #include <iostream>
      
      #define AP_left_KW 56
      #define AP_right_KW 57
      #define AP_end_KW 58
      
      using namespace std;
      
      int number;
      int symbol;
      
      int A(int);
      int yylex() {
      // ввод символов исходного текста
        char s;
        cin>>s;
        switch (s) {
          case '(': return AP_left_KW;
          case ')': return AP_right_KW;
          case '$': return AP_end_KW;
          default : return -1;
        }
      }
      
      int Y(int inherited){
        int synthesized;
        switch (symbol){
          case AP_left_KW:{
            if ((synthesized=A(inherited)) == -1) { 
              return -1; // Y ::= { Ai = Yi } A )
            }
            else if(symbol==AP_right_KW) {
              return synthesized; // {Ys = As }
            }
            else {
              return -1;
            }
          }
          case AP_right_KW: {
            symbol = yylex();  //Y ::= )
            return inherited;  // { Ys = Yi }
          }
          default: return -1;
        }
      }
      
      int T(int inherited){
        symbol=yylex();
        return Y(inherited+1); // T ::= ( { Yi = Ti + 1 } Y { Ts = Ys }
      }
      
      int Z() {
        switch (symbol) {
          case AP_left_KW: 
            T(0); 
            return Z(); // Z ::= { Ti = 0 } T Z
          case AP_right_KW: 
            return 0; // Z ::= Λ
          case AP_end_KW: 
            return 0; // Z ::= Λ
          default: return -1;
        }
      }
      
      int A(int inherited) {
        if(symbol==AP_left_KW) {
          int synthesized=T(inherited); // A ::= { Ti = Ai } T Z
          Z();
          return synthesized; // { As = Ts }
        }
        else 
          return -1;
      }
      
      int main() {
        symbol=yylex();
        int y=A(0);
        //A - аксиома
        // анализ результата трансляции:
        if (y<0)
          cout<<"error\n";
        else 
          cout<<"prefix length "<< y << '\n';
      }

      Терминальные символы грамматики в программе обозначены идентификаторами вида AP_X_KW в предположении, что значения этих идентификаторов формируются и возвращаются функцией int yylex() лексического анализа. Поле X заполнено в идентификаторах терминалов словами left, right или end для, соответственно, открывающей скобки, закрывающей скобки или маркера конца строки. Для работы функций синтаксического анализа текущий терминальный символ помещается в переменную symbol.

      Наследуемый атрибут нетерминала передаётся внутрь соответствующей функции через её параметр, а синтезируемый атрибут возвращается функцией оператором return. При обнаружении синтаксической ошибки функции возвращают -1.

      Так, например, функция int T(int inherited) сконструирована в соответствии с правилом

      $$
      \textbf{T ::= (} \hspace{10mm} \{ Y_i = T_i + 1 \}\hspace{10mm} \textbf{Y} \hspace{10mm} \{ T_s = Y_s \}.
      $$

      Терминальный префикс '(' правой части правила проверяется функциями A и Z непосредственно перед вызовом функции T. Поэтому дополнительную проверку наличия этого символа в анализируемой строке функция T может не выполнять, а может сразу же выполнить перемещение по этой строке к следующему справа символу. Такое перемещение выполняется посредством вызова функции yylex.Следующий символ Y правой части правила предписывает выполнение вызова функции int Y(int inherited). При этом правило { Yi = Ti + 1 } вычисления наследуемого атрибута указывает на то, что аргумент функции Y должен быть на 1 больше аргумента функции T, а правило { Ts = Ys } вычисления синтезируемого атрибута – на то, что значение, возвращаемое функцией T, должно совпадать со значением, возвращаемым функцией Y. Таким образом, этот фрагмент правой части правила атрибутной грамматики в тексте программы может быть описан единственным оператором:

      return Y(inherited+1).

      Явного возвращения -1 в функции T не предусмотрено, поскольку, как уже было сказано, внутри нее не анализируется текущий терминальный символ. Тем не менее, функция T может возвратить -1 посредством функции Y.

Просмотр 0 веток ответов
  • Для ответа в этой теме необходимо авторизоваться.