скачать рефераты
  RSS    

Меню

Быстрый поиск

скачать рефераты

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

Генератор предоставляет широкие возможности для задания структуры входного потока программы. Пользователь 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, ..., которые соответствуют значениям, возвращаемым правой частью правила, слева направо. Тогда, если правило выглядит как

               A:B C D ;

       то $2 - значение, возвращаемое C, $3 - значение, возвращаемое D.

Лексический анализ.

       Для чтения входного потока и передачи лексем (при необходимости, со значениями) программе разбора пользователь должен разработать лексический анализатор. Лексический анализатор - функция, возвращающая целое, с именем yylex. Функция возвращает целое число, называемое номером лексемы, которое обозначает тип прочитанной лексемы. Если с лексемой связано значение, оно должно присваиваться внешней переменной yylval.

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

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

       Как уже упоминалось, номера лексем могут выбираться либо самим построителем, либо пользователем. По умолчанию они выбираются построителем. Номер по умолчанию для литерального символа - числовое значение его кода в наборе символов. Другие имена получают номера, начиная с 257.

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

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

Как работает построитель.

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

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

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

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

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

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

               IF shift 34

       Это означает, что если очередная лексема есть IF, состояние 56 заталкивается в стек, а текущим состоянием (верхушка стека) становится 34. Очередная лексема обнуляется.

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

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

               . reduce 18

       ссылается на правило 18, а действие

               IF shift 34

       ссылается на состояние 34.

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

               A: x y z;

       Свертка зависит от символа в левой части (в данном случае A) и количества символов в правой части (в данном случае три).  Для свертки из стека выталкиваются три состояния. (В общем случае, количество выталкиваемых состояний равно количеству символов в правой части.) Фактически, эти действия были помещены в стек при распознавании x, y и z и больше они не нужны. После этого текущим состоянием становится состояние, в котором находился распознаватель перед обработкой правила. С помощью этого состояния и символа в левой части правила выполним сдвиг A. Полученное новое состояние помещается в стек, и разбор продолжается. Однако, существуют значительные различия между обработкой символа в левой части и обычным сдвигом лексемы, поэтому это действие называется переходом. В частности, очередная лексема при сдвиге очищается, а при переходе нет. В любом случае новое состояние содержит строку вида:

             A goto 20

       вследствие чего состояние 20 помещается в стек и становится текущим.

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

       Свертка также существенна при обработке задаваемых пользователем значений и действий. При свертывании правила программный фрагмент, связанный с ним, выполняется перед выравниваем стека.  В дополнение к стеку, содержащему состояния, существует стек, в котором содержатся значения, возвращаемые лексическим анализатором и действиями.  При сдвиге ввнешняя переменная yylval копируется в стек значений.  Свертка выполняется после возврата из пользовательского фрагмента. При переходе в стек значений копируется внешняя переменная yyval.  К стеку значений можно обращаться по именам псевдопеременных $1, $2 и т.д.

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

По умолчанию применяются два правила однозначности:

         1.  В конфликте сдвиг-свертка предпочтение отдается сдвигу.

         2.  В конфликте свертка-свертка предпочтение отдается первой встреченной свертке.

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

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

Обработка ошибок.

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

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

       Для того, чтобы пользователь мог управлять этим процессом, yacc предоставляет простое, но достаточно универсальное средство. Для обработки ошибок зарезервирована лексема с именем error. Это имя может использоваться в грамматических правилах: им отмечаются места, где может встретиться ошибка и где необходимо провести восстановление.  Распознаватель выталкивает состояния из стека до тех пор, пока не найдет состояние, в котором error допустимо. Далее считается что error - очередная лексема, и выполняются соответствующие действия. Затем значение очередной лексемы устанавливается равным лексеме, вызвавшей ошибку. Если никаких других правил не указано, при обнаружении ошибки обработка прекращается.

Среда выполнения yacc.

       Если на вход yacc подать спецификацию, на выходе получается файл с программой на Си, чаще всего называемый y.tab.c. В нем содержится функция, возвращающая целое, по имени yyparse().  Для получения входных лексем эта функция вызывает функцию лексического анализатора yyerror(). Далее, либо будет обнаружена ошибка и в этом случае (если не задано действий по обработке ошибок) yyparse() вернет 1, либо лексический анализатор вернет конечный маркер и распознаватель завершит обработку возвратом 0.

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


Новости

Быстрый поиск

Группа вКонтакте: новости

Пока нет

Новости в Twitter и Facebook

  скачать рефераты              скачать рефераты

Новости

скачать рефераты

© 2010.