Реферат: Разработка конвертора из текстового формата nroff в гипертекстовый формат HTML
В случае, когда на каждом шаге подстановок заменяется самый левый нетерминальный символ, такой вывод называется левосторонним или левым выводом. Для каждого дерева существует единственный левый вывод, так как благодаря условию выбора самого левого нетерминала место каждой подстановки устанавливается единственным образом. Аналогично, для дерева существует единственный правосторонний или правый вывод, который получается если заменять всегда самый правый нетерминал.
Дерево вывода цепочки контекстно-свободного языка сложно описать кратко, поэтому покажу пример подобного дерева.
Пусть дана следующая грамматика (начальный нетерминал <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. В состоянии приема команды из потока принимается две латинских буквы, за которыми могут следовать один или более пробелов.
а) В соответствии с полученными символами выбирается лексема и передается синтаксическому анализатору.
б) Если полученные символы не подходят под шаблон ни одной из команд, то команда объявляется неизвестной. Перед возвращением лексемы в синтаксический анализатор, лексический анализатор переходит в состояние ожидания аргумента команды.
Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15
