Реферат: Проектирование трансляторов

                                         ряемый фрагмент>;

   и праворекурсивные вида

   <имя нетерминала>: <многократно повторяемый фрагмент>

                      <имя нетерминала>;

     YACC допускает оба вида рекурсивных правил, однако, при  ис-

пользовании правил с правой рекурсией об'ем анализатора  увеличи-

вается, а во время разбора возможно переполнение внутреннего сте-

ка анализатора.

     Рекурсивные правила необходимы при задании последовательнос-

тей и списков. Следующие примеры иллюстрируют универсальный  спо-

соб описания этих конструкций:

     последовательность: элемент

                         | последовательность элемент;

     список: элемент | список ',' элемент;

     Заметим, что в каждом из этих случаев первое правило (не со-

держащее рекурсии) будет применено только для первого элемента, а

второе (рекурсивное) - для всех последующих. Нетерминальные  сим-

волы, связанные с последовательностями или  списками  разнородных

элементов, могут описываться произвольным  числом  рекурсивных  и

нерекурсивных правил. Например, группа правил

   идентификатор: буква  |

                  '$'    |

                  идентификатор буква |

                  идентификатор цифра |

                  идентификатор '_' ;

     описывает идентификатор как последовательность букв, цифр  и

символов "_", начинающуюся с буквы или символа "$". Следует обра-

тить внимание на то, что рекурсивные правила не имеют смысла, ес-

ли для определяемого ими нетерминала не задано ни одного  правила

без рекурсии. Для обеспечения возможности задания пустых  списков

или последовательностей в  качестве  нерекурсивного  правила  ис-

пользуется пустое:

   последовательность : | последовательность элемент ;

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

собом представления грамматик и ведет к большей их общности,  од-

нако,некорректное использование пустых правил может вызывать кон-

фликтные ситуации (раздел 5) из-за неоднозначности выбора  нетер-

минала, соответствующего пустой последовательности.

     Секция деклараций состоит из последовательности  строк  двух

видов: строк-директив и строк исходного текста.

     Строки исходного текста без изменений копируются в  выходной

файл y.tab.c и могут содержать операторы препроцессора  и  описа-

ние внешних об'ектов. Область действия  переменных,  описанных  в

секции  деклараций,  распространяется  на  весь  спецификационный

файл, т.е. они доступны как в операторах действий, так и в проце-

дурах, находящихся в секции программ.

     Строки-директивы начинаются символом "%" (этот символ в YACC

играет роль своего рода esc-символа). Две  специальные  директивы

%{ и %} ограничивают с двух сторон группы строк исходного текста.

Остальные директивы служат для задания дополнительной  информации

о грамматике.

                     ДЕКЛАРАЦИЯ ИМЕН ЛЕКСЕМ

     %token <список имен лексем>

     Пользователь при описании грамматики решает, какие конструк-

ции целесообразнее непосредственно выделять из входного текста на

этапе лексического анализа, и на уровне этих конструкций (лексем)

задает грамматические правила. Все виды лексем, кроме  литералов,

обозначаются некоторыми именами и под этими именами фигурируют  в

секции правил.  Благодаря  декларации  имен  лексем  в  директиве

%token YACC отличает имена лексем от имен  нетерминальных  симво-

лов. Однако, декларация ни в коей мере не обеспечивает  распозна-

вания лексем, и пользователю рекомендуется считать для  себя  ди-

рективу %token напоминанием о необходимости построения  лексичес-

кого анализатора и руководствоваться этой директивой при его  на-

писании.

     Заметим, что ключевые слова описываемого входного языка час-

то бывает удобно считать лексемами. Имена лексем могут  совпадать

с этими ключевыми словами, недопустимым является лишь  совпадение

имен лексем с зарезервированными словами языка Си.

         ДЕКЛАРАЦИЯ ПРИОРИТЕТОВ И АССОЦИАТИВНОСТИ ЛЕКСЕМ

    %left <список лексем>

    %right <список лексем>

    %nonassos <список лексем>

     Лексемы в данных директивах задаются литералами или именами.

В последнем случае декларация приоритета заменяет также  деклара-

цию имени лексемы, хотя в целях обеспечения наглядности  описания

является желательным присутствие в списке директивы %token  всего

