В конце прошлой части я пообещал разобрать текст программы на части: понять, где кончается одно слово и начинается другое. Взялся и почти сразу наткнулся вот на такую строку:

        .string "http://x"

Мой ассемблер собрал её в 0 байт, вернул код успеха и не пожаловался ни на что. Латать это на месте я пробовал дважды, и вторая заплатка сломала то, что починила первая.

▍ Навигация по серии

• Часть 1. Двенадцать символов, двадцать один байт

• Часть 2. Мой код терял бы 230 байт из 231

• Часть 3. Моя рекурсия зависла навсегда

• Часть 4. Точка входа, которую никто не читает

• Часть 5. Свой ассемблер

• Часть 6. Разбор текста на слова ← вы здесь

Если вы попали сюда с середины

В этой серии я делаю ассемблер с нуля, на питоне. Ассемблер это программа, которая читает текст вроде addi sp, sp, -16 и выдаёт 4 байта, понятные процессору. К пятой части мой умел собрать ровно одну программу, и на ней всё сходилось байт в байт с настоящим as из состава GNU.

Читал он исходник просто: брал строку, срезал комментарий, искал двоеточие в конце, делил остаток по запятым. Эта статья про то, где такое чтение ломается.

Ассемблер знать не нужно. Беда, о которой пойдёт речь, знакома каждому, кто хоть раз резал строку по разделителю: запятая внутри кавычек в CSV, точка с запятой внутри значения, кавычка внутри кавычек. Символ, который обычно что‑то значит, попадает внутрь текста и перестаёт значить это. Здесь то же самое, только вместо запятой две косые черты.

Где построчные правила ломаются

Когда мой ассемблер чего‑то не понимает, он обычно останавливается и называет номер строки: пошёл и поправил. Неприятно, но видно. Со строкой из начала статьи вышло иначе:

        .string "http://x"

настоящий as:  9 байт, 8 символов и ноль
мой:           собрано 0 байт, код возврата 0

Я протрассировал разбор, и вот что там происходит. Правило «всё после // это комментарий» оставляет от строки .string "http:. Дальше вступает второе, „строка, кончающаяся двоеточием, это метка“: оно видит хвост с двоеточием и заводит метку с именем .string "http, с пробелом и кавычкой внутри. Я вывел таблицу меток и увидел её там рядом с _start и msg.’”

Каждое правило по отдельности верно. Ломается их сочетание, и ломается тихо: ни одно из них не знало, что оно сейчас внутри строки в кавычках.

Самое очевидное возражение

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

Я написал две заплатки подряд. Первая помнит, что она внутри двойных кавычек. Вторая знает ещё и одиночные: два выключателя вместо одного, четыре строки работы. Ровно так их и пишут, по одному случаю за раз.

Прогон идёт по 10 строкам. Показываю 5, на которых хоть что‑то менялось, остальные 5 верны у всех четырёх способов, а счёт внизу по всем десяти.

строка                       наивно       заплатка 1   заплатка 2   состояние
------------------------------------------------------------------------------
.string "http://x"           *** НЕТ      верно        верно        верно
.string "a#b"                *** НЕТ      верно        верно        верно
.byte '#'                    *** НЕТ      *** НЕТ      верно        верно
.string "a'b" # хвост        верно        верно        *** НЕТ      верно
.byte '"' # хвост            верно        *** НЕТ      *** НЕТ      верно
------------------------------------------------------------------------------
наивно       неверно 3 из 10
заплатка 1   неверно 2 из 10
заплатка 2   неверно 2 из 10
состояние    неверно 0 из 10

Вторая заплатка починила .byte '#' и сломала .string "a'b" # хвост, который первая собирала верно. Счёт не сдвинулся: два неверных было, два и осталось. Обе спорные строки настоящий as собирает верно, обе лежат в стенде.

Вторая заплатка не знает про первую. Апостроф в слове it's внутри двойных кавычек включает признак одиночной, и дальше срезание считает себя внутри литерала, хотя вышло оттуда давно. Два выключателя, и ни один не помнит, кто из них сейчас главный.

Заплатки не выстраиваются в цепочку. Они мешают друг другу.

Одно моё предсказание тут не сбылось: я ждал поломки на .string "a\"b" с экранированной кавычкой, а срезать в ней нечего, нет ни //, ни #.”

Правил, кстати, не два, а три

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

text = COMMENT_BLOCK.sub(" ", открыть(файл).read())   # 1: блочный /* */
for n, raw in enumerate(text.split("\n"), 1):
    line = raw.split("//")[0].split("#")[0].strip()   # 2: строчный
    while line:
        m = LABEL.match(line)                          # 3: метка
        ...

