Вычисление выражений

В TRM значения в регистрах (включая PC) и памяти однозначно определяют одно уникальное состояние компьютера. Поэтому по логике печать регистров и сканирование памяти должны помогать отладить все проблемы. Но для удобства мы также хотим, чтобы простой отладчик помогал вычислять выражения с регистрами и памятью. Поэтому в простой отладчик нужно добавить вычисление выражений. Для простоты сначала рассмотрим реализацию вычисления математических выражений.

Вычисление математических выражений

Вам дана строка выражения

"5 + 4 * 3 / 2 - 1"

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

1. сначала распознать все единицы в выражении
2. рекурсивно вычислить выражение согласно его индуктивному определению.

Лексический анализ

«Лексический анализ» — громкое имя для того, чтобы сделать первое из перечисленного выше: «распознать все единицы в выражении». «Единица» здесь — подстрока с собственным смыслом, формально называемая token. Конкретно, в выражении выше нужно распознать token'ы 5, +, 4, *, 3, /, 2, - и 1. Может показаться, что это довольно просто, но рассмотрим следующее выражение.

"0x80100000+   ($a0 +5)*4 - *(  $t1 + 8) + number"

В нём гораздо больше возможностей: шестнадцатеричные целые (0x80100000), скобки, доступ к регистрам ($a0), разыменование указателя (вторая *), доступ к переменным (number). На самом деле такие сложные выражения при отладке используют часто, и token'ы нужно корректно распознавать при переменном числе пробелов (ноль или больше). Разумеется, можно делать это и вручную (если любите усложнять себе жизнь), а быстрее и проще — использовать регулярные выражения. Регулярные выражения удобно сопоставляют сложные pattern'ы и обязательны для программиста. Если вы никогда не встречали регулярные выражения, пожалуйста STFW. В эксперименте достаточно понять некоторые базовые знания о регулярных выражениях (например, метасимволы).

Когда научитесь пользоваться простыми регулярными выражениями, можно думать, как с их помощью распознавать token'ы. Начнём с простого случая — арифметического выражения, где в вычисляемом выражении разрешены только следующие типы token'ов:

• десятичные целые
• +, -, *, /
• (, )
• строка пробелов (один или несколько пробелов).

Сначала нужно с помощью регулярных выражений написать правила, распознающие каждый из этих типов token'ов. В каркасном коде правило — это пара (реализована структурой C), состоящая из регулярного выражения и типа token'а. Каркасный код уже даёт правила для + и строки пробелов, где тип token'а для строки пробелов — TK_NOTYPE, потому что строка пробелов в вычислении не участвует и после распознавания её можно отбросить, а тип token'а для + — '+'. На самом деле тип token'а — просто целое, нужно лишь гарантировать, что разные типы token'ов закодированы разными целыми. В каркасном коде есть ещё правило, распознающее двойной знак равенства, но пока его можно игнорировать.

Эти правила при инициализации простого отладчика через init_regex() компилируются во внутреннюю структуру данных для сопоставления pattern'ов; её используют библиотечные функции, и она используется снова и снова, но вам не нужно заботиться, как она устроена. Однако если компиляция регулярного выражения не пройдёт, NEMU вызовет assertion fail, и тогда нужно проверить, что написанные правила соответствуют синтаксису регулярных выражений.

Дано выражение для вычисления — сначала нужно распознать в нём token'ы, этим занимается функция make_token(). Функция make_token() работает очень прямолинейно: переменной position она указывает, где сейчас обрабатывает, и по порядку пытается сопоставить строку в текущей позиции со всеми правилами. Когда правило успешно совпало и совпавшая подстрока как раз там, где position, мы успешно распознали token, и макрос Log() выводит сообщение об успешном распознавании. Вам нужно лишь сохранить информацию о распознанном token'е (за исключением строки пробелов); для записи информации о token'е мы используем структуру Token:

typedef struct token {
  int type;
  char str[32];
} Token;

