Реферат: Разработка конвертора из текстового формата nroff в гипертекстовый формат HTML

               [^abc]

       удовлетворяет всем символам, кроме a,b и с, включая все специальные и управляющие символы, а

               [^a-zA-Z]

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

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

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

               [40-176]

       удовлетворяет всем печатаемым символам кода ASCII, от восьмеричного 40 (пробел) до 176 (черта сверху).

Задание вариантов.

       Знак вопроса означает вариант в регулярном выражении. Например

               ab?c

       удовлетворяет либо ab или abc.

Указание повторений.

       Повторяющиеся классы указываются операторами * и +. Например,

     a*

       удовлетворяет любому количеству (включая 0) последовательно идущих символов a, в то время, как

    a+

       удовлетворяет одному или нескольким символам. Например,

               [a-z]+

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

               [A-Za-z][A-Za-z0-9]*

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

Альтернативы и группирование.

       Вертикальная черта указывает альтернативы. Например,

               (ab|cd)

       удовлетворяет либо ab либо cd. Для группирования применяются скобки, хотя на верхнем уровне они не обязательны. Например

               ab| cd

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

               (ab|cd+)?(ef)*

       удовлетворяет таким строкам, как abefef, efefef, cdef и cddd, но не abc, abcd или abcdef.

Чувствительность к контексту.

       Lex распознает ограниченный объем окружающего контекста. Два простейших оператора - ^ и $. Если первым символом выражения указан ^, оно будет удовлетворяться при расположении в начале строки (после символа перевода строки или в начале входного потока). Такой смысл не противоречит значению этого символа при задании классов, так как в этом случае он указывается внутри квадратных скобок. Если последним символом выражения служит $, выражение будет удовлетворяться при нахождении в конце строки. Последний оператор - частный случай более общего оператора /, задающего правый контекст. Выражение

               ab/cd

       удовлетворяет строке ab только в том случае, если за ней следует cd.  Таким образом

               ab$

       аналогично

               ab/\n

Задание повторяющихся выражений.

       Фигурные скобки задают либо повторение (если внутри цифры), либо определение подстановки (если внутри имя). Например

               {digit}

       ищет заранее определенную строку с именем digit и вставляет ее в заданной точке.  А выражение

               a{1,5}

       ищет от одного до пяти вхождений символа a.

Задание определений.

       Определения помещаются в первой части спецификации перед правилами и завершаются символом процента.

Задание действий.

       Если выражение удовлетворяет некоторому фрагменту вводимого текста, lex выполняет соответствующее действие. В этом разделе описываются некоторые особенности, помогающие при написании действий.  Существует действие по умолчанию, заключающееся в копировании входного потока в выходной. Копированию подвергаются строки, не удовлетворившие правилам. Таким образом, для поглощения всего входного потока нужно задать выражение, удовлетворяющее всем символам. При использовании lex совместно с yacc это считается нормальной ситуацией. Вы можете рассматривать копирование как некоторое действие, которое можно не указывать.

       Одно из простейших действий - игнорирование входного потока. Это выполняется с помощью пустого оператора Си (;).

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

         Иногда правила некорректно распознают символы на границах входного потока. Для этой ситуации удобны две функции. Yymore() указывает, что следующее входное выражение должно помещаться в конец только что найденного. Обычно следующее выражение затирает текущее содержимое yytext.  Yyless(n) вызывается тогда, когда в данный момент нужны не все символы, удовлетворившие текущему правилу. Аргумент указывает количество символов, возвращаемых во входной поток. Это обеспечивает просмотр вперед, но в несколько иной форме, нежели при $.

Можно пользоваться и внутренними функциями ввода-вывода. К ним относятся:

         1.  input() следующий символ из потока;

         2.  output(c) вывод символа в поток;

         3.  unput(c) возврат символа в поток.

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

Lex не использует без надобности просмотр вперед, но к нему приводят правила, содержащие /, или заканчивающиеся на один из следующих символов:

               + * ? $

       Просмотр вперед также необходим при обработке выражения, служащего префиксом другого выражения.

Еще одна функция, которую иногда переопределяют, - yywrap. Она вызывается при достижении конца файла. Если она возвращает 1, выполняется нормальное завершение работы. Иногда бывает удобно организовать дополнительный ввод из другого источника. В этом случае пользователь пишет свою версию этой функции, которая выполняет новый ввод и возвращает 0. Это приводит к продолжению обработки. По умолчанию yywrap всегда возвращает 1.

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

Обработка неоднозначных правил.

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

          * Выбирается самая длинная последовательность.

          * Из всех подходящих правил выбирается первое.