Первое правило вычищает /* */ по всему файлу разом, ещё до того, как файл разрезан на строки. Оно не знает даже, в какой строке находится, не говоря уже о кавычках. Отсюда третья молчаливая порча:

.string "a /* b */ c"

настоящий as:  a /* b */ c
мой:           a   c

Четыре символа исчезли, ошибки нет. А незакрытый /* внутри строки, наоборот, выживает, хотя я считал его тоже съеденным: выражению нужен закрывающий */.

Разбор на слова: один проход и одно состояние

Разница не в количестве правил, а в том, когда они применяются.

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

Разбор на слова работает иначе. Один проход слева направо, по одному символу. У прохода есть состояние: он сейчас в обычном тексте, или внутри двойных кавычек, или внутри одиночных, или внутри блочного комментария. И символ значит разное в зависимости от состояния.

Символ / в обычном тексте вместе со вторым таким же начинает комментарий. Тот же символ внутри кавычек это просто символ. Двоеточие в обычном тексте закрывает метку, внутри кавычек это двоеточие.

Отсюда видно, почему заплатки не сходятся, а состояние сходится. Правил у меня 3, а положений, в которых может оказаться символ, 4: обычный текст, двойные кавычки, одиночные кавычки, блочный комментарий. Заплатками это чинится по клеткам, и клеток тут 3 на 4, каждую надо выучить отдельно. Проход с состоянием платит 3 плюс 4: правила описываются один раз, положения описываются один раз, а перемножать их не приходится, потому что состояние общее.

Что такое «слово» на выходе. Не просто кусок текста. У каждого есть вид, исходный текст и уже посчитанное значение:

Token(kind="string", text='"http://x"', value=b"http://x")
Token(kind="number", text="0x10",       value=16)
Token(kind="char",   text="'A'",        value=65)

Виды всего шесть: слово, число, строка, символ, знак и конец строки. Значение считается сразу при разборе, и это потом сэкономит работу: старому коду не придётся второй раз узнавать, что 'A' это 65.

Весь проход по форме вот такой. Это не псевдокод, это настоящий цикл, из которого убраны только тела веток:

while i < n:
    c = text[i]

    if c == "\n":                       # конец строки
        ...
    if c in " \t\r":                    # пробелы, пропускаем
        i += 1; continue
    if text.startswith("/*", i):        # блочный комментарий
        ...                             # умеет переходить на другую строку
    if text.startswith("//", i) or c == "#" or c == ";":
        while i < n and text[i] != "\n":
            i += 1                      # до конца строки, но НЕ дальше
        continue
    if c == '"':                        # строковый литерал
        ...
    if c == "'":                        # символьный литерал
        ...
    if c.isdigit():                     # число, в том числе 0x
        ...
    if c.isalpha() or c in "._$":       # имя, метка, директива
        ...

    two = text[i:i + 2]                 # знаки, сперва двухсимвольные
    if two in ("<<", ">>", "//"):
        out.append(Token(PUNCT, two, two, line)); i += 2; continue
    out.append(Token(PUNCT, c, c, line)); i += 1

Порядок веток тут не косметика. Проверка на комментарий стоит до проверки на знак, иначе // прочитается как два деления. Двухсимвольные знаки проверяются до односимвольных по той же причине: иначе << станет двумя <.

А вот сердцевина, ветка про кавычки, целиком:

if c == '"':
    j, buf = i + 1, bytearray()
    while True:
        if j >= n or text[j] == "\n":
            raise LexError("строка %d: кавычка не закрыта" % line)
        if text[j] == "\\":
            code, eaten = _read_escape(text, j, line)
            buf.append(code)
            j += eaten
            continue
        if text[j] == '"':
            break
        buf.extend(text[j].encode("utf-8"))
        j += 1
    out.append(Token(STRING, text[i:j + 1], bytes(buf), line))
    i = j + 1
    continue

Встретили кавычку, дальше читаем до закрывающей и по дороге ни на что не отвлекаемся. Ни //, ни #, ни двоеточие тут ничего не значат.

Отдельная ветка нужна обратной косой: \" внутри строки не закрывает её, а даёт саму кавычку. Разбор экранирования вынесен в свою функцию на 9 строк. Она знает \n, \t, \r, \0 и сами кавычки, а незнакомое экранирование пропускает как есть: \q даёт букву q, и настоящий as делает ровно то же самое.»

