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

Контекстно-зависимые и контекстно-независимые грамматики.

    Задача разработки транслятора соприкасается с дисциплиной, именуемой лингвистическое обеспечение САПР, некоторые положения которой мы и рассмотрим.

Прежде всего стоит отметить, что различают два основных типа грамматик: контекстно-зависимые и контекстно-независимые.

    Если порождающее правило имеет следующий вид:

             aAb ::= axb,

    то порождающее правило называется контекстно-зависимым, то есть замена нетерминального символа A на последовательность x может иметь место только в контекстах a и b. Соответственно, и грамматика, содержащая подобное правило, называется контекстно-зависимой.

    Если порождающее правило имеет вид:

         A ::= x, где A – нетерминальный символ, а x - терминальный или нетерминальный. То есть, если левая часть порождающего правила состоит из одного нетерминального символа, который в итоге (через ряд промежуточных шагов) может заменяться на последовательность x, стоящую в правой части, независимо от контекста, в котором этот нетерминальный символ встречается, то такое правило и, соответственно, грамматика называются контекстно-независимыми.

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

Контекстно-свободные грамматики.

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

    Слова из словаря языка играют роль терминальных символов (терминалов). Контекстно-свободная грамматика может также содержать любое конечное число терминалов. В языках программирования терминалами являются фактически используемые в них слова и символы: do, else, + и т.п.

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

    Один_нетерминал à любая конечная цепочка из терминалов и нетерминалов.

    При этом цепочка справа от стрелки может быть и пустой. Например,

    <A> à x

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

    <оператор> à IF <логическое_выражение> THEN <оператор>

    Один из нетерминалов выделен как начальный нетерминал или начальный символ, с которого должны начинаться выводы цепочек языка. Для языков программирования таким нетерминалом может быть <программа>. Обычно начальный символ обозначают <S>.

    Итак, контекстно-свободная грамматика будет задаваться:

    1) конечным множеством нетерминалов;

2) конечным множеством терминалов, которое не пересекается с множеством нетерминалов;

3) конечным множеством правил вида <A> à a, где A – нетерминал, а a - цепочка терминалов и нетерминалов (возможно, пустая); нетерминал <A> называется левой частью правила, а a - правой частью;

4) одним нетерминальным символом, выделенным в качестве начального.

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

Для описания грамматик очень часто используют способ записи, получивший название формы Бэкуса-Науэра или БНФ. Здесь символ à заменяется символом ::=, за которым может следовать любое число правых частей, разделенных вертикальной чертой |. Здесь также нетерминалы заключаются в угловые скобки.

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

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

Множество терминальных цепочек, которые можно вывести из начального символа грамматики, называется языком. Говорят, что язык определяется, грамматикой, порождается ею или выводится в ней. Язык, порождаемый контекстно-свободной грамматикой, также называется контекстно-свободным языком.

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

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

Пусть дана следующая грамматика (начальный нетерминал <S>):

    1. <S> à a<A><B>c

    2. <S> à x

    3. <A> à c<S><B>

    4. <A> à <A>b

    5. <B> à b<B>

    6. <B> à a

Пусть дана цепочка:    a<A><B>c, тогда вывод будет выглядеть следующим образом:

<S> (1) ==> a<A><B>c (2) ==> a<A>b<B>c (3) ==> ac<S><B>b<B>c (4) ==> ac<S>ab<B>c (5) ==> acab<B>c (6) ==> acabac (7).

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

(1)                   <S>

(2)          <S>

         a        <A>      <B>      c

(3)          <S>

         a        <A>      <B>      c

          <A>  b

(4)          <S>

         a        <A>      <B>      c

                     <A>     b

                c <S> <B>  

(5)          <S>

               a        <A>      <B>      c

                     <A>      b

                c <S>  <B>

                                a

(6)          <S>

     a        <A>      <B>      c

                     <A>      b

                c <S>  <B>

x         a

(7)          <S>

     a        <A>      <B>      c

                     <A>      b     a

                c <S>  <B>

x         a

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

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

Таким образом, резюмируя вышесказанное, можно подытожить:

1. Каждой цепочке, выводимой в данной контекстно-свободной грамматике, соответствует одно или несколько деревьев вывода.

2. Каждому дереву соответствует один или более выводов.

3. Каждому дереву соответствует единственный правый и единственный левый выводы.

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

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

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

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

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

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

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

Если все символы правой части правила продуктивны, то продуктивен и символ, стоящий в ее левой части.

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

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

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

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

    Для написания программы-транслятора файлов из формата nroff в файлы формата HTML мы будем использовать генератор программ lex, компилятор компиляторов yacc, а также стандартный компилятор языка Си cc.

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

На следующем этапе создаем файл, описывающий грамматику нашей задачи, то есть пишем грамматический анализатор. Полученный файл, называющийся nroff2html.yacc, мы подаем в компилятор компиляторов yacc одновременно с файлом lex.yy.c. На выходе yacc мы получим два файла ytab.c (непосредственно грамматический анализатор) и y.output (структура правил грамматического анализатора).

Следующим этапом будет создание исполняемого модуля. Производится совместное компилирование файлов lex.yy.c, y.tab.c и стандартных библиотек.

 Порядок работы с программой-транслятором nroff2html таков: на вход программы подается текстовый файл в формате nroff, а на выходе получаем текстовый файл в формате HTML.

Конкретные шаги при разработке транслятора.

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

