Задание.

Разработать транслятор документов из формата nroff в формат HTML.

1. Транслятор должен быть реализован средствами программ lex и yacc.

2. Трансляции подлежит обособленный документ. (Один файл –один документ).

3. В качестве тестовых примеров использовать документы из руководства
ОС UNIX (man-файлы).

4. В качестве среду разработки использовать ОС UNIX.

Введение.

В настоящее время все большее распространение находит использование для доступа к RISC-серверам, на которых работают наиболее мощные системы
САПР, вместо X-терминалов более дешевых и при этом более универсальных персональных компьютеров.

Для связи между персональными компьютерами и RISC-серверам используются программы, эмулирующие на персональном компьютере работу X- терминалов. При этом на персональном компьютере, работающем под управлением
Windows, запускается UNIX-сессия с графическим интерфейсом пользователя
(GUI). В качестве графического интерфейса может использоваться как любой из доступных на сервере графический интерфейс, так и интерфейс Windows.

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

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

Документация в системе UNIX представлена в виде так называемых ‘manual pages’. Она просматривается с помощью команды системы UNIX ‘man’. При этом вызывается файл, содержащий требуемую документацию. Файлы, используемые командой ‘man’ написаны в текстовом формате nroff, являющимся стандартным форматом текста системы UNIX. Для чтения этих файлов также можно применять команду UNIX ‘nroff’.

Для чтения файлов, записанных в формате ‘nroff’, можно установить на персональном компьютере какую-либо из UNIX-подобных систем и, скопировав документацию на персональный компьютер, читать ее с помощью средств системы. Но при этом теряется одно из важнейших преимуществ использования персонального компьютера – его универсальность, так как станет либо совершенно невозможно использование программ, работающих под управлением
Windows (в случае полной замены операционной системы), либо для их использования потребуется перезагрузка компьютера (в случае установки двух операционных систем на одном компьютере).

Другой путь состоит в преобразовании файлов документации системы UNIX из формата nroff в какой-либо формат, чтение которого возможно на персональном компьютере. Возникает вопрос, какой формат выбрать. К этому формату предъявляются следующие требования:

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

Windows. Желательно также, чтобы эти тексты можно было просматривать и на сервере под управлением UNIX.

. Тексты должны сохранять форматирование, имеющееся в документах

‘manual pages’.
Представляется, что оптимальным будет выбор формата HTML. Этот формат просматривается с помощью программ, версии которых работают как под управлением Windows, так и под управлением UNIX. Формат HTML поддерживает широкие возможности форматирования. Кроме того, этот формат является стандартным форматом для документов во всемирной системе Internet, а, как уже говорилось, проблема, вызвавшая необходимость переноса части задач с сервера на персональный компьютер, приобретает наибольшую остроту именно при связи между сервером и рабочим местом пользователя посредством
Internet. Используя формат HTML, можно сделать документацию, преобразованную из ‘manual pages’ UNIX, общедоступной, поместив ее в один из узлов сети Internet. И последнее – этот формат является открытым, в отличие от большинства форматов текста на персональных компьютерах под управлением Windows, таких как, например, формат тестового редактора Word, что делает его удобным для использования, так как тексты в открытых форматах легко создавать и редактировать при минимальной вероятности возникновения ошибки.

Существует несколько путей решения проблемы. В настоящее время созданы программы-трансляторы из формата nroff в формат HTML. Все они имеют свои преимущества и недостатки.

Рассмотрим несколько существующих программ.

1.Программа "nroff2HTML" (автор - Р. Ричи).

Программа написана на языке "C", работает под управлением ОС "UNIX".
При конвертации вставляет в текст конечного файла обязательные теги формата
HTML (такие, как , , ) и затем копирует предварительно отформатированный с помощью программы nroff текст, заключив его в пару тэгов .

2. Программа "man2html", входящая в GUI * "Gnome".

Программа написана на языке "C", работает под управлением ОС
"Linux", тесно интегрирована с GUI (графический пользовательский интерфейс)
"GNOME".

Данная программа работает не с реальными файлами, а выступает как фильтр при выводе текста с помощью программы man на экран компьютера, перенаправляя вывод в окно HTML-броузера и снабжая его при этом всеми командами, необходимыми для форматирования. Полученный на экране текст выглядит наилучшим образом, т.к. в нем сохраняются все необходимые виды форматирования и поддерживаются перекрестные ссылки. Но данная программа не может работать без пакета "GNOME", для работы которого, в свою очередь, необходима ОС "Linux".