А восьмеричное он не умеет, и это я узнал, когда сел сверять ветку с as: на .string "a\015b" настоящий даёт возврат каретки, а мой ноль и дальше буквы 1 и 5. Ветку я не чинил, она идёт в тот же список, что и арифметика в операндах.

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

На выходе получается не строка покороче, а список слов. Вот та же злополучная строка:

word     '.string'
string   '"http://x"'

2 слова. Второе целиком, с кавычками и с двоеточием внутри. Никакое последующее правило уже не сможет принять его за метку: это не текст, который можно перечитать по‑своему, а помеченный кусок с готовым значением.

Новый разбор подставляется в ассемблер заменой одной строки (за ней стоит тот самый переходник, про него сразу после):

asm.read_lines = lexer.read_lines

Дальше вопрос: собирается ли всё, что собиралось раньше, байт в байт.

Сначала я проверил это на первой программе серии. 63 байта, совпало. Обрадовался и чуть не пошёл писать текст.

Регрессия, которую эта проверка не увидела

И вот тут перед текстом я проверил ещё несколько строк отдельно. Первой же попалась вот эта:

        addi sp, sp, -16

Та самая инструкция, вокруг которой крутились три предыдущие части. С новым разбором она перестала собираться.

Причина вытекает из устройства. Разбор на слова отдаёт - и 16 двумя отдельными словами, и это правильно: решать, унарный тут минус или вычитание, дело следующего этапа, а не резки. Но следующего этапа у меня пока нет, а старый код ждёт готовое -16.

Всего сломанных нашлось 3: addi sp, sp, -16, lw t0, -8(sp) и li t0, -1.

Починил я их не в лексере, и это важно. В лексере всё верно: он отдаёт - и 16 порознь, потому что решать про унарный минус дело разбора. Склейку я положил в переходник к старому коду, функцию _render на 37 строк. Она собирает слова обратно в строку и по дороге приклеивает минус к числу, если перед ним запятая, скобка или другой знак, то есть если минус тут не вычитание.

Переходник это цена того, что разбора у меня пока нет. Появится вычислитель, и склейка уедет к нему, а _render исчезнет. Пока же за строчкой 16 из 16 ниже стоит в том числе он. Я выключил в нём склейку минуса и прогнал приёмку заново: стало 13 из 16, ровно те три строки и отвалились.

А проверка на первой программе этого не заметила, потому что отрицательных чисел в ней нет ни одного. Она сказала «байт в байт совпало» и была права ровно про то, что проверяла.

Проверка, которая молчит, и проверка, которая говорит «всё хорошо», выглядят одинаково.

Приёмку я переписал. Теперь она сверяет 16 отдельных конструкций, которые старый ассемблер точно умеет, и первую программу целиком:

строк сверено 16, байт в байт совпало 16
первая программа серии целиком: 63 байт, совпало

Заодно я узнал про свой ассемблер то, чего не знал. Хотел прогнать по нему все программы серии и получил на второй же:

строка 3: не знаю директиву .equ

Он умеет ровно одну программу, ту, на которой я его писал.

Что починилось

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

Старому коду при этом не пришлось узнавать про кавычки вообще. Он по‑прежнему получает строку, но уже разобранную: символьный литерал в ней заменён готовым числом.

А теперь то же самое, но программой

Всё выше я доказывал сравнением байтов: у настоящего as 9, у меня 0. Это числа в таблице, и по ним не видно, чем такая потеря оборачивается.

Поэтому я собрал программу, которая печатает адрес этого самого репозитория. Обычный скелет из первой части серии, и вся разница в одной строке данных: .string "https://github.com/Pro100lamer/uart-to-lang". Собрал её дважды, меняя ровно одно, чем разрезан исходник на строки, и запустил обе в эмуляторе: qemu-system-riscv32, машина virt, вывод в тот же UART, что и в первой части.

сборка           байт     что напечатала программа
----------------------------------------------------------------------------
старый разбор    40       (ничего)
лексер           84       https://github.com/Pro100lamer/uart-to-lang
----------------------------------------------------------------------------

40 байт против 84, и первая сборка молчит. Не падает, не ругается, доходит до конца и останавливается где положено. Просто не печатает ничего.

Вот это и есть то, чего не видно в сравнении байтов. Ноль байт в таблице выглядит как строчка отчёта. Молчащая программа не выглядит никак: запустилась и ничего не сделала. Будь это прошивка в плате, я пошёл бы проверять провода, скорость порта и питание. А виновата строка исходника, разобранная тремя шагами раньше, и никакой шевелёж проводов до неё бы не добрался.

