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

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

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

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

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

{правила}

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

К настоящему моменту мы описали только правила. Необходимо также определить переменные как для программы, так и для 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. Таблицы наборов символов в виде

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

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 требует непосредственного объявления имен лексем. В дополнение, по причинам, объясняемым ниже, часто желательно включение лексического анализатора как части файла спецификации. Может оказаться полезным и включения ряда других программ. Таким образом, любой файл спецификации состоит из трех частей: объявлений, правил и программ. Части (или разделы) разделяются двойным знаком процента (%%). (Символ процента часто применяется в спецификациях в виде специального символа.)

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

объявления

правила

программы

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

правила

Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15