Непейвода Н.Н., Скопин И.Н. Основания программирования

Подождите немного. Документ загружается.

10.5. ПРОГРАММНЫЕ ПРЕДСТАВЛЕНИЯ ГРАФА СОСТОЯНИЙ

615

В настоящее время широко применяются следующие языки разметки, ко-

торые можно считать стандартными:

• T

X и в первую очередь надстройка над ним L

X - для типографской

подготовки текстов,

•

HTML

— стандартный язык разметки текстов в Интернет и

•

XML

— язык разметки текстов в Интернет, ориентированный на актив-

ную работу с ними.

Их основное назначение связывается со структурированным представлени-

ем визуализации информации. С точки зрения автоматической трансляции

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

ответить, в какой мере разметка текста позволяет описывать требуемые пре-

образования. Но предварительно зададимся вопросами о том, правомерно ли

языки разметки считать языками программирования, и если да, то какие сти-

ли программирования они в принципе могут поддерживать.

Построение разного рода визуализаций текстов и сопутствующей им ин-

формации — определяющая функция языков разметки, которая реализуется

путем размещения разметочных команд вместе с предъявляемой информа-

цией. Эти команды являются управляющими сигналами для некоего вычи-

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

ставление команд и данных для их выполнения естественно рассматривать

в качестве операционной и одновременно информационной среды вычисли-

теля-визуализатора. В первую очередь совмещение данных и задания на их

обработку отличает язык разметки от языка программирования.

Пример 10.5.1. Текст данного примера в языке разметки L

X (точнее, в

том пакете определений над ним, который разработан для верстки данного

текста и других работ одного из авторов) для автоматического размещения

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

латься на Пример 10.5.1, форматирования тела примера и отработки его кон-

ца, окружен командами

\begin{example}\label{markupeample0}

и \end{example}.

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

дополнительную разметку (чтобы команда была проинтерпретирована как

часть текста)

\verb|\begin{example}\label{markupeample0}|\\.

616

ГЛАВА 10. МЕТОДЫ ПРОГРАММИРОВАНИЯ ОТ СОСТОЯНИЙ

И,наконец,конечно же,предыдущая строка также потребовала дополнитель-

ной разметки, но во избежание бесконечного регресса на этом закончим.

Конец примера 10.5.1.

Для употребляющихся в Интернет языков разметки визуализатором слу-

жит браузер. Но визуализация — далеко не единственное вычисление, кото-

рое можно связывать с операционно-информационной средой браузера. Над

ней можно задавать совершенно различные обобщенные вычисления. Эти вы-

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

времени, что непринципиально, но они всегда могут быть эксплицированы

при рассмотрении оперирования, задаваемого языком разметки. Примени-

тельно к числовой разметке, использованной в § 10.2.5 для задания таблицы

конечного автомата, правомерно трактовать разметку как команды трех ви-

дов вычислений:

• визуализация таблицы —трактовка разметочных символов как команд,

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

интерфейсного предъявления;

• трансляция таблицы — автоматическое построение программы, вы-

полняющей действия автомата;

• интерпретация таблицы — трактовка разметочных символов как ко-

манд, выполняющих действия с операндами, в качестве которых ис-

пользуются текстовые фрагменты.

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

сматривая подходящие вычислители для нее. Иными словами, речь идет о

программировании на языке разметки. Наиболее полно эта концепция про-

слеживается в технологии

XML/XSL

Если обратиться к стилю программирования, который в принципе может

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

рактерным видом вычислений этого стиля являются не просто продуциро-

вание новых данных с сохранением операндов, а глобальные трансформа-

ции данных, существенно зависящие от контекста. Мы еще будем обсуждать

данный стиль безотносительно задачи оперирования с таблично заданными

автоматами, а пока заметим, что в определенном смысле любой сентенци-

альный язык можно рассматривать в качестве языка разметки перераба-

тываемых данных. Иногда такая разметка явно расставляется по структу-

ре данных (пример — язык

Рефал

), иногда она выносится в специальную

10.5. ПРОГРАММНЫЕ ПРЕДСТАВЛЕНИЯ ГРАФА СОСТОЯНИЙ