Ни одна из этих программ не удовлетворяет нашим требованиям, так как, во-первых, нам необходимо сохранять максимально полный объем форматирования, добившись переносимости программы и максимальной ее независимости от наполнения операционной среды.

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

Согласно условиям технического задания программа должна функционировать в вычислительных системах под управлением ОС "Unix" и совместимых с ней ("Linux"). Проблема состоит в том, что исполняемые файлы
ОС "UNIX" могут быть неработоспособны в среде "Linux". В то же время, многие из UNIX-подобных систем поставляются пользователю в виде текстов исходных файлов (исходников), предназначенных для компилирования. Так же и в данном случае можно передавать программу в виде исходников, снабженных программой компиляции. Это, с одной стороны, повысит переносимость программы, а с другой - позволит вносить достаточно опытному пользователю необходимые поправки и корректировки, расширяя возможности транслятора в соответствии с потребностями пользователя. При этом необходимым условием становится написание программы при помощи таких средств, которые присутствовали бы в любой UNIX-подобной ОС.

Первым очевидным элементом, присутствующим во всех таких ОС, является компилятор языка "С", на котором, собственно, и написана ОС "UNIX". Но язык
"С" является достаточно сложным языком и не все пользователи знакомы с ним.
В то же время, в ОС "UNIX" существуют другие средства написания программ: это генераторы программ LEX и YACC. Описание их команд настолько просто и логично, что позволяет вносить коррективы в существующую программу не имея специальной подготовки, и, возможно, даже не будучи знакомым с описанием этих средств, имея только текст исходной программы.

Nroff.

Nroff используется для форматирования текста в операционной системе
UNIX при выводе на экран монитора или на принтер. Имеет достаточно простые команды, которые и будут дальше рассмотрены.

Команды для управления шрифтом:
.bd - bold font
.ft имя_шрифта - устанавливает шрифт
.ps n - устанавливает размер символа

Команды управления страницами:
.bp - начать новую страницу
.pl - установить длину страницы
.pn - установить номер страницы
.rt - вертикальный возврат для столбцов

Команды управления текстом:
.ad l (r,c,b,n) - выравнивание текста влево (вправо, по центру, по ширине, без выравнивания).
.br - следующая строка
.ce - центрирование
.fi - заполнение
.na - нет управления текстом (no adjust)
.nf - нет заполнения (no fill)

Вертикальные пропуски:
.ls - пропуск строки
.sp - пространство

- новая строка + пропуск

Управление строкой:
.in - отступ
.ll - длина строки
.ti - временный отступ

Уже установленные переменные:
% - номер страницы dw - день недели (1-7) dy - день месяца mo - месяц yr - год ln - текущая строка
.c - текущая строка от ввода
.f - текущий шрифт
.i - текущий отступ
.j - текущая регулировка (adjustment) текста
.l - длина строки

