Simple language compiler

Ниже представлена грамматрика языка. Нетерминальные символы зыключены к двойные ковычки ", за исключение выражения, описывающего STR, там они заключены в одинарные ковычки '. Символ ANY означет любой символ.

S       ->    L {L}
L       ->    (A | I | C) {BLANK} ";"
A       ->    "print" (STR | NUM | ID)
I       ->    ["int"] ID "=" E
C       ->    "str" ID "=" STR
E       ->    T | E LBINOP T
T       ->    F | T HBINOP F
F       ->    "read" | ID | NUM | "(" E ")"
STR     ->    '"' {ANY}/{'"'} '"'
NUM     ->    ["-"] digit {digit}
ID      ->    char {char | "_" | digit}
char    ->    "a" | ... | "z" | "A" | ... | "Z"
digit   ->    "0" | ... | "9"
LBINOP  ->    "+" | "-"
HBINOP  ->    "*" | "/" | "%"
BLANK   ->    " " | "\t" | "\n"

В языке предусмотрена возможность записывать комментарии. Для этого перед комментарием необходимо написать #. Тогда лексический анализатор проигнорирует все символы после # до символа переноса строки.

Пример кода:

#Считываем целое число и записываем в x
print "Введите значение x";
int x = read;
#Считываем целое число и записываем в y
print "Введите значение y";
int y = read;
#Выполняем некоторое выражение
int z = x * y;
#Печатаем результат
print z;

Лексический анализатор

Лексический анализатор разбивает входной тексовый файл на список токенов, игнорируя все незначащие символы \t, \n, " ". Токен имеет три параметра: type, line и union {str, num}. Типы токенов:

• ID - идентификатор

• KWORD - ключевое слово

• LBRC - открывающая скобка

• RBRC - закрывающая скобка

• BINOP - бинарная операция +-=*/%

• NUM - целое число

• STR - строка

• SCLN - символ ;

• TEND - конец токенов

Для токенов ID и STR задается праметр str, а для NUM параметр num. Далее полученный список токенов скармливается синтаксическому анализатору.

Синтаксический анализатор

Синтаксический анализ языка довольно прост. Каждое выражение L должно начинаться с одного из следующих символов ID, "print", "int". Поэтому можно сразу определить какие символы должны стоять дальше. Заканчиваться любое выражение L должно символом ;. Проблема возникает при анализе арифметических выражений. Для них был использован конечный автомат.

Здесь под BINOP подразумевается {BINOP}/{"="}, а под READ - KWORD: "read". Слово init указывает на точку входа в автомат, а exit - на точку выхода.

Семантический анализатор

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

• char **strings - массив ссылок на все строки, которые встречаются в коде;

• unsigned max_depth - максимальная глубина в выражениях, чтобы знать сколько регистров понадобится;

• unsigned num_of_strings - кол-во строк (тип str) в коде;

• unsigned num_of_ints - кол-во переменных типа int;

• unsigned num_of_instructions - кол-во инструкций типа struct Instr;

• struct Instr *instructions - указатель на инструкции.

Все эти данные собраны в структуру ForGenerator.

Генератор кода

Генерирует ассемблер для процессора risc-v. Принимает на вход struct ForGenerator и название файла, в который нужно будет записывать генерируемы код. Имеет ограничения. Максимальное кол-во переменных не должно превышать 485 штук. Данное число получено следующим образом: (2048 - 12 + 1) * 8 - 4 / 4 = 485. Здесь 12 - кол-во регистров s0-s11, которые хранятся в стеке с выравниваем в 8 byte, к ним прибавляется еще регистр ra. 4 byte занимают записываемые слова (то есть переменные), поэтому делим на 4. Так же 4 байта в стеке резервируются для функции read, результат ее работы всегда записывается в регистр sp + 0, потом переносится в необходимое место. 2048 - максимальное значение которое можно использовать в команде addi для перемещения по стеку. Каждое аримфетическое выражение переводится в обратную польскую нотацию. Есть ограничея на глубину такого выражения - 18 (кол-во используемых регистров) переменных и чисел идущих подряд без операций.

Сборка проекта

Для сборки проекта необходимо выполнить следующие действия:

• Шаг 1. git clone https://github.com/Hiraev/Compiler

• Шаг 2. cd Compiler

• Шаг 3. cmake .

• Шаг 4. make

• Шаг 5. mv mh-compiler tools

• Шаг 6. Скачать SiFive GNU Embedded Toolchain

• Шаг 7. Распаковавать скаченный файл

• Шаг 8. Переместить все файлы из полученной директории в директорию compiler/riscv

После всех проделанных шагов директория tools должна содержать следующие файлы:

• tools/mh-compiler

• tools/mh-driver

• tools/README.MD

• tools/riscv/README.MD

• tools/riscv/bin

• tools/riscv/include

• tools/riscv/lib

• tools/riscv/libexec

• tools/riscv/riscv64-unknown-elf

• tools/riscv/share

Для запуска компиляции необходимо запустить утилиту mh-driver. Можно указать в качестве опции ключ --save-temps, чтобы сохранить промежуточные .s - файлы. Ключ необходимо указывать первым. За ним идут названия файлов, которые необходимо скомпилировать, разделенные пробелеми. При успешной компиляции будет выведено сообшение Файл {$file} успешно скомпилирован или Не удалось скомпилировать файл {$file}, если возникла какая-то ошибка. В результате компиляции получатся исполняемые файлы с таким же названием, но с расширением .out.

Требование к входной программе

Грамматика языка была описана выше.

Программа должна соответсвовать синтаксису языка.

Названия переменных

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

Объявление строк

Объявив строку, ее необходимо тут же и инициализировать. Синтаксис следующий str {name} = "String"; Максимальная длина строки - 64 символа.

Объявление целочисленных переменных

Числа так же, как и строки необходимо сразу же инициализировать. Синтаксис следующий int {name} = {Expression};. Expression - выражение любой длины в форме инфиксной записи, разрешено использовать числа, переменные, которые были уже объявлены и ключевое слово read, которое запрашивает ввод у пользователя. Разрешено использовать круглые скобки для выделения приоритета операций. Разрешенные операции: +, -, *, /, %.

В выражениях знак -, может означать как вычитание, так и отрицательное числа. Если между знаком "минус" и числом нет пробела, то такая запись будет интерпритирована как отрицательное число.

Печать

Печатать можно как строки, так и числа. После ключевого слова print идет либо название переменной, либо число, либо строка.

Ограничения

• Максимальная длина строк и названий перемнных - 64

• Максимальная глубина выражение в ОПН - 18

• Максимальное кол-во переменных числового типа - 485