Входной поток обычно разбивается на части так, что lex не ищет все возможные вхождения всех выражений. Каждый символ считается один и только один раз.

Иногда это неприемлемо. Действие REJECT означает переход к следующей альтернативе. Оно приводит к выполнению правила, которое было бы следующим. Позиция указателя во входном потоке устанавливается соответствующим образом. В общем случае, действие REJECT полезно, когда задачей служит не разбиение входного потока, а обнаружение всех вхождений некоторого выражения (иногда перекрывающихся) во входном потоке. REJECT не осуществляет повторного просмотра. Вместо этого запоминается результат предыдущего просмотра. Это означает, что если найдено правило с правым контекстом и выполнено действие REJECT, запрещается использовать unput для изменения символов, поступающих из входного потока. Это единственное ограничение, накладываемое на манипуляции еще не обработанной входной информацией.

Чувствительность к левому контексту.

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

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

         1.  Применение флагов (при изменении условий правила меняются незначительно).

         2.  Использование начальных состояний.

         3.  Использование нескольких лексических анализаторов, работающих одновременно.

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

Задание определений.

       Рассмотрим общий формат входной спецификации:

               {определения}

               %%

               {правила}

               %%

               {программы пользователя}

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

         Правила превращаются в программу. Любой фрагмент входной спецификации, не интерпретируемый lex, копируется в генерируемую программу. Эти фрагменты можно разделить на три класса:

         1.  Любая строка, не являющаяся частью правила или действия, и начинающаяся с пробела или табуляции, копируется в генерируемую программу. Если строки находятся перед первым символом %%, они будут внешними по отношению к любой функции. Если они находятся в разделе правил, они будут относиться к сгенерированной функции. Строки должны выглядеть как фрагменты программы и помещаться до начала описания правил.

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

         2.  Весь текст между символами %{ и %} также копируется. Ограничители отбрасываются. Этот формат позволяет вводить операторы препроцессора, начинающиеся в первой позиции, а также строки, мало напоминающие программный код.

         3.  Весь текст после третьего ограничителя %% копируется в генерируемую программу.

       Определения, предназначенные для lex, помещаются перед первым ограничителем %%. Любая строка этого раздела, не находящаяся внутри %{ %} и начинающаяся с позиции 1, считается строкой подстановки. Ее формат следующий:

               имя     подстановка

       Цепочкам из части подстановки присваивается имя. Имя и подстановка должны разделяться как минимум одним пробелом и имя должно начинаться с буквы. Подстановка вызывается в правиле с помощью конструкции {имя}.

Сгенерированные программы выполняют ввод-вывод символов только с помощью функций input(), output() и unput(). Используемое в этих функциях представление символов воспринимается lex и передается как возвращаемое значение в массиве yytext.  При внутреннем употреблении символ представлен небольшим целым числом, и при использовании стандартной библиотеки ввода-вывода его значение равно целому, соответствующему набору битов для этого символа в ЭВМ. Обычно символ a представлен так же, как и символьная константа:

               'a'

       Если это представление меняется с помощью функций ввода-вывода, выполняющих трансляцию, lex должен быть извещен об этом посредством таблицы трансляции.  Эта таблица должна находиться в разделе определений и ограничиваться строками, содержащими только %T.  Таблица содержит строки следующего формата:

               {целое} {символьная строка}

       Строки связывают с символом соответствующее значение.

Формат входного текста.

       Общий формат входного текста следующий:

               {определения}

               %%

               {правила}

               %%

               {подпрограммы пользователя}

       Раздел определений может содержать следующую информацию:

         1.  Определения в виде "имя пробел значение".

         2.  Включаемый фрагмент в виде "пробел фрагмент".

         3.  Включаемый фрагмент в виде

                     %{

                     фрагмент

                     %}

         4.  Начальные состояния в виде

                     %S имя1 имя2 имя3 ...

         5.  Таблицы наборов символов в виде

         %T

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

                 %T

         6.  Модификация размеров внутренних таблиц в виде

                     %x nnn

             где nnn - десятичное число, соответствующее размеру массива, а x - параметр следующего вида:

             Символ  Параметр

             p       позиции

             n       состояния

             e       узлы дерева

             a       переходы

             k       упакованные символьные классы

             o       размер выходного массива

       Строки в разделе правил имеют следующий формат:

               выражение       действие

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

       В регулярных выражениях допустимы следующие операторы:

       x       Символ x.

       x       Всегда x, даже если это оператор.

       \x      Всегда x, даже если это оператор

       [xy]    Символы x или y.

       [x-z]   СИмволы x, y или z.

       [^x}    Любой символ кроме x.

       .       Любой символ кроме перевода строки.

       ^x      Символ x в начале строки.

       <y>x    Символ x, если lex находится в состоянии <y>.

       x$      Символ x в конце строки.

       x?      Необязательный x.

       x*      0, 1, 2 ... вхождений x.

       x+      1, 2, 3 ... вхождений x.

       x|y     x или y.

       (x)     x.

       x/y     x за которым следует y.

       {xx}    Подстановка xx из раздела определений.

       x{m,n}  Число вхождений x - от m до n.

