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

     /* error transitions */

          {unput(*--yylastch);break;}

     /* state  =  YYU(yyt  ->  advance )+yysvec - по таблице

пеpеходов пеpейти в новое состояние автомата

     *lsp++ = state -  сохpанить  в  стеке  состояний  новое

состояние */

           *lsp++ = yystate = YYU(yyt->advance)+yysvec;

     /* Пеpейти к ШАГУ 2 */

                      goto contin;

                      }

/***********************************************************

     ШАГ 9.  Если возможен пеpеход по алтеpнативе,  то  аль-

теpнативное  состояние  сделать текущим и пеpейти к ШАГУ 4 в

пpотивном случае пеpейти к ШАГУ 10.

***********************************************************/

     /* yystate = yystate -> yyoter - сделать состояние аль-

теpнативы текущим состоянием

     yyt = yystate -> yystoff - плучить новый адpес  таблицы

смещений

     if ( state ) - если сушествует альтеpнативное состояние

        то

         if ( yyt != yycrank) - если из этого состояния

                             существует пpямой пеpеход */

       if ((yystate = yystate->yyother) && (yyt =

            yystate->yystoff) != yycrank){

     /* Пеpейти к ШАГУ 4 */

                             goto tryagain;

                             }

 #endif

                      else

                             {unput(*--yylastch);break;}

               contin:

                      }

     /* Конец обpаботки входного потока  и  начало  пpовеpки

что это за лекскма */

/***********************************************************

     ШАГ 10. Веpнуть последний введенный символ в устpойство

ввода.

     ШАГ 11.  Если достигнуто начальное состояние, то пpейти

к ШАГУ 13 в пpотивном случае пеpейти к шагу 12.

***********************************************************/

               while (lsp-- > yylstate){

     /* Удалить из yytext последний смвол и поставить  пpиз-

нак конец стpоки */

                      *yylastch-- = 0;

/***********************************************************

     ШАГ 12.  Если в текущее состояние пpинадлежит множеству

возможных конечных состояний,  то в таблице конечных состоя-

ний узнать номеp pаспознанной лексемы и закончить выполнение

алгоpитма. В пpотивном случае пеpейти в пpедыдущее состояние

и пеpейти к ШАГУ 10.

     ШАГ 13. Закончить выполнение алгоpитма и выдать состоя-

ние ошибки.

***********************************************************/

     /* Если  номеp  текущего состояния в стеке состояний не

нулевой и текущее состояние пpимнадлежит множеству  конечных

состояний, то есть (*lsp)->yystop > 0 */

   if (*lsp != 0 && (yyfnd= (*lsp)->yystops) && *yyfnd > 0){

     /* Сохpанить значения в глобальных пеpеменных */

                             yyolsp = lsp;

                             yyprevious = YYU(*yylastch);

                             yylsp = lsp;

                             yyleng = yylastch-yytext+1;

     /*   Установить пpизнак конца стpоки в yytext   */

                             yytext[yyleng] = 0;

     /* Возвpатить номеp pаспознанной лексемы */

                             return(*yyfnd++);

                             }

     /* если  лексема не pаспознана,  то веpнуть символ вов-

ходной поток */

                      unput(*yylastch);

                      }

     /* если достигнут конец файла, то веpнуть 0 */

               if (yytext[0] == 0  /* && feof(yyin) */)

                      {

                      yysptr=yysbuf;

                      return(0);

                      }

               yyprevious = yytext[0] = input();

               if (yyprevious>0)

                      output(yyprevious);

               yylastch=yytext;

               }

        }

                            ЛЕКЦИЯ 10

          КРАТКИЕ СВЕДЕНИЯ О ГЕНЕРАТОРЕ СИНТАКСИЧЕСКИХ

                        АНАЛИЗАТОРОВ YACC

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

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

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

чах, где пользователю при задании входной  информации  предостав-

ляется относительная свобода (в отношении сочетания и  последова-

тельности структурных элементов), синтаксический анализ достаточ-

но сложен. При решении подобных задач существенную поддержку  мо-

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

таксических (грамматических) анализаторов на основе заданных све-

дений о синтаксической структуре входной информации.  YACC  отно-

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

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

     Поскольку обширной областью, где наиболее явно видна необхо-

димость  (нетривиального)  грамматического  анализа,  а  следова-

тельно и его автоматизации, является область создания  транслято-

ров (в частности, компиляторов), программы, подобные YACC,  полу-

чили еще название компиляторов (или генераторов) компиляторов.

     Заметим, что понятие транслятора может относиться не  только

к языкам программирования, но и к командным языкам, входным  язы-

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