Член type записывает тип token'а. Для большинства token'ов достаточно записать только тип, например +, -, *, /, но для некоторых token'ов этого мало: если записать только тип token'а десятичного целого, то при вычислении мы всё ещё не будем знать, чему это десятичное целое равно. Нужно записать и соответствующую подстроку token'а, для этого служит член str. Заметьте, что у str длина ограничена, поэтому когда поймёте, что буфер вот-вот переполнится, нужно обработать это соответственно (подумайте, как бы вы это обработали?), иначе получится баг, который трудно понять. Массив tokens хранит распознанные token'ы по порядку, а nr_token указывает число уже распознанных token'ов.

Если все опробованные правила не могут сопоставить token в текущей позиции, распознавание не удаётся, и каркасный код выводит текущую позицию token'а (когда выражение слишком длинное и в терминале нужен перенос строки, ^ может не указывать верную позицию; тогда положение token'а лучше искать по выведенному значению position). Обычно это следствие недопустимого выражения, и функция make_token() вернёт false, показывая, что лексический анализ не удался.

Реализовать лексический анализ арифметических выражений

Нужно сделать следующее.

• Добавить правила для различных типов token'ов в арифметическом выражении. Нужно учитывать наличие escape-символов в строках C и роль метасимволов в регулярных выражениях.
• После успешного распознавания token'а по порядку записать информацию о token'е в массив tokens.

Аксиомы отладки

• Машина всегда права.
  • Следствие: если программа не даёт желаемого вывода, виноват программист.
• Каждая строка непротестированного кода всегда неверна.
  • Следствие: ошибки с большой вероятностью появятся в коде, который «обязан быть правильным».

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

Jyy раньше предлагал их как факты. На самом деле бесчисленные программисты (включая старших курсов вашей школы) на практике снова и снова подтверждали их правильность, поэтому здесь мы предлагаем их как аксиомы.

Как отлаживать

• Не используйте «отладку взглядом», думайте, как правильными инструментами и методами помочь отладке.
  • На курсе программирования, пялясь на десятки строк программы, вы, возможно, ещё можете в мозгу симулировать выполнение программы, как NEMU; но когда программа станет больше, вы скоро сдадитесь: мозг не симулирует огромный конечный автомат.
  • Мы изучаем компьютеры, чтобы узнать, как они работают, а не чтобы работать механически, как компьютер.
• Используйте assert(), чтобы ставить контрольные точки и перехватывать непредвиденные ситуации.
  • Например, assert(p != NULL) может перехватить ошибки сегментации из-за разыменования нулевого указателя.
• Используйте printf(), чтобы видеть, как выполняется программа, в связке с пониманием её поведения (обратите внимание на переводы строк в строках)
  • printf() выводит произвольное сообщение, которым можно проверить достижимость кода: соответствующее сообщение выводится тогда и только тогда, когда выполнен соответствующий блок кода.
• printf() выводит значение переменной — можно проверить, как и почему оно менялось.
• Используйте GDB, чтобы наблюдать произвольное состояние и поведение программы.
  • Печать переменных, точки останова, точки наблюдения, стек вызовов функций...

Если сказанное выше вдруг показалось вам очень разумным, значит на курсе программирования вы не получили нужной подготовки.

Почему вывод printf() нужно переводить на новую строку?

Что может произойти, если перевода строки не будет? Можете попробовать в коде, подумать почему, а затем STFW и сравнить со своими мыслями.

Золотое правило проектирования систем — правило KISS

KISS здесь — сокращение от Keep It Simple, Stupid, что можно перевести так: не стремитесь к абсолютному совершенству с самого начала.

Вы уже прошли основы программирования, то есть научились писать программы, но это ещё не значит, что вы готовы к PA: в реальном мире нужны системы, которые работают, а не маленькие программы, считающие факториал. NEMU — маленькая система с объёмом кода больше 3000 строк (без пустых строк). По мере продвижения PA кода будет всё больше, взаимодействие модулей — всё сложнее, поддержка проекта станет очень трудной, и очень глупый баг может отлаживаться несколько дней. В такой ситуации главное — чтобы система запустилась; что не работает — неважное. Гнаться за полнотой покрытия только усложнит поддержку кода.

