2. Регулярные выражения

При функционировании трансформатора (программы XSLT) используется описание DTD преобразуемого документа XML.

Мы используем следующее DTD для машины Тьюринга.

<!ELEMENT Go (Instruction, State, TapeLeft, Symbol, TapeRight)>
<!ELEMENT TapeLeft  (Nod) >
<!ELEMENT TapeRight (Nod) >
<!ELEMENT Nod ((Square, Nod) | Square) >
<!ELEMENT Symbol    (#PCDATA) >
<!ELEMENT Square    (#PCDATA) >
<!ELEMENT State     (#PCDATA) >
<!ELEMENT Instruction (Instruction | EMPTY) >
<!ATTLIST Instruction
                       CurrentState  CDATA #REQUIRED
                       CurrentSymbol CDATA #REQUIRED 
                       NextSymbol    CDATA #REQUIRED
                       NextState     CDATA #REQUIRED
                       Move          CDATA #REQUIRED >

Здесь Instruction - это набор инструкций для машины Тьюринга, State - текущее внутреннее состояние, TapeLeft - левая часть ленты до обозреваемого сивола, Symbol - обозреваемый символ, TapeRight - правая часть ленты.

Логично было бы ленту для машины Тьюринга записывать в виде последовательности символов, у нас - Square. Мы не стали выбирать такое представление по двум причинам. По идеологии машины Тьюринга все действия происходят на ленте локально около обозреваемого символа. Язык XSLT не позволяет просто переписать остаток ленты, приходится переписывать все оставшиеся символы по одному, что приводит к неэффективности. Поэтому у нас на каждом уровне дерева записывается один символ и одна ссылка на оставшуюся часть ленты. Вторая причина состоит в том, что по смыслу интерпретации приходится постоянно сравнивать значения из различных мест. В языке XSLT как только написано <xsl:for-each . . . > , так сразу попадаем внутрь поддерева, и другие части дерева становятся или недоступны, или доступны сложным образом.

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

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

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

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

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

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

$ENTRY IntDTD {
 ((Go )
 ((Instruction (CurrentState  e.503 )
               (CurrentSymbol e.504 )
               (NextSymbol    e.505 )
               (NextState     e.506 )
               (Move          e.507 )) e.495 )
 ((State ) e.514)
 ((TapeLeft  ) ((Nod ) ((Square ) e.534) e.516 ))
 ((Symbol ) e.518 )
 ((TapeRight ) ((Nod ) ((Square ) e.538) e.520 )))
  =
 ((Go )
 ((Instruction (CurrentState )
               (CurrentSymbol )
               (NextSymbol )
               (NextState )
               (Move )) <F78 e.495 >)
 ((State ) Text )
 ((TapeLeft  ) ((Nod ) ((Square ) Text ) <S1 e.516 >))
 ((Symbol ) Text )
 ((TapeRight ) ((Nod ) ((Square ) Text ) <S1 e.520 >))) ;
}