Сначала, с помощью генератора программ "Lex" строится лексический анализатор. В задачу лексического анализатора входит полное поглощение входного файла (потока) и передача в синтаксический анализатор найденных лексем, а также некоторых необходимых данных (например, может быть найдена лексема. NUMBER, а в качестве данных передается числовое значение найденного числа или цифры). Лексемы, содержащиеся в спецификации лексического анализатора должны полностью описывать все возможные наборы символов. Синтаксический же анализатор строится с помощью генератора программ YACC. В синтаксическом анализаторе с помощью высокоуровневых правил полностью описывается структура входного потока. Правила могут быть рекурсивными, то есть может существовать правило, элементом которого является оно само. Первым правилом синтаксического анализатора обычно выбирается такое, которое полностью описывает любой возможный входной файл.

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

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

2. Всякая строка, не имеющая в начале точки, является строкой текста.

3. Пустая строка (не содержащая никаких символов, кроме конца строки) означает команду "Перевод строки" и вывод пустой строки.

4. За командой может следовать один или более пробельный символ и аргумент.

5. После аргумента до конца строки может следовать ноль, один или более пробельный символ.

6. Аргумент может быть строкой, символом или цифрой.

Лексический анализатор разбирает входной поток следующим образом:

1. В начальном состоянии считывается первый символ из потока.

а) Если символ является точкой, то анализатор переходит в состояние ожидания команды.

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

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

2. В состоянии приема текста строка из потока принимается целиком, до символа конца строки. Лексический анализатор возвращает синтаксическому анализатору лексему, означающую текст, предварительно перейдя в начальное состояние.

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

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

б) Если полученные символы не подходят под шаблон ни одной из команд, то команда объявляется неизвестной. Перед возвращением лексемы в синтаксический анализатор, лексический анализатор переходит в состояние ожидания аргумента команды.

4. Предполагается, что аргументы команд могут быть трех типов – слово (например, название шрифта у команды .ft); символьный (например, тип выравнивания у команды .ad) или числовой (например, количество строк у команды .br). После определения лексемы, лексичепский анализатор переходит в начальное состояние и передает лексему синтаксическому анализатору.

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

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

в) Если аргумент состоит из одной и более цифр, то он передается как число.

Для передачи данных (текст, содержащийся в строке; значение аргументов) используется текстовый буфер (массив символов yytext[]), в который записывает считанные из потока данные лексический анализатор, построенный при помощи lex и который может использоваться любой функцией, т.к. является внешней переменной.

Единственным условием, накладываемым на программы, созданные при помощи взаимодействия генераторов программ lex и yacc, является необходимость полного соответствия в названии лексем, возвращаемых лексическим анализатором, и описанных в разделе объявлений синтаксического анализатора директивой %token.

Пользователь не должен переопределять такие функции, как input(), output(c) и unput(c), т.к. они используются анализатором и их переопределение может привести к ошибке.

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

1. Если синтаксический анализатор получает от лексического анализатора лексему "текст", то он выводит в выходной поток содержимое буфера yytext.

2. Если получена лексема "пустая строка", то в выходной поток выводится тэг HTML <br>.

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

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

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

В формате nroff принята такая система команд, при которой у большинства команд аргументом является количество строк, на которые будет распространятся действие этой команды. В HTML же область действия команды определяется местоположением открывающего и закрывающего тэгов. Для того, что бы определить место вывода закрывающего тэга, введены переменные-счетчики. В момент получения команды им присваивается значение аргумента, и затем оно уменьшается при выводе в выходной поток очередной порции текста. При достижении счетчиком значения "ноль", в выходной поток выводится закрывающий тэг. Если значение счетчика меньше нуля, то это значит, что он сейчас неактивен.

Для вывода в выходной поток тэга <br> - команда перевода строки – применяется специальная функция breakline(). Необходимость такого шага обусловлена тем, что в nroff существует команда ".ls", которая определяет, сколько пустых строк выводится по команде ".br" (аналогом которой является тег <br>). При поступлении лексемы, соответствующей команде ".ls" значение ее аргумента присваивается переменной LS, которая определяет сколько раз подряд выведется тэг <br>  в выходной файл.

Особо надо оговорить обработку команды nroff ".ex". При получении лексемы, соответствующей этой команде, синтаксический анализатор завершает свою работу, возвращая в головную функцию значение "0", свидетельствующее о нормальном завершении работы.

LEX.

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

Для полного оформления задачи пользователь задает дополнительные части программы, включая подготовленные другими генераторами. Программа-распознаватель генерируется в виде фрагментов программ на языке Си. lex не является законченным языком, это всего лишь генератор, дополняющий язык Си новыми возможностями.

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

Регулярные выражения.

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

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

               "\[]^?.*+|()$/{}%<>

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

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

 экранироваться. Распознаются также несколько специальных последовательностей языка Си:

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

               \t      табуляция

               \b      шаг назад

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

       Так как в выражении перевод строки недопустим, он должен экранироваться. Заметьте, что любой символ всегда является текстовым. Исключение составляют пробелы, табуляции, переводы строки и приведенные выше управляющие символы.

Запуск программы.

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

  Результирующая программа помещается в файл a.out и может впоследствии быть выполнена.

Классы символов.

Классы символов задаются с помощью квадратных скобок. Конструкция:

               [abc]

       удовлетворяет одному символу из множества a, b, c.  Внутри скобок большая часть операторов игнорируется.  Специальными являются только три: обратная дробная черта (\), минус (-) и стрелка вверх (^). Минус определяет диапазон символов, например:

               [a-z0-9<>_]

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

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

               [-+0-9]

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

       При определении классов оператор ^ должен быть первым символом после открывающей скобки, он указывает, что полученная строка должна рассматриваться как исключение из всего множества символов ЭВМ. Таким образом

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