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

Для создания отказоустойчивых программных систем известно множество подходов, использующихся на практике. К их числу относится методология мультиверсион-ного, или N -вариантного программирования [1], одной из отличительных черт которой является разработка нескольких версий одного и того же функционального модуля или компонента. В целом данная методология является дополнением к таким способам получения отказоустойчивых систем, как тестирование и верификация программного обеспечения.

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

• – языки программирования модулей;

• – алгоритмы решения типовых задач;

• – средства программирования;

• – методы тестирования.

Авторами ряда работ по мультиверсионному подходу отмечается тот факт, что при разработке программного обеспечения важно применение различных языков программирования для оформления вариантов [2] или версий [3] программных модулей, поскольку реализация различных версий модуля на разных языках позволяет уменьшить вероятность появления в версиях однотипных ошибок, связанных с языком.

Процесс создания мультиверсионных программных систем подразумевает их архитектурное разбиение на компоненты и модули, создаваемые независимо друг от друга. Однако нередко возникает необходимость в кодировании этих модулей на разных языках в рамках одного и того же исходного текста, как, например при создании динамических HTML-страниц с включением кода на язы- ках JavaScript и (или) VB Script [4]. Традиционный процесс разработки мультиверсионных систем не позволяет выполнить это простым способом. Обойти данное ограничение можно с помощью мультисинтаксических языков программирования [5] и автоматизированной системы MuYacc построения трансляторов языков этого класса.

Итак, в рамках одного исходного текста программы могут одновременно использоваться языки со свойствами, различающимися с точки зрения синтаксиса, и, как следствие, генерируемые разными классами грамматик. В связи с этим такие языки можно отнести к классу муль-тисинтаксических языков (МСЯ).

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

Мультиавтомат с магазинной памятью. В основу системы MuYacc положено устройство распознавания МСЯ в виде мультиавтомата с магазинной памятью (МП-мультиавтомат). При этом каждый вспомогательный анализатор основывается на обычном автомате с магазинной памятью (МП-автомат), который принято описывать семеркой элементов [6]:

P = ( Q , E, Г, 5, q o , Z o , F ) , где Q - множество состояний автомата; E - алфавит входных символов; Г - алфавит магазинных символов; 5 -графически и таблично заданная функция переходов;

q ₀ – начальное состояние автомата; F – множество конечных состояний автомата P ; Z ₀ – символ, обозначающий дно магазина.

Функция 5 с тремя аргументами ( q - текущим состоянием автомата, a – текущим входным символом или пустой строкой £ , а также X - символом на вершине магазина) в качестве результата выдает пару элементов (р , у ), где р - новое состояние автомата; у - цепочка магазинных символов, замещающая X на вершине магазина. Если у = £ , то магазинный символ снимается. Если у = X , то содержимое магазина не меняется. Например, если у = YZ , то X заменяется на Z , а затем Y добавляется в магазин.

Для мультиавтомата P _mul данный набор расширяется за счет введения трех дополнительных элементов. Таким образом, требуемое абстрактное устройство описывается следующим образом:

P mui = ( Q ,S,Г,5, q 0 , Z 0 , F , M , S ,ф ) ,       (1)

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

N

Множество M = 0 или M = U M j , где M j , j = 1, N - 1

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

Аналогично множество S с Q также может быть пустым ( S = 0 ). В общем случае S = U S_j , где 1

S j , j = 1, K - особое состояние из соответствующего множества мощностью K . Количество особых состояний может быть больше либо равно количеству вспомогательных автоматов ( K >  N) , поскольку из различающихся особых состояний возможно переключение на один и тот же автомат.

Мультиавтомат считается заданным ошибочно в следующих случаях:

• – если количество особых состояний меньше количества вспомогательных автоматов ( K <  N ), так как бессмысленно включать в устройство столь ресурсоемкий элемент, ни разу не получая шанса переключиться на него. Однако при желании это ограничение можно снять, зарезервировав, например, один или несколько вспомогательных автоматов для дальнейшего использования;

• - если м = 0 , а S * 0 , так как тогда исчезает необходимость в выделении особых состояний.

• - если м * 0 , а S = 0 по тем же соображениям, что и в первом пункте.

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

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

В первом случае для этого должны быть указаны номер (неотрицательное целое число J_M ) вспомогательного магазинного автомата из множества M и номер особого состояния из множества S ( J_S ). В итоге получаем функцию ф _notempty, принимающую пять аргументов и дающую на выходе результат в виде набора из трех элементов:

• ^ф notempty ( q , a , ^X , ^J M , ^J S ) : { P , У , ^M J_M } ,         ⁽²⁾

где p - новое состояние автомата; у - цепочка магазинных символов; M J_M – автомат с номером J_M из множества M . Если взглянуть на это с конструктивной точки зрения, то именно в этот момент и осуществляется переход к вспомогательному автомату с магазинной памятью в виде вызова соответствующей процедуры или перехода по таблице в зависимости от реализации, которая в свою очередь зависит от требуемой эффективности функционирования транслятора.

