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

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 - пространство

<blank line> - новая строка + пропуск

Управление строкой:

.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 14^th

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

 

HTML.

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

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

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

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

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

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

<BODY> </body> - заключает в себе гипертекст, который собственно определяет Web-страницу, отображаемую броузером. Внутри этого элемента можно использовать все элементы, предназначенные для дизайна Web-страницы. Внутри стартового тэга можно располагать ряд атрибутов, обеспечивающих установки для всей страницы целиком. Атрибуты:

background=”Путь к файлу фона”

bgcolor=”#RRGGBB” – здесь три 2-разрядных 16-ричных числа, которые определяют интенсивность красного, зеленого и синего цветов.

text=”#RRGGBB” – цвет текста страницы

link=”#RRGGBB” – цвет гиперссылки

vlink=”#RRGGBB” – цвет использованных гиперссылок

alink=”#RRGGBB” – цвет последней выбранной пользователем ссылки

<H1> </h1> - элемент заголовка. Существует 6 уровней заголовков, которые обозначаются H1..H6. Заголовок уровня 1 – самый крупный, уровень 6 – самый маленький. Для этого элемента можно использовать атрибут, задающий выравнивание влево, по центру или вправо:

align=”left” (“center”, “right”).

<HR> - горизонтальная линия. Этот элемент не имеет конечного тэга, но допускает ряд атрибутов:

align=”left” (“center”, “right”, “justify”) – выравнивание влево, по центру, вправо, по ширине.

size=толщина в пикселях – толщина линии

width=длина в пикселях

width=длина в процентах%

color=”Цвет”

Варьируя параметры длины и толщины можно представлять линию в виде прямоугольника.

<A> </a> - гиперссылки. Частный случай – шаблон для создания меток: <A name=”Метка”></a>

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

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

<P> </p> - элемент абзаца (paragraph). В принципе позволяет использовать только начальный тэг, так как следующий элемент Р обозначает конец предыдущего и начало следующего абзаца. Вместе с этим элементом используются атрибуты:

align=”left” (“center”, “right”)

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

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

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

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

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

<DIV> </div> - элемент, похожий на предыдущий, позволяет выравнивать содержимое по левому, правому краю или по центру. Для этого стартовый тэг должен содержать атрибут:

align=”left” (“center”, “right”)

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

<BIG> </big> - увеличенный размер шрифта

<SMALL> </small> - уменьшенный размер шрифта

<I> </i> - выделение текста курсивом

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

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

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

<U> </u> - подчеркнутое начертание текста.

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

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

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

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

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

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

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

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

<BASEFONT> - элемент, определяющий базовый (основной) размер шрифта. Внутри элемента необходимо указать атрибут:

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

<FONT> </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>

<BODY>

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

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

форматирования текста <BR>

<BR>

Пропуск строки<BR>

<BR>

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

<P align="left">Выровнять по левому краю

<P align="center">Выровнять по центру

<P align="right">Выровнять по правому краю</p>

<BR>

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

шрифтами:<BR>

Обычный шрифт<BR>

<FON T face="Arial">Другой(вызванный)шрифт

</font><BR>

<U>Подчеркнутый текст</u>

<P align="center"><U>Подчеркнутый

отцентрированный текст</u></p>

</body>

</html>

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

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

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

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

<P> … </p> - начало и конец нового абзаца

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

<FONT> … </font> - между этими тэгами текст выводится другим шрифтом, указанным в конструкции:

face=”font_name”

<U> … </u> - выводит подчеркнутый текст

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

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

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

 

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

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

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

aAb ::= axb,

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

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

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

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

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

 

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

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

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

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

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

<A> à x

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

<оператор> à IF <логическое_выражение> THEN <оператор>

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1. <S> à a<A><B>c

2. <S> à x

3. <A> à c<S><B>

4. <A> à <A>b

5. <B> à b<B>

6. <B> à a

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

<S> (1) ==> a<A><B>c (2) ==> a<A>b<B>c (3) ==> ac<S><B>b<B>c (4) ==> ac<S>ab<B>c (5) ==> acab<B>c (6) ==> acabac (7).

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

