|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Anatoly Kochubey 2:5020/400 04 Jun 2003 13:36:35
To : ‚ ¤Ё¬ ‡Ґ«ҐЁ
Subject : Re: Hужны идеи по генерации кода
--------------------------------------------------------------------------------
Привет,
----- Original Message -----
From: "Вадим Зеленин" <green@vista.spb.su>
To: "Alexander Taradov" <fido7.ru.algorithms@talk.ru>
Sent: Wednesday, June 04, 2003 11:09 AM
Subject: Re: Hужны идеи по генерации кода - fido7.ru.algorithms
> AT> Допустим есть некая машина, которая: имеет 2 регистра R1 и R2, не
имеет
> AT> другой памяти (в том числе и стека), обладает набором инструкций:
> [skip]
> AT> Всегда ли хватит двух регистров? Я контр-примеров придумать не смог.
>
> а распиши такое выражение:
> (1*2+3*4)*(5*6+7*8)
В такой последовательности - нельзя.
А в такой - 1*2*5*6 + 1*2*7*8 + 3*4*5*6 + 3*4*7*8 можно.
Рисуем дерево вычисления
1 2 1 2 3 4
3 4
* 5 * 7 * 5
* 7
* 6 * 8 * 6
* 8
* * *
*
+
+
+
Факт: последовательные "листовые" операции одного приоритета требуют 1
регистр (mov, +/* на число сколько нужно раз). Результат - в этом регистре.
"Hелистовые" операции одного приоритета требуют максимум 2х регистров.
Поэтому построим дерево иначе, исходя из операций разного приоритета:
1 2 5 6 1 2 7 8 3 4 5 6 3
4 7 8
* * * * * * * * *
* * *
+ +
+
"ширина" такого дерева некритична - мы можем выполнять операции
последовательно. А вот высота ограничена - у нас всего два регистра, поэтому
мы не можем посчитать дерево с высотой больше 2.
Поэтому так
1 2 3 4 5 6 7 8
* * * *
+ +
*
не получится.
Грубо говоря, задача решается, если мы можем изменить выражение, чтобы
соотв. дерево было высоты 2.
А так как у арифметических операций всего 2 приоритета, то это, видимо,
всегда возможно (путем раскрытия всех скобок).
bw, Anatoly
P.S. sorry, если не шибко понятно объяснил..
P.P.S. имхо, в общем виде, нам для N приоритетов потребовалось бы N
регистров.
--
Отправлено через сервер Форумы@mail.ru - http://talk.mail.ru
--- ifmail v.2.15dev5
* Origin: Talk.Mail.Ru (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
Re: Hужны идеи по генерации кода 