Теперь предположим, что M = 0 . Иначе говоря, в нашем абстрактном устройстве нет никаких вспомогательных автоматов. В этом случае необходимо, чтобы функция переключений ф вела себя точно так же, как функция переходов 5 обычного автомата. В результате получаем функцию ф _empty, которая при ближайшем рассмотрении отличается от функции переходов лишь своим названием:

• ^ф empty ( q , a , ^X ) : { P , У } .                     ⁽³⁾

В общем виде функция переключений ф приобретает вид ф( q, a, X, Jm , Js ) = фnotempty (q, a, X, JM , JS ) : {P, У, MJM } ,

= 1

если M *0 и S *0 и |M | < | S |,      (4)

^Ф empty ( q , a , X ) : { p , у } ,

• если M = 0 и S = 0 .

Теперь дадим формализованное описание МП-муль-тиавтомата с учетом выражений (2) и (3):

^ mul =^

• ( Q , S , Г , 5 , q о , Z o , F , M , S , ф по^ ) , если M *0 и S *0 и |M | < | S |,

• ( Q , S , Г , 5 , q о , Z о , F , M , S , ф е,^ ) , если M = 0 и S = 0 ,

Ошибка в противном случае.

Эквивалентным для (5), с учетом (4), будет следующее формальное определение мультиавтомата, которое отличается от (1) лишь явным указанием на ошибку в описании:

( Q , S , Г , 5 , q о , Z о , F , M , S , ф ) ,

^P mul =1    если | ^M | < | ^S | ,

Ошибка в противном случае.

Функционирование МП-мультиавтомата. Работа простого автомата, а также вырожденного МП-мульти-автомата с магазинной памятью описывается сменой конфигураций [7], где под конфигурацией МП-автомата, или его мгновенным описанием (ID), понимается тройка элементов, описывающих состояние q , оставшуюся часть входной цепочки символов, составляющих программу ю , и содержимое магазина у . Таким образом ID = ( q , ст, у ) .

Если P - это МП-автомат, а 5 ( q , a , X ) содержит ( p , a ) , то рP определяет отношение, которое для всех цепочек ю из 2 * и р из Г * такое, что

( q , а ет , X р ) рP ( p , ет , ap ) .

По аналогии с этими понятиями дадим определение конфигурации, или мгновенного опис ания IDmul, МП-мультиавтомата Pmul. Поскольку в некоторый момент времени в выделенном состоянии может быть запущен вспомогательный МП-автомат, то помимо текущего состояния оставшейся части входа и содержимого своего магазина мультиавтомат описывается также через конфигурации каждого из содержащихся в нем МП-автоматов. Последнее является множеством IDaux в формуле

N

ID aux = U ID j ,                  (7)

где N – количество вспомогательных автоматов. Таким образом, получаем мгновенное описание мультиавтомата в виде следующей формулы:

ID mul

( q , m , у , 0 ) , если P mui = P ,

— <                                              (8)

( q , ет , у , ID aux ) , в противном случае.

Также определим для МП-мультиавтомата бинарное отношение перехода рP mul . Если P mul - это описанный МП-мупыиавтсмат, и ф ( q , а , X , J M , J S ) содержит ( p , a, M J M ) , то р P _mul определяет отношение, которое для всех цепочек ю из 2 * и р из Г * такое, что

⁽ q , a ^ет, X Р, ^M J m ) рP mu| ⁽ p , ^ет, <  ^M J m ) .

Используем символ рPmul* для представления нуля или более переходов МП-мультиавтомата. Итак, имеем сле- дующее индуктивное определение.

Базис : I р P mul * I для любого мгновенного описания I .

Индукция : I р P mul * J , если существует некоторое мгновенное описание K , удовлетворяющее условиям

• ^{1    рP} mul ^K и ^{K рP} mul * ^J .

Таким образом, I р P _mul * J , если существует такая последовательность мгновенных описаний K ₁, K ₂, …, K_n , у которой I = K 1 , J = K n и K i р P mul K i + 1 для всех I = 1,2,..., n -1.

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

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

Таким образом, если Pmul – это мультиавтомат, описанный выражением (6), то тогда языком L(Pmul), допускаемым мультиавтоматом по заключительному состоя- нию, является выражение

L ( P mul ) — H q 0 , ю, Z 0 , ^ID mul ) ^Р P -V ( q , ^ a, ^ ) } . (9)

Докажем это утверждение.

• 1.    Сначала предположим, что мультиавтомат не содержит вспомогательных автоматов, тогда, как указывалось выше, он ничем не отличается от обычного МП-автомата. Следовательно, доказательство его сходимости к конечной конфигурации не отличается от доказательства, приведенного, например, в [8].

