В конце прошлой части я пообещал разобрать текст программы на части: понять, где кончается одно слово и начинается другое. Взялся и почти сразу наткнулся вот на такую строку:
.string "http://x"
Мой ассемблер собрал её в 0 байт, вернул код успеха и не пожаловался ни на что. Латать это на месте я пробовал дважды, и вторая заплатка сломала то, что починила первая.
▍ Навигация по серии
Часть 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. Форматы инструкций, если захочется проверить байты руками.
