ISSN 0236-235X (P)
ISSN 2311-2735 (E)

Journal influence

Higher Attestation Commission (VAK) - К1 quartile
Russian Science Citation Index (RSCI)

Bookmark

Next issue

2
Publication date:
16 June 2024

The article was published in issue no. № 4, 2008
Abstract:
Аннотация:
Authors: (kovalev.fsu@mail.ru) - , Ph.D, A.S. Kuznetsov (askuznetsov@mitht.ru) - Moscow Technological University (MIREA) (Assistant), Moscow, Russia, Ph.D
Keywords: , , development
Page views: 10827
Print version
Full issue in PDF (8.40Mb)

Font size:       Font:

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

 

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

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

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

С целью автоматизации процесса генерации компиляторов МСЯ предлагается разработать так называемый компилятор компиляторов. Для этого разумнее воспользоваться каким-либо хорошо зарекомендовавшим себя средством, модифицировать его в соответствии с поставленной задачей, отладить и внедрить в эксплуатацию. Наиболее подходящими инструментами являются родственные друг другу программы Bison и Byacc. Они строят программы восходящего синтаксического анализа, работающие по алгоритму LALR(1), покрывая большинство практически применяемых языков программирования.

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

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

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

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

·    Проверка семантических соглашений и синтез выполняются на языке программирования либо описываются в формате XML.

·    В качестве лидера в действующей версии используется язык С++, однако одновременно ведется разработка версий для языков C# и Java.

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

Итак, в основе MuYacc лежит входная спецификация BYacc, которая в общем случае состоит из трех частей, разделенных символами %%:

·     объявления,

%%

1.  правила,

%%

·    пользовательские функции.

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

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

Во входной спецификации используется ключевое слово %regexp, которое определяет конкретное регулярное выражение (его имя, описание, действия), даже если оно не используется в качестве терминального символа в алфавите реализуемого языка и не встречается в продукциях его грамматики. Чтобы описать терминальный символ, достаточно создать регулярное выражение с таким же именем.

Приведем фрагмент с описанием терминальных символов и продукции упрощенной грамматики для арифметических выражений.

%regexp letter [a-z]

%regexp digit [0-9]

%regexp IDENT letter(letter|digit)*

%action% {strcpy($$,yytext);}

%regexp NUM digit+ %action% {$$=atoi(yytext);}

%token IDENT

%token NUM

%%

expr : expr ¢+¢ expr | ¢(¢expr¢)¢ | IDENT | NUM;

%%

Введение конструкции %regexp дает возможность:

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

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

При генерации спецификации для Flex и BYacc небольшую трудность представляет процесс формирования спецификации Flex. Для того чтобы ее получить, необходимо обработать все конструкции %regexp и %token. В спецификацию BYacc достаточно просто скопировать все, что не касается %regexp.

Возможность описания мультисинтаксиса реализуется четырьмя ключевыми словами: %tokengroup, %endtokengroup, %syntaxgroup, %endsyntaxgroup, размещаемыми соответственно в первой и второй частях входной спецификации.

Ключевые слова %tokengroup и %endtokengroup играют роль своего рода операторных скобок, в которые заключаются группы регулярных выражений. Аналогично для групп продукций в качестве скобок выступают слова %syntaxgroup и %endsyntaxgroup. Обе открывающие скобки именуют начало группы и дают название процедурам соответственно лексического и синтаксического анализа для их дальнейшего использования (свойство name). Для групп продукций также указываются название особенной лексемы (свойство kword) и наименование соответствующей группы лексем и регулярных выражений (свойство tokengroup).

Для обозначения особенной лексемы во входной спецификации анализатора-лидера можно использовать еще одно ключевое слово – %switchtoken. Пример возможной спецификации:

%tokengroup name=¢¢arith_tokens¢¢

%regexp letter [a-z]

%regexp digit [0-9]

%regexp IDENT letter(letter|digit)*

%action% {strcpy($$,yytext);}

%regexp NUM digit+ %action% {$$=atoi(yytext);}

%token IDENT

%token NUM

%endtokengroup

%switchtoken ARITH

%%

analyzer           :

| analyzer ¢ ¢

| expressions analyzer

;

expressions       : ARITH ¢{¢ arith_expressions ¢}¢

;

%syntaxgroup name=¢¢arith_expressions¢¢

kword=ARITH

tokengroup=¢¢arith_tokens¢¢

expr : expr ¢+¢ expr | ¢(¢ expr ¢)¢ | IDENT | NUM;

%endsyntaxgroup

%%

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

Описанный подход позволяет заметно уменьшить время на разработку компиляторов, облегчить поиск ошибок в отлаживаемых программах синтаксического анализа на основе существующих спецификаций Flex и BYacc, а также снизить вероятность их появления за счет использования автоматизированного средства. Это подтверждается результатами внедрения в практику разрабатываемой программы компиляции МСЯ, особенно для мультиверсионного программного обеспечения.


Permanent link:
http://swsys.ru/index.php?page=article&id=1631&lang=&lang=&like=1&lang=en
Print version
Full issue in PDF (8.40Mb)
The article was published in issue no. № 4, 2008

Perhaps, you might be interested in the following articles of similar topics: