Зенин Мирон Александрович, Группа P33101
Вариант: forth | stack | neum | hw | tick | struct | trap | port | cstr | prob2
Без усложнения
<program> ::= <term>
<term> ::= <term> <term> |
<number> |
<sign-word> |
<comparator-word> |
<word> |
<system-word> |
<variable-operation> |
<word-def> |
<comment> <NL> |
<print-char-sequence> |
<for-cycle> | <do-while-cycle> | <if-statement>
<digit> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
<digit-sequence> ::= <digit>[<digit>]
<starting-digit> ::= <digit> \ 0
<number> ::= [-]<digit> | [-]<starting-digit><digit-sequence>
<sign-word> ::= + | - | / | *
<comparator-word> ::= <> | = | > | >= | < | <=
<word-possible-symbol> ::= <latyn> | -
<word> ::= <latyn> [<word-possible-symbol>]
<system-word> ::= [_]+ <word>
<word-or-system-word> ::= <word> | <system-word>
<variable-operation> ::= <word-or-system-word> [?&!] | <word-or-system-word> - <digit-sequence>
<contructive-term> ::= <term> \ <word-def>
<contructive-terms> ::= <contructive-term> | <contructive-term> <contructive-term>
<word-def> ::= ":"<word><contructive-terms>";"
<comment> ::= "\" <any-symbol-sequence>
<print-char-sequence> ::= "<any-symbol-seq-except-dq-and-NL>"
<cycle-term> ::= <contructive-term> | "leave"
<for-cycle> ::= do [i] <cycle-term> loop
<do-while-cycle> ::= begin <cycle-term> until
<if-statement> ::= if <contructive-term> [else <contructive-term>] thenКод выполняется последовательно, но за несколькими исключениями:
- на
loopиuntilв начало цикла в случае продолжения цикла - на
ifна терм послеelseв случае лжи и существования блокаelse, на терм послеthenв случае его существования или в случае истины после последнего терма внутри блокаif - на первый терм блока определения слова в случае использования пользовательского слова и на терм после него после последнего терма определения
Определения слов (<word-def>) имеют глобальную область видимости и не выполняются непосредственно,
остальные члены (<term>) (в том числе и внутри вызываемых слов) исполняются последовательно
В языке предусмотрены комментарии, которые начинаются с символа \ - все, что идет после него в строчке, игнорируется
Числа (в том числе отрицательные) кладутся на пользовательский стек
Знаковые операции выполняют действия над верхушкой пользовательского стека:
+- суммирует верхние элементы, вынимая их из стека, и пушит результат-- вычитает из нижнего элемента верхний/- деление нижнего на верхний*- их произведение
Знаки сравнения делают то же самое:
>- пушится 0 если нижний больше верхнего (оба вынимаются), иначе -1<- если нижний меньше верхнего=- при равенстве<>- при неравенстве>=- больше или равно<=- меньше или равно
Системное слово отличается от обычного тем, что оно предназначено для использования транслятором. Впрочем, ничего не запрещает вызывать его пользователю (но не определять)
Обычное слово, или слово, определяемое пользователем, производит вызов кода из определения слова (<constructive-terms>).
По окончании идет возврат в место вызова. Рекурсия разрешается
Определен ряд системных слов, выполняющих различные действия:
mod- пушится остаток от деления нижнего на верхний (польз. стек), оба вынимаются из стекаput- в нижнем должно находится число, которое кладется на место элемента, находящегося в N элементах ниже элемента под нижним элементом, где N - нижний элемент. Если N=0, то вместо того элемента (сразу после нижнего). Адрес и само число вынимаются из стекаput_absolute- нижний элемент используется как абсолютный адрес, нужно быть предельно аккуратным, потому что это дает доступ к памяти всей машиныpick- кладет на стек копию элемента, находящегося в N элементах ниже нижнего элемента, где N - верхний элемент. Адрес вынимается из стекаpick_absolute- верхний элемент используется как абсолютный адресswap- меняет местами верхний и нижний элементыdrop- вытаскивает верхний элемент со стекаdup- кладет на стек копию верхнего элементаdudup- кладет на стек нижний, а затем и бывший верхний элементы
Ряд системных слов, выполняющих работу с вводом-выводом:
emit- в основной порт кладется значение с вершины пользовательского стека (вытаскивается), флаг непрочитанного девайсом вывода со стороны процессора устанавливается в 0cant_emit- на стек кладется флаг нулевого (основного) порта, равный 0 в случае непрочитанного девайсом вывода со стороны процессора и -1 если вывод процессора был считанkey- на пользовательский стек кладется значение с основного порта, флаг непрочитанного процессором вывода со стороны девайса устанавливается в -1has_input- на стек кладется флаг нулевого (основного) порта, равный 0 в случае непрочитанного процессором вывода со стороны дейвайса
Ряд системных слов, участвующих в организации переходов / выполняющих переходы:
Открывающие:
do- начало цикла, использует верхний элемент в качестве начального значения и нижний - в качестве конечного (искл). Эти значения вынимаютсяdoi- то же самое, но теперь в начале на стек кладется текущее значение этого счетчикаbegin- метка начала цикла while, ничего сама по себе не делаетif- вытаскивает верхний элемент, при равенстве его 0 выполняет термы из блокаif, игнорируя затем термы из блокаelse(если таковой есть), при неравенстве же делает ровно наоборот
Переходные:
else- обозначает конец блокаifи начало блокаelseleave- покидает ближайший по иерархии цикл (начинает исполнение термов после него)
Закрывающие:
then- обозначает конец блокаelseили блокаif(При отсутствии блокаelse)until- вытаскивает верхний элемент, при равенстве его 0 продолжает исполнение с терма после соответствующего ему в иерархииbegin, иначе исполнение продолжается со следующего послеuntilтермаloop/mloop- увеличивает / уменьшает счетчик и сравнивает его с конечным элементом. В случае неравенства исполнение продолжается с соответствующего в иерархии термаdo/doi, иначе - со следующего послеloop/mloopтерма
Переменные сохраняются в памяти данных, причем, так как они глобальные, место для них выделяется при запуске. Место выделяется так, чтобы поместился самый крупный элемент (например, в одном месте variable-10, в другом - variable-8, будет выделена память для 10-элементного массива для переменной с таким именем).
Описание семантики переменных:
variable!- вытаскивает верхний элемент, записывая его по адресу, где лежит первое значение переменной (оговорка важна для случая с массивами)variable?- кладет на стек первое значение переменнойvariable&- кладет на стек абсолютный адрес первого значения переменнойvariable-N- выделяет память в памяти данных для N элементов
Любое упоминание переменной в первых трех случаях означает обязательное выделение памяти для 1 элемента
На данном этапе следует сказать, что использование пользовательских слов доступно отовсюду, как и обращение к глобальным переменным
Есть специальные слова, которые при трансляции раскладываются в код, который мог бы написать и пользователь, пока что оно только одно: print_string
Его код:
_string_pointer!
begin
_string_pointer? pick_absolute
dup
if
drop
leave
then
begin
cant_emit
0 = until
emit
_string_pointer? 1 + _string_pointer!
0 untilСистемные переменные используются в трансляторе - тут _string_pointer, их использование не рекомендуется ввиду того, что память может быть испорчена неожиданным раскрытием специального слова внутри транслятора
Двойные кавычки с последовательностью символов внутри - отдельный вопрос. В начало программы вставляется код выделения памяти для таких строк и вставки - таким образом при "заходе" в код пользователя мы имеем уже выделенные и заполненные строки в виде переменных-массивов. Важно, что учитывается уникальность - одной и той же строке, упомянутой в нескольких местах, соответствует она область в памяти.
Какая последовательность вставляется в начало программы:
_string_{индекс}-{длина строки + 1 (для 0 обозначающего конец строки)}
_string_{индекс}& _string_pointer!После идет повторяющийся код вставки всех символов из последовательности:
{код очередного символа}
_string_pointer? put_absolute
_string_pointer? 1 + _string_pointer!А затем:
0 _string_pointer? put_absoluteВ месте использования строки:
_string_{индекс}& print_stringВ конце идет раскрытие кода из специального слова print_string
Таким образом идет сохранение строкового литерала в память данных, а в местах использования - вывод такой нуль-терминированной строки
Числовой литерал ограничен 56 битовым числом aka long в языке Java
Память данных и команд не разделяется
Машинное слово - 64 бита, знаковое. Линейное адресное пространство. Реализуется списком чисел
Команды помещаются с учетом того, что 8 бит уйдет на кодирование команды, а остальные 56 - на ее аргумент, если предусмотрено.
Внутри же машины это объекты python с неопределенным размером (Instruction), есть еще дополнительные данные, необходимые для ведения логов
Память выглядит так (последовательно с 0 адреса):
- Инструкции прерываний портов - сначала на запись в порт от процессора, затем на чтение девайсом порта (первым идет порт 0, потом 1 и т.п.)
- Таблица указателей на начала наборов инструкций прерываний портов в том же порядке
- Память переменных (в том числе строковые литералы в виде массивов)
- Инструкции исполняемой программы. Указатель на текущую операцию при запуске ставится именно первую инструкцию программы
- Пользовательский стек, растущий вверх
- Служебный стек, растущий вниз
Статическая память это память переменных, в качестве динамической используется пользовательский стек
Косвенную адресацию используется неявно системными словами, участвующими в организации переходов / выполняющими переходы, упомянутые ранее, а еще она используется при вызове пользовательских слов и выходе из таких блоков.
Также ее используют команды (одноименные инструкции) put и pick
Абсолютная адресация неявно используется для доступа к переменным.
Также ее используют команды (одноименные инструкции) put_absolute и pick_absolute
Ввиду наличия команд put_absolute и pick_absolute программист может получить доступ (в том числе изменение) к любой ячейке памяти
Явного доступа к регистрам не предусмотрено, хотя они и задействуются при работе программы.
Описание регистров:
VarDataStartPoint- указатель на начало статической памяти, используется для организации косвенной адресации при обращении к переменным - и правда, на этапе компиляции мы можем определить лишь сдвиг относительно этой точки, а не абсолютный адрес, так как мы не знаем, сколько памяти потребуется на инструкции прерыванийIP- указатель на исполняющуюся в данный момент инструкциюPRA_SHP- указатель на вершину служебного стекаOD_SHP- указатель на вершину пользовательского стекаinstruction_stage_number- тик инструкции, исполняющийся в данный моментtop- верхний элемент пользовательского стека, есть гарантия соответствия после исполнения любой инструкцииnext- нижний, та же гарантия- Специальный бит, обозначающий состояние прерывания (активно / не активно)
Прерывания организованы так, что при нахождении в прерывании прерывания игнорируются. Если же прерывание возможно, то бит прерывания устанавливается в активное состояние и происходит следующее:
- На служебный стек кладется IP
- На служебный стек кладется тик
- Читается нужная строка таблицы прерываний и помещается в IP
- тик устанавливается в 1
Предположительно это происходит за 3 тика (минимальная оценка ввиду тройного доступа к памяти).
Так как каждая компилируемая программа оканчивается инструкцией halt (это делает транслятор), она интерпретируется в контексте прерывания несколько иначе: происходит выход из прерывания, а именно восстановление этих регистров из стека (предположительно за 2 тика ввиду 2 доступов в память)
Числовые литералы помещаются сначала в пользовательский стек, а затем, по желанию, возможно поместить их в переменную или на любую позицию переменной не единичного размера, что, однако, ввиду использования абсолютной адресации требует осторожности, так как выход за пределы никак не обрабатывается
Строковые литералы представляются в памяти в качестве массивов кодов символов с 0 в конце строки
- Проверка на прерывание
- Заходим в прерывание (дальше не идем) или Выборка инструкции (предположительно 1 тик)
- Исполнение инструкции
У каждого порта есть 64-битный регистр данных, битные регистры вида активен / неактивен, обозначающие состояние после вставки - от девайса и от процессора
Инструкции ввода-вывода манипулируют этими регистрами
Некоторые команды переводятся в соответствующие инструкции, поэтому у них комментария не будет - он будет в описании инструкции
Здесь верхний - top, а нижний - next
| Язык | Инструкция | Кол-во тактов | Описание |
|---|---|---|---|
| number | 1 | arg кладется на пользовательский стек |
|
| + | sum | 2 | суммирует верхние элементы, вынимая их из стека, и пушит результат |
| - | diff | 2 | вычитает из нижнего элемента верхний |
| / | div | 2 | деление нижнего на верхний |
| * | mul | 2 | их произведение |
| > | gr | 2 | пушится 0 если нижний больше верхнего (оба вынимаются), иначе -1 |
| < | less | 2 | если нижний меньше верхнего |
| = | eq | 2 | при равенстве |
| <> | neq | 2 | при неравенстве |
| >= | ge | 2 | больше или равно |
| <= | le | 2 | меньше или равно |
| mod | mod | 2 | пушится остаток от деления нижнего на верхний (польз. стек), оба вынимаются из стека |
| put | put | 2 | в нижнем должно находится число, которое кладется на место элемента, находящегося в N элементах ниже элемента под нижним элементом, где N - нижний элемент. Если N=0, то вместо того элемента (сразу после нижнего). Адрес и само число вынимаются из стека |
| put_absolute | put_absolute | 2 | нижний элемент используется как абсолютный адрес |
| pick | pick | 2 | кладет на стек копию элемента, находящегося в N элементах ниже нижнего элемента, где N - верхний элемент. Адрес вынимается из стека |
| pick_absolute | pick_absolute | 2 | верхний элемент используется как абсолютный адрес |
| swap | swap | 2 | меняет местами верхний и нижний элементы |
| drop | shift_back | 1 | вытаскивает верхний элемент со стека |
| dup | dup | 1 | кладет на стек копию верхнего элемента |
| dudup | dudup | 2 | кладет на стек нижний, а затем и бывший верхний элементы |
| - | write_port | 1 | в порт под индексом arg кладется значение с вершины пользовательского стека (вытаскивается), флаг непрочитанного девайсом вывода со стороны процессора устанавливается в 0 |
| emit | write_port 0 | 1 | кладется в порт под индексом 0 |
| - | has_port_filled_with_cpu | 1 | на стек кладется флаг порта под индексом arg, равный 0 в случае непрочитанного девайсом вывода со стороны процессора и -1 если вывод процессора был считан |
| cant_emit | has_port_filled_with_cpu 0 | 1 | кладется флаг порта под индексом 0 |
| - | read_port | 1 | на пользовательский стек кладется значение порта под индексом 0, флаг непрочитанного процессором вывода со стороны девайса устанавливается в -1 |
| key | read_port 0 | 1 | кладется из порта под индексом 0 |
| - | has_port_filled_with_device | 1 | на стек кладется флаг порта под индексом arg, равный 0 в случае непрочитанного процессором вывода со стороны дейвайса |
| has_input | has_port_filled_with_device 0 | 1 | кладется флаг порта под индексом 0 |
| - | pop_to_ret | 1 | вынимает из стека пользователя и кладет в служебный стек |
| do | swap pop_to_ret pop_to_ret | 2 + 1 + 1 = 4 | начало цикла, использует верхний элемент в качестве начального значения и нижний - в качестве конечного (искл). Эти значения вынимаются |
| - | push_to_od | 3 | копируем со служебного стека и кладем на стек пользовательский |
| doi | do push_to_od | 4 + 1 = 5 | то же самое, но теперь в начале на стек кладется текущее значение этого счетчика |
| begin | - | - | метка начала цикла while, ничего сама по себе не делает |
| - | if_exec | 1 | вытаскивает верхний элемент, при равенстве его 0 перепрыгивает следующую инструкцию, иначе следующая инструкция выполняется |
| - | jmp | 1 | к IP добавляется arg |
| if | if_exec jmp | 1 + 1 = 2 | Если на стеке лежит не 0, то будет выполнен jmp на блок else, иначе jmp пропускается и будет выполняться блок if |
| else | jmp | 1 | jmp указывает на команду сразу после then, на команду после jmp |
| leave | jmp | 1 | jmp указывает на команду сразу после цикла по текущей иерархии |
| then | - | - | обозначает конец блока else или блока if (При отсутствии блока else) |
| - | exec_cond_jmp | 1 | вытаскивает верхний элемент, если он 0, то переходим к следующей команде, иначе IP += arg + 1 |
| until | number(0) neq exec_cond_jmp | 1 + 2 + 1 = 4 | если верхний элемент истинный, то продолжаем крутиться в цикле |
| - | inc/decrement_ret | 3 | вершина служебного стека увеличивается / уменьшается на 1 |
| - | eq_not_consuming_ret | 3 | на служебный стек кладется 0 в случае равенства головы и следующего элемента служ. стека и -1 в случае неравенства |
| - | exec_cond_jmp_ret | 1 | со служебного стека снимается элемент, если не 0, то прыжок IP += 1 + arg, иначе продолжим со следующей инструкции |
| - | shift_back_ret | 3 | со служебного стека снимается элемент |
| loop / mloop | inc/decrement_ret eq_not_consuming_ret exec_cond_jmp_ret shift_back_ret(x2) | 3 + 3 + 1 + 3*2 = 13 | если верхний элемент истинный, то продолжаем крутиться в цикле |
| variable! | write_vardata | 2 | вытаскивает верхний элемент, записывая его по адресу, где лежит первое значение переменной (оговорка важна для случая с массивами) |
| variable? | read_vardata | 2 | кладет на стек первое значение переменной |
| sum_top_with_vdsp | sum_top_with_vdsp | 1 | суммирует верхний элемент с адресом начала статики |
| variable& | number sum_top_with_vdsp | 1 + 1 = 2 | кладет на стек абсолютный адрес первого значения переменной |
| variable-N | - | - | выделяет память в памяти данных для N элементов |
| - | halt | - | завершение программы (или, в случае прерывания, выход из прерывания) |
| :word | - | - | начало блока определения слова |
| ; | jmp_pop_pra_shp | 2 | прыжок на вытащенное из служебного стека значение IP |
| - | push_inc_inc_to_pra_shp | 1 | кладет на служебный стек IP + 1 + 1, то есть пропускаем следующую инструкцию |
| word | push_inc_inc_to_pra_shp jmp | 1 + 1 = 2 | кладем на стек адрес следующей команды, прыгаем в тело определения слова |
- Машинный код сериализуется в список JSON.
- Один элемент списка -- одна инструкция.
- Индекс списка -- адрес инструкции. Используется для команд перехода.
Пример:
[
{
"opcode": "number",
"arg": 123,
"term": {
"line_number": 1,
"line_position": 5,
"name": "123"
}
}
]где:
opcode- строка с кодом операции;arg- аргумент (при отсутствии надобности вnull);term- информация о связанном месте в исходном коде (если есть).
Типы данных в модуле isa, где:
Opcode- перечисление кодов операций;Term- структура для описания значимого фрагмента кода исходной программы.
Интерфейс командной строки: translator.py <input_file> <target_file>
Реализовано в модуле: translator
Этапы трансляции (функция translate):
- Трансформирование текста в последовательность значимых термов.
- Проверка корректности программы (парность квадратных скобок).
- Разложение спец-термов
- Генерация машинного кода.
Правила генерации машинного кода:
- одна команда может быть отображена во множество инструкций, а может и не быть отображена вовсе (e.g.
begin) - для команд, однозначно соответствующих инструкциям - прямое отображение;
- с соблюдением парности: каждому
beginдолжен соответствовать свойuntil, причем на своем уровне вложенности, это касается иdo[i]сloop, а такжеif[else]then
Интерфейс командной строки: machine.py <code_file> <input_file> <emit-port-interruption-handler> <key-port-interruption-handler> [<output-port-interruption-handler> <input-port-interruption-handler]*
Первые два файла содержат обработчики для основного (0 индекс) порта, поэтому они должны обязательно присутствовать
Реализовано в модуле: machine
Реализован в классе DataPath.
data_memory - однопортовая память, поэтому либо читаем, либо пишем
Сигналы (обрабатываются за один такт, реализованы в виде методов класса):
latch_ip- защелкнуть выбранное значение вIPlatch_od_shp- вOD_SHPlatch_pra_shp- вPRA_SHPlatch_top- вTOPlatch_next- вNEXTlatch_memory_data- в памятьsignal_increment_instruction_stage_number- увеличенный на 1isnвisnsignal_reset_instruction_stage_number- 1 вisnlatch_port_flags- флаги порта (индекс вarg)latch_port_value- значение портаlatch_is_in_interruption- состояние прерывания
Реализован в классе ControlUnit.
- Hardwired (реализовано полностью на Python).
- Метод
next_tick_executeмоделирует выполнение тика инструкции (такта процессора). - instruction_stage_number необходим для многотактовых инструкций
Особенности работы модели:
- Цикл симуляции осуществляется в функции simulation.
- Шаг моделирования соответствует одному такту с выводом состояния в журнал.
- Для журнала состояний процессора используется стандартный модуль logging.
- Количество инструкций для моделирования лимитировано.
- Остановка моделирования осуществляется при:
- превышении лимита количества выполняемых инструкций;
- исключении StopIteration -- если выполнена инструкция halt вне прерывания.
В качестве тестов использовано четыре алгоритма:
- alice
- cat
- hello-world
- prob1
Интеграционные тесты реализованы в модуле integration_test в виде golden тестов:
CI при помощи Github Action:
name: Translator Model Python CI
on:
push:
branches:
- main
paths:
- ".github/workflows/*"
- "./**"
pull_request:
branches:
- main
paths:
- ".github/workflows/*"
- "./**"
defaults:
run:
working-directory: .
jobs:
test:
runs-on: ubuntu-latest
steps:
- name: Checkout code
uses: actions/checkout@v4
- name: Set up Python
uses: actions/setup-python@v4
with:
python-version: 3.11
- name: Install dependencies
run: |
python -m pip install --upgrade pip
pip install poetry
poetry install
- name: Run tests and collect coverage
run: |
poetry run coverage run -m pytest .
poetry run coverage report -m
env:
CI: true
lint:
runs-on: ubuntu-latest
steps:
- name: Checkout code
uses: actions/checkout@v4
- name: Set up Python
uses: actions/setup-python@v4
with:
python-version: 3.11
- name: Install dependencies
run: |
python -m pip install --upgrade pip
pip install poetry
poetry install
- name: Check code formatting with Ruff
run: poetry run ruff format --check .
- name: Run Ruff linters
run: poetry run ruff check .где:
poetry- управления зависимостями для языка программирования Python.coverage- формирование отчёта об уровне покрытия исходного кода.pytest- утилита для запуска тестов.ruff- утилита для форматирования и проверки стиля кодирования.
Пример проверки исходного кода:
$ poetry run pytest . -v ✔ forthchan
====================================================================================================================================================================================================== test session starts =======================================================================================================================================================================================================
platform linux -- Python 3.11.7, pytest-7.4.4, pluggy-1.4.0 -- /home/imperator/Documents/university/labs/arch-comp/forthchan/venv/bin/python
cachedir: .pytest_cache
rootdir: /home/imperator/Documents/university/labs/arch-comp/forthchan
configfile: pyproject.toml
plugins: golden-0.2.2
collected 4 items
integration_test.py::test_translator_and_machine[golden/cat.yml] PASSED [ 25%]
integration_test.py::test_translator_and_machine[golden/hello_world.yml] PASSED [ 50%]
integration_test.py::test_translator_and_machine[golden/prob2.yml] PASSED [ 75%]
integration_test.py::test_translator_and_machine[golden/alice.yml] PASSED [100%]
======================================================================================================================================================================================================= 4 passed in 1.03s ========================================================================================================================================================================================================
$ poetry run ruff check . ✔ forthchan
$ poetry run ruff format . ✔ forthchan
4 files left unchanged| ФИО | алг | LoC | code байт | code инстр. | инстр. | такт. | вариант |
| Зенин Мирон Александрович | alice | 17 | - | 350 | 1502 | 2280 | forth | stack | neum | hw | tick | struct | trap | port | cstr | prob2 |
| Зенин Мирон Александрович | cat | 47 | - | 80 | 1336 | 1336 | forth | stack | neum | hw | tick | struct | trap | port | cstr | prob2 |
| Зенин Мирон Александрович | hello | 1 | - | 116 | 399 | 621 | forth | stack | neum | hw | tick | struct | trap | port | cstr | prob2 |
| Зенин Мирон Александрович | prob2 | 62 | - | 126 | 1760 | 2636 | forth | stack | neum | hw | tick | struct | trap | port | cstr | prob2 |



