Не могли бы вы меня навести на алгоритм оптимизации выражений в ПОЛИЗ, существует ли таковой, особенно это касается свертки констант?
Дело в том что если константы разбросаны по исходному выражению то при симуляционном выполнении арифметического стека (самая простейшая оптимизация какую мне удалось найти), когда переменные откидываются, удается свернуть только следующие впереди переменных константы, завершающие выражение константы остаются не свернутыми. К сожалению не смог найти больше информации по ПОЛИЗу как по методу разбора и трансляции/компиляции выражений, а оптимизированный код для выражений хотелось бы иметь в арсенале. Шутка ли объемы простеньких программ для разработанной архитектуры процессора в силу отсутствия оптимизации легко выпрыгивают за 8 и 16 Кб кода, и немалый вклад в оверхед вносят в первую очередь выражения. Буду очень благодарен за развернутый ответ.
Уточнения
Пишет st,
Вопрос интересный, но требует разных уточнений и примеров. Какая грамматика, какой метод разбора, каковы используемые стадии и что на выходе?
Например, рекурсивный спуск формирует синтаксическое дерево, соответствующее вызовам команд для RPN-ПОЛИЗ. Все константы попадают в соответствующую таблицу, исключающую дублирование, вызовы используют адреса констант. Должно получаться крайне компактно, как в Форте.
Думаю, будет проще, если описать какой-нибудь простой конкретный пример, вызывающий проблемы.
В качестве иллюстрации приведу собственный пример компиляции выражения в код для стековой виртуальной машины без оптимизации.
Выражение
Синтаксическое дерево и таблицы (без оптимизации, текстовый формат)
Исполняемый модуль (текстовый формат), умещается в несколько десятков байт
ПОН и методы оптимизации
Пишет digitalinvitro,
Да, Сергей, думаю что Вы правы, начну с примера:
вот пример для идеального сворачивания констант
как видно все константы предшествуют членам выражения с переменным значением (переменным грубо говоря)
методом Дейкстры получаем это выражение в ПОН (Польская обратная нотация или ПОЛИЗ)
24: Constant value 30
23: Constant value 4
22: ( 8) Operate *
21: Constant value 255
20: ( 7) Operate +
19: Constant value 10
18: ( 7) Operate +
17: Local var t
16: ( 7) Operate +
15: Constant value 2
14: Global var j
13: (20) Operate *
12: Constant value 3
11: Constant value 90
10: (20) Operate *
9: (19) Operate -
8: Constant value 2
7: ( 8) Operate /
6: ( 7) Operate +
5: Global var b
4: Constant value 100
3: (19) Operate -
2: Constant value 2
1: ( 8) Operate *
0: ( 7) Operate -
в скобках указан уровень (приоритет) операций полученный для ПОН дополнительно при преобразовании выражения, таким образом я пытался выйти на свертку операций до минимально нижнего уровня, где потом попробовать перемещать исключительно слагаемые - но оказалось сложновато, алгоритм таких перестановок слагаемых не очевиден.
после оптимизации записи ПОН(симулятицией вычисления)
Хорошо видно что все константы свернулись в одну суммарную.
Берем не подготовленный к оптимизации таким способом пример:
Хорошо видно что за членами выражения с переменным значением располагается константа, а именно шестнадцатеричное 0xFF (255).
Разбор выражения в ПОН:
24: Constant value 30
23: Constant value 4
22: ( 8) Operate *
21: Constant value 10
20: ( 7) Operate +
19: Local var t
18: ( 7) Operate +
17: Constant value 2
16: Global var j
15: (20) Operate *
14: Constant value 3
13: Constant value 90
12: (20) Operate *
11: (19) Operate -
10: Constant value 2
9: ( 8) Operate /
8: ( 7) Operate +
7: Global var b
6: Constant value 100
5: (19) Operate -
4: Constant value 2
3: ( 8) Operate *
2: ( 7) Operate -
1: Constant value 255
0: ( 7) Operate +
после оптимизации записи ПОН(симуляцией вычисления)
Хорошо видно что впереди идущие константы свернулись, а вот 255 так и не присовокупилась к ней, так как простейший алгоритм оптимизации пробует вычислять сумму если оба слагаемых константы, а для 255 впереди идущий член - переменная.
Теперь понятно
Пишет st,
Алексей, спасибо за развернутый текст, теперь понятно. И еще, мы уже переходили на "ты", так что не будем забывать эту традицию.
Как я понимаю, ты используешь алгоритм Дейкстры "Сортировочная станция", который непосредственно формирует готовый к исполнению стек. В этом способе есть как преимущества (быстрота разбора и простота реализации, фактически, это небольшая надстройка над лексическим анализатором), так и недостатки (невозможность дальнейшей оптимизации по дереву синтаксического разбора).
Вернемся к твоему примеру.
Если бы анализатор генерировал на выходе синтаксическое дерево, то без оптимизации оно могло бы выглядеть так:
Первоначальная оптимизация дерева по простому алгоритму исключения узлов с двумя подузлами-константами дала бы аналогичный результат, что и алгоритм Дейкстры.
Но это не предел. Теперь можно использовать дополнительную оптимизацию.
Обходим дерево "снизу", от листев к корню (на моей картинке это с самого правого верхнего узла).
1. если узел А1 - константа, то запоминаем узел, его операцию Б1 и поднимемся вверх
иначе переходим к следующему листу А2
2. если операция выше В1 имеет более низкий приоритет чем Б1, то выход
иначе смотрим второй узел Б2 операции В1 (первый - Б1)
3. если Б2 - константа, то проводим операцию Б1 с константой А1 и Б2, заменяем его значением Б2, удаляем узел А1, а Б1 заменяем на А2 (удалив Б1)
4. если Б2 - операция, имеет более высокий приоритет, то поднимаемся еще выше к Г1 и повторяем по п.1
иначе опускаемся по Б2 и смотрим его подузлы А4 и А5 по п.3
Прошу прощения за нестрогую формулировку алгоритма, над этим надо серёзно поработать, но, думаю, что идея понятна.
В итоге получится дерево вида
Если я ничего не упустил, то на этом арифметика завершается. Дальнейшая оптимизация дерева - это алгебраические преобразования, т.е. потребуются соответствующие алгоритмы, используемые в системах компьютерной алгебры и разных решателях уравнений.
Понятно
Пишет digitalinvitro,
Да Сергей я кажется понял, то есть ПОЛИЗ как инструмент оптимизации ограничен и алгоритмы его полной оптимизации не разработаны. Необходим переход к синтаксическому дереву, а точнее рассмотрение выражения триплетами, что еще полнее сворачивать константы. В принципе я вижу путь преобразования ПОН в дерево триплетов, опять таки через использования стека, а именно имея готовый стек S0 и новый S1
Подымаем текущий элемент pop и проверяем его тип, если это ОПЕРАНД, опускаем push его в стек S1, если это ОПЕРАТОР, со стека S1 подымаем pop два элемента ОПЕРАНДА (а это будут именно ОПЕРАНДЫ при условии правильности ПОН) и подключаем в триплет, вместе с ОПЕРАТОРОМ. Получившийся триплет опускаем push в стек S1 (триплет тоже ОПЕРАНД). Прогоны вдоль стека повторяем пока не останется один единственный триплет.
Сергей что мне очень интересно, Дейкстра столп алгоритмики использовал ПОН, он должен был видеть его недостатки или тогда вопросы оптимизации мало кого заботили (хотя например и Вирт и Кнут озабачивались)? Хотя зная мощности тех вычислительных ресурсов наоборот должны были мобилизовывать на поиск преобразований ПОН. Мне кажется алгоритм поиска по синтаксическому дереву - должен транспонироваться на ПОН. Даже свой довесок к ПОН (такой как уровень операций) я считаю избыточным для него, с уровнем операций (когда в зависимости от прохождения скобок равные операции поднимаются на максимальный уровень приоритета) я вижу (пока еще не могу формализовать) алгоритм свертки ПОН триплетами до минимально возможного уровня операций, при котором возможно перемещение членов выражения со своим оператором вдоль стека до ближайшей константы с последующей сверткой. Но как я уже и говорил уровень операций - избыток для ПОН, ну мне так какжется вполне вероятно я и не прав. Так есть потенциал у ПОН или ПОН полностью исследована и заброшена алгоритмиками?
Обойти синтаксическое дерево
Пишет digitalinvitro,
Сергей, думаю что получилось у меня преобразовать в дерево, однако хотелось бы его обозреть так же красиво как ты нарисовал :) не подскажешь алгоритм обхода, понятно что как то рекурсивно - но получается сумятица.
Дерево и стек
Пишет st,
Алексей, восстановить дерево выражения из стека без потери семантки в частном случае можно, если, например, зафисировать правила:
- только левое или только правое заполнение
- узлы - операции, листья - операнды (константы, переменные)
Значит привиденный алгоритм для дерева может быть реализован и на стеке. Просто мне было нагляднее в виде дерева представить логику работы. Без дерева это будет выглядеть, как перебор операндов, нахождение соответствующей ему операции и попытки переместить операнд выше или ниже по стеку без потери семантики (т.е. с учетом приоритетов). Мне кажется, что алгоритм будет сложный, сложнее "деревянного".
Алгоритм Дейкстры имеет вполне конкретную область применения - вычисление алгебраических выражений без синтаксического разбора. Это позволяет обойтись лексическим анализатором (токенайзером), который есть в стандартной библиотеке Си. Видимо, для простых задач вроде вычислений в командной строке этого было достаточно, а для более сложных создавался полноценный транслятор с внутренним представлением семантики, пригодным для глубокой оптимизации.
Т.о., если ты хочешь работать с деревом, то тебе нет смысла реализовывать алгоритм Дейкстры, нужно написать простенький синтаксический анализатор для грамматики выражений (или сгенерировать flex/bison по имеющимся в открытом доступе описаниям). Он будет сразу давать на выходе дерево или упомянутые тобой "тройки" (два операнда и операция).
Обход дерева, как правило, рекурсивный. Он проще в написании, но сложнее в отладке. Вот пример псевдокода для простой оптимизации свертки констант (стартовать надо с корня):
Спасибо за науку
Пишет digitalinvitro,
Сергей, спасибо, буду применять полученные знания :)
Про flex/bison не то что бы я не знал про эти инструменты, знал конечно. Но если честно не умею пользоваться, это серьезные вещи и мне кажется я еще не дорос до такого уровня специализации.
Сергей а вот серьезные компиляторы, предположим icc или скажем тот же Watcom они умеют втаскивать константы под скобки, сокращать их, т.е. упрощать выражения на более высоком уровне?
Оптимизация
Пишет st,
Спасибо за спасибо, правда, до науки тут еще далеко. Интересно, что практически вся используемая сейчас теория трансляции и языков программирования была разработана и доведена до инженерных технологий еще в 1960-х годах.
Конечно, flex/bison - это отдельный мир, непростой, поэтому для создания простых трансляторов его использование под вопросом. Да и не все языки укладываются в поддерживаемые ими грамматики.
По поводу продвинутых компиляторов, можно провести эксперимент с GCC.
Тестовый пример
Генерируем ассемблерный код без оптимизации
gcc -c -O0 -g -Wa,-a,-ad test01.c > test01.s
Смотрим сгенерированный ассемблер (файл test.s). В тексте можно увидеть константы "130" и "255". То есть даже без оптимизации, семантический анализатор сворачивает константы в дереве.
Первый уровень оптимизации:
gcc -c -O1 -g -Wa,-a,-ad test01.c > test01.s
В сгенерированом файле исчезли все константы. По видимому, компилятор, обнаружив, что переменные в программе суть константы (не изменяются), просто подставил их значения и вычислил выражение целиком.
Чтобы избежать такой предусмотрительности, изменим исходник.
При генерации с уровнем оптимизации -O1 видны все те же константы "130", "255", что и без оптимизации, но появляется "-270".
При генерации с уровнем оптимизации -O3 видна "255", остальные, видимо, преобразованы другим способом.