Преобразование алгебраического выражения в язык ассемблера

#java #c_sharp #массивы #алгоритм

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

Алгебраическое выражение  может содержать латинские строчные и заглавные буквы, а
также "+", "-", "*", "/", "(", ")". Пример: "A+B-c*(a-B)"

Компьютер имеет 10 регистров - ячеек памяти (R0..R9) и один сумматор.
Каждая команда в последовательном списке команд начинается с новой строки и содержит
сам код команды (команды опишу ниже) и, через пробел, операнд (имя переменной или регистр).
Команды:

Команда: L операнд Смысл: сумматор := операнд
Команда: A операнд Смысл: сумматор := сумматор + операнд
Команда: S операнд Смысл: сумматор := сумматор - операнд
Команда: M операнд Смысл: сумматор := сумматор * операнд
Команда: D операнд Смысл: сумматор := сумматор / операнд
Команда: ST регистр Смысл: регистр := сумматор


Есть два файла: input.txt и output.txt

input.txt содержит само алгебраическое выражение (не более 100 символов), которые
можно вычислить, используя не более 10 регистров.

output.txt должен содержать последовательность команд языка ассемблера, в результате
выполнения которых полученное значение помещается в сумматор. Ассемблерная программа
должна содержать все операции выражения (без экономии операций).

Пример:
input.txt

A*B-C*(B+X)


output.txt

L A    или    L B
M B           A X
ST R0         M C
L B           ST R1
A X           L A
ST R1         M B
L C           S R1
M R1
ST R1
L R0
S R1


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

Ответы

Ответ 1

Если у Вас это задание вызывает непонимание, то читать про сложные, но эффективные
методы синтаксического разбора не советую. Слона нужно есть по частям. 

Часть 1. Синтаксический анализ выражения. 
Как советовал @Mike, прочитайте про обратную польскую запись и алгоритме вычисления
с ее использованием. Это совсем не сложно, интуитивно понятно и базируется на простых
базовых принципах. Напишите калькулятор,  который выражение будет, собственно, вычислять. 

Часть 2. Трансляция. 
При успешном решении предыдущей задачи, эта является, по сути, просто творческим
переосмыслением пороцесса вычислентя. Единственное условно сложное упражнение здесь
- придумать, как команды в польской нотации записываются в виде ассемблерных инструкций
- это нужно просто аккуратно сделать, работа  чисто редакторская. 

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


Ответ 2

Строим обыкновенное дерево разбора.
Обходим его dfs'ом и вычисляем.
Можно заметить, что переходы между собой в паре +- можно осуществлять без сохранения
левого аргумента в регистре. Аналогично с парой */.
В остальных случаях значение левого операнда следует помещать в регистр.


Собственно, это всё. Но есть один момент. Число регистров ограничено, так что если
будет слишком сложное выражение, то неясно, что же с ним делать.