Единственное, что может спасти вас из хаоса багов, — правило KISS: от простого к сложному, шаг за шагом, за раз одно дело и меньше постороннего. Если не понятно, что это значит, возьмём как пример упомянутую выше проблему переполнения буфера члена str. Правило KISS говорит: используйте assert(0) — даже если это не «прилично» обработает проблему выше, на корректность ядра вычисления выражений это всё равно не повлияет. Если помните аксиомы отладки, увидите связь: второй пункт аксиом говорит, что непротестированный код всегда неверен. Вместо того чтобы сразу писать столько «неверного» кода, лучше assert(0) поможет сократить эти «ошибки».

Если толковать правило KISS в области программной инженерии, оно подчёркивает важность модульных тестов: написать функцию, протестировать её, написать следующую функцию и снова протестировать... Хороший способ тестировать — использовать assertion; reg_test() — такой пример. Научиться пользоваться assertion полезно и для тестирования, и для отладки программы.

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

Рекурсивное вычисление

Когда token'ы в выражении распознаны, можно переходить к вычислению. Заметьте, что теперь мы работаем с массивом token'ов; для удобства будем называть его «token-выражением». Например, вычисляемое выражение

"4 +3*(2- 1)"

имеет token-выражение

+-----+-----+-----+-----+-----+-----+-----+-----+-----+
| NUM | '+' | NUM | '*' | '(' | NUM | '-' | NUM | ')' |
| "4" |     | "3" |     |     | "2" |     | "1" |     |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+

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

<expr> ::= <number>    # число — это выражение
  | "(" <expr> ")"     # если взять выражение в скобки — тоже выражение
  | <expr> "+" <expr>  # сумма двух выражений — тоже выражение
  | <expr> "-" <expr>  # дальше вы уже всё поняли
  | <expr> "*" <expr>
  | <expr> "/" <expr>

Запись выше — знаменитая BNF; любой формальный учебник языка программирования использует BNF, чтобы задать синтаксис этого языка.

Исходя из определения BNF выше, решение уже вырисовывается: раз длинное выражение составлено из коротких, сначала вычисляем короткое выражение, затем — длинное. Это естественное решение — применение «разделяй и властвуй», которое легко понять, даже если вы не слышали этого популярного термина. А чтобы реализовать это решение, рекурсия — ваш выбор.

Чтобы указать подвыражение в token-выражении, можно использовать два целых p и q — начало и конец подвыражения. Так каркас функции вычисления легко записать:

eval(p, q) {
  if (p > q) {
    /* Недопустимое выражение */
  }
  else if (p == q) {
    /* Один token.
     * Пока этот token должен быть числом.
     * Вернуть значение числа.
     */
  }
  else if (check_parentheses(p, q) == true) {
    /* Выражение окружено парой согласованных скобок.
     * Если так, просто отбросить скобки.
     */
    return eval(p + 1, q - 1);
  }
  else {
    /* Здесь нужно сделать больше. */
  }
}

Функция check_parentheses() нужна, чтобы определить, окружено ли выражение парой согласованных скобок, и проверить, согласованы ли левые и правые скобки выражения; если не согласованы, выражение синтаксически неверно, и продолжать вычисление не нужно. Посмотрим на примеры того, что делает check_parentheses():

"(2 - 1)"             // true
"(4 + 3 * (2 - 1))"   // true
"4 + 3 * (2 - 1)"     // false, всё выражение не окружено парой
                      // согласованных скобок
"(4 + 3)) * ((2 - 1)" // false, недопустимое выражение
"(4 + 3) * (2 - 1)"   // false, самая левая '(' и самая правая ')' не согласованы

А как проверять, согласованы ли левые и правые скобки, оставим как задание по программированию — подумайте сами!

