Стили и методы программирования
         

Постановка задачи


При обсуждении программы 10.3.1 было показано, что предложенный текст размечен символами _i, i=1,...,5 а также то, как от размеченного текста переходить к программе на языке С++ или к интерпретации таблицы. У такой разметки только один недостаток: она не стандартизована, а потому о распространении за пределы среды разработчиков системы, предназначенной для поддержки применения таблиц, говорить не приходится.

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

  • TEX и, в первую очередь, надстройка над ним LATEX — для типографской подготовки текстов.
  • HTML — стандартный язык разметки текстов в Интернет.
  • XML — язык разметки текстов в Интернет, ориентированный на активную работу с ними.

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

Построение разного рода визуализаций текстов и сопутствующей им информации — определяющая функция языков разметки, которая реализуется путем размещения разметочных команд вместе с предъявляемой информацией. Эти команды являются управляющими сигналами для вычислителя, который отвечает за визуализацию. Внутреннее совместное представление команд и данных для их выполнения естественно рассматривать в качестве операционной и одновременно информационной среды вычислителя–визуализатора. Язык разметки от языка программирования отличает в первую очередь совмещение данных и задания на их обработку.

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


\begin{example}\label{markupeample0} и \end{example}.

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

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

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

Для употребляющихся в Интернет языков разметки визуализатором служит браузер. Но визуализация — далеко не единственное вычисление, которое можно связывать с браузером или другой программой, обрабатывающей размеченный текст. Над информацией можно задавать разные обобщенные вычисления. Эти вычисления могут быть либо совмещены в одном процессе, либо разнесены во времени, что непринципиально. Применительно к числовой разметке, использованной в §10.3 для задания таблицы конечного автомата, правомерно трактовать разметку как команды трех видов вычислений:

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


Подобные вычисления можно определять для любого языка разметки, рассматривая подходящие абстрактные вычислители. Иными словами, существует программирование на языке разметки. Наиболее полно эта концепция прослеживается в технологии XML/XSL.

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


Иногда такая разметка явно расставляется по структуре данных (пример — язык Рефал), иногда она выносится в специальную структуру (Prolog), но в обоих случаях контекст, определяющий выполнение команд, и замена данных путем порождения результатов команд остаются. В развитии языков разметки прослеживается тенденция отделять распознавание структуры текста — сентенциальная часть обработки — от использования этой структуры для задания действий, которые определяют обобщенные вычисления2).

Ниже описывается решение задачи автоматической трансформации таблиц конечного автомата с использованием наиболее подходящего для этих целей языка XML (см. книгу [19]).

Если описывать тексты в современных языках разметки, таких, как LATEX [15] или XML, то возникает задача описывать и программировать преобразования подобных текстов. Решением этой задачи могут быть специализированные языки преобразований текстов либо соответствующие методики программирования, поддержанные автоматизированным преобразованием спецификаций в программу. Здесь мы рассмотрим методику, базирующуюся на автоматах.

Применим возможности системы XML/XSL к нашей задаче: описание конечного автомата (за основу взята таблица переходов 9.1).

<?xml version="1.0" encoding="windows-1251" ?> <automat name="Test"> <action><![CDATA[char symbol; int cnt;]]> </action> <ref>St1</ref> <state name="St1"> <if> <condition><![CDATA[’a’<=symbol & symbol <= ’z’]]> </condition> <action><![CDATA[printf ("%c", symbol); cnt = 1;]]> </action> <ref>St2</ref> </if> <eif> <condition> <![CDATA[ symbol != ’\n’]]> </condition> <action><![CDATA[/*Так как нужно печатать только слова, действия не заполняются */ ]]> </action> <ref> St1 </ref> </eif> <eif> <condition> <![CDATA[ symbol == ’\n’]]> </condition> <action><![CDATA[/*Так как нужно печатать только слова, действия не заполняются */ ]]> </action> <ref> St3 </ref> </eif> </state> <state name="St2"> <if> <condition><![CDATA[ ’a’<=symbol & symbol <= ’z’]]> </condition> <action><![CDATA[printf ("%c", symbol); cnt++;]]> </action> <ref>St2</ref> </if> <eif> <condition><![CDATA[ symbol != ’\n’]]> </condition> <action><![CDATA[printf (" - %i\n", cnt);]]> </action> <ref>St1</ref> </eif> <eif> <condition> <![CDATA[ symbol == ’\n’]]> </condition> <action><![CDATA[printf (" - %i\n", cnt);]]> </action> <ref>St3</ref> </eif> </state> <state name="St3"> <if> <condition><![CDATA[’a’<=symbol & symbol <= ’z’]]> </condition> <action><![CDATA[printf ("%c", symbol); cnt = 1;]]> </action> <ref>St2</ref> </if> <eif> <condition> <![CDATA[ symbol != ’\n’]]> </condition> <action><![CDATA[/* Так как нужно печатать только слова, действия не заполняются */ ]]> </action> <ref> St1 </ref> </eif> <eif> <condition> <![CDATA[ symbol == ’\n’]]> </condition> <action><![CDATA[/* Переход не требует чтения, symbol == ’\n’ не нужно читать */ ]]> </action> <ref>Exit</ref> </eif> </state> </automat>



Листинг 11.2.1. Решение задачи автоматической трансформации таблиц конечного автомата