процессами и т.п.

     Пользователь YACC должен описать структуру своей входной ин-

формации (ГРАММАТИКУ) как набор ПРАВИЛ в виде, близком к  Бэкусо-

во-Науровской форме (БНФ). Каждое правило описывает  грамматичес-

кую конструкцию, называемую НЕТЕРМИНАЛЬНЫМ СИМВО- ЛОМ,  и  сопос-

тавляет ей имя. С точки зрения  грамматического  разбора  правила

рассматриваются как правила вывода (подстановки).  Грамматические

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

которые называются лексическими единицами, или ЛЕКСЕМАМИ.  Имеет-

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

употреблять в грамматических правилах имя лексемы.  Как  правило,

имена сопоставляются лексемам, соответствующим классам  об'ектов,

конкретное значение которых не существенно для целей грамматичес-

кого анализа. (Иногда в литературе с понятием  лексемы  совпадает

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

минальными символами отдельные символы стандартного набора). При-

мерами имен лексем могут служить "ИДЕНТИФИ- КАТОР" и  "ЧИСЛО",  а

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

си идентификаторов и чисел. В некоторых случаях имена лексем слу-

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

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

за, определяемой пользователем.  Пользователь  же  предварительно

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

вать непосредственно, и в соответствии  с  этим  об'являет  имена

лексем.  Пользовательская  программа  лексического   анализа    -

ЛЕКСИЧЕСКИЙ АНАЛИЗАТОР - осуществляет чтение реальной входной ин-

формации и передает грамматическому анализатору распознанные лек-

семы.

     Как уже отмечалось, YACC  обеспечивает  автоматическое  пос-

троение лишь процедуры грамматического анализа. Однако,  действия

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

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

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

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

струкций семантических про-

цедур (ДЕЙСТВИЙ) с тем, чтобы они были включены в программу грам-

матического разбора. В зависимости от характера  пользовательских

семантических  процедур  (интерпретация  распознанного  фрагмента

входного текста, генерация фрагмента об'ектного кода,  отметка  в

справочной таблице или форматирование вершины в  дереве  разбора)

генерируемая с помощью YACC программа  будет  обеспечивать  кроме

анализа тот или иной вид обработки входного текста, в  частности,

его компиляцию или интерпретацию.

     Итак,  пользователь  YACC  подготавливает  общее    описание

(СПЕЦИФИКАЦИИ) обработки  входного  потока,  включающее  правила,

описывающие входные конструкции, кодовую часть, к которой  должно

быть организовано обращение при обнаружении этих  конструкций,  и

программу  ввода   базовых    элементов    потока    (лексический

анализатор). Kомпилятор компиляторов обеспечивает  создание  под-

программы (грамматического  анализатора),  реализующей  процедуру

обработки входного потока в соответствии с  заданными  специфика-

циями.

     К компонентам компилятора компиляторов  относятся  выполняе-

мый файл yacc, библиотека стандартных программ /lib/liby.a,  Файл

/usr/lib/yaccpar. Заключительная фаза построения компилятора тре-

бует применения компилятора языка Си.

                      ПРИНЦИПЫ РАБОТЫ YACC

     Грамматические анализаторы, создаваемые с помощью YACC, реа-

лизуют так называемый LALR(1)-разбор, являющийся модификацией од-

ного из основных методов разбора "снизу  вверх"  -  LR(k)-разбора

(буквы L(eft) и R(ight) в  обоих  сокращениях  означают  соответ-

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

правостороннего вывода. Индекс в скобках показывает число предва-

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

     Любой разбор по принципу "снизу вверх" (или восходящий  раз-

бор) состоит в попытке приведения всей совокупности входных  дан-

ных (входной цепочки) к так называемому "начальному символу грам-

матики" путем последовательного применения правил вывода.

     В каждый момент грамматического разбора анализатор  находит-

ся в некотором СОСТОЯНИИ, определяемом предысторией разбора, и  в

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

ствие для перехода к новому состоянию. Различают  два  типа  дей-

ствий:  "СДВИГ",  т.е.  чтение  следующей  входной  лексемы,    и

"СВЕРТКУ", т.е. применение одного из правил подстановки для заме-

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

правой части правила. Работа YACC по генерации процедуры  грамма-

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

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

следующего состояния в соответствии с каждой из входных лексем.

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

ствами. В этом смысле YACC предполагает контекстносвободные грам-

матики со свойствами LALR(1). LALR(1)- грамматики,  являясь  под-

множеством LR(1)-грамматик, допускают при построении таблиц  раз-

бора сокращение общего числа состояний за счет об'единения  иден-

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

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

из правил вывода, если разбор по  этому  правилу  проходил  через

данное состояние). Другие грамматики являются неоднозначными  для