Использование числовых переменных:
.nr R v [i] - присвоить числовой переменной R значение v с необязательным инкрементом i
.af R c - установить формат числовой переменной (1,01,i,I,a,A)
nx -использовать регистр x
n(xy - использовать регистр xy – две буквы
n+x - добавить инкремент, а затем использовать
n-(xy - вычесть инкремент, а затем использовать

Использование строковых переменных:
.ds R str - присвоить переменной R содержимое str
.as R str - дописать str в конец строковой переменной R
*x - использовать регистр x
*(xy - использовать регистр xy – две буквы
w’string’ - размер строки

Комментарии:
” комментарий

Макросы:
.de xx ” –начало определения макроса
Today is $1 the $2.
.. ” –конец определения макроса
Использование макроса:
.xx Monday 14th

Получится: Today is Monday the 14th

HTML.

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

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

- отличительный признак Web-страница. Имеет редко используемые атрибуты version, lang, dir. Этот тэг допускает вложение элементов HEAD, BODY, PLAINTEXT. Конечным тэгом заканчиваются все гипертекстовые документы.

- область заголовка Web-страницы, служит для формирования общей структуры документа. Этот элемент может иметь атрибуты lang, dir и допускает вложения элементов TITLE, ISINDEX, BASE, META, LINK,
NEXTID.

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

- описание стиля некоторых элементов Web-страницы.
Например, элемент H2 {font-family: Arial;} определяет стиль шрифта в элементе H2.

- заключает в себе гипертекст, который собственно определяет Web-страницу, отображаемую броузером. Внутри этого элемента можно использовать все элементы, предназначенные для дизайна Web-страницы.
Внутри стартового тэга можно располагать ряд атрибутов, обеспечивающих установки для всей страницы целиком. Атрибуты: background=”Путь к файлу фона” bgcolor=”#RRGGBB” – здесь три 2-разрядных 16-ричных числа, которые определяют интенсивность красного, зеленого и синего цветов. text=”#RRGGBB” – цвет текста страницы link=”#RRGGBB” – цвет гиперссылки vlink=”#RRGGBB” – цвет использованных гиперссылок alink=”#RRGGBB” – цвет последней выбранной пользователем ссылки

- элемент заголовка. Существует 6 уровней заголовков, которые обозначаются H1..H6. Заголовок уровня 1 – самый крупный, уровень 6
– самый маленький. Для этого элемента можно использовать атрибут, задающий выравнивание влево, по центру или вправо: align=”left” (“center”, “right”).

- горизонтальная линия. Этот элемент не имеет конечного тэга, но допускает ряд атрибутов: align=”left” (“center”, “right”, “justify”) – выравнивание влево, по центру, вправо, по ширине. size=толщина в пикселях – толщина линии width=длина в пикселях width=длина в процентах% color=”Цвет”
Варьируя параметры длины и толщины можно представлять линию в виде прямоугольника.

- гиперссылки. Частный случай – шаблон для создания меток:

- элемент для создания базового адреса (UR) для ссылок.

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

- элемент абзаца (paragraph). В принципе позволяет использовать только начальный тэг, так как следующий элемент Р обозначает конец предыдущего и начало следующего абзаца. Вместе с этим элементом используются атрибуты: align=”left” (“center”, “right”)

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

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

- элемент для обозначения текста, отформатированного заранее (preformatted).

- обозначение цитаты. Этот элемент требует наличия конечного тэга. Текст не претерпевает никаких изменений, но абзац располагается с отступом. В настоящее время существует сокращенное написание этого элемента: BQ.

- элемент для центрирования текста, а точнее любого содержимого. Принято, когда это возможно использовать вместо этого элемента атрибут align=”center”

- элемент, похожий на предыдущий, позволяет выравнивать содержимое по левому, правому краю или по центру. Для этого стартовый тэг должен содержать атрибут: align=”left” (“center”, “right”)

- выделение текста полужирным шрифтом.

- увеличенный размер шрифта

- уменьшенный размер шрифта

- выделение текста курсивом

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

- элемент, обозначающий текст телетайпа (teletype).

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

- подчеркнутое начертание текста.

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

- элемент, создающий эффект нижнего индекса (subscript).

- элемент, создающий эффект верхнего индекса
(superscript).

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

, и - элементы, предназначенные для вывода фрагментов программ. CODE используется для форматирования текста программы. SAMP предполагается задействовать при иллюстрации примеров (sample) вывода данных на экран. VAR был создан для выделения переменных (variables).

- этот элемент предназначен для указания текста, который пользователь должен ввести с клавиатуры (keyboard).

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

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

- элемент, определяющий базовый (основной) размер шрифта.
Внутри элемента необходимо указать атрибут: size=Базовый размер шрифта – его величина может лежать в предела от 1 до
7. По умолчанию используется величина 3. Установка, выполняемая этим элементом, имеет значение для элемента FONT, который позволяет задавать относительный размер шрифта.

- определение типа, размера и цвета шрифта. Все эти характеристики определяются с помощью соответствующих атрибутов. Например, абсолютный размер шрифта задается с помощью атрибута: size=абсолютный размер шрифта – этот атрибут может принимать значение от
1 до 7.
Также размер шрифта может задаваться относительно базового: size=+число (-число)
Атрибут цвета: color=”Цвет”
Тип шрифта: face=”название шрифта”.

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

Вид документа в разных форматах.

Для наглядности приведу пример текстового документа с различными приемами форматирования текста, а затем представлю его в обоих рассматриваемых форматах (nroff и HTML).

Результирующий текст (тот, который мы хотим видеть на экране):

Это пример текстового документа

Здесь показаны некоторые возможности форматирования текста

Пропуск строки

Работа с расположением текста:

Выровнять по левому краю

Выровнять по центру

Выровнять по правому краю

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

Обычный шрифт

Другой (вызванный) шрифт

Подчеркнутый текст

Подчеркнутый отцентрированный текст

Представим теперь этот текст в формате nroff.

.ft Times New Roman

.ad l

.nf

Это пример текстового документа

.br

Здесь показаны некоторые возможности форматирования текста

.sp

Пропуск строки

.sp

Работа с расположением текста:

.ad l

Выровнять по левому краю

.ad c

Выровнять по центру

.ad r

Выровнять по правому краю

.br

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

.br

Обычный шрифт

.br

.ft Arial

Другой (вызванный) шрифт

.ft Times New Roman

.br

.ul 1

Подчеркнутый текст

.ce 1

.ul 1

Подчеркнутый отцентрированный текст

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

.ft Times New Roman – установка для документа определенного шрифта (а позже его временная смена на шрифт Arial)

.ad l (c, r) – выравнивание текста по левому краю (центру, правому краю)

.sp – пропуск строки

.br – начало новой строки

.ul 1 – подчеркивание следующей (одной) строки

.ce 1 – центрирование следующей (одной) строки

Это простейший пример, в принципе, возможности формата nroff значительно шире. Используя весь набор команд nroff, можно достаточно полно применять разные способы и приемы форматирования текста.
А теперь представим тот же документ, но уже в формате HTML.

Это пример текстового документа

Здесь показаны некоторые возможности форматирования текста

Пропуск строки

Работа с расположением текста:

Выровнять по левому краю

Выровнять по центру

Выровнять по правому краю

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

Обычный шрифт

Другой(вызванный)шрифт

Подчеркнутый текст

Подчеркнутый отцентрированный текст

Также как и с предыдущим форматом, поясню некоторые команды и конструкции языка.

… - эти тэги говорят о том, что мы имеем дело с документом в формате HTML

… - между этими тэгами находятся все команды, а также текст HTML-документа.

- начало новой строки

… - начало и конец нового абзаца align=”left” (center, right) – используется для указания типа выравнивания текста: по левому краю, центру или правому краю.

… - между этими тэгами текст выводится другим шрифтом, указанным в конструкции: face=”font_name”

… - выводит подчеркнутый текст

Аналогично с форматом nroff, возможности HTML намного шире представленных в этом примере.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

( (

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

( IF THEN

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1. ( ac

2. ( (

3. ( c

4. ( b

5. ( b

6. ( a

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

(1) ==> ac (2) ==> abc (3) ==> acbc (4) ==> acabc (5) ==> acabc (6) ==> acabac (7).

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

(1)

(2) a c

(3) a c b

(4) a c b c

(5) a c b c a

(6) a c b c

. a

(7) a c b a c

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

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

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

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

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

Особо надо оговорить обработку команды 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] удовлетворяют всем цифрам и знакам плюс и минус.

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

[^abc] удовлетворяет всем символам, кроме a,b и с, включая все специальные и управляющие символы, а

[^a-zA-Z] удовлетворяет любому символу, не являющемуся буквой. Обратная дробная черта играет роль экранирующей последовательности для любого символа в квадратных скобках, который, если перед ним стоит обратная дробная черта, рассматривается буквально.

Задание произвольных символов.

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

[40-176] удовлетворяет всем печатаемым символам кода ASCII, от восьмеричного
40 (пробел) до 176 (черта сверху).

Задание вариантов.

Знак вопроса означает вариант в регулярном выражении. Например ab?c удовлетворяет либо ab или abc.

Указание повторений.

Повторяющиеся классы указываются операторами * и +. Например, a* удовлетворяет любому количеству (включая 0) последовательно идущих символов a, в то время, как a+ удовлетворяет одному или нескольким символам. Например,

[a-z]+ удовлетворяет всем строкам из строчных букв, а

[A-Za-z][A-Za-z0-9]* удовлетворяет всем алфавитно-цифровым строкам, начинающимся с буквы.

Альтернативы и группирование.

Вертикальная черта указывает альтернативы. Например,

(ab|cd) удовлетворяет либо ab либо cd. Для группирования применяются скобки, хотя на верхнем уровне они не обязательны. Например ab| cd аналогично предыдущему примеру. Скобки используется для более сложных выражений, например

(ab|cd+)?(ef)* удовлетворяет таким строкам, как abefef, efefef, cdef и cddd, но не abc, abcd или abcdef.

Чувствительность к контексту.

Lex распознает ограниченный объем окружающего контекста. Два простейших оператора - ^ и $. Если первым символом выражения указан ^, оно будет удовлетворяться при расположении в начале строки (после символа перевода строки или в начале входного потока). Такой смысл не противоречит значению этого символа при задании классов, так как в этом случае он указывается внутри квадратных скобок. Если последним символом выражения служит $, выражение будет удовлетворяться при нахождении в конце строки.
Последний оператор - частный случай более общего оператора /, задающего правый контекст. Выражение ab/cd удовлетворяет строке ab только в том случае, если за ней следует cd.
Таким образом ab$ аналогично ab/n

Задание повторяющихся выражений.

Фигурные скобки задают либо повторение (если внутри цифры), либо определение подстановки (если внутри имя). Например

{digit} ищет заранее определенную строку с именем digit и вставляет ее в заданной точке. А выражение a{1,5} ищет от одного до пяти вхождений символа a.

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

Определения помещаются в первой части спецификации перед правилами и завершаются символом процента.

Задание действий.

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

Одно из простейших действий - игнорирование входного потока. Это выполняется с помощью пустого оператора Си (;).

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

Иногда правила некорректно распознают символы на границах входного потока. Для этой ситуации удобны две функции. Yymore() указывает, что следующее входное выражение должно помещаться в конец только что найденного. Обычно следующее выражение затирает текущее содержимое yytext.
Yyless(n) вызывается тогда, когда в данный момент нужны не все символы, удовлетворившие текущему правилу. Аргумент указывает количество символов, возвращаемых во входной поток. Это обеспечивает просмотр вперед, но в несколько иной форме, нежели при $.

Можно пользоваться и внутренними функциями ввода-вывода. К ним относятся:

1. input() следующий символ из потока;

2. output(c) вывод символа в поток;

3. unput(c) возврат символа в поток.

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

Lex не использует без надобности просмотр вперед, но к нему приводят правила, содержащие /, или заканчивающиеся на один из следующих символов:

+ * ? $

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

Еще одна функция, которую иногда переопределяют, - yywrap. Она вызывается при достижении конца файла. Если она возвращает 1, выполняется нормальное завершение работы. Иногда бывает удобно организовать дополнительный ввод из другого источника. В этом случае пользователь пишет свою версию этой функции, которая выполняет новый ввод и возвращает 0. Это приводит к продолжению обработки. По умолчанию yywrap всегда возвращает 1.

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

Обработка неоднозначных правил.

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

* Выбирается самая длинная последовательность.

* Из всех подходящих правил выбирается первое.

Входной поток обычно разбивается на части так, что lex не ищет все возможные вхождения всех выражений. Каждый символ считается один и только один раз.

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

Чувствительность к левому контексту.

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

Существует три способа обработки, используемые в различных условиях:

1. Применение флагов (при изменении условий правила меняются незначительно).

2. Использование начальных состояний.

3. Использование нескольких лексических анализаторов, работающих одновременно.

В любом случае, существуют правила, распознающие необходимость изменения условий, в которых будет анализироваться текст, и устанавливающие ряд параметров для фиксации измененных условий. Это может быть, например, флаг, проверяемый в пользовательских действиях. Это самый простой способ решения задачи, так как lex здесь вообще не участвует. Может оказаться удобным запомнить флаги в качестве начальных состояний правил. С начальным состоянием может быть связано любое правило. Оно будет применяться только в том случае, когда lex находится в этом состоянии. Текущее начальное состояние может быть изменено в любое время. И наконец, если наборы правил для различных состояний сильно отличаются, более ясным подходом было бы написание нескольких отдельных анализаторов, переключаемых при необходимости.

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

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

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

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

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

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

%T

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

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

программы

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

%% правила

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

Раздел правил состоит из одного или более грамматических правил.
Грамматическое правило записывается в формате

A : BODY ;

A представляет собой нетерминальное имя, BODY - последовательность имен и литералов (возможно пустую).

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

Литерал представляет собой символ, заключенный в апострофы. Так же, как и в Си, обратная дробная черта служит механизмом экранирования внутри литералов, распознаются все специальные последовательности языка Си:

n Перевод строки

r Возврат каретки

' Апостроф

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

t Табуляция

b Шаг назад

f Перевод формата

xxx Восьмеричное число xxx

По ряду причин символ NUL (ПУС, или 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.

Для получения работающей программы пользователь должен снабдить распознаватель некоторой средой выполнения. Например, как у любой программы на Си должна существовать функция main, всегда вызывающая yyparse(). Далее. для печати сообщений об ошибках должна вызываться функция yyerror().

Эти функции в той или иной форме должны задаваться пользователями.

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

Lex и yacc. lex может использоваться как самостоятельно для несложных преобразований, так и как средство анализа и сбора статистики на лексическом уровне. Он также может применяться для построения программ лексического анализа, они особенно хорошо стыкуются с программами, сгенерированными yacc. Программы lex распознают только регулярные выражения, а программы, построенные yacc, воспринимают довольно широкий класс контекстно-свободных грамматик, но требуют анализатора низкого уровня для распознавания входных лексем. Таким образом, сочетание yacc и lex часто оказывается весьма неплохим решением. Если lex используется как препроцессор к программе разбора, он разбивает входной поток на фрагменты, которым программа синтаксического разбора ставит в соответствие некоторые структуры. К программам, построенным с помощью lex, несложно добавить программы, построенные другими генераторами или написанными вручную.
Пользователи yacc заметят, что имя программы yylex совпадает с именем программы входного разбора, которое требует yacc. Это облегчает взаимодействие двух генераторов.
Из регулярных выражений, задаваемых во входной спецификации lex строит детерминированный конечный автомат. Для экономии памяти автомат не компилируется, а интерпретируется. Несмотря на это анализатор все же остается достаточно быстрым. В частности, время, необходимое для распознавания и разбора входного потока, пропорционально его длине. При определении скорости количество и сложность входных правил не имеют значения, если только правила с правым контекстом не требуют значительного объема повторных просмотров. Количество и сложность правил увеличивают размер конечного автомата, а, следовательно, и размер генерируемой программы.

Если вы хотите использовать эти две программы совместно, обратите внимание, что lex называет свою программу yylex, то есть именем, которое требует yacc для своего анализатора. Обычно это функцию вызывает головная программа по умолчанию (main) из библиотеки lex, но если используется также и yacc со своей головной программой, функцию будет вызывать он. В этом случае каждое правило должно заканчиваться return (token); возвращая соответствующую лексему. Несложный способ получения доступа к именам лексем yacc - включение выходного файла lex как части выходного файла yacc с помощью строки:

#include "lex.yy.c"

Соответствие команд nroff и HTML, а также их внутреннее представление.

.br BREAKLINE (LS раз)

.sp argument SPACE

.bd argument BOLD (Действует на argument строк)

.ul argument UNDERLINE (Действует на argument строк)

.cu SUNDERLINE (Действует на одну строку)

.ce SCENTER (Действует на одну строку)

.ft argument FONT

.ps argument SIZE

.ad argument ADJUST

.na NOADJUST

.fi FILL tFILL=1

.nf NOFILL tFILL=0

.ls argument LINESPACE LS=argument

.ll LINELENGTH Команда поглоща- ется, но игнорируется

.in argument IN cIN=argument

.ti argument TIN cTIN=argument

.ex EXIT Завершение работы

Описание файлов системы разработки транслятора.

Описание файла nroff2html.lex.

Лексический анализатор lex обрабатывает входной файл. В данном случае производится «механическая» обработка, то есть lex просто распознает лексемы, но не предпринимает никаких действий по отношению к ним, а передает это право yacc’у.

Считывание идет посимвольное, при этом если первый символ в строке не является ‘.’ или символом перевода строки, то строка распознается как текст, то есть в yacc передается соответствующее предупреждение.

Если первый символ в строке – ‘.’, то за ним следует команда.
Следующие два символа сравниваются с командами, имеющимися в банке данных, и при идентификации имя опознанной команды передается в yacc. В случае, если команда неизвестна (то есть за точкой идут два символа и пробел либо символ табуляции, но она не совпадает ни с одной из имеющихся в БД), то сама команда поглощается при выводе (не выводится), а текст, к которому эта команда относится, выводится в HTML-файл соответственно с предыдущими установками.

Comarg – аргумент команды. В данной программе различаются четыре варианта аргумента: либо пустой, либо цифровой (darg), либо символьный – единственный символ - (char), либо строка (символ и еще один или несколько символов, кроме пробела и табуляции). Различие символьного и строкового аргумента заключается в особенности lex’а – если какая-то лексема удовлетворяет нескольким правилам, то выбирается то правило, которое представляет лексему большей длины.

В файле есть функция Dlex(T) – выполняющая роль «монитора» при отладке программы.

При компиляции этого файла в результирующий файл будут включены стандартные библиотеки math.h, stdio.h, которые обеспечат поддержку математических операций и стандартного ввода/вывода.

Описание файла nroff2html.yacc.

В этом файле содержится описание действий, сопоставляющихся команде, передаваемой из lex’а.

В начальном разделе этого файла должны быть описаны ВСЕ лексемы- команды, которые могут быть переданы из lex’а.

Помимо этого в файле есть несколько функций.

Dyacc – аналог такой же функции в .lex-файле – выполняет роль
«монитора», выдавая дебагговские сообщения при отладке.

Переменные: c… - счетчики для подсчета строк. Три состояния: -1 – счетчик выключен, >0 – счетчик включен, =0 – счетчик сработал, пора выводить закрывающий тэг. t… - триггеры, используются при использовании различных шрифтов. Связано с некоторым различием: в nroff вызов нового шрифта автоматически прекращает действие предыдущего, а в HTML необходим закрывающий тэг. tFILL – есть заполнение или нет cIN – отступ (число пропусков) cTIN – временный отступ

Отличие отступа от временного отступа в формате nroff заключается в следующем: временный отступ действует лишь на одну строку и является
«вложенным» по отношению к общему отступу. Временный отступ отмеряется от общего и может быть положительным (сдвиг вправо) и отрицательным (сдвиг влево). Счетчику присваивается значение, соответствующее количеству строк, на которое действует правило, а потом идет декрементирование до нуля, когда включается закрывающий тэг. Временный отступ отключается командой .in с нулевым аргументом (то есть отступ равен нулю).

LS – количество строк в пустом пробеле (действует на весь текст). В nroff команда .ls задает пробел между выводимыми строками. nhtext[YYLMAX] – массив символов. Из lex в yacc передается через yylval(int) – рабочая переменная, в которой хранится значение команды; или через yytext([char]) – хранится то, что взял lex, то есть непосредственно лексема.

$$ - внутренняя псевдопеременная yacc.

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

Схема действия проста: lex опознает лексему и передает соответствующую команду в yacc, а далее yacc запрашивает lex на предмет опознания аргумента.

Существует функция breakline – она призвана для реализации команды
.ls. Breakline вставляет в результирующий HTML-файл столько тэгов
(перенос строки), сколько было передано в качестве аргумента командой .ls.

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

В файл y.tab.c после компиляции включается в исходном виде все, что в файле nroff2html.yacc заключено между %{ и %} (в разделе объявлений), в том числе файл lex.yy.c, полученный при компиляции nroff2html.lex.

Описание файла nroff2html.c.

nroff2html.c – исходный текст головной программы, при компиляции этого файла образуется исполняемый модуль.

При компиляции включается файл y.tab.c, то есть все вышеперечисленные файлы.

Формат запуска исполняемого модуля таков: nroff2html input_file output_file

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

Если же есть аргументы, то программа переходит к имени входного файла и открывает свое устройство (yyin) для чтения. Далее переход ко второму аргументу и открытие соответствующего устройства (yyout) для записи.

Далее в результирующий файл записываются стандартные открывающие тэги для HTML-файла (, , , , , ).

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

По окончании отработки своего функцией yyparse(), программа nroff2html.c вписывает закрывающие основные тэги HTML-файла: и
.

Описание файла y.output.

Этот файл подробно показывает КАК реально все выполняется и когда какое правило применяется. Файл представляет из себя набор состояний для yacc’а. При этом показывается какие правила и как в этих состояниях выполняются.

Поясню лишь некоторые функции: goto – безусловный переход к состоянию. reduce i – заносит текущее состояние в стек и переход к i. shift – замена состояния в стеке.

Строка $accept : _list $end – означает взять весь файл.

Описание команд.

SPACE .sp - (с аргументом) SPACER

LINESPACE .ls - (с аргументом) определяет LS, используется при выводе разрывов строки в HTML.

BOLD .bd - (с аргументом) включает триггер, вставляет , включает счетчик.

UNDERLINE .ul - аналогично с BOLD

SUNDERLINE .cu - (без аргумента) подчеркнуть одну строку. Счетчик =

1.

SCENTER .ce - (без аргумента) Центрирование одной строки. Счетчик

= 1.

BREAKLINE .br - вызывается функция вставки breakline, если LS, то соответствующее число раз.

FONT .ft - (с аргументом) если триггер включен, то закрывает существующий font, выводит тэг