Распознавание Tail-рекурсивных функций с помощью Flex + Bison и преобразование кода в итеративную форму

Question

Я пишу калькулятор с возможностью принимать новые определения функций. Зная о необходимости новичков пробовать рекурсивные функции, такие как Фибоначчи, я хотел бы, чтобы мой калькулятор мог распознавать рекурсивные функции с хвостом с помощью Flex + Bison и преобразовывать код в итерационную форму. Я использую Flex & Bison, чтобы сделать работу. Если у вас есть какие-либо намеки или идеи, я приветствую их тепло. Спасибо!

EDIT:

Давайте не будем беспокоиться о выводе C или C ++ из Flex & Bison. В основном, я хочу идею или подсказку. Спасибо.

Answer 1

Как я предположил в своем комментарии, это не проблема для лексера, и, возможно, только немного для парсера. Если у вас есть что-то вроде этого:

func f( a ) 
    if ( a == 0 )  
       return a
    return f( a - 1 )

тогда для типичного компилятора C было бы до оптимизатора / генератора кода преобразовать этот рекурсивный вызов в цикл. Конечно, в калькуляторе интерпретации вы можете быть гораздо более гибким, но я бы предположил, что это все же один из последних процессов, которые должны выполнять удаление хвостовых вызовов, а не первые.

Answer 2

Предположим, у вас есть функция ...

def func(args)
   #stuff
return func(otherargs)

затем обратите внимание, что в AST будет что-то вроде return -> func -> otherargs, с некоторыми аннотациями о типах и других типах. Когда вы обойдете его и заметите, что существует возврат F, где F - текущий функциональный фрейм, вы можете преобразовать его в PUSH ARGS, GOTO F вместо полного формирования стекового фрейма и так далее. Вам придется самостоятельно возиться с возвращаемыми значениями.

Также обратите внимание, что это будет значительно сложнее, если вы захотите ходить и выполнять вместо многопроходной системы. Мой инстинкт подсказывает, что ходьба и выполнение потребуют оглядки.

И, нет, я не думаю, что бизон сделает это для вас без цепочки парсеров. Вы анализируете семантику контекстно-зависимым способом.

Answer 3

Совет, который я всегда слышал, таков: не применяйте обнаружение хвостовой рекурсии, если вместо этого вы можете реализовать обнаружение хвостового вызова. Гораздо больше методов заканчиваются вызовом другого метода, чем самим вызовом.

Если ваш стек вызовов не важен для конечного пользователя / разработчика (т. Е. Устранение хвостовых вызовов в Java сведет на нет большую часть значения трассировки стека, если только он не будет обработан очень хитро), тогда вам следует взглянуть на этот маршрут.