Заметка Разрабатываем свой компилятор на ассемблере. Лексер

[Gemfory]

Разработка собственного компилятора -это, пожалуй, самая нетривиальная задача, которую может поставить перед собой системный программист, тем более на ассемблере.
Как минимум для меня - это создание инструмента, который сам порождает программы. В нашем случае мы отказываемся от использования тяжеловесных фреймворков вроде
LLVM.

Введение
1. Первый этап этого конвейера - Лексер, или лексический анализатор. Он должен превратить сырой поток символов из исходного файла в упорядоченную последовательность токенов. Процессору абсолютно всё равно, сколько пробелов вы поставили между числами или как назвали свою переменную, поэтому лексер съедает лишние отступы, распознает числа, операторы и идентификаторы, присваивая каждому свой уникальный тип. На выходе мы получаем компактный буфер в памяти, где вместо тяжелых строк лежат легкие 16-байтовые структуры, с которыми на следующих этапах будет максимально удобно работать через регистры x86_64. В этой части мы как раз таки и займемся написанием лексера.
2. Вторая часть - это Парсер, или синтаксический анализатор. Он берет список токенов и проверяет, имеют ли они смысл в данной последовательности: например, два плюса подряд или число сразу после закрывающей скобки должны вызывать немедленную ошибку компиляции. Именно здесь реализуется логика приоритетов операций, чтобы ваш компилятор понимал, что умножение выполняется раньше сложения. Для этого часто используют алгоритм сортировочной станции Эдсгера Дейкстры или строят дерево абстрактного синтаксиса (AST), где узлами являются операции, а листьями - конкретные значения.
3. Третьим важным компонентом является Таблица символов, которая служит оперативной памятью для самого компилятора во время сборки. Когда в коде встречается объявление переменной, компилятор не может просто забыть её имя; он должен записать его в таблицу, связать с определенным типом данных и выделить под неё смещение в стеке или адрес в секции данных. При каждом последующем обращении к этой переменной парсер будет стучаться в эту таблицу, чтобы проверить, была ли она объявлена ранее и какой объем памяти (byte, word, dq) нужно зарезервировать для операций с ней.
4. Четвертвый этап - это семантический анализ, где проверяется логическая связность программы. На этой стадии компилятор убеждается, что вы не пытаетесь сложить строку с числом или передать в функцию три аргумента, когда она ожидает только два.
5. Пятый этап - так называемый Backand этап. Мы превращаем наше дерево вычислений в реальные байты машинных инструкций вроде MOV, ADD, SUB и CALL. Мы можем пойти двумя путями: либо генерировать текстовый файл с ASM-кодом, который потом соберет FASM, либо с JIT, но, про это в следующих статьях.

Завершающий этап - это компоновка и формирование исполняемого файла формата PE (Portable Executable) для Windows. Сам компилятор разрабатывается конкретно под Windows.
Нужно будет вручную сформировать заголовки DOSи PE, прописать секции кода (.text), данных (.data) и, самое главное, таблицу импорта (.idata), чтобы наша скомпилированная программа могла вызывать системные функции вроде ExitProcess или printf.

Начинаем разработку минимальнного арифметического лексера.

rsi - курсор по исходнику
r12 - курсор по буферу токенов
r13 - временный указатель для вывода
rbx - аккумулятор для чисел

Вместо того чтобы пытаться охватить всё выражение разом, мы создаем курсор, который передвигается по исходному коду символ за символом.
Компилятору плевать на человеческую эстетику: лишние пробелы, табуляции и переносы строк должны нещадно отсекаться еще до того, как логика анализатора начнет классифицировать символы.
С точки зрения реализации это банальный cmp al, 20h с последующим переходом, но без этого костыля вся дальнейшая обработка чисел и идентификаторов просто превратится в бесконечный поток ошибок

next_char:
    movzx eax, byte [rsi]
    test al, al
    jz compilation_end

    cmp al, ' '
    je skip_char
    cmp al, 9
    je skip_char
    cmp al, 10
    je skip_char
    cmp al, 13
    je skip_char

    cmp al, '0'
    jb .check_letters
    cmp al, '9'
    ja .check_letters
    call parse_number
    jmp next_char