617

структуру (

Prolog

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

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

Вполне закономерна тенденция, прослеживающаяся в развитии языков раз-

метки, отделять распознавание структуры текста — сентенциальная часть

обработки — от использования этой структуры для задания действий, кото-

рые определяют обобщенные вычисления.

Обзор языков разметки с точки зрения выделения обобщенных вычисле-

ний естественно поместить в более позднюю главу, посвященную сентенци-

альному программированию, поскольку и вычисления, и структуры, задан-

ные этими языками, естественно соотносятся в первую очередь с методами

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

после знакомства с синтаксическими таблицами, некоторые из аспектов об-

работки структурированных текстов и обобщенных вычислений над ними

естественно обсудить именно в связи с автоматами и методами программи-

рования от состояний. Поэтому ниже описывается конкретное решение за-

дачи автоматической трансформации таблиц конечного автомата с использо-

ванием наиболее подходящего для этих целей языка

XML

(см. книгу [55] и

§13.3.2).

10.5.3. Автоматное преобразование структурированных текстов

Если описывать тексты в современных языках разметки, типа L

X [43]

или

XML

то возникает задача описывать и программировать преобразования

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

ями являются специализированные языки преобразований текстов либо со-

ответствующие методики программирования, поддержанные автоматизиро-

ванным преобразованием спецификаций в программу. Здесь мы рассмотрим

методику, базирующуюся на автоматах.

Применим возможности системы

XML/XSL

к нашей конкретной задаче:

описание конечного автомата.

Программа 10.5.1

Как мы уже имели возможность убедиться (см., например, § 3.5 и 3.6), тенденция отде-

ления распознавания от обработки характерна и для других стилей программирования. Но

для сентенциального стиля она оказывается решающей.

То, что мы ссылаемся на более поздний параграф, — осознанное решение. В технических

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

сующее Вас место. Чтение книги как последовательного файла — слишком часто наименее

эффективный метод ее изучения.

618

ГЛАВА 10. МЕТОДЫ ПРОГРАММИРОВАНИЯ ОТ СОСТОЯНИЙ

<?xml version=’1.0’ encoding=’windows-1251’ ?>

</action>

<if>

</condition>

</action>

</if>

<eif>

<action><![CDATA[/*

Так как нужно печатать только слова,

действия не заполняются

*/ ]]>

</action>

</eif>

<eif>

</condition>

<action><![CDATA[/*

Переход не требует чтения,

symbol == ’\n’

не нужно читать

*/ ]]>

</action>

</eif>

</state>

<if>

</condition>

</action>

</if>

<eif>

10.5. ПРОГРАММНЫЕ ПРЕДСТАВЛЕНИЯ ГРАФА СОСТОЯНИЙ

619

</condition>

</action>

</eif>

<eif>

</condition>

</action>

</eif>

</state>

</automat>

В этом описании нашли свое отражение следующие свойства нашего конеч-

ного автомата (за основу взята таблица конечного автомата из § 10.2.3):

• Конечный автомат (тег

) включает в себя теги

<state>

— пе-

речень всех состояний в любом порядке а также теги

— дей-

ствие и

<ref>

— ссылка на исходное состояние

• Каждый

<state>

содержит атрибут

name

, чтобы на него можно было

ссылаться, и набор условий: один тег

<if>

и любое количество (> 0)

тегов

<eif>

(означающих “

else if

”). Эти два тега также можно было бы

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

не различается, но опять же этого не сделано по соображениям облег-

чения форматирования.

• Каждый

<if>

или

<eif>

включает в себя три тэга:

— соб-

ственно условие и уже описанные теги

<ref>

— действие

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

• Теги

содержат специальный тег

<![CDATA[...]]>

для включения строк на языке

C++

Можно было бы оформить эти тэги с помощью особого состояния

Init

, но при этом мы

бы потеряли универсальность тэга

<state>

, т. к. состояние

Init

, например, не нуждается в

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

в последствии, универсальность составных частей модели сильно упрощает работу с ней.

620

ГЛАВА 10. МЕТОДЫ ПРОГРАММИРОВАНИЯ ОТ СОСТОЯНИЙ

В описание не включено состояние

Exit

. Это сделано (а точнее не сделано)

по причине того, что эта часть является статичной (одинаковой у различных

автоматов), а потому нецелесообразно ее индивидуализировать и явно опи-

сывать.

Данное описание является основой для построения различных визуали-

заций автомата с помощью

XSL

. Например, достаточно просто строится та-

бличная визуализация, практически не отличающаяся от ранее составленной

таблицы:

Программа 10.5.2

<?xml version="1.0"?>

<xsl:stylesheet xmlns:xsl="http://www.w3.org/TR/WD-xsl">

<xsl:template match="/">

<xsl:for-each select="automat">

<TR>

</TR>

<xsl:for-each select="state">

<TR>

<xsl:value-of select="@name" /></td>

</TR>

<xsl:for-each select="eif">

<TR>

</TR>

</xsl:for-each>

</TABLE>

10.5. ПРОГРАММНЫЕ ПРЕДСТАВЛЕНИЯ ГРАФА СОСТОЯНИЙ

621

</xsl:for-each>

</DIV>

</xsl:template>

</xsl:stylesheet>

Следующая визуализация — это автоматическое преобразование

XML

осно-

вы в программу на языке

С/С++

. Стоит обратить внимание на то, что резуль-

тирующий текст оказывается практически тем же самым, что и в программе

10.2.4). Причины тому глубже, чем простота именно такой интерпретации-

