DYSTA 為一個從抽象語法樹上進行靜態分析的時間複雜度計算工具，其特色在於能夠分析含有 While、If Else 的程式。這些語法常常出現在嵌入式系統中，但是既有的以抽象語法樹分析為基礎的時間複雜度分析工具，卻無法支援同時含有 While、If Else 的程式，原因在於這些工具沒有使用符號表來記錄變數或是維護符號表的演算法無法處理遇到if-else選擇結構的情況。本研究提出了一個動態規劃的符號表演算法並實作於DYSTA當中，在走訪抽象語法樹的同時，以符號表預先記錄條件分歧與巢狀結構裡各種可能用來計算迴圈執行次數的變數。本研究使用動態規劃，使得在最差的情況下從符號表中搜尋變數的時間複雜度大幅地降低。從較直覺演算法的O(n*2^h)降低為線性時間O(n)，其中n為符號表內的符號個數、h為作用域堆疊的深度。 ;Power consumption of embedded system can be reduced by hardware and software, and it can be calculated from hardware level by current and voltage.However, for software, it is impossible to directly calculate the power consumption of a program because a program may have different power consumption due to different execution environments.To address this issue, we consider the problem of power consumption from time complexity since it has positive correlation with power consumption. In other words, using time complexity to evaluate whether consuming more power or not.In this work, we propose an automated time complexity analyzer called DYSTA to help software designers rapidly analyze time complexities of functions in a large project in order to understand which functions will consume more power.
DYSTA is a time complexity analyzer using static AST analysis.It features in analyzing a program having ′while′, ′if-else′ statements.So far as we know, existing time complexity analyzers based on AST analysis cannot deal with a program contains those statements, though those statements are usually used in a embedded system program.The reason might include the lack of using symbol table and the handling for ′if-else′ statement.In this work, we propose a symbol table algorithm and give a preliminary implementation, DYSTA. We use symbol table to maintain variables in selection/nested structure and calculate the execution times of loop during AST traversal. Our work uses dynamic programming to reduce the time complexity of searching a variable in symbol table in the worst case. Instead of O(n*2^h) in a naive implementation, the time complexity in DYSTA is reduced to linear time O(n), which n is the number of variables in symbol table and $h$ is the depth of scope stack.
