Читайте также: |
|
выражений (по А.В.Вальковскому)
Этот метод, использует отношение старшинства между операциями. Идея метода в том, что в выражении выделяются подвыражения, содержащие самые высокоприоритетные операции. Выделенные подвыражения одинаковой глубины «склеиваются» в более крупное подвыражение, таким образом «вырастает» выражение, все подвыражения которого имеют равномерную глубину.
Обычно в качестве знаков арифметических операций используют: +, -, *, /,!,μ. Две последние операции — возведение в степень и унарный минус. При неформальном изложении знак умножения * иногда опускается. Вводится стар-
шинство, или приоритет, операций:
Pr(μ) = 4; Pr(!) = 3; Pr(*) = Pr(/) =2; Pr(+) = Pr(-) = 1.
Опишем один вариант алгоритма более подробно, используя для наглядности только лишь выражения с операциями +, *.
Для хранения текущей информации нам потребуется следующая память:
ячейки х — для сканируемых операндов, у — для сканируемых операций, L —
для операции, стоящей слева от текущего операнда, R — для аналогичной опе-
рации справа, Out — для выходного выражения, Т i — ячейки для записи про-
межуточных результатов. Кроме того, воспользуемся вектор-стеком: St = (St1,
St2) — компонента St1 для операндов; St2 — для операций; Sc — процедура
сканирования следующего символа входной строки; символ —> обозначает за-
сылку. Считается, что входное выражение слева и справа ограничено пробелами, Рг (▬) = 0. Первоначально в R и Out содержится пробел.
Шаг 1. Sc —> х, Sc—> у, R —> L, у — > R. Сканируется очередной опе-
ранд и знак операции после него. Операция (пробел) слева от операнда х засы-
лается в ячейку L, справа от x — в ячейку R.
Шаг 2. Если ( St = O OR Рг (L) < Рг (R) OR Рг (St2)<Рг (L) ) AND Рг (R)≠
O, то на шаг 3, иначе на шаг 4.
Шаг 3. х —> St1, y —> St2, переход на шаг1. Запоминаем операнд и операцию и переходим к сканированию следующей пары (операнд, операция).
Шаг 4. Если Рг (L) = Рг (St2), то на шаг 5, иначе на шаг 6.
Шаг 5. Out Tk у —> Out. Если Pr (y) = 0, то конец разбора, иначе па шаг 1. Здесь промежуточная ячейка Тk = (St1 St2 x). Таким образом, когда найдены две операции одного старшинства, первая из них с соседними операндами группируется в промежуточный результат Tk, вслед за ним выписывается вторая операция, и все это приписывается к выходной строке. Далее Tk воспринимается алгоритмом как атомный операнд.
Шаг. 6. Out х у —> Out, если у = "_", то конец разбора, иначе на шаг. 1. В
случае если не находится двух операций одного старшинства и приоритеты
пошли на убывание, операнд и операция просто приписываются к выходной
строке.
Приведенный алгоритм описывает один из проходов, после которого неко
торые из подвыражений «свертываются» в промежуточные результаты Т k. По-
сле этого алгоритм повторяется до тех пор, пока все выражение не сведется к
единственному Tk.
Покажем выражение е = а + b + с * d* I* f + g после серии последо-
вательных проходов.
1. Входная строка: ▬ а + b +c*d*l*f+g ▬.
2. Результат 1-го прохода: ▬ T1 + T2 * Т3 + g ▬, где
T1 = (а + b), T2 = (с*d), Т3 = (1 *f).
3. Результат 2-го прохода: ▬ T4 + Т5 ▬, где
T4 = (T2 * T3), T5 = (T1 + g).
4. Результат 3-го прохода: ▬T6 ▬; T6 = (T4 + T5).
5. Выходная строка: ▬ (((с * d) * (l * f)) + ((а + b ) + g)) ▬
Представим таблицу, подробно описывающую весь процесс преобразования указанного выражения.
Проход | Такт | x | y | L | R | Out | |||
a | + | ▬ | + | a | + | ||||
b | + | + | + | ▬ + | |||||
c | * | + | * | ▬ + | c | * | |||
d | * | * | * | ▬ + * | |||||
l | * | * | * | ▬ + * | l | * | |||
f | * | * | * | ▬ + * + | |||||
g | ▬ | * | ▬ | ▬ + * +g▬ | |||||
+ | ▬ | + | ▬ + | + | |||||
* | + | * | ▬ + * | + * | |||||
+ | * | + | ▬ + + | = * | + | ||||
g | ▬ | + | ▬ | ▬ + | = +g | ||||
+ | ▬ | + | ▬ + | + | |||||
▬ | + | ▬ | ▬ ▬ |
Дерево выходного выражения (ЯПФ, полученная на основе сравнения старшинства операций)
Доказано, что описанный алгоритм дает в результате выражение с мини-
мальным временем выполнения. Однако он имеет ряд существенных недостат-
ков, главный из которых—многопроходность: он требует столько проходов, ка-
ково время выполнения сгенерированного выражения. Чтобы избавиться от
многопроходности, нужно в процессе разбора «нести» попутно информацию об
уровне формируемых конструкций. Имеется однопроходная версия метода.
Дата добавления: 2015-07-08; просмотров: 301 | Нарушение авторских прав
<== предыдущая страница | | | следующая страница ==> |
МЕЛКОЗЕРНИСТЫЙ ПАРАЛЛЕЛИЗМ | | | Метод списочных расписаний. |