YACC.

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

Yacc(CP) представляет собой универсальный инструмент для описания входного потока программ. Это имя является сокращением фразы «yet another compiler compiler» («еще один компилятор компиляторов»). Пользователь задает как структуру входного потока, так и фрагменты программ, вызываемых при распознавании объектов в потоке. Компилятор компиляторов (или генератор программ синтаксического разбора, далее просто генератор) переводит спецификацию в некоторую подпрограмму, управляющую процессом ввода. Часто оказывается удобным осуществлять управление пользовательской задачей с помощью этой подпрограммы.

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

Генератор используется как для разработки компиляторов широко распространенных языков (языки Си, Паскаль и пр.), так и для нетрадиционных приложений (язык управления фотонаборной установкой, языки настольных калькуляторов, система доступа к документам, отладчик Фортрана).

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

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

Спецификации

 для синтаксического анализатора yacc.

К нетерминальным символам или лексемам обращаются по именам. Yacc требует непосредственного объявления имен лексем. В дополнение, по причинам, объясняемым ниже, часто желательно включение лексического анализатора как части файла спецификации. Может оказаться полезным и включения ряда других программ. Таким образом, любой файл спецификации состоит из трех частей: объявлений, правил и программ. Части (или разделы) разделяются двойным знаком процента (%%). (Символ процента часто применяется в спецификациях в виде специального символа.)

    Другими словами, полная спецификация может быть записана следующим образом:

               объявления

               %%

               правила

               %%

               программы

Раздел объявлений может быть пустым. Более того, если опускается раздел программ, то второй разделитель %% можно не указывать. Тогда минимальная спецификация выглядит как

               %%

               правила

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

    Раздел правил состоит из одного или более грамматических правил. Грамматическое правило записывается в формате

               A : BODY ;

A представляет собой нетерминальное имя, BODY - последовательность имен и литералов (возможно пустую).

         Имена могут быть произвольной длины и составляются из букв, точки, подчеркивания и цифр. Цифры в начале имени не допускаются. Прописные и строчные буквы считаются различными. Имена, используемые в теле грамматического правила, могут являться как лексемами, так и нетерминальными символами.

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

       \n    Перевод строки

       \r    Возврат каретки

       \'    Апостроф

       \     Обратная дробная черта

       \t    Табуляция

       \b    Шаг назад

       \f    Перевод формата

       \xxx  Восьмеричное число xxx

По ряду причин символ  NUL (ПУС, \0 или 0) никогда не должен использоваться в грамматических правилах.

    Если у нескольких правил одинаковая левая часть, во избежание ее повторения может применяться символ |. Точка с запятой в конце правила перед вертикальной чертой может опускаться. Таким образом, следующие правила:

               A:B C D;

               A:E F ;

               A:G ;

       могут быть записаны как:

               A:B C D;

               |E F

               |G;

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

Если нетерминальный символ соответствует пустой строке, можно  записать следующую конструкцию:

               empty:;

         Имена, представляющие лексемы, должны объявляться явно.  Это можно сделать в разделе объявлений:

               %token name1 name2 ...

Из всех нетерминальных символов один, называемый начальным, играет особую роль. Анализатор строится так, чтобы распознавать начальный символ; таким образом, он должен описывать самую большую, наиболее общую структуру, представляемую грамматическими правилами. По умолчанию, начальным символом считается левая часть первого грамматического правила в разделе правил. Возможно и желательно явно объявить начальный символ в разделе объявлений с помощью ключевого слова  %start:

         %start list

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

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

Действия.

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

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

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

       Для возврата значения действие обычно присваивает псевдопеременной $$ какое-либо значение. Например, действие, которое ничего не выполняет кроме возврата 1:

               {$$=1;}

       Для получения значений, возвращаемых предыдущими действиями и лексическим анализатором, действие может пользоваться псевдопеременными $1, $2, ..., которые соответствуют значениям, возвращаемым правой частью правила, слева направо. Тогда, если правило выглядит как

Страницы: 1, 2, 3, 4, 5, 6