Каркас выше уже учёл первые два определения арифметического выражения в BNF; дальше рассмотрим остальные случаи (то есть содержимое последнего else в псевдокоде выше). Вопрос: дано длинное выражение, у которого самый левый и самый правый элементы — не оба скобки; как правильно расщепить его на два подвыражения? «Главный оператор» определим как оператор, который при ручном вычислении выражения выполняется на последнем шаге; он указывает тип выражения (например, если последний шаг выражения — вычитание, по сути это выражение вычитания). Правильно расщепить длинное выражение — значит найти его главный оператор. Продолжим разбирать это на примере выше.

"4 + 3 * ( 2 - 1 )"
/*********************/
case 1:
    "+"
   /   \
"4"     "3 * ( 2 - 1 )"


case 2:
        "*"
       /   \
"4 + 3"     "( 2 - 1 )"


case 3:
              "-"
             /   \
"4 + 3 * ( 2"     "1 )"

Выше перечислены 3 возможных расщепления; заметьте, что нельзя расщеплять на token'е, который не оператор, иначе результат расщепления не будет допустимым выражением. По определению главного оператора легко увидеть, что верно только первое расщепление. Это согласуется с ручным вычислением: сначала считаем 4 и 3 * ( 2 - 1 ), затем складываем их результаты. Второй вид расщепления нарушает приоритет арифметических операций и заставляет сложение произойти раньше умножения. Третий вид расщепления разрушает баланс скобок. Так что результат 2-го и 3-го расщепления — не допустимое выражение.

На простом примере выше можно подытожить, как искать главный оператор в token-выражении:

• Token, который не оператор, не является главным оператором.
• Token, который появляется в паре скобок, не является главным оператором. Заметьте, что случая, когда скобки окружают всё выражение, здесь не будет: его уже обработали в соответствующем блоке if у check_parentheses().
• У главного оператора в выражении наименьший приоритет. Потому что главный оператор выполняется последним.
• Когда несколько операторов имеют наименьший приоритет, по ассоциативности главным оператором будет тот, который связывается последним. Пример — 1 + 2 + 3, его главный оператор — + справа.

Чтобы найти главный оператор, достаточно один раз просканировать token-выражение и по способу выше однозначно определить главный оператор.

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

eval(p, q) {
  if (p > q) {
    /* Недопустимое выражение */
  }
  else if (p == q) {
    /* Один token.
     * Пока этот token должен быть числом.
     * Вернуть значение числа.
     */
  }
  else if (check_parentheses(p, q) == true) {
    /* Выражение окружено парой согласованных скобок.
     * Если так, просто отбросить скобки.
     */
    return eval(p + 1, q - 1);
  }
  else {
    op = позиция главного оператора в token-выражении;
    val1 = eval(p, op - 1);
    val2 = eval(op + 1, q);

    switch (op_type) {
      case '+': return val1 + val2;
      case '-': /* ... */
      case '*': /* ... */
      case '/': /* ... */
      default: assert(0);
    }
  }
}