skip_char:
    inc rsi
    jmp next_char

Суть проста: регистр rsi выступает в роли указателя, который перебирает каждый байт исходного текста.
Сначала идет проверка на нулевой байт через test al, al. Если он найден, работа лексера завершается и управление уходит на метку compilation_end.
Далее следует блок фильтрации. Команды cmp и je отсекают пробелы, табуляцию (9) и символы переноса строки (10, 13). Если текущий байт пустой, срабатывает skip_char, указатель rsi инкрементируется, и цикл начинается заново.
Если под курсором оказался значащий символ, программа проверяет его принадлежность к цифрам. Сравнение cmp al, '0' и cmp al, '9' определяет границы диапазона в таблице ASCII. Если байт является цифрой, вызывается процедура parse_number, которая конвертирует текст в реальное число. После обработки числа управление возвращается в начало цикла для поиска следующего токена.

Для хранения результатов сканирования мы выделяем область памяти под названием tokens_buffer. В секции данных это выглядит как директива rq 500. Мы резервируем 500 квадвордов, чего с запасом хватит для разбора среднего арифметического выражения. Каждая запись о токене будет занимать фиксированное место, что позволит нам в будущем обращаться к любому элементу через простые смещения в регистрах.
Сам исходный текст лежит в переменной source_code, в нем находится математический пример, который наш лексер будет разбивать на токены.

parse_number:
    xor rbx, rbx         
.digit_loop:
    movzx eax, byte [rsi]
    sub al, '0'
    imul rbx, 10
    add rbx, rax
    inc rsi
    movzx eax, byte [rsi]
    cmp al, '0'
    jb .done
    cmp al, '9'
    jbe .digit_loop
.done:
    mov qword [r12], 1   
    mov qword [r12+8], rbx
    add r12, 16
    ret

Теперь стоит разобрать логику процедуры parse_number. Она выполняет математическое преобразование текстовых символов в реальное число. Внутри используется регистр rbx в роли аккумулятора. Когда мы находим первую цифру, мы вычитаем из ее ASCII кода значение 48 или символ 0 чтобы получить чистое число. Каждая следующая цифра заставляет нас умножить текущий rbx на 10 и прибавить к нему новый разряд. Цикл работает до тех пор, пока под курсором rsi находятся цифры.
Непосредственно после расчетов резуьлтат нужно надежно куда-то сохранить, для этого используется регистр r12, который всегда указывает на свободную ячейку в буфере токенов. Мы посто записываем в первую половину ячейки константу 1, которая обозначаеет тип Число, а вторую половину ладем накопленное в rbx значение.
Если проверка на цифру не сработала, программа прыгает на метку check_letters. Это точка входа для распознавания имен переменных и математических знаков. Здесь применяется похожий принцип: лексер ищет совпадения в таблице символов или проверяет принадлежность байта к алфавиту:

.check_letters:
    cmp al, 'A'
    jb .not_cap
    cmp al, 'Z'
    jbe .is_ident
.not_cap:
    cmp al, 'a'
    jb .not_low
    cmp al, 'z'
    jbe .is_ident
.not_low:
    cmp al, '_'
    je .is_ident
 
    jmp check_operators

.is_ident:
    call parse_identifier
    jmp next_char

parse_identifier:
    mov qword [r12], 6  
    mov qword [r12+8], rsi
.ident_loop:
    inc rsi
    movzx eax, byte [rsi]
    cmp al, '0'
    jb .check_alpha
    cmp al, '9'
    jbe .ident_loop
.check_alpha:
    cmp al, 'A'
    jb .check_low
    cmp al, 'Z'
    jbe .ident_loop
.check_low:
    cmp al, 'a'
    jb .check_underscore
    cmp al, 'z'
    jbe .ident_loop
.check_underscore:
    cmp al, '_'
    je .ident_loop
.done:
    add r12, 16
    ret

Важно, у нас еесть нкекая база символов, которые понимает лексер:

По сути мы подготовили словарь, с помощью которого программа будет объяснять нам, что именно она нашла в исходном коде. Каждая такая строка привязана к конкретному идентификатору типа из нашего буфера токенов.
Здесь заложена вся будущая грамматика языка. Да и здесь не только арифметика.. но и сложные операторы сравнения вроде == или !=, логические связки и битовые сдвиги.
Если же задать вопрос: как все это проверяется? Если ли определенная метка, то да, - visual_loop

Программа берет из буфера первый квадворд (тип токена) и начинает серию сравнений через команды cmp. Если в регистре единица, значит это число и мы прыгаем на метку .p_num. Если двойка - это плюс и мы уходим на .p_plus.
Каждая такая метка это точка входа для подготовки данных к выводу. Внутри метки мы загружаем адрес нужной строки из секции данных в регистр rcx. Например, для числа мы берем адрес str_num, а для идентификатора - str_ident.

.start_visual:
    lea rcx, [header2]
    call [printf]
    lea r13, [tokens_buffer]
.visual_loop:
    cmp r13, r12          
    jae .finish
    mov rbx, [r13]    
    mov rdx, [r13+8]  
    cmp rbx, 1        
    je .p_num
    cmp rbx, 2        
    je .p_plus
    cmp rbx, 3        
    je .p_minus
    cmp rbx, 4        
    je .p_mul
    cmp rbx, 5        
    je .p_div
    cmp rbx, 6
    je .p_ident
    cmp rbx, 7
    je .p_lparen
    cmp rbx, 8
    je .p_rparen
    cmp rbx, 9
    je .p_assign
    cmp rbx, 10
    je .p_colon_assign
    cmp rbx, 11
    je .p_eq
    cmp rbx, 12
    je .p_neq
    cmp rbx, 13
    je .p_lt
    cmp rbx, 14
    je .p_gt
    cmp rbx, 15
    je .p_lte
    cmp rbx, 16
    je .p_gte
    cmp rbx, 17
    je .p_and
    cmp rbx, 18
    je .p_or
    cmp rbx, 19
    je .p_not
    cmp rbx, 20
    je .p_bit_and
    cmp rbx, 21
    je .p_bit_or
    cmp rbx, 22
    je .p_bit_xor
    cmp rbx, 23
    je .p_bit_not
    cmp rbx, 24
    je .p_plus_assign
    cmp rbx, 25
    je .p_minus_assign
    cmp rbx, 26
    je .p_mul_assign
    cmp rbx, 27
    je .p_div_assign
    cmp rbx, 28
    je .p_shl
    cmp rbx, 29
    je .p_shr
    cmp rbx, 30
    je .p_string
    cmp rbx, 31
    je .p_char
    cmp rbx, 32
    je .p_semicolon
    cmp rbx, 33
    je .p_comma
    cmp rbx, 34
    je .p_comment
    jmp .next_v
.p_num:
    lea rcx, [str_num]
    jmp .do_v
.p_plus:
    lea rcx, [str_plus]
    jmp .do_v
.p_minus:
    lea rcx, [str_minus]
    jmp .do_v
.p_mul:
    lea rcx, [str_mul]
    jmp .do_v
.p_div:
    lea rcx, [str_div]
    jmp .do_v
.p_ident:
    lea rcx, [str_ident]
    jmp .do_v
.p_lparen:
    lea rcx, [str_lparen]
    jmp .do_v
.p_rparen:
    lea rcx, [str_rparen]
    jmp .do_v
.p_assign:
    lea rcx, [str_assign]
    jmp .do_v
.p_colon_assign:
    lea rcx, [str_colon_assign]
    jmp .do_v
.p_eq:
    lea rcx, [str_eq]
    jmp .do_v
.p_neq:
    lea rcx, [str_neq]
    jmp .do_v
.p_lt:
    lea rcx, [str_lt]
    jmp .do_v
.p_gt:
    lea rcx, [str_gt]
    jmp .do_v
.p_lte:
    lea rcx, [str_lte]
    jmp .do_v
.p_gte:
    lea rcx, [str_gte]
    jmp .do_v