В этом описании нашли отражение следующие свойства нашего конечного автомата (за основу взята таблица переходов 9.1):

  • Конечный автомат (тег <automat>) включает в себя теги <state> — перечень всех состояний в любом порядке, а также теги <action> — действие и <ref> — ссылка на исходное состояние3).
  • Каждый <state> содержит атрибут name, чтобы на него можно было ссылаться, и набор условий: один тег <if> и любое количество тегов <eif> (означающих "else if"). Эти два тега также можно было бы заменить одним универсальным, тем более что структура их потомков не различается, но опять же этого не сделано по соображениям облегчения форматирования.
  • Каждый <if> или <eif> включает в себя три тега: <condition> — собственно условие и уже описанные теги <action> и <ref> — действие при выполненном условии и ссылка на следующее состояние.
  • Теги <action> и <condition> содержат специальный тег <![CDATA[...]]> для включения строк на языке C++.


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

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



<?xml version="1.0"?> <xsl:stylesheet xmlns:xsl="http://www.w3.org/TR/WD-xsl"> <xsl:template match="/"> <DIV STYLE="font-family:Courier; font-size:12pt"> <xsl:for-each select="automat"> <TABLE border="1" width="75%"> <TR> <TD colspan="3"><xsl:value-of select="action" /></TD> <TD width="10%"><xsl:value-of select="ref" /></TD> </TR> <xsl:for-each select="state"> <TR> <td rowspan="3" width="10%" valign="top"> <xsl:value-of select="@name" /></td> <td><xsl:value-of select="if/condition" /></td> <td><xsl:value-of select="if/action" /></td> <td><xsl:value-of select="if/ref" /></td> </TR> <xsl:for-each select="eif"> <TR> <TD><xsl:value-of select="condition" /></TD> <TD><xsl:value-of select="action" /></TD> <TD><xsl:value-of select="ref" /></TD> </TR> </xsl:for-each> </xsl:for-each> </TABLE> </xsl:for-each> </DIV> </xsl:template> </xsl:stylesheet>



Листинг 11.2.2. Решение задачи автоматической трансформации таблиц конечного автомата

Следующая визуализация — это автоматическое преобразование XML–основы в программу на языке С/С++. Стоит обратить внимание на то, что результирующий текст оказывается практически тем же, что и в программе 10.2.5. Причины тому глубже, чем простота преобразования. Существование локального (без использования контекстно"=зависимой информации) описания следует из структуры конечного автомата, не требующей для определения перехода ничего вне состояния.

<?xml version="1.0"?> <xsl:stylesheet xmlns:xsl="http://www.w3.org/TR/WD-xsl"> <xsl:template match="/"> <blockquote> <pre STYLE="font-family:Courier; font-size:12pt;" > <xsl:for-each select = "automat">//C code for automat "<xsl:value-of select="@name" />" <![CDATA[ #include <stdio.h> #define 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" /> ) <blockquote>{ <xsl:value-of select="if/action" /> goto <xsl:value-of select="if/ref" />; } </blockquote> <xsl:for-each select="eif"> else if (<xsl:value-of select="condition" /> ) <blockquote>{ <xsl:value-of select="action" /> 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>

Листинг 11.2.3. Решение задачи автоматической трансформации таблиц конечного автомата

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



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

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

Хотя данная технология позволяет легко создавать С++/С# программы, основой для них остается язык XML. Чтобы составить новый автомат, программист должен как минимум знать синтаксис этого языка. Следующим естественным шагом будет исключение этого звена: требуется скрыть внутреннее представление данных от конечного пользователя, оставив только интуитивно понятное представление в виде таблицы. Но для этого в первую очередь необходимо выбрать:

  • преобразование таблица => XML представление и
  • средство для удобного редактирования таблиц.


Естественно редактировать таблицы там же, где мы их уже научились генерировать — в окне браузера. Доступ к редактированиюэтих таблиц может предоставить DOM (стандарт, реализованный в браузерах Internet Explorer 5.0 и Netscape Navigator 6.0). Изменения, добавления и другие редактирующие действия определяются довольно просто. Например, на языке 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 Definition, DTD). Хранимые в начале файла XML или внешним образом в виде файла *.DTD, эти определения описывают информационную структуру документа. DTD перечисляют возможные имена элементов, определяют имеющиеся атрибуты для каждого типа элементов и сочетаемость одних элементов с другими.

Каждая строка в определении типа документа может содержать декларацию типа элемента, именовать элемент и определять тип данных, которые элемент может содержать. Она имеет следующий вид:

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

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

<!ELEMENT action (#PCDATA)>

определяет элемент с именем action, содержащий символьные данные (т. е. текст). Декларация

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

определяет элемент с именем special_report, содержащий подэлементы state_1, state _2 и state_3 в указанном порядке, например:

<automat> <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 будут, видимо, заменены более мощными и простыми в использовании схемами, работа над которыми ведется в настоящее время.

  1)

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

  2)

  Тенденция отделения распознавания от обработки характерна и для других стилей программирования. Но для сентенциального стиля она оказывается решающей.

  3)

  Можно было бы оформить эти теги с помощьюо особого состояния Init, но при этом мы бы потеряли универсальность тега <state>, т. к. состояние Init, например, не нуждается в чтении символа, не содержит условий и должно быть всегда первым. Как будет понятно впоследствии, универсальность составных частей модели упрощает работу с ней.

Содержание раздела