• 2.    Далее предположим, что рассматриваемый нами мультиавтомат содержит единственный вспомогательный МП-автомат. Поскольку по определению передача ему управления осуществляется в одном из специально выделенных состояний МП-мультиавтомата, а после возврата управления последнему осуществляется переход к следующему обычному состоянию в соответствии с функцией перехода и никакого иного влияния вспомогательный автомат на наше абстрактное устройство не оказывает, то его можно удалить из мультиавтомата. Тогда доказательство сходимости может быть сведено к п. 1.

• 3.    Теперь допустим, что мультиавтомат имеет два вспомогательных МП-автомата. Поскольку, как было указано выше, они друг на друга не влияют, то мы можем поочередно удалить их из мультиавтомата. Тогда доказательство сходимости может быть сведено к п. 2.

• 4.    По этой же схеме доказывается конечность алгоритма работы мультиавтомата при любом количестве МП-автоматов больше одного.

Мультисинтаксический язык является допускаемым мультиавтоматом с магазинной памятью по пустому магазину, если он начал свою работу в начальной конфигурации, получив на вход цепочку символов, составляющих программу, прочитал ее полностью и закончил работу при наличии в магазине лишь маркера его дна:

• ^L    ( P mul ) — { ® |( q 0 , ”, ^Z 0 , ^ID mul ) рP m/ ( q , ^ , ^ , ID -ul ) } .(10)

Ограничения на вспомогательные автоматы здесь те же, что и в выражении (9).

В [8] приводится доказательство эквивалентности языков, допускаемых по пустому магазину и по заключительному состоянию. Следовательно, построив мультиавтомат с магазинной памятью, допускающий язык по пустому магазину, эквивалентный такому же устройству, допускающему язык по заключительному состоянию, мы можем использовать доказательство выражения (9).

Формирование таблиц синтаксического анализа мультисинтаксических языков программирования. Итак, предложенный выше МП-мультиавтомат может быть использован в качестве основы программы синтаксического анализа МСЯ. Однако на каждом шаге он может требовать наличия нескольких магазинов произвольного размера в каждый момент времени, что не всегда приемлемо даже для ресурсов современных средств вычислительной техники. В силу этой и ряда других причин, трансляторы языков программирования, как правило, строятся на базе таблично-управляемых алгоритмов синтаксического анализа [7]. Эти алгоритмы в достаточной мере представлены в специальной литературе, и автором данной статьи было принято решение модифицировать один из алгоритмов формирования таблиц синтаксического анализа с тем, чтобы в дальнейшем воспользоваться им для создания системы MuYacc.

Известно, что метод LALR(1) восходящего синтаксического анализа позволяет покрыть большинство синтаксических аспектов применяемых на практике языков программирования [7]. Модификация этого метода позволила получить алгоритм mLALR (1), который унаследовал от своего родителя необходимость построения таблиц, строки которых соответствуют состояниям синтаксического анализатора, а столбцы – терминальным и нетерминальным символам контекстно-свободной грамматики, описывающей каждый язык-компонент МСЯ. При этом для анализаторов вспомогательных языков используется классический LALR(1)-алгоритм с элементами, которые могут принимать значения четырех типов [7]. В то же время синтаксический анализатор для языка-лидера использует таблицы с элементами пяти типов, из которых первые четыре унаследованы от LALR(1)-алгоритма:

• –    элементы переноса. Эти элементы имеют вид S_k и означают следующее: поместить в магазин символ, соответствующий столбцу; поместить в магазин состояние k и перейти к состоянию k ; если рассматриваемый символ – терминальный, то принять его. Если данный перенос подразумевает запуск анализатора вспомогательного языка, то это действие выполняется;

• –    элементы свертки. Они имеют вид R_m и означают, что нужно выполнить свертку с помощью правила m ; удалить N символов и N состояний из магазина ( N – количество символов в правой части правила m ); перейти к состоянию, находящемуся на вершине магазина. Нетерминал из левой части продукции m считается следующим входным символом;

• –    элементы ошибок. Они являются пустыми ячейками таблицы и соответствуют синтаксическим ошибкам;

• –    элементы остановки, которые имеют вид Accept. Ими завершается процесс синтаксического анализа (входная строка принимается). Если анализируется вспомогательный язык, то процедуре анализа лидирующего языка возвращается успешное значение;

• –    элементы запускающего переноса. Эти элементы имеют вид E_k и означают следующее: поместить в магазин символ, соответствующий столбцу; поместить в магазин состояние k ; найти и запустить анализатор соответствующего вспомогательного языка; если этот анализатор закончил анализ состоянием ошибки, то завершить анализ лидирующего языка с ошибкой; в противном случае перейти к состоянию k . Поскольку рассматриваемый символ – терминальный, то его принимают.

Анализатор языка-лидера начинает свою работу из начального состояния 0 и, переходя из одного состояния в другое, может закончить свою работу либо в состоянии Accept, либо в состоянии ошибки.