преобразования основы. Сама осуществимость локального (без использова-

ния контекстно-зависимой информации) описания следует из структуры ко-

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

ния. И именно это свойство предопределяет простоту локального описания.

Программа 10.5.3

<?xml version="1.0"?>

<xsl:stylesheet xmlns:xsl="http://www.w3.org/TR/WD-xsl">

<xsl:template match="/">

<xsl:for-each select = "automat">//C code for automat

"<xsl:value-of select="@name" />"

<![CDATA[

#include <stdio.h>

#deﬁne failure true

void main( void )

{]]>

<xsl:value-of select = "action"/>

goto <xsl:value-of select = "ref"/>;<br/>

<xsl:for-each select="state">

<xsl:value-of select="@name" />: symbol = getchar ();

<blockquote>if (<xsl:value-of select="if/condition" /> )

goto <xsl:value-of select="if/ref" />; }

</blockquote>

<xsl:for-each select="eif">

else if (<xsl:value-of select="condition" /> )

622

ГЛАВА 10. МЕТОДЫ ПРОГРАММИРОВАНИЯ ОТ СОСТОЯНИЙ

goto <xsl:value-of select="ref" />; }

</blockquote>

</xsl:for-each>

</blockquote>

</xsl:for-each>

Exit: return;<br/>}

</xsl:for-each>

</pre>

</blockquote>

</xsl:template>

</xsl:stylesheet>

Как легко видеть, разница этой и предыдущей визуализаций только в том, что

там, где в таблице вставляются графические элементы, которые изображают

рамки, образующие саму таблицу, здесь находятся части синтаксиса языка

С++/C#

и отступы для лучшей читаемости получаемой программы.

Итак, благодаря использованию формата представления данных

XML

, мы

получили возможность автоматически создавать программы для данной за-

дачи путем простой замены стилевых таблиц!

Отметим теперь еще несколько интересных возможностей, которые мы

бы могли использовать.

Хотя данная технология позволяет легко создавать

С++/С#

программы,

основой для них остается язык

XML

и чтобы составить новый автомат, про-

граммист должен как минимум знать синтаксис этого языка. Следующим

естественным шагом будет исключение этого звена: требуется скрыть вну-

треннее представление данных от конечного пользователя, оставив только

интуитивно понятное представление в виде таблицы. Но для этого в первую

очередь необходимо выбрать:

• преобразование таблица =>

XML

представление и

• средство для удобного редактирования таблиц.

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

генерировать — в окне браузера. Доступ к редактированию этих таблиц мо-

жет предоставить упомянутый не стр. 786

DOM