принятого в YACC метода разбора и вызовут конфликты.

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

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

разбора, то YACC позволяет без перестройки  грамматики  построить

грамматический анализатор, разрешающий конфликты на основе  меха-

низма приоритетов.

               ВХОДНЫЕ И ВЫХОДНЫЕ ФАЙЛЫ, СТРУКТУРА

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

     Входная информация  для  YACC  задается  в  СПЕЦИФИКАЦИОННОМ

ФАЙЛЕ. На выходе компилятора компиляторов в результате  обработки

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

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

y.tab.c является процедура yyparse, реализующая алгоритм  грамма-

тического разбора.  При  формировании  ее  YACC  использует  файл

/usr/lib/yaccpar, содержащий неизменяемую часть анализатора. Кро-

ме yyparse, в файл y.tab.c YACC включает построенные  им  таблицы

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

фикаций.

     Процедура yyparse представляет собой целочисленную  функцию,

возвращающую значение 0 или 1. Значение 0 возвращается  в  случае

успешного разбора по достижении признака конца файла, значение 1-

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

Процедура yyparse содержит  многократное  обращение  к  процедуре

лексического анализа yylex, текст которой либо переносится в файл

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

ледствии.

     Для организации обращения к процедуре yyparse  в  библиотеке

YACC существует стандартная процедура main, не содержащая  помимо

обращения к yyparse никаких действий.  Пользователь  может  напи-

сать собственную процедуру main, включив в нее как начальные дей-

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

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

завершении разбора, которым должен предшествовать анализ  возвра-

щаемого yyparse значения; действиями в случае  успешного  разбора

могут быть закрытие файлов, вывод  результатов,  вызов  следующей

фазы транслятора, в частности, повторный вызов yyparse. Для заме-

ны стандартной процедуры  пользовательской  программой  main  она

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

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

     Кроме выходного файла y.tab.c, YACC может дополнительно гене-

рировать следующие выходные файлы:

     y.output содержащий описание состояний анализатора и сообще-

ния о конфликтах;

     y.tab.h содержащий описание лексем.

     Для генерации этих файлов требуется задание  соответствующих

флагов при вызове YACC.

        ПРОЦЕДУРА ПОСТРОЕНИЯ ГРАММАТИЧЕСКОГО АНАЛИЗАТОРА

     Построение грамматического анализатора осуществляется в  два

этапа. На первом этапе файл спецификаций входного языка обрабаты-

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

дная строка yacc [-vd] yfile. Здесь yfile - имя файла  специфика-

ций, а флаги имеют следующий смысл:  v  -  сформировать  в  файле

y.output подробное  описание  грамматического  анализатора;  d  -

сформировать в файле y.tab.h описание лексем.

      Текстовые файлы y.output и y.tab.h содержат справочную  ин-

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

пе построения грамматического анализатора. Основной результат ра-

боты YACC - процедура yyparse и грамматические  таблицы  -  поме-

щается в файл y.tab.c. На втором этапе построения  грамматическо-

го анализатора для получения в файле a.out исполняемой  программы

компилируется файл y.tab.c и  присоединяются  другие  программные

компоненты:

         cc y.tab.c [cfile...ofile...lfile...] -ly

     где cfile, ofile,lfile - имена исходных, объектных и библио-

течных файлов, содержащих присоединяемые процедуры. В  этот  спи-

сок не включается имя стандартной библиотеки YACC /lib/liby.a, ее

подключение обеспечивается заданием флага ly. Этот  флаг  полезно

считать обязательным.

                 ЗАДАНИЕ ВХОДНОЙ ИНФОРМАЦИИ YACC

     Структура спецификационного файла

     Пользовательские спецификации, задающие правила  организации

входной информации и алгоритм ее обработки, об'единяются в специ-

фикационный файл следующей структуры:

     декларации

     %%

     правила

     %%

     программы

     Ядром спецификационного  файла  и  единственной  его  обяза-

тельной частью является  секция  правил.  При  отсутсивии  секции

программ может быть опущена вторая  группа  "%%";  следовательно,

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

   %%

   правила

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

допустимо лишь появление их в именах.  Комментарий,  ограниченный

символами "/*" в начале и "*/" в конце,  может  находиться  между

любыми двумя разделителями в любой секции входного файла.

     СЕКЦИЯ ПРАВИЛ состоит из одного или нескольких  грамматичес-

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

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

обработке входного потока.

     Назначение СЕКЦИИ ДЕКЛАРАЦИИ состоит в  основном  в  задании