набора имен лексем.

     Использование лексемы само по себе  не  требует  задания  ее

приоритета или ассоциативности.

     При вызове YACC с флагом -d последовательность операторов

#define помещается также в информационный файл y.tab.h.

     Переопределив  при  необходимости  ряд  номеров  типов  лек-

сем,пользователь должен проверить уникальность номеров у всех ис-

пользуемых лексем.

               ДЕКЛАРАЦИЯ ИМЕНИ НАЧАЛЬНОГО СИМВОЛА

     %start <имя начального символа>

     Директива отменяет действующий по умолчанию выбор  в  качес-

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

тическим правилом.

     Секция программ-процедуры, которые должны  быть  включены  в

генерируемую программу грамматического анализа. Любая из  опреде-

ляемых пользователем программных  компонент  может  находиться  в

секции программ спецификационного файла, либо  присоединяться  на

этапе вызова Си-компилятора для трансляции файла y.tab.c и компо-

новки выходной программы. Перечислим процедуры, которые одним  из

этих способов должны быть заданы:

     - лексический анализатор - функция с именем yylex();

     - все процедуры, вызовы которых содержатся в действиях, свя-

занных с грамматическими правилами;

     - главная процедура main()  при  необходимости  заменить  ее

стандартный библиотечный вариант, который имеет вид:

     main() { return (yyparse(); }

     - процедура обработки ошибок yyerror() -  также  для  замены

библиотечного варианта (его текст приводится ниже).

     #include <stdio.h>

     yyerror(s)char *s; { fprintf(stderr, "%s0, s);}

     Для обеспечения корректной работы грамматического анализато-

ра функция лексического анализа yylex должна быть  согласована  с

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

требованиям. Основная задача функции yylex состоит  во  вводе  из

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

соответствующей одной из лексем, и возвращении номера  типа  этой

лексемы. Для нелитеральных  лексем  номером  типа  может  служить

об'явленное в секции деклараций имя лексемы (с помощью  механизма

#define YACC обеспечивает замену его нужным  номером),  в  случае

литералов номером типа является числовое значение  символа  (если

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

попытке нахождения сначала более сложных (нелитеральных) лексем и

лишь при несовпадении ни с одной из них текущих  элементов  ввода

возвращать номер типа литеральной лексемы (любой однозначный сим-

вол, не начинающий ни одну из возможных лексем, сам образует лек-

сему).

     Действия с использованием  псевдопеременных.Для  обеспечения

связи между действиями, а также между  действиями  и  лексическим

анализатором создаваемые YACC грамматические анализаторы  поддер-

живают специальный стек, в котором сохраняются значения лексем  и

нетерминальных символов. Значение лексемы автоматически  попадает

в стек после ее распознавания лексическим анализатором (напомним,

что им считается текущее значение переменной yylval). После  каж-

дой свертки вычисляется значение нетерминала, заместившего  свер-

нутую строку, и помещается в вершину  стека;  значения  элементов

правой части примененного правила  перед  этим  выталкиваются  из

стека. Заметим, что таким образом к моменту свертки любого прави-

ла все значения нетериналов в правой части оказываются  вычислен-

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

ла будет рассмотрен ниже.

     Описанный механизм не требует вмешательства  пользователя  и

предоставляет ему следующие возможности:

     - Использовать в действиях, осуществляемых после свертки  по

правилу, значение любого элемента его правой части. Доступ к этим

значениям обеспечивается набором так называемых  ПСЕВДОПЕРЕМЕННЫХ

с именами $1,$2,..., где $i соответствует значению i-го элемента;

элементы правой части правила нумеруются слева направо без разли-

чия лексем и нетерминальных символов;

     - Формировать в  действиях  значение,  образованного  в  ре-

зультате свертки  нетерминала  путем  присвоения  этого  значения

псевдопеременной с именем $$. Eсли  в  действии  не  определяется

значение переменной $$ (а также если действие отсутствует),  зна-

чением нетерминала после свертки по умолчанию  становится  значе-

ние первого элемента правой части, т.е. неявно выполняется  прис-

ваивание.

     Несколько иная ситуация в отношении использования  псевдопе-

ременных имеет место для правил, содержащих действия внутри  пра-

вой части. На самом деле YACC интерпретирует правило вида

     A: B C {действие 1} D {действие 2} K

 как

     A: B C EMPTY1 D EMPTY2 K;

     EMPTY1: {действие 1}

     EMPTY2: {действие 2}

     и в точке, где вставлено действие, при разборе осуществляет-

ся свертка по пустому правилу, сопровождающаяся выполнением  ука-

занного действия. При этом независимо от характера действия  оче-

редной элемент в стеке значений отводится для  хранения  значения

неявно присутствующего "пустого" нетерминала. В действии, находя-

щемся в конце правила, соглашение  о  значениях  псевдопеременных

остается прежним, если иметь в виду наличие дополнительных симво-

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

ниям элементов B, C, D, K следовало бы использовать соответствен-

но псевдопеременные $1, $2, $4, $6; псевдоперемнные $3,  $5  хра-

нят результаты действий 1 и 2. В  действиях,  находящихся  внутри

правила, с помощью псевдоперемнных $i доступны значения  располо-

женных левее элементов, а также результаты предшествующих  встав-

ленных в тело действий. Результатом  внутреннего  действия  (т.е.

значением неявного нетерминалА) является значение, присвоенное  в

этом действии псевдопеременной $$, при отсутствии такого присваи-

вания результат действия не определен. Заметим, что  присваивание

значения псевдопеременной $$ во внутренних действиях не  вызывает

предварительной установки значения нетерминала, стоящего в  левой

части правила: это значение в любом случае устанавливется  только

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

                            ЛЕКЦИЯ 11

                     СЕМАНТИЧЕСКИЕ ПРОГРАММЫ

     Генерация какого─либо промежуточного  кода  большей  частью

осуществляется одновременно с  синтаксическим  анализом.  С  этой

целью включаются действия, вызов которых обеспечивает  не  только

генерацию кода, но и построение таблиц символов, обращение к  ним

и т.д. Свяжем с каждым правилом грамматики семантическую програм-

му, которая должна выполнять соответствующую семантическую  обра-

ботку, когда связанное с ней правило вызывает синтаксическую  ре-

дукцию. Рассмотрим как осуществить перевод арифметического  выра-

жения с данными правилами в различные внутренние формы:

     Правила грамматики:

     Z ::= E

     E ::= T|E+T|E─T|─T

     T ::= F|T*F|T|F

     F ::= I|(E)

     1. Перевод инфиксной записи в польскую. Всякий раз, когда  в

сентециальной форме найдена основа Х, редуцируемая к  нетерминалу

U, синтаксический распознаватель вызывает программу, связанную  с

правилами U ::= X.

     Программа осуществляет обработку символов в Х  и  выдает  ту

часть польской цепочки, которая имеет непосредственное  отношение

к Х. Так как : (1) основа редуцируется при каждой редукции,то (2)

если в основе встречается нетерминал V, то часть польской  цепоч-

ки, включающая подцепочку, которая приводится к V, уже была  сге-

нерирована.

     Считаем, что генерируемая польская цепочка хранится  в  од─

номерном  массиве Р.  Пусть р ─ содержит адрес первого свободно─

го элемента Р (Рнач=1). Вызванная программа имеет доступ к симво-

лам основы s(1),...,s(i), находящимся в синтаксическом стеке рас-

познавателя.

           Программа, связанная с правилом Е1 ::= Е2+Т

     В момент ее вызова согласно (2) массив Р содержит

             ...<код для Е2><код для Т>,

     т.к. сначала генерируется код для Е (основа ─ самая левая

простая фраза), потом для Т. Справа от Т только терминалы.

     Очевидно данная программа должна поместить знак +  в  поль─

скую  цепочку.  При этом Е2+Т переводится в запись Е2 Т +.  Следо─

вательно семантическая программа имеет вид Р(р):="+";р:=р+1.

      Программа для правила F ::= I (I─любой идентификатор)

     По правилам польской  записи  (ЛК10)  идентификаторы  пред─

шествуют своим операторам и идут в том же порядке, что и в инфик-

сной записи. То есть необходимо лишь занести идентификатор в Р.

     Р(р) := s(i); р:=р+1   s(i)─верхний символ стека

     Для правила F ::= (E) действия не включаются, т.к. скобок в

польской записи нет,  а для Е польская запись  уже  сгенерирова─

на. Аналогично рассуждая получим:

         правило               семантическая программа

     (1) Z ::= T                        нет

     (2) E ::= T                        нет

     (3) E ::= E+T                  P(p):='+';p:=p+1

     (4) E ::= E─T                  P(p):='─';p:=p+1

     (5) E ::= ─T                   P(p):='@';p:=p+1

     (6) T ::= F                        нет

     (7) T ::= T*F                  P(p):='*';p:=p+1

     (8) T ::= T/F                  P(p):='/';p:=p+1

     (9) F ::= I                    P(p):=s(i);p:=p+1

     (10)F ::= (E)                      нет

     Очевидно для  правил  3,4,7,8  можно иметь одну программу:

                     P(p):=s(i─1); p:=p+1

     2.Преобразование инфиксной записи в тетрады

     Будем генерировать теперь для А*(В+С) тетрады:

                  +В,С,Т1

                  *А,Т1,Т2

     Первую тетраду  попытаемся  сгенерировать при редукции по прави─

лу Е ::= Е+Т.  К этому моменту синтаксическое дерево будет иметь

вид (а).

                                      Е,Т1

         Е                             │

         │                          ┌──┴──┐

    T    T   T                      │     │

    │    │   │                     E,B    │

    F    F   F                      │     │

    │    │   │              T,A    T,B   T,C

    A * (B + C)              │      │     │

                            F,A    F,B   F,C

       (a)                   │      │     │        (б)

                             A *  ( B  +  C )

     На следущем шаге приведения Е+Т к Е семантическая  программа

должна выдать тетраду, однако  сентенциальная  форма  {Т*(Е+Т)}не

содержит информации об именах Е и Т. При получении польской

записи имена В и С заносились в выходную цепочку при  выполне─

нии редукций F ::= B и F ::= C.

     Очевидно, что нам также необходимо в момент редукций F ::=I где─то запомнить информацию об именах редуцируемых

идентификаторов до момента их использования. Заметим, что ска─

нер для каждого идентификатора выдает пары вида (I,B),(I,C),.., причем символ I связан с синтаксической инфор─

мацией, В или С (имя) ─ с семантикой символа.

     Привяжем к каждому нетерминалу U (узлу  дерева)  семанти─

ческую информацию U.SEM.  Кроме того, будем генерировать имена

Т1,Т2,.. для обозначения  подвыражений,  используя  для  этого

счетчик i.  В начале i=0. Операция генерации нового идентифика─

тора и его привязка к U имеет вид

           i:=i+1; U.SEM:=Ti

     Для генерации тетрады используем процедуру  с  4  палитрами:

     ENTER(W,X,Y,Z). Тогда получим:

    правило             семантическая программа

  (1) Z ::= Е               Z.SEM:=E.SEM

  (2) E ::= T               E.SEM:=T.SEM

  (3) E1 ::= E2+T           i:=i+1  E1.SEM:=Ti

                            ENTER('+',E2.SEM,T.SEM,E1.SEM)

  (4) E1 ::= E2─T           i:=i+1  E1.SEM:=Ti

                            ENTER('─',E2.SEM,T.SEM,E1.SEM)

  (5) E ::= ─T              i:=i+1  E.SEM:=Ti   P(p):='@';p:=p+1

                            ENTER('@',0,T.SEM,E.SEM)

  (6) T ::= F               T.SEM:=F.SEM

  (7) T ::= T*F

  (8) T ::= T/F

  (9) F ::= I

  (10)F ::= (E)             F.SEM:=E.SEM

    Реализация семантических программ и семантических стеков

     Для привязки  семантических  атрибутов  к  нетерминалам  ис-

пользуются семантические стеки для  каждого  атрибута  (или  один

стек с отдельными полями для хранения синтаксического  символа  и

его семантических атрибутов). Эти стеки должны  хранить  семанти-

ческую информацию, которая связана с нетерминалами,  входящими  в

текущую сентенциальную форму. Эти стеки  работают  параллельно  с

синтаксическим стеком S (т.е. удаление и занесение в них  синхро-

низировано). Семантическая программа имеет доступ ко всем стекам.

          ┌───┬────────┬──────┬───────┬────┐

          │ E │        │ REAL │       │ 20 │

          ├───┼────────┼──────┼───────┼────┤

          │ + │        │      │       │    │

          ├───┼────────┼──────┼───────┼────┤

          │ T │        │ INT  │       │ 40 │

          ├───┼────────┼──────┼───────┼────┤

          │ . │        │  .   │       │ .  │

          │ . │        │  .   │       │ .  │

          │ . │        │  .   │       │ .  │

          └───┴────────┴──────┴───────┴────┘

     В действительности не имеет значения,  сколько  используется

стеков.

         Рассмотрим несколько алгоритмов семантической  обработки

для языка типа АЛГОЛ.

     1.Условные инструкции

     <инстр1>::=<условие><инстр2>ELSE<инстр3>│<условие><инстр2>

     <условие>::=IF<выраж>THEN,

     где <выраж> должно иметь тип BOOLEAN.

     Необходимо сгенерировать тетрады одного из двух  видов:  (1)

  тетрады для Т::=<выраж> (1)  тетрады  для  Т::=<выраж>  (p)  BZ

  q+1,T,0 (p) BZ q,T,0

  <инстр2>                       <инстр2>

  (q) BR r                       (q)

  (q+1) <инстр3>

  (r)

     Программа  генерации  (Р)тетрады   связана    с    правилом:

     <условие>::=IF<выраж>THEN и имеет следующий вид:

     (1) Р:=<выраж>,ENTRY;─занести в Р адрес элемента TS для <выфаж>

     (2) CHECKTYPE(P,BOOLEAN); ─проверить, что тип <выраж> BOOLEAN

     (3) <условие>,JUMP:=NEXTQUAD;  ─запомнить номер следущей тетрады

     (4) ENTER(BZ,0,P,0);           ─генерация BZ─тетрады

     Общее правило для доступа к семантическим стекам: Если осно-

ва х рассматриваемой сентенциальной формы должна быть приведена с

помощью правила U::=x к U, то для работы  с  семантикой  символов

используется программа, которая:

     1) заносит информацию в TS или проверяет ее;

     2) проверяет семантическую информацию, связанную с х;

     3) генерирует тетрады;

     4) связывает семантическую информацию с U;

     Для обращения в стеки за семантической информацией SEM, свя-

