一個基於解析器的腳本語言調用圖產生器

Abstract

調用圖(Call Graph)是一個可以用來表示電腦程式中子程序(Subroutine)間呼叫關係的有向圖，它也是一個基本的程序分析結果，可以用來幫助程式設計師理解程式碼。雖然目前已經有許多調用圖的工具，但大多數只針對編譯語言(Compiled Language)，如gprof、cflow、doxygen等。針對腳本語言(Script Language)的調用圖產生器，如phpCallGraph與pyCallGraph，相對稀少。因此在本論文當中，我們針對腳本語言提出了一個基於解析器(Parser)的調用圖產生器。這個調用圖產生器是建立於現有的編譯器產生器(Compiler Generator)之上，如Yacc(Yet Another Compiler Compiler)與PLY(Python Lex-Yacc)。本論文所提出的調用圖產生器由調用圖詞彙分析器(Call-graph Lexer)、調用圖解析器(Call-graph Parser)、調用圖渲染器(Call-graph Renderer)所組成。在案例研究中，我們分別針對Lua與PHP實作了兩個調用圖產生器。我們將產生出的調用圖與phpCallGraph進行比較，圖形結果顯示我們所產生的調用圖在表達巢狀函式(Nested Function)與進入函式(Entry Function)方面更能夠讓使用者理解。

A call graph is a directed graph that represents calling relationships between subroutines in a computer program, and it also is a basic program analysis result that can be used for human understanding of programs. There have already been many call-graph tools, but most of them only support complied language. The call-graph tools for script languages (e.g., phpCallGraph, pyCallGrpah, etc.) are relatively few. As a result, we present a parser-based call-graph generator for script languages in this thesis. The proposed call-graph generator is constructed by using a compiler generator, such as yacc (Yet Another Compiler Compiler) and PLY (Python Lex-Yacc). The proposed call-graph generator is composed of the call-graph lexer, the call-graph parser and the call-graph renderer. In the simulation cases, we implement two call-graph generators for Lua and PHP respectively. We compare the generated call graphs with phpCallGraph, and the graphic results shows that the call graph we generated is better for understanding in handling nested functions and entry functions.