Конференции ИВТ СО РАН

V Всероссийская конференция молодых ученых по математическому моделированию и информационным технологиям с участием иностранных ученых

1-3 ноября, г. Новосибирск, Россия

Тезисы докладов

Информационные технологии

Графический метаязык для описания транслятора

Стасенко А.П.

Институт Систем Информатики им. А. П. Ершова (Новосибирск)

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

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

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

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

Дополнительные материалы: Полный текст доклада
Примечание. Тезисы докладов публикуются в авторской редакции

Ваши комментарии
Обратная связь

[Головная страница]
[Конференции]