Транслятор с языка Sim-nML » History » Revision 2
Revision 1 (Alexander Kamkin, 09/30/2011 02:12 PM) → Revision 2/17 (Alexander Kamkin, 09/30/2011 02:14 PM)
h1. Транслятор с языка Sim-nML Данный документ содержит описание схемы трансляции спецификаций микропроцессоров на языке Sim-nML в набор Java классов, которые могут быть использованы инструментом MicroTESK для автоматизированной генерации тестовых программ. h2. Язык Sim-nML Язык Sim-nML является расширением языка nML. Грамматика языка доступна по адресу: http://www.cse.iitk.ac.in/users/simnml/docs/parser.pdf Описание языка доступно по адресу: http://www.cse.iitk.ac.in/users/simnml/docs/simnml.pdf h2. Java классы, создаваемые при трансляции Список Java классов, которые создаются при трансляции: #Класс @ProcessorName@, 1.Класс ProcessorName, который наследуется от класса @Processor@. Processor. Содержит большую часть информации о специфицируемом процессоре. >> *TODO:* TODO: уточнить, каким образом формируется имя этого класса. Возможен вариант получаеть это имя из имени файла со спецификацией на Sim-nML, или же можно требовать задавания этого имени от пользователя в качестве одного из параметров метода, который осуществляет трансляцию, или же можно использовать какие-то специальные аннотации в самой спецификации. Правила грамматики для «общих» нетерминальных символов Бинарная операция Правила грамматики для определения бинарных операций. BinOp : ''+'' | ''-'' | ''*'' | ''/'' | ''%'' | DOUBLE_STAR | LEFT_SHIFT | RIGHT_SHIFT | ROTATE_LEFT | ROTATE_LEFT | ROTATE_RIGHT | ''<'' | ''>'' | LEQ | GEQ | EQ | NEQ | ''&'' | ''^'' | ''|'' | AND | OR Числовая константа Правила грамматики для определения числовых констант. ConstNumExpr : ConstExprVal | ConstNumExpr BinOp ConstExprVal ConstExprVal : CARD_CONST | FIXED_CONST | HEX_CONST | ''!'' ConstNumExpr | ''~'' ConstNumExpr | ''+'' ConstNumExpr %prec ''~'' | ''-'' ConstNumExpr %prec ''~'' | ''('' ConstNumExpr '')'' TODO: предлагается все числовые константные выражения сразу вычислять, в оттранслированный Java код вставлять уже только значения выражений. Выражение Правила грамматики для определения выражений Bit_Expr : ID | Bit_Expr ''+'' Bit_Expr | Bit_Expr ''-'' Bit_Expr | Bit_Expr ''*'' Bit_Expr | Bit_Expr ''/'' Bit_Expr | Bit_Expr ''%'' Bit_Expr | Bit_Expr DOUBLE_STAR Bit_Expr | ''('' Bit_Expr '')'' | FIXED_CONST | CARD_CONST | STRING_CONST | BINARY_CONST | HEX_CONST OR правило OrRule : Identifier_Or_List Identifier_Or_List : ID | Identifier_Or_List ''|'' ID AND правило AndRule : ''('' ParamList '')'' ParamList : | ParamListPart | ParamList '','' ParamListPart ParamListPart : ID '':'' TypeExpr | ID '':'' ID Атрибуты В языке Sim-nML атрибуты используются для описания свойств инструкций и режимов адресации. Описание каждого такого объекта может содержать произвольное число атрибутов. Атрибуты можно разделить на два класса: предопределенные атрибуты и пользовательские атрибуты. Описание предопределенных атрибутов приведено ниже. Правила грамматики для атрибутов: AttrDefList : | AttrDefList AttrDef AttrDef : ID ''='' AttrDefPart | SYNTAX ''='' ID ''.'' SYNTAX | SYNTAX ''='' AttrExpr | IMAGE ''='' ID ''.'' IMAGE | IMAGE ''='' AttrExpr | ACTION ''='' ID ''.'' ACTION | ACTION ''='' ''{'' Sequence ''}'' | USES ''='' UsesDef AttrDefPart : Expr | ''{'' Sequence ''}'' Атрибут syntax Атрибут syntax используется для описания ассемблерного кодирования инструкции или режима адресации. Значения данного атрибута должны иметь строковый тип. Можно выделить следующие основные варианты определения атрибута syntax: 1)Строковая константа — значение определяется посредством строковой константы. Например, “nop”. 2)Атрибут параметра — значение атрибута определяется как значение этого же атрибута syntax у одного из параметров описываемого объекта. Например, x.syntax. 3)Форматированная строка — значение атрибута определяется с помощью специальной конструкции format. Данная конструкция является аналогом оператора printf в языке программирования С. Например, format(“%5b”, r). // TODO: добавить полное формальное описание конструкции format + описание транслчции данной конструкции в строковое выражение Java Трансляция: При трансляции данного атрибута в классе, соответствующем описываемому объекту создается метод со следующей сигнатурой: public String syntax() Для случая 1 из приведенного выше списка тело метода просто возвращает данную строковую константу. Для случая 2 метод возвращает результат вызова метода syntax соответствующего аргумента данного объекта. Такой аргумент должен содержаться в качестве поля в классе, соответствующем описываемому объекту. Для случая 3 метод возвращает результат трансляции конструкции format в строковое выражение языка Java. Атрибут image Атрибут image используется для описания бинарного кодирования описываемого объекта. Значения данного атрибута должны иметь строковый тип, причем допустимы только строки, содержащие символы «0», «1» и пробел. Пробелы используются для улучшения читаемости. Варианты определения атрибута image совпадают с вариантами определения атрибута syntax. Трансляция: Полностью аналогична трансляции атрибута syntax. Атрибут action Атрибут action используется для описания семантики выполнения инструкций. Трансляция: // TODO: при трансляции атрибута action обратить внимание на то, что в некоторых спецификациях данные между соседними в дереве инструкциями передают с использованием переменных (var). Это надо корректно учитывать, так как по умолчанию при трансляции таких объектов предлагается создавать локальные переменные соответствующих методов. С другой стороны, использование переменных для передачи данных между операциями противоречит описанию языка, в котором сказано, что состояние переменных не сохраняется при переходе от одной инструкции к другой. Атрибут uses В текущей версии инструмента данный атрибут не рассматриваем. Основные конструкции языка h3. Конструкция let Конструкция let используется для объявления констант. Константы обладают следующими свойтсвами: 1.Константы получают глобальную область видимости. 2.Константа может быть определена только один раз. Правила грамматики для конструкции let: LetDef : LET ID ''='' LetExpr LetExpr : ConstNumExpr | STRING_CONST | IF ConstNumExpr THEN LetExpr OptionalElseLetExpr ENDIF | SWITCH ''('' ConstNumExpr '')'' ''{'' CaseLetExprList ''}'' OptionalElseLetExpr : | ELSE LetExpr CaseLetExprList : CaseLetExprList1 | CaseLetExprList1 DEFAULT '':'' LetExpr CaseLetExprList1 : CaseLetExprStat | CaseLetExprList1 CaseLetExprStat CaseLetExprStat : CASE ConstNumExpr '':'' LetExpr Примеры: let REGS = 5 let byte_order = “big” let PC = “NIA” let SP = “GPR[29]” Проблемы: Не ясна семантика if и switch в том случае, когда определяемая величина не получает никакого значения, например let c = if 0 then 0 endif Ограничения: На первом этапе разработки прототипа предлагается ограничить поддержку конструкции let только простыми вариантами (без if и switch). Сложные вариаты let практически не используются на практике (ни один из примеров спецификаций представленных на сайте языка не содержал таких конструкций), их ценность представляется сомнительной. Трансляция: Если LetExpr является ConstNumExpr, то вычисляется значение этого выражения. Для каждой определенной в спецификации константы определяется поле к классе ProcessorName следующего вида public static final <type> ID = LetExpr; где <type> может принимать следующие значения: String – в случае, если LetExpr является STRING_CONST int – в случае, если LetExpr является числовым выражением и вычисленное значение есть целое.число, убирающееся в int. long – в случае, если LetExpr является числовым выражением и вычисленное значение есть целое.число, не убирающееся в int. float – в случае, если LetExpr является числовым выражением и его вычисленное значение есть число с фиксированной или плавающей точкой, убирающееся в тип float. double – в случае, если LetExpr является числовым выражением и его вычисленное значение есть число с фиксированной или плавающей точкой, не убирающееся в тип float. Ошибочные ситуации: наличие целых чисел, которые «не убираются» в long наличие чисел с плавающей точкой, которые «не убираются» в double Конструкция type Конструкция type используется для определения синонимов новых типов. Синонимы определяются на основе существующих стандартных типов: bool: определяет булевский тип, имеющий два предопределенных значений false и true. При применении преобразования типов (смотри coerces) false отображается в 0, true – в 1. При обратном преобразовании 0 отображается в false, любое ненулевое значение отображается в true. int(n):определяет интервал целых чисел card(n): определяет интервал натуральных чисел float: определяет число с плавающей точкой согласно стандарту IEEE754 // TODO: несоответствие грамматики и описания fix(n, m):определяет число с фиксированной точкой, в котором n бит отводятся под мантису и m бит под экспоненту.// TODO: уточнить, что описано в документации [n..m]: определяет интервал натуральных чисел (ограничение) enum(): определяет перечислимый тип, где именованные константы принимают значения от 0 до n-1.Будет совпадать с типом card(ceiling()) Правила грамматики для конструкции type: TypeSpec : TYPE ID ''='' TypeExpr TypeExpr : BOOL | INT ''('' ConstNumExpr '')'' | CARD ''('' ConstNumExpr '')'' | FIX ''('' ConstNumExpr '','' ConstNumExpr '')'' | FLOAT ''('' ConstNumExpr '','' ConstNumExpr'')'' | ''['' ConstNumExpr DOUBLE_DOT ConstNumExpr '']'' | ENUM ''('' IdentifierList '')'' IdentifierList : ID | ID ''='' CARD_CONST | IdentifierList '','' ID | IdentifierList '','' ID ''='' CARD_CONST Примеры: type bit = card ( 1 ) type byte = card ( 8 ) type address = card ( REGS ) type breakcode = card (20 ) Проблемы:Моделирование чисел с фиксированной точкой. Ограничения: в текущей реализации не рассматриваем случаи, когда определяется интервал, по мощности превосходящий максимальный соответствующий стандартный тип а Java. Например, исключаем из рассмотрения card (128). Трансляция: Для каждого такого типа-синонима создается новый класс с именем ID, единственным полем которого будет переменная объемлющего типа, а методы будут обеспечивать корректность работы с этой переменной, контролируя невыход их множества допустимых значений. В случае нарушения данных ограничений метод должен выбрасывать исключение. Необходимо учесть, что при трансляции операторов присваивания таким переменным, надо использовать методы set из соответствующих классов. Причем эти методы set должны в качестве параметров принимать так же номер строки и позицию в nml файле, по которой находится данный оператор присваивания. Эти данные используются отладки спецификаций в случае ошибок. Перечисления транслируются в стандартные Java перечисления. Например, пусть есть перечисление: type <name> = enum(id1 = val1, id2 = val2, …, idn = valn) Оно транслируется в отдельный файл <name>.java, который содержит Java перечисление следующего вида: public enum <name> { id1(val1), id2(val2), …, idn(valn) } Ошибочные ситуации: h3. Конструкция mem Конструкция mem используется для описания памяти моделируемого микропроцессора. Общий вид такого определения представлен ниже: mem M [N, type] [optional-properties] В этом определении, M – имя данного объекта памяти, N – количество ячеек памяти, и type – тип каждой такой ячейки памяти. Если тип не указан, то по умолчанию тип полагается равным card(8). Доступ к данным ячейкам памяти осуществляется по средствам оператора индексирования:M[0], M[1], … , M[n-1]. Опциональные параметры могут быть следующими: alias – описывает новую память как синоним какойто части уже описанной памяти. В этом случае оба имени будут ссылать на одни и те же ячейки памяти, но могут интерпретировать их по разному. Например: mem A[6, int(32)] mem M[3, card(32)] alias = A[3] В этом случае ячейки памяти, доступные по обращениям A[3], A[4], A[5], теперь могут быть доступны и по обращениям M[0], M[1], M[2] соответственно. Отличие заключается в том, что в случае обращений с использованием имени A содержимое ячейки интерпретируется как 32-ух разрядное знаковое число, в случае же, когда обращение идет по имени M, содержимое интерпретируется, как беззнаковое число. Правила грамматики для конструкции mem: Bit_Optr : BIT_LEFT Bit_Expr DOUBLE_DOT Bit_Expr BIT_RIGHT MemorySpec : MEM ID ''['' SizeType '']'' OptionalMemVarAttr SizeType : TypeExpr | ConstNumExpr | ConstNumExpr '','' TypeExpr OptionalMemVarAttr : | ALIAS ''='' MemLocation MemLocation : ID Opt_Bit_Optr | ID ''['' NumExpr '']'' Opt_Bit_Optr Opt_Bit_Optr : | Bit_Optr Bit_Optr : BIT_LEFT Bit_Expr DOUBLE_DOT Bit_Expr BIT_RIGHT // TODO: не ясна семантика Opt_Bit_Expr в грамматики для конструкции mem, в примерах использование именно такой формы тоже не было встречено. Примеры: mem A[6, int(32)] mem M[3, card(32)] alias = A[3] Проблемы: Ограничения: Трансляция: Анализ спецификаций на языке Sim-nML позволил выявить, что конструкция mem может быть использована для двух различных целей. Во-первых, она может использоваться для описания памяти моделируемого микропроцессора. В этом случае число ячеек памяти в описании довольно большое (N >> 1). Необходимо найти описание с максимальным числом ячеек, именно оно будет транслироваться в класс, моделирующий память. При трансляции данного описания создается класс ProcessorNameMemory, который является наследником абстрактного класса Memory из библиотеки поддержки трансляции. Класс ProcessorNameMemory имеет следующий вид: class ProcessorNameMemory { public static final SIZE = <N>; protected HashMap(Long, <type>) memoryHashMap = new HashMap(Long, <type>)(); } Для всех других описаний памяти, которые являются синонимами основной памяти (используют alias <имя основной памяти>), в атрибутах action для операций необходимо изменять обращения по этим именам на обращения по имени основной памяти. Второй класс описаний памяти составляют описания, которые имеют небольшое число ячеек (обычно 1 или 2). Такие описания используются в качестве локальных переменных при описании атрибутов action для инструкций. Все такие описания при трансляции запоминаются. Затем при трансляции атрибутов action в методы инструкций, для каждой запомненной памяти, по которой присутствует обращение в данном атрибуте, вводится локальная переменная соответствующего типа. Все обращения по данным элементам памяти заменяются при трансляции на обращения к данной переменной. Например, mem tmp_signed_byte [ 1 , int (32) ] … action = { tmp_signed_byte = 31 … } При трансляции атрибута action получаем получим: public void execute(...) { int tmp_signed_byte … } // TODO: определить абстрактный класс Memory Ошибочные ситуации: h3. Конструкция reg Конструкция reg используется для описания регистров микропроцессора. Общая форма описания регистров представлена ниже: reg R [N, type] [optional-properties] В представленном определении R – имя регистрового файла, N – опциональный параметр, показывающий количество регистров в регистровом файле и type – тип каждого регистра. Если параметр N не указан, то по умолчанию он полагается равным 1.Доступ к регистрам данного регистрового файла осуществляется посредством оператора индексирования — R[0], R[1], …, R[N-1]. Определение регистров может иметь следующие опциональные атрибуты: Ports: позволяет указать число портов чтения и записи для данного регистрового файла. Например: reg R[16, int(8)] port = 3, 2 В представленном примере регистровый файл R имеет 3 порта для записи и 2 порта для чтения. Кроме того, каждый регистр в данном регистровом файле имеет 2 порта для чтения, так же как и весь регистровый файл, и один порт для записи. Порты чтения и записи для регистров рассматриваются в качестве ресурсов и используются для определения зависимостей между инструкциями. Initial: позволяет указать начальное значение для описанных регистров. Например: reg R[1, card(32)] initial = 100 Правила грамматики для конструкции reg: RegisterSpec : REG ID ''['' SizeType '']'' OptionalRegAttr OptionalRegAttr : | PortsDef | InitialDef | PortsDef InitialDef | InitialDef PortsDef PortsDef : PORTS ''='' CARD_CONST '','' CARD_CONST InitialDef : INITIALA ''='' ConstNumExpr Примеры: reg GPR [2 ** REGS, signed_long] reg LO [1, signed_long] reg NIA [1, long] Проблемы: Ограничения: Трансляция: Для каждого описанного регистрового файла создается класс RegisterFileName, который является наследником абстрактного класса библиотеки поддержки трансляции Register. Класс Register содержит следующие поля и методы: class Register { public static final int WRITE_PORTS = 1; public static final int READ_PORTS = 1; ... } Класс RegisterFileName содержит следующие поля и методы: class RegisterFileName { public static final int READ_PORTS = <read_ports>; protected <type> value = <init_value>; ... } Так же в класс ProcessorName добавляются следующие поля и методы: public static final int RegisterFileName_WRITE_PORTS = <write_ports>; protected RegisterFileName <some_uniq_name> [] = { new RegisterFileName(), ... } Причем количество элементов в массиве RegisterFileName равно N. Ошибочные ситуации: h3. Конструкция var Конструкция var используется для определения временных переменных. Типичная конструкция определения временной переменной выглядит следующим образом: var TEMP[N, type] В приведенном выше определении TEMP – имя массива временных переменных, N – количество переменных в определенном массиве и type – тип каждой переменной в массиве. Если параметр N не определен, то по умолчанию он полагается равным 1. Доступ к переменным осуществляется посредством оператора индексирования — TEMP[0], TEMP[1], …, TEMP[N-1]. Важно отметить, что значения временных переменных не сохраняются при переходе от одной инструкции к другой. // COMMENT: по всей видимости переменные были введены в язык для прекращения нецелевого использования конструкций определения памяти для введения временных данных. Смотри второй класс конструкций определения памяти в разделе «трансляция» описания конструкции mem. Правила грамматики для конструкции var: // TODO: противоречие между текстовым описанием и грамматикой. VarSpec : VAR ID ''['' SizeType '']'' OptionalMemVarAttr Примеры: var amod[1, card(8)] var carry[1, card(1)] var op1[1, int(32)] Проблемы: Ограничения: Трансляция: Трансляция выполняется аналогично второму классу конструкций определения памяти. Описание приводится в разделе «трансляция» описания конструкции mem. Ошибочные ситуации: Конструкция mode Конструкция mode используется для спецификации механизмов адресации. Основу данного описания этих механизмов составляют два вида конструкций: «И»-правила и «ИЛИ»-правила. «ИЛИ»-правила используются для описания логически связанной группы механизмов адресации. С помощью «ИЛИ»-правила можно задать группе таких механизмов общие атрибуты. Общий вид «ИЛИ»-правила следующий: «И»-правила используются для описания листовых элементов в дереве механизмов адресации. Общий вид «И»-правила следующий: Правила грамматики для конструкции mode: ModeRuleSpec : MODE ID ModeSpecPart ModeSpecPart : AndRule OptionalModeExpr AttrDefList | OrRule OptionalModeExpr : | ''='' Expr Примеры: Проблемы: Ограничения: Трансляция: Трансляция дерева «И»-«ИЛИ» правил проводится идентично как для инструкций, так и для режимов адресации. Подробные описания общих концепций трансляции приведены в разделе «Трансляция» описания конструкции op. Эти положения верны и при описании режимов адресации. Специфические моменты при трансляции этих описаний отражены ниже. У и правил конструкции mode может присутствовать дополнительный опциональный элемент, который вычисляет значение параметра, передающегося данным способом адресации. Для каждого правила, обладающего таким элементом, в соответствующем классе создается тело метода getValue() на основе описания данного элемента. Метод возвращает оттранслированное выражение записанное в правиле после знака равенства. Ошибочные ситуации: h3. Конструкция op Конструкция op используется для описания системы команд моделируемого процессора. Правила грамматики для конструкции op: OpRuleSpec : OP ID OpRulePart OpRulePart : AndRule AttrDefList | OrRule Примеры: Проблемы: Ограничения: Трансляция: Общие положения при трансляции древовидной структуры «И»-«ИЛИ» правил заключаются в следующем. Для каждого правила создается класс. Классы, соответствующие элементам из правых частей «ИЛИ» правил связываются с классом, соответствующим элементу в левой части, отношением наследования. Каждый класс, соответствующий элементу из списка параметров в «И»-правиле, связывается с классом, соответствующим элементу из левой части правила, отношением агрегации. На примере ниже продемонстрированы данные принципы с использованием нотации UML для отображения зависимостей между классами. op instruction(inst alu_op) op alu_instruction = add | sub В каждом из этих классов создаются методы, соответствующие атрибутам. Механизм трансляции атрибутов подробно описан в разделе «Атрибуты». Имена создаваемых классов должны содержать некоторый служебный суффикс, что будет говорить о служебном внутреннем использовании данных классов. Для каждого элемента из списка параметров «И» правила в соответствующем классе создаются поле. Для класса также создается конструктор с сигнатурой, соответствующей данному правилу, который инициализирует эти поля. // TODO: посмотреть информацию про модификаторы доступа классов, пакетов для защиты служебных классов от некорректного использования. Далее, для каждого листового элемента в дереве инструкций создается еще один класс, который наследуется от класса Instruction (соответствует корню дерева). Эти классы распределяются по пакетам в соответствии со структурой дерева. Для каждого не листового узла дерева создается отдельный пакет, куда вложены все пакеты и классы, соответствующие потомкам данного узла. Ошибочные ситуации: