diplom (664366), страница 3

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 3)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

text: text string

Такое правило описывает входной поток рекурсивно как набор строк, образующих текст. В некоторых форматах (например, таких, как RTF) начальным правилом было бы

text: text word

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

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

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

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

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

Заключение.

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

3. Технология реализации транслятора с помощью генераторов программ Lex и Yacc.

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

3.1 Определение лексем, встречающихся в формате nroff

Прежде всего, в формате nroff можно выделить четыре группы лексем: текст, команды, аргументы команд и переменные.

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

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

Переменные могут располагаться в любом месте текста. Все переменные сначала объявляются при помощи специальной команды.

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

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

Состояния, имеющиеся в формате nroff.

Основные лексемы, встречающиеся в формате nroff.

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

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

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

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

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

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

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

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

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

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

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

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

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

3.2 Описание грамматических правил преобразования из формата nroff в формат HTML.

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

1. Если синтаксический анализатор получает от лексического анализатора лексему "текст", то он выводит в выходной поток содержимое буфера yytext, используя для этого специально определенную функцию textout().

2. Если получена лексема "пустая строка", то в выходной поток выводится тэг HTML
   при помощи функции breakline().

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

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

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

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

При выводе текста функцией textout() происходит анализ на содержание в тексте переменных. Если переменные найдены, то происходит подстановка их значений в выводимый текст.

Характеристики

Список файлов реферата