.p_and:
    lea rcx, [str_and]
    jmp .do_v
.p_or:
    lea rcx, [str_or]
    jmp .do_v
.p_not:
    lea rcx, [str_not]
    jmp .do_v
.p_bit_and:
    lea rcx, [str_bit_and]
    jmp .do_v
.p_bit_or:
    lea rcx, [str_bit_or]
    jmp .do_v
.p_bit_xor:
    lea rcx, [str_bit_xor]
    jmp .do_v
.p_bit_not:
    lea rcx, [str_bit_not]
    jmp .do_v
.p_plus_assign:
    lea rcx, [str_plus_assign]
    jmp .do_v
.p_minus_assign:
    lea rcx, [str_minus_assign]
    jmp .do_v
.p_mul_assign:
    lea rcx, [str_mul_assign]
    jmp .do_v
.p_div_assign:
    lea rcx, [str_div_assign]
    jmp .do_v
.p_shl:
    lea rcx, [str_shl]
    jmp .do_v
.p_shr:
    lea rcx, [str_shr]
    jmp .do_v
.p_string:
    lea rcx, [str_string]
    jmp .do_v
.p_char:
    lea rcx, [str_char]
    jmp .do_v
.p_semicolon:
    lea rcx, [str_semicolon]
    jmp .do_v
.p_comma:
    lea rcx, [str_comma]
    jmp .do_v
.p_comment:
    lea rcx, [str_comment]
    jmp .do_v
.do_v:
    sub rsp, 20h
    call [printf]
    add rsp, 20h
.next_v:
    add r13, 16          
    jmp .visual_loop

Забыл рассказать про parse_identifier, это - процедура, которая выцепляет имена переменных из общего потока байтов. Когда лексер натыкается на букву или символ подчеркивания, управление переходит сюда.
Внутри работает цикл ident_loop. Он разрешает использовать в именах не только буквы, но и цифры, что позволяет распознавать переменные типа var1 или x2.

Еще важные метки, это - вспомогательные процедуры, которые превращают простую читалку текста в полноценный инструмент анализа. Без них лексер не смог бы обрабатывать такие важные вещи, как комментарии или символьные литералы. Начнем с процедуры
parse_char, которая отвечает за распознавание одиночных символов в кавычках. Когда курсор rsi натыкается на одинарную кавычку, программа инкрементирует указатель, считывает сам символ в регистр rax и сохраняет его в буфер токенов с типом 31. После этого обязательна проверка на закрывающую кавычку, иначе лексер выдаст ошибку. Это критически важно для работы со строками и чарами, так как позволяет процессору хранить не текст, а готовый ASCII-код символа в поле Value:

.parse_char:
    inc rsi
    movzx eax, byte [rsi]
    mov qword [r12], 31
    mov qword [r12+8], rax
    inc rsi
    movzx eax, byte [rsi]
    cmp al, "'"
    jne .char_error
    inc rsi
    add r12, 16
    ret

Следующий блок отвечает за игнорирование комментариев, что является обязательной функцией любого вменяемого компилятора. Метка .is_line_comment запускает цикл, который просто проматывает rsi вперед до тех пор, пока не встретит код 10 или 13, то есть перевод строки. Мы помечаем это как токен типа 34, но по факту это способ очистить код от пояснений программиста, которые не должны попасть в финальный бинарник:

.is_line_comment:
    mov qword [r12], 34
    mov qword [r12+8], 0
    add r12, 16
.line_comment_loop:
    inc rsi
    movzx eax, byte [rsi]
    cmp al, 10
    je next_char
    cmp al, 13
    je next_char
    cmp al, 0
    je compilation_end
    jmp .line_comment_loop

Более же сложная логика заложена в метке .is_block_comment, которая обрабатывает многострочные комментарии вида слеш-звездочка. Здесь нам недостаточно просто найти конец строки, нам нужно дождаться специфической комбинации символов. Программа крутит цикл .block_comment_loop, пропуская всё подряд, пока не встретит звездочку. В этот момент управление переходит на .check_block_end, где мы проверяем следующий байт. Если это слеш, то комментарий официально закрыт и мы выходим из цикла.