занной с U,  применяем обозначение U.SEM.  1.I.NAME ─ указатель,

используется для доступа к имени идентификатора

     2.<пер>ENTRY ─  выдает  указатель на элемент таблицы символов для переменной <пер>

     3.<выр>ENTRY ─  указатель на значение (уже выполненного) выражения <выр>

     4.<условие>JUMP ─ содержит номер BZ тетрады, в которую позднее надо добавить адрес перехода,  который еще не известен

     Следущая редукция будет связана с правилом:  <инстр1>::=<ус-

ловие><инстр2> I:=<условие>.JUMP Занести номер  следущей  тетрады

во вторую QU- AD(I,2):=NEXTQUAD компоненту тетрады с  помощью  I,

т.е. получить (BZq+1,p,0)

     Операнды во внутренней форме будем представлять указателем Р

на соответствующий элемент таблицы символов. Ссылка на его  атри-

бут будет иметь вид: Р.TYPE,P.TYPE1.  Очевидно,  если  инструкция

содержит ELSE, то между <инстр2> и <инстр3> нужно  как  бы  вста-

вить команду BR. Но при таком синтаксисе конструкция  <инстр1>  с

ELSE будет распознана лишь после  разбора  <инстр2>  и  <инстр3>.

Т.е. будет специфицирована цепочка команд для <инстр2> и <инстр3>.

     Преобразуем синтаксис в соответствии с желаемой  семантикой:

     <инстр1>::=<ист.часть><инстр3>

     <ист.часть>::=<условие><инстр2>ELSE

     <ист.часть>::=<условие><инстр2>ELSE

     <ист.часть>.JUMP:=NEXTQUAD; ─ запомнить номер следущей тетрады

     ENTER(BR,0,0,0);              в стеке

     I:=<условие>.JUMP;        ─ занести в BZ переход через <инстр1>

     QUAD(I,2):=NEXTQUAD;

        <инстр1>::=<ист.часть><инстр3>

I:=<ист.часть>.JUMP;      - вставить адрес перехода через

QUAD(I,2):=NEXTQUAD;        <инстр2> в (BR...)

Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16