Кристалл я тут не доставал нарочно, хотя в прошлой части он работал и стоит на столе. Порча происходит на моей машине, до того как хоть один байт уедет в плату: ассемблер отдал 40 байт вместо 84, и любое железо честно исполнит ровно эти 40. Прошить плату значило бы показать, что одинаковое одинаково.

Повторяется командой make url.

Второе обещание: что стало с выражением в операнде

Пятая часть кончилась вот так:

Пока мой ассемблер режет строки пробелами и запятыми, и на первом же выражении в операнде это развалится.

Проверял я это 9 строками: 8 с выражением в операнде и одна с простым числом -16, для сравнения. Настоящий as собирает все 9.

Причина, по которой мой не собирает, лежит в одной функции. Мой разбор числа умеет ровно две вещи: попробовать int(t, 0) и поискать имя в таблице меток (метка это имя для адреса, вроде msg: перед строкой данных). Арифметики там нет вовсе, и 16*2 для него не число и не метка.

Разбор на слова это не вычисление, но часть работы он закрывает сам. Вот те же 9 строк, слева старый разбор, справа новый:

строка                     старый    с лексером
addi sp, sp, -16*2         упал      упал
addi sp, sp, 8+8           упал      упал
addi t0, t0, 1<<4          упал      упал
addi sp, sp, -(16)         упал      упал
addi t0, t0, 0x10|0x01     упал      упал
lw t0, (4*2)(sp)           упал      упал
addi t0, zero, 'A'         упал      собрал
addi sp, sp, 8 + 8         упал      упал
addi sp, sp, -16           собрал    собрал

собиралось 1 из 9, стало 2 из 9

Прибавилась одна строка, та, где выражение это символ в кавычках: разбор посчитал 'A' числом 65 прямо при резке и отдал дальше готовое число, а старому коду не пришлось узнавать ни про кавычки, ни про таблицу символов. Остальные 7 ждут арифметики.

Вот что происходит с первой строкой таблицы:

слова:   addi sp , sp , - 16 * 2
сборка:  не собирается

Слова нарезаны правильно, все 8. Никто их не считает.

И это ровно та граница, которую я поначалу пытался перепрыгнуть. Резать текст на слова и вычислять выражения это две разные работы. Первая знает, где кончается одно слово и начинается другое. Вторая знает, что умножение делается раньше сложения. Смешивать их в одном проходе можно, и многие так делают, но тогда обе получаются хуже.

Итог

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

Главное про него не в объёме, а в том, что он не набор правил, а одно состояние. Правил было 3, положений 4: заплатками это чинится по клеткам, 3 на 4, а проход с состоянием платит 3 плюс 4. Я написал две заплатки подряд, и счёт неверных после второй не сдвинулся.

Со вторым обещанием так: из 9 строк с выражением в операнде мой ассемблер собирал 1, а с разбором на слова собирает 2. Прибавилась та, где выражение было символом в кавычках. Остальным 7 нужна арифметика, а она отдельная работа.

По дороге нашлись 2 строки из 7, на которых старый разбор молча отдавал не то, что просили, с кодом успеха. Виноваты правила, каждое из которых верно по отдельности: достаточно двоеточия внутри http://, и данные исчезают, а в таблице меток появляется метка с кавычкой в имени.

Код: github.com/Pro100lamer/uart‑to‑lang, тег article-06. Опыты повторяются командами make cases, make silent, make refute, make accept и make url. Приёмка это та самая, которая сначала молчала про сломанное.

Из тех 9 строк с выражением мой ассемблер собирает 2. Слова в остальных нарезаны верно, а складывать и умножать их некому. В следующей части напишу вычислитель, рекурсивным спуском, и доведу счёт до 9 из 9.

Заодно покажу, во что обходится сама рекурсия. Каждый вызов функции это не только её работа: на входе надо сохранить то, что уже лежит в регистрах, а на выходе вернуть обратно. На наивном Фибоначчи эта обвязка съедает 53,3% всей исполненной работы, на разборе выражения 15,5%. Цена вызова зависит от того, много ли функция делает по сравнению с тем, сколько сохраняет. Фибоначчи, на котором эту цену принято показывать, худший случай, а не обычный.

Для тех, кто хочет разобраться сам

• Документация GNU as, раздел про синтаксис. Что именно as считает комментарием, меткой и литералом, и чем это отличается на разных платформах.

• Crafting Interpreters, глава Scanning. Разбор на слова с нуля и по шагам, на английском, читается легко.

• Спецификация RISC‑V, том 1. Форматы инструкций, если захочется проверить байты руками.