информации о лексемах.

     СЕКЦИЯ ПРОГРАММ представляет собой некоторый набор  процедур

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

тического разбора. Например, это могут быть процедура лексическо-

го анализа yylex и пользовательские процедуры, вызываемые в  дей-

ствиях.

     СЕКЦИЯ ПРАВИЛ. В данной секции с помощью набора грамматичес-

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

впоследствии будут строиться входные тексты. Не подлежат  опреде-

лению в секции правил лишь конструкЦии, выбранные пользователем в

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

ми единицами. Правила задаются в форме, близкой БНФ.

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

дается таким образом: <имя нетерминального символа>: определение;

здесь ':' и ';' специальные символы YACC. Правая часть правила  -

определение  -  представляет  собой   упорядоченную    последова-

тельность элементов (нетерминальных символов и  лексем),  состав-

ляющих описываемую конструкцию. При грамматическом разборе  такая

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

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

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

именами или литералами. Запись имен и литералов совпадает  с  за-

писью идентификаторов и символьных констант, принятой в Си.

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

семам или нетерминальным символам. YACC считает именами  нетерми-

налов все имена, не объявленные в секции деклараций именами  лек-

сем. Все нетерминалы должны быть определены, т.е. имя каждого  из

них должно появиться в левой части хотя бы одного правила. Допус-

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

символ, т.е. правил с одинаковой левой частью. Такие правила  оп-

ределяют конструкции, идентичные на некотором уровне.

     Правила с общей левой частью можно  задавать  в  сокращенной

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

альтернативных определений символ "|".

     При необходимости с любым правилом можно связать действие  -

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

распознавании конструкции во входном тексте. Действие не  являет-

ся обязательным элементом правил.

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

правой частью правила, т.е. правило с действием имеет вид:

     <имя нетерминального символа>: определение {действие};

     Точка с запятой после правила с действием может  опускаться.

При использовании сокращенной записи правил с общей левой  частью

следует иметь в виду, что действие может относиться только к  от-

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

трирует задание действий в случае правил с общей левой частью.

     На операторы, входящие в действия, не накладывается  никаких

ограничений. В частности, в действиях  могут  содержаться  вызовы

любых функций. Отдельные операторы могут  быть  помечены,  к  ним

возможен переход из других действий.

     Существует возможность задания действий, которые  будут  вы-

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

Действие в этом случае помещается после одного из элементов  пра-

вой части так, чтобы положение  действия  соотвествовало  моменту

разбора, в который данному действию будет передано управление.

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

вило, должны использовать некоторые общие переменные,

т.е.  переменные, доступные во всех действиях и сохраняющие  свои

значения по окончании очередного действия. Такие переменные  опи-

сываются в начале секции правил, все  описание  ограничивается  с

двух сторон строками

       %{

          и %}

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

сматриваемые как общие действия для всех правил.

     Укажем еще на два вида объектов, использующихся в действиях.

Это, во-первых, глобальные переменные, которые описываются в сек-

ции деклараций , и, во-вторых, специальные переменные  (псевдопе-

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

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

ся в наборе правил иерархически,  т.е.  каждое  правило  соответ-

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

ледовательность задания правил может не отражать этой иерархии  и

быть вполне произвольной. Единственно необходимой  для  YACC  яв-

ляется информация о том, какой из нетерминалов задает вершину ие-

рархии,  т.е. соотвествует  конструкциям,  определяющим   входной

текст  в  целом.  Этот  нетерминал  принято  называть   НАЧАЛЬНЫМ

СИМВОЛОМ. Приведение входного текста к начальному символу являет-

ся целью грамматического анализатора. По умолчанию  YACC  считает

начальным символом тот нетерминал, имя  которого  стоит  в  левой

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

вол в первом правиле пользователю неудобно, он может явно  задать

имя начального символа в секции деклараций.

     Существует два специфических вида правил, на которые  полез-

но обратить внимание. Во-первых, это пустое правило вида

              <имя нетерминального символа>: ;

     определяющее пустую последовательность  символов.  Сочетание

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

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

тельность вхождения соответствующей конструкции. Например,  сово-

купность правил

     целое_число:знак целое_без_знака; знак: | '+'|'-';

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

него. Другой способ описать эту  возможность  состоит  в  задании

следующей группы правил:

   целое_число:знак целое_без_знака  |  целое_без_знака  ;  знак:

   '+'|'-';

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

ствие:

     ИМЯ: {тело_действия} ;

     Во-вторых, правила часто описывают некоторую конструкцию ре-

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

мый нетерминальный символ. Различают леворекурсивные правила вида:

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

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