Цитата(ARV @ May 30 2014, 14:10)
я делаю интерпретатор собственного байт-кода. ОПЗ позволяет получить строго линейный байт-код, т.е. извлекаю байт за байтом и исполняю, не нужно передвигать указатели, помнить предыдущие состояния и т.п., как для дерева. получение ОПЗ из нативной формулы достаточно простое, я его уже реализовал. чем лучше дерево для интерпретации - не понимаю.
Дерево может быть представлено в виде префиксной записи (ОПЗ - это постфиксная запись). Т.е. в том же линейном виде, без каких либо указателей и предыдущих состояний. Для вычисления (и печати) дерева применяется рекурсивная функция, т.е. если ваш CPU не накладывает ограничений на глубину стека, то префиксная запись однозначно лучше.
Выглядит это приблизительно так (пример):
Исходная формула:
(10+20)*30ОПЗ:
10 20 + 30 *Префиксная форма:
* (+) 10 20 30 (Скобки вокруг операции показывают наличие скобок, используется только для вывода, кодируется старшим битом)
Процедура вычисления (кусочек):
Код
char* position;
int eval()
{
int arg1, arg2;
switch(*position++ & 0x7F)
{
case '+': arg1=eval(); arg2=eval(); return arg1+arg2;
case '*': arg1=eval(); arg2=eval(); return arg1*arg2;
case 'I': /* constant */ arg1=*(int*)position; position+=sizeof(int); return arg1;
...
}
}
Процедура печати (тоже кусочек)
Код
char* position;
void print()
{
char cmd=*position++;
int arg1;
if (cmd&0x80) printf("(");
switch(cmd & 0x7F)
{
case '+': print(); printf("+"); print(); break;
case '*': print(); printf("*"); print(); break;
case 'I': /* constant */ arg1=*(int*)position; position+=sizeof(int); printf("%d",arg1); break;
...
}
if (cmd&0x80) printf(")");
}
Обратная польская запись, преобразование не туда, а обратно
May 30 2014, 06:48
