Лекция
Привет, Вы узнаете о том , что такое автоматное преобразование структурированных текстов, Разберем основные их виды и особенности использования. Еще будет много подробных примеров и описаний. Для того чтобы лучше понимать что такое автоматное преобразование структурированных текстов , настоятельно рекомендую прочитать все из категории Стили и методы программирования.
Данная лекция предназначена для тех, кто уже имеет начальные навыки работы на языке разметки XML1.
Серьезный недостаток предложенного в 
10.3 решения задачи автоматического преобразования таблиц переходов в программы связан с идеей препроцессорного построения, удобного для обработки представления таблиц переходов. Игнорирование обратной связи между исходным представлением автомата и его интерпретируемым представлением порождает проблемы. Если не рассматривать развитие программы, то отслеживать эту связь не нужно. Но как только встает вопрос хотя бы о минимальных переделках, возникают проблемы.
Разработка технологии включает в себя создание и использование инструментов поддержки всех этапов, из которых состоит технологическая цепочка оперирования с таблицами. Ключевым моментом является выбор формата представления таблиц, приспособленный как к ручной, так и к автоматической обработке. Есть смысл попытаться отыскать универсальное решение. Если, вдобавок, оно будет стандартизовано, то появится возможность создать технологию. Сегодня предпосылки для такого решения существуют, в частности, использование так называемых языков разметки текстов и, в первую очередь, XML.
При обсуждении программы 10.3.1 было показано, что предложенный текст размечен символами _i, i=1,...,5 а также то, как от размеченного текста переходить к программе на языке С++ или к интерпретации таблицы. У такой разметки только один недостаток: она не стандартизована, а потому о распространении за пределы среды разработчиков системы, предназначенной для поддержки применения таблиц, говорить не приходится.
В настоящее время используются следующие языки разметки, которые можно считать стандартными:
Их основное назначение — структурированное представление визуализации информации. С точки зрения автоматической трансляции таблиц целесообразно обсудить алгоритмический аспект этих языков, т. е. ответить, в какой мере разметка текста позволяет описывать требуемые преобразования. Но предварительно зададимся вопросами о том, правомерно ли языки разметки считать языками программирования, и если да, то какие стили программирования они в принципе могут поддерживать.
Построение разного рода визуализаций текстов и сопутствующей им информации — определяющая функция языков разметки, которая реализуется путем размещения разметочных команд вместе с предъявляемой информацией. Эти команды являются управляющими сигналами для вычислителя, который отвечает за визуализацию. Внутреннее совместное представление команд и данных для их выполнения естественно рассматривать в качестве операционной и одновременно информационной среды вычислителя-визуализатора. Язык разметки от языка программирования отличает в первую очередь совмещение данных и задания на их обработку.
Пример 11.2.1. Текст данного примера в языке разметки LATEX (точнее, в том пакете определений над ним, который разработан для верстки данного текста и других работ автора) для автоматического размещения заголовка, создания идентификатора, по которому в дальнейшем можно ссылаться на Пример 11.2.1, форматирования тела примера и отработки его конца, окружен командами
\begin{example}\label{markupeample0}
и \end{example}.
Для того, чтобы напечатать первую из этих команд, пришлось применить дополнительную разметку (чтобы команда была проинтерпретирована как часть текста)
\verb|\begin{example}\label{markupeample0}|\\.
И, наконец, предыдущая строка также потребовала дополнительной разметки, но, во избежание бесконечного регресса, на этом закончим.
Для употребляющихся в Интернет языков разметки визуализатором служит браузер. Но визуализация — далеко не единственное вычисление, которое можно связывать с браузером или другой программой, обрабатывающей размеченный текст. Над информацией можно задавать разные обобщенные вычисления. Эти вычисления могут быть либо совмещены в одном процессе, либо разнесены во времени, что непринципиально. Применительно к числовой разметке, использованной в 10.3 для задания таблицы конечного автомата, правомерно трактовать разметку как команды трех видов вычислений:
Подобные вычисления можно определять для любого языка разметки, рассматривая подходящие абстрактные вычислители. Иными словами, существует программирование на языке разметки. Об этом говорит сайт https://intellect.icu . Наиболее полно эта концепция прослеживается в технологии 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):
В описание не включено состояние 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. Чтобы составить новыйавтомат, программист должен как минимум знать синтаксис этого языка. Следующим естественным шагом будет исключение этого звена: требуется скрыть внутреннее представление данных от конечного пользователя, оставив только интуитивно понятное представление в виде таблицы. Но для этого в первую очередь необходимо выбрать:
Естественно редактировать таблицы там же, где мы их уже научились генерировать — в окне браузера. Доступ к редактированиюэтих таблиц может предоставить 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)>
определяет элемент с именем automat, содержащий подэлементы 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 будут, видимо, заменены более мощными и простыми в использовании схемами, работа над которыми ведется в настоящее время.
Выводы из данной статьи про автоматное преобразование структурированных текстов указывают на необходимость использования современных методов для оптимизации любых систем. Надеюсь, что теперь ты понял что такое автоматное преобразование структурированных текстов и для чего все это нужно, а если не понял, или есть замечания, то не стесняйся, пиши или спрашивай в комментариях, с удовольствием отвечу. Для того чтобы глубже понять настоятельно рекомендую изучить всю информацию из категории Стили и методы программирования
Комментарии
Оставить комментарий
Стили и методы программирования
Термины: Стили и методы программирования