語法數

語法數（語法樹）作為一種重要的程序中間表示形式，其基本形成過程可以大致分為三個步驟，即首先對源程序代碼進行詞法分析，對詞法分析生成的單詞流進行語法分析，最後進行語義分析形成源代碼的語法樹。語法樹作為一種良好的中間表示，語法樹包含了完整的源程序信息。利用語法樹可以實現多種源程序處理工具，比如智能編輯器、源程序瀏覽器等。此外，語法樹的解析器也可以作為程序靜態分析工具的前端，為其提供一種便於分析的輸入 ^[1]  。語法樹的構建首先要創建相應源代碼的節點，每個節點表示一個類別的代碼。節點的類型分為複合節點和基節點，代碼中的非終結符對應着複合節點，而終結符對應着基節點。其次要根據所要解析語言的語法結構設計出合適的樹形結構來表示不同種類的程序語句，設計的好壞直接影響後面對程序的分析效率。

作為程序編譯過程的第一個階段，將程序源代碼作為字符流依次輸入，對讀入的字符序列進行掃描分析，最終轉換成單詞序列輸出，其中“單詞”是組成程序的最小單位。此過程並不考慮單詞之間的關係。詞法分析為抽象語法樹的生成提供了符號節點。

此過程是程序編譯過程的第二個階段，主要是對程序進行邏輯分析。其主要任務是在第一個階段產生的單詞序列的基礎上，根據所分析語言的語法規則，分析出程序的基本語法結構，如方法、變量、表達式等各種組成程序的成分。

此過程是編譯過程的第三個階段，主要是對程序進行邏輯分析，主要分析目標是結構上沒有錯誤的源程序，主要分析方法是對這類源程序進行上下文有關的性質核査，以及類型的核査，主要是為了確定源程序在語義上是否準確。比如它的一個工作就是審查源程序中的每個算法的運算對象是否符合程序語言的規範。如果不符合，則應該報錯 ^[2]  。

語法樹結構比較簡單，其對應的詞法規則和語法規則易於構造，使用flex和bison工具生成的解析器能夠有效地對抽象語法樹進行解析。解析器由三部分組成，分別是flex生成的詞法分析器、bison生成的語法分析器和手工編寫的驅動程序。詞法分析器識別抽象語法樹文件的記號流，提供給語法分析器；語法分析器利用嵌入其中的語義動作識別語法樹節點，完成解析任務；驅動程序負責為詞法分析器和語法分析器提供一個調用接口，並提供解析所需的數據結構和函數的實現。

為使解析後的抽象語法樹便於遍歷，使用哈希表作為抽象語法樹的存儲結構，每個哈希表節點對應一個抽象語法樹節點，樹節點編號作為哈希表的關鍵字，採用直接定址法構造哈希函數。哈希表節點存儲樹節點的節點編號、節點標識符和指向節點標記列表的指針。節點標記列表採用鏈表存儲，每個哈希表節點包含一個指向該鏈表的指針。解析過程主要使用鏈表、哈希表等數據結構，因此Linux下實現該解析器，可以使用glib庫提供的鏈表、哈希表及其操作函數作為解析器所需的數據結構和函數。