(стандарт, реализованный в

браузерах

Internet Explorer 5.0

Netscape Navigator 6.0

). Изменения, доба-

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

10.5. ПРОГРАММНЫЕ ПРЕДСТАВЛЕНИЯ ГРАФА СОСТОЯНИЙ

623

Например, на языке

Java script

добавление новой ячейки в таблицу можно

описать следующим образом:

var oRow;

var oCell;

oRow = oTable.insertRow();

oCell = oRow.insertCell();

oCell.innerHTML = "This cell is <b>new</b>."

Точно так же можно создавать таблицы, строки и ячейки в них. Реализа-

ция же самого интерфейса (кнопочек, средств выделения, полей ввода) зави-

сит только от вашей фантазии.

Тот же

DOM

, точно таким же образом, может работать с

XML

, реплицируя

все действия конечного пользователя с таблицей в

XML

представление для

последующей записи последнего в виде готового файла со структурой нового

конечного автомата.

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

XML

может

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

лены все теги представления, правила их вложения и способы задания, тем

самым получился новый язык (по аналогии с современными языками, по-

строенными таким же образом, мы можем назвать его “

automatML

”). Пока

теги и элементы

XML

используются исключительно ради удобства для ваше-

го собственного проекта (как если бы вы использовали

CSS

на своей домаш-

ней страничке), то не имеет никакого значения, что вы даете этим элементам

и тегам имена, смысл которых отличается от стандартного и известен только

вам. Если же, с другой стороны, вы хотите предоставлять данные внешнему

миру и получать информацию от других людей, то это обстоятельство при-

обретает огромное значение. Элементы и атрибуты должны употребляться

вами точно так же, как и всеми остальными людьми, или, по крайней мере,

вы должны документировать то, что делаете.

Для этого придется использовать определения типов документов (

Document

Type Deﬁnition

DTD

). Хранимые в начале файла

XML

или внешним образом в

виде файла

*.DTD

, эти определения описывают информационную структуру

документа.

DTD

перечисляют возможные имена элементов, определяют име-

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

одних элементов с другими.

Каждая строка в определении типа документа может содержать деклара-

цию типа элемента, именовать элемент и определять тип данных, которые

624

ГЛАВА 10. МЕТОДЫ ПРОГРАММИРОВАНИЯ ОТ СОСТОЯНИЙ

элемент может содержать. Она имеет следующий вид:

<!ELEMENT имя_элемента (тип_данных)>

Например, декларация

<!ELEMENT action (#PCDATA)>

определяет элемент с именем

action

, содержащий символьные данные (т. е.

текст). Декларация

<!ELEMENT automat (state_1, state_2, state_3)>

определяет элемент с именем

special_report

,содержащий подэлементы

state_1

state _2

state_3

в указанном порядке, например:

<state_1>XML

: время пришло

</state_1>

<state_2>XML

превосходит самое себя

</state_2>

<state_3>

Управление сетями и системами с помощью

XML</state_3>

</automat>

После определения элементов

DTD

могут также определять атрибуты с

помощью команды

!ATTLIST

. Она указывает элемент, именует связанный с

ним атрибут и затем описывает его допустимые значения.

!ATTLIST

позволя-

ет управлять атрибутами и многими другими способами: задавать значения

по умолчанию, подавлять пробелы и т. д.

DTD

могут также содержать декла-

рации

!ENTITY

, где определяются ссылки на объекты, а также декларации

!NOTATION

, указывающие, что делать с двоичными файлами не в формате

XML

Серьезное и несколько удивительное ограничение

DTD

состоит в том, что

они не допускают типизации данных, т. е. ограничивают данные конкретным

форматом (таким, как дата, целое число или число с плавающей точкой). Как

вы, вероятно, уже заметили,

DTD

используют иной синтаксис, нежели

XML

и не очень-то интуитивно понятны. По названным причинам

DTD

будут, ви-

димо, заменены более мощными и простыми в использовании схемами

XML

работа над которыми ведется в настоящее время.

Возможно,вам приходилось слышать определения ‘правильно составлен-

ный’ (well-formed) и ‘действительный’ (valid) применительно к документам