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

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

Целью работы является разработка простого и понятного языка описания конечных автоматов и создания транслятора описания произвольного конечного автомата в исходный код на языке описания аппаратуры Verilog [см. 4, 8]. Это во многом упрощает использование автоматного подхода при проектировании аппаратуры. Транслятор, по полученному описанию конечного автомата, генерирует модуль - «черный ящик» на языке Verilog, представляющий из себя абстрактную управляющую модель, поведение которой задано исходным автоматом. Это позволяет реализовать строго модульный подход к проектированию, так как управляющий модуль максимально абстрагирован от любой низкоуровневой работы. Эта абстракция дает возможность описывать конечный автомат без использования любой терминологии, присущей языкам описания аппаратуры, что, фактически, может реализовать разработку управляющего модуля и остальной части проекта разными людьми. Более того, при использовании таких технологий, человек, разрабатывающий управляющий модуль может не иметь никакого отношения к разработке остальных частей проекта и даже не иметь отношения к программированию на языках описания аппаратуры вообще. Для больших проектов это может означать, например, более качественную работу, так как специалист, обладающий глубокими знаниями в предметной области, умеющий разрабатывать высокоуровневые модели управления и специализирующийся на этом, выполнит работу лучше, чем Verilog-программист широкого профиля. Подходы к генерации аппаратуры на базе ПЛИС (FPGA) уже применялись с использованием пакета Simulink для MathLab [5], однако это ПО не обладает открытым исходным кодом и требует дорогостоящей лицензии.

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

При разработке проекта был создан язык описания конечных автоматов (далее SML – State Machine Language). SML – максимально императивный язык, так как императивность больше соответствует идеологии языков описания аппаратуры. К сожалению, нет возможности сделать его полностью императивным. Тому есть ряд причин, например то, что блоки описания состояний конечного автомата сами по себе являются понятием декларативным. По этой причине не были использованы другие текстовые и графические языки и трансляторы для описания автоматов, например, [6] или [7].

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

Сам процесс трансляции можно разбить на три этапа. Первый этап – считывание входного файла в память с использованием легко изменяемого лексемного набора. Второй этап – разбор считанного, построение дерева разбора (точнее, AST) с использованием алгоритма рекурсивного спуска и обход по дереву со сбором необходимых для конечной трансляции данных. Для модуля конечной трансляции не нужно дерево целиком. Ему нужна лишь некоторая информация об этом дереве, целиком задающая результат трансляции. Именно эта информация и собирается вторым модулем после построения дерева. Третий этап трансляции – окончательное преобразование данных, собранных на втором этапе, в код на языке описания аппаратуры Verilog.

Работа выполнена на языке C++, в среде KDevelop, в операционной системе Linux. Исходный код программы находится в репозитории https://github.com/Nexx0f/SMT.

Автор благодарит компанию Intel за предоставленную на время работы плату FPGA, а также ее сотрудника Романа Фадеева за ценные консультации по языку Verilog и конструированию аппаратуры.

Список литературы

[1] А. А. Шалыто, Н. И. Туккель, SWITCH-технология — автоматный подход к созданию программного обеспечения «реактивных» систем, журнал «Программирование», №5, 2001 г.
[2] Н. И. Поликарпова, А. А. Шалыто. Автоматное программирование.
[3] С. Э. Вельдер, М. А. Лукин, А. А. Шалыто, Б. Р. Яминов, «Верификация автоматных программ», «Наука», 2001 г.
[4] А. К. Поляков. Языки VHDL и Verilog в проектировании цифровой аппаратуры.
[5] Ю. Ю. Янкин, А. А. Шалыто, «Автоматное программирование ПЛИС в задачах управления электроприводом», «Информационно-управляющие системы», №1, 2011 г.
[6] И. А. Лагунов, «Разработка текстового языка автоматного программирования» (http://is.ifmo.ru/diploma-theses/fsml).
[7] Л. В. Столяров. Трансляция описаний конечных автоматов в исходный код на языке Си. «Прикладная дискретная математика (Приложение)», Томск: ТомГУ, 2009, №1, С. 81-83.
[8] П. Хоровиц. У. Хилл. Искусство схемотехники.
[9] Материалы с сайта stackoverflow.com.

Научный руководитель: И. Р. Дединский.