(1) <S>

(2) <S>

a <A> <B> c

(3) <S>

a <A> <B> c

<A> b

(4) <S>

a <A> <B> c

<A> b

c <S> <B>

(5) <S>

a <A> <B> c

<A> b

c <S> <B>

a

(6) <S>

a <A> <B> c

<A> b

c <S> <B>

x         a

(7) <S>

a <A> <B> c

<A> b a

c <S> <B>

x         a

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Создание программы-транслятора.

 

Для написания программы-транслятора файлов из формата nroff в файлы формата HTML мы будем использовать генератор программ lex, компилятор компиляторов yacc, а также стандартный компилятор языка Си cc.

Процедура создания программы следующая. Для начала нам необходимо описать лексические правила нашей конкретной задачи или, говоря другими словами, написать лексический анализатор. Получившийся файл, называющийся nroff2html.lex, мы пропускаем через lex в результате чего получаем на выходе файл с именем lex.yy.c (непосредственно лексический анализатор).

На следующем этапе создаем файл, описывающий грамматику нашей задачи, то есть пишем грамматический анализатор. Полученный файл, называющийся nroff2html.yacc, мы подаем в компилятор компиляторов yacc одновременно с файлом lex.yy.c. На выходе yacc мы получим два файла ytab.c (непосредственно грамматический анализатор) и y.output (структура правил грамматического анализатора).

Следующим этапом будет создание исполняемого модуля. Производится совместное компилирование файлов lex.yy.c, y.tab.c и стандартных библиотек.

 Порядок работы с программой-транслятором nroff2html таков: на вход программы подается текстовый файл в формате nroff, а на выходе получаем текстовый файл в формате HTML.

Конкретные шаги при разработке транслятора.

Для построения конвертора выбран следующий подход:

Сначала, с помощью генератора программ "Lex" строится лексический анализатор. В задачу лексического анализатора входит полное поглощение входного файла (потока) и передача в синтаксический анализатор найденных лексем, а также некоторых необходимых данных (например, может быть найдена лексема. NUMBER, а в качестве данных передается числовое значение найденного числа или цифры). Лексемы, содержащиеся в спецификации лексического анализатора должны полностью описывать все возможные наборы символов. Синтаксический же анализатор строится с помощью генератора программ YACC. В синтаксическом анализаторе с помощью высокоуровневых правил полностью описывается структура входного потока. Правила могут быть рекурсивными, то есть может существовать правило, элементом которого является оно само. Первым правилом синтаксического анализатора обычно выбирается такое, которое полностью описывает любой возможный входной файл.

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

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

2. Всякая строка, не имеющая в начале точки, является строкой текста.

3. Пустая строка (не содержащая никаких символов, кроме конца строки) означает команду "Перевод строки" и вывод пустой строки.

4. За командой может следовать один или более пробельный символ и аргумент.

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

6. Аргумент может быть строкой, символом или цифрой.

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

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

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

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

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

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

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

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

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

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

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

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

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

Для передачи данных (текст, содержащийся в строке; значение аргументов) используется текстовый буфер (массив символов yytext[]), в который записывает считанные из потока данные лексический анализатор, построенный при помощи lex и который может использоваться любой функцией, т.к. является внешней переменной.

Единственным условием, накладываемым на программы, созданные при помощи взаимодействия генераторов программ lex и yacc, является необходимость полного соответствия в названии лексем, возвращаемых лексическим анализатором, и описанных в разделе объявлений синтаксического анализатора директивой %token.

Пользователь не должен переопределять такие функции, как input(), output(c) и unput(c), т.к. они используются анализатором и их переопределение может привести к ошибке.

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

1. Если синтаксический анализатор получает от лексического анализатора лексему "текст", то он выводит в выходной поток содержимое буфера yytext.

2. Если получена лексема "пустая строка", то в выходной поток выводится тэг HTML <br>.

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

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

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

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

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

Особо надо оговорить обработку команды 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 в начале строки.

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

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

 объявления

%%

правила

%%

программы

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

%%

правила

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

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

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 и т.д.

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

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