#abstract-syntax-tree #control-flow-graph
Вопрос:
Я знаю, что график потока управления(CFG) может быть построен из абстрактного синтаксического дерева (AST).
Однако мне неясно, является ли CFG подмножеством AST?
В качестве примера, учитывая CFG, можем ли мы вернуться к AST?
Комментарии:
1. Это не подмножество, это новая структура. Но очевидно, что они связаны. И вы всегда можете спроектировать трансформатор, чтобы он был обратимым, так что «можем ли мы вернуться» — это тривиальная истина. (Q. v. функциональное программирование.,)
2. Как вы определяете CSG? На странице Википедии на CFGs есть изображение с некоторыми примерами, которые довольно явно нельзя использовать для восстановления AST, потому что график просто не содержит никакой информации, кроме узла для каждого базового блока и ребра для каждого возможного перехода.
Ответ №1:
Однако мне неясно, является ли CFG подмножеством AST?
Нет, AST-это полностью синтаксическая конструкция. Но CST хорошо интегрирован с семантикой языка. Кроме того, они представляют собой разные вещи.
В качестве примера, учитывая CFG, можем ли мы вернуться к AST?
Это зависит от языка и от того, как конструкции на этом языке соотносятся с потоком управления. Например, эти 2 фрагмента будут создавать совершенно разные AST;
print('a') if a else print('b')
if a:
print('a')
else:
print('b')
Но сгенерированный CFG будет одинаковым для обоих из них.