Важно заметить, что в каркасе выше нет обработки ошибок: когда при вычислении выражение оказывается недопустимым, верхней функции нужно вернуть признак ошибки, сообщающий, что «результат вычисления недействителен». Например, в check_parentheses() выражения (4 + 3)) * ((2 - 1) и (4 + 3) * (2 - 1) оба возвращают false, потому что в первом случае выражение недопустимо и успешно вычислить его нельзя; а во втором случае это допустимое выражение, и вычисление успешно. Второе — законное выражение, которое можно успешно вычислить, только его форма не принадлежит "(" <expr> ")" в BNF, его нужно обрабатывать через главный оператор, поэтому нужно ещё как-то их различить. Разумеется, при обнаружении недопустимого выражения можно и assert(0) завершить программу. Но тогда пользоваться вычислением выражений нужно будет очень осторожно.

Наконец, для единообразия считаем, что все результаты имеют тип uint32_t.

Реализовать рекурсивное вычисление арифметических выражений

Поскольку ICS — не курс алгоритмов, идею и каркас рекурсивного вычисления мы уже изложили. Вам нужно понять эту идею и заполнить каркас соответствующим содержимым. Когда вычисление выражений реализовано, команду p реализовать уже нетрудно.

Вычисление арифметических выражений с отрицательными числами (по желанию)

В реализации выше мы не учитывали отрицательные числа, например

    "1 + -1"
    "--1"    /* Декремент не реализуем, здесь это следует понимать как -(-1) = 1 */

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

• И знак минуса, и вычитание — это -, как их различить?
• Минус — унарный оператор, на что обратить внимание при расщеплении?

Можно не реализовывать отрицательные числа, но со схожими проблемами вы скоро столкнётесь.

Заглянуть в компилятор через вычисление выражений

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

На самом деле лексический анализ — первый шаг, которым компилятор компилирует исходный код. Компилятору тоже нужно распознать token'ы в вашем исходном коде, и это тоже можно сделать регулярными выражениями, только типов token'ов больше и они сложнее. Этим же объясняется, почему в исходный код можно вставлять любое число пробельных символов (включая пробел, tab, перевод строки) и семантика программы не изменится; можно и весь исходный код написать в одну строку — компиляция всё равно пройдёт.

Интересное приложение, связанное с лексическим анализом, — подсветка синтаксиса. На курсе программирования вы, возможно, вовсе не думали, что программу подсветки синтаксиса можно написать самому. Правда в том, что эта кажущаяся магия на самом деле не так сложна, и сейчас у вас действительно есть способность её реализовать: считать исходный код строкой, поданной в программу подсветки; в цикле распознав token, в зависимости от типа token'а снова вывести его содержимое другим цветом. Если хотите вывести подсвеченный код в терминал, можно использовать цвета ANSI escape-кодов.

В рекурсивном вычислении выражения логически делаются две вещи: первая — по token'ам разобрать структуру выражения (к какому случаю BNF оно относится), вторая — уже само вычисление. В компиляторе есть соответствия: синтаксический анализ подобен разбору структуры выражения, только компилятор разбирает структуру программы: что функции, что операторы и т.д. Разумеется, структура программы сложнее структуры выражения, поэтому компиляторы обычно используют стандартный каркас, чтобы анализировать структуру программы; чтобы понять этот каркас, нужно больше знаний, здесь это не разворачиваем. Если интересно, можно также посмотреть BNF синтаксиса C.

Соответствие последнему вычислению выражения в компиляторе — генерация кода. На теоретическом курсе ICS есть отдельная глава о связи кода C и инструкций ассемблера, так что даже не зная в точности, как код порождается, связь всё равно можно понять. Потому что код C от природы тесно связан с кодом ассемблера, и мышление сильного программиста на C даже может переключаться между кодом C и ассемблером. Если копнуть процесс генерации кода глубже, нетрудно догадаться, что он сделан рекурсией: например, чтобы породить код функции, сначала порождают код каждого оператора внутри, затем каким-то способом соединяют их.

Мы заглядываем в устройство компилятора через реализацию вычисления выражений, чтобы закрепить мысль: учиться автомобилестроению — не только чтобы научиться водить машину, а чтобы узнать, как проектируют двигатель. Также очень рекомендуем в будущем пройти курс «Основы компиляции» и глубже изучить, «как проектировать двигатель».

Как тестировать свой код

В дальнейшем вы будете пользоваться своей реализацией вычисления выражений, чтобы помогать последующей отладке, а это значит, что дни курса программирования в стиле «код как-нибудь протестировал, сдал и можно забить» уже не вернутся. Для тестов нужны тестовые случаи, и чем больше тестов пройдено, тем больше уверенности в коде. Но если поручить вам проектировать тестовые случаи, десятка полтора уже наскучат — есть ли способ автоматически порождать тестовые случаи?

Распространённый метод — случайное тестирование. Сначала нужно подумать, как случайно породить допустимое выражение. На самом деле порождение выражений гораздо проще, чем их вычисление. Снова по BNF выше легко написать каркас порождения выражения.

void gen_rand_expr() {
  switch (choose(3)) {
    case 0: gen_num(); break;
    case 1: gen('('); gen_rand_expr(); gen(')'); break;
    default: gen_rand_expr(); gen_rand_op(); gen_rand_expr(); break;
  }
}

С первого взгляда должно быть понятно, как работает код выше: uint32_t choose(uint32_t n) — очень простая и очень важная функция, она порождает случайное число меньше n, и почти всё случайно порождаемое содержимое выбирается через неё.

С этими случайными выражениями как тестовым входом — как узнать, верный ли вывод? Если считать эти выражения вручную, слишком хлопотно. Если при порождении выражений порождать и их результаты, получатся тестовые случаи в духе OJ! Но вычисление выражений в NEMU мы несколько упростили, поэтому нужен «калькулятор», удовлетворяющий условиям:

• выполняются только беззнаковые операции
• ширина данных — 32 бита
• переполнение не обрабатывается

Хей! Если запихнуть эти выражения в исходный файл такой программы на C:

#include <stdio.h>
int main() {
  unsigned result = ???; // заменить ??? на выражение
  printf("%u", result);
  return 0;
}

Затем скомпилировать её gcc и выполнить, чтобы она вывела результат выражения — разве это не тот «калькулятор», который мы хотим?

Так и в самом деле можно! Каркасный код этого генератора выражений мы уже подготовили (в nemu/tools/gen-expr/gen-expr.c). Нужно реализовать функцию void gen_rand_expr(), которая выводит случайно порождённое выражение в буфер buf. Код в функции main вызовет вашу реализацию gen_rand_expr(), затем подставит случайное выражение из buf в код программы на C выше. Останется скомпилировать и запустить эту программу на C; в коде для этого используют библиотечные функции вроде system() и popen(). Наконец, каркасный код выведет печать этой программы на C вместе со случайно порождённым выражением — так получается набор тестовых случаев.

Как генератор выражений получает вывод программы на C?

В этой части кода нет никаких комментариев, и сообразительный человек, возможно, сразу поймёт: это ловушка RTFM! Читать руководство, чтобы понять конкретное поведение API, — базовый навык программиста. Если кажется, что прошлый год программистом прошёл впустую, начните как следует тренироваться сейчас.

Но при реализации вы скоро обнаружите, что нужно разобрать ещё несколько деталей:

• Как гарантировать, что выражения выполняют только беззнаковые операции?
• Как случайно вставлять пробелы?
• Как порождать длинные выражения и при этом не переполнить buf?
• Как отфильтровать выражения, у которых при вычислении есть деление на 0?

Большинство этих вопросов связано с C, так что считайте это ещё одним упражнением по программированию на C.

Зачем использовать беззнаковые типы? (Предлагается подумать на втором проходе)

В вычислении выражений мы условились, что все операции беззнаковые. Знаете, почему так условились? Если выполнять знаковые операции, какая проблема может возникнуть?

Точное поведение деления на 0

Если в порождённом выражении есть деление на 0, каким будет поведение написанного вами генератора выражений?

Фильтровать выражения с делением на 0

На первый взгляд задача кажется трудной: каркасный код отвечает только за порождение выражения, а чтобы обнаружить деление на 0, выражение как минимум нужно вычислить. Соедините ответы на первые два вопроса в синих блоках (при условии, что вы поняли их достаточно глубоко) — и найдёте решение, причём оно не единственное!

Реализовать генератор выражений

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

./gen-expr 10000 > input

В файл input будет порождено 10000 тестовых случаев, по одному в строке, в формате

результат выражение

Ещё немного переделайте функцию main() в NEMU, чтобы она читала тестовые выражения из файла input, сразу вызывала expr() и сравнивала с результатом. Чтобы вместить вычисление длинных выражений, нужно также изменить размер массива tokens.

По мере того как программа проходит всё больше тестов, уверенности в коде будет всё больше.

Подсказка

На этом заканчивается этап 2 PA1.