.is_block_comment:
    mov qword [r12], 34
    mov qword [r12+8], 0
    add r12, 16
    inc rsi
.block_comment_loop:
    movzx eax, byte [rsi]
    cmp al, '*'
    je .check_block_end
    cmp al, 0
    je compilation_end
    inc rsi
    jmp .block_comment_loop
.check_block_end:
    inc rsi
    movzx eax, byte [rsi]
    cmp al, '/'
    je .block_comment_end
    jmp .block_comment_loop
.block_comment_end:
    inc rsi
    jmp next_char

Теперь про .save_op и save_two_char. Вместо того чтобы в каждой ветке кода заново писать логику сохранения, мы просто подготавливаем тип токена в регистре rbx и прыгаем сюда. Разница между ними лишь в том, на сколько байт нужно сдвинуть входной указатель rsi. Для простых знаков вроде плюса или минуса используется инкремент на единицу, а для составных операторов вроде равно-равно или не-равно мы прыгаем сразу через два байта. Это делает код чище и избавляет от дублирования однотипных операций по записи 16-байтовых структур в r12.

Важным моментом в процедуре .save_op является то, что мы обнуляем поле Value для всех математических знаков. Поскольку для плюса или скобки не нужно хранить дополнительную информацию, мы просто забиваем эти 8 байт нулем:

.save_op:
    mov qword [r12], rbx
    mov qword [r12+8], 0
    add r12, 16
    inc rsi
    jmp next_char

.save_two_char:
    mov qword [r12], rbx
    mov qword [r12+8], 0
    add r12, 16
    add rsi, 2
    jmp next_char

Особое внимание стоит уделить обработке ошибок через метки .string_error и .char_error. Если лексер встречает открывающую кавычку, но не находит закрывающую до конца строки или файла, он не должен просто зависать. Мы вызываем функцию printf с форматом fmt_error и передаем ей текущий адрес rsi. Это позволяет программисту сразу увидеть, в каком месте он допустил опечатку. На ассемблере такая диагностика реализуется максимально прямо: мы берем адрес из регистра и выводим его в консоль вместе с текстом ошибки. Это стандарт де-факто для системного ПО, когда инструмент четко указывает на место сбоя:

.char_error:
    lea rcx, [fmt_error]
    mov rdx, rsi
    call [printf]
    jmp exit_proc

Завершает эту цепочку логика возврата в next_char или выхода в compilation_end. Каждый раз, когда комментарий пропущен или токен успешно сохранен, лексер обязан проверить, не закончились ли данные в исходном коде. Если под rsi оказывается нулевой байт, мы мгновенно прекращаем работу:

next_char:
    movzx eax, byte [rsi]
    test al, al
    jz compilation_end

    cmp al, ' '
    je skip_char
    cmp al, 9
    je skip_char
    cmp al, 10
    je skip_char
    cmp al, 13
    je skip_char

    cmp al, '0'
    jb .check_letters
    cmp al, '9'
    ja .check_letters
    call parse_number
    jmp next_char

И:

compilation_end:
    lea rcx, [header1]
    call [printf]
    lea r13, [tokens_buffer]
    xor r14, r14

Обращение к header1 который хранит в себе строку для красивого вывода и сохранение указателя в r13.

Самую базу написанного мною лексера разобрать смог, если его разбирать полностью - статья выйдет на слишком много символов, попытался объяснить вкратце.
Если же запустить наш лексер, к примеру взять пример прогнать через него пример математики x = y + 10 * (z - 5), то в консоли мы увидим четко структурированный результат. Вместо сырого текста программа выведет упорядоченный список, где каждый символ получил свой уникальный паспорт. Давайте же проверим:

Еще мне очень сильно нравится, как лексер распознает скобки, проверим на примере (1) + (2) = 3:

Красота, база готова, продолжим со следующей статьи.
В заключение хочется сказать: этот компилятор пишется для будущей ОС, которая также будет создана на чистом ассемблере. Любите ассемблер.