語法數

語法數，也稱語法樹（Syntax tree），是原始碼語法結構的一種抽象表示。它以樹狀的形式表現程式語言的語法結構，樹上的每個節點都表示原始碼中的一種結構。也稱抽象語法樹，之所以說語法是“抽象”的，是因為這裡的語法並不會表示出真實語法中出現的每個細節。比如，嵌套括弧被隱含在樹的結構中，並沒有以節點的形式呈現；而類似於 if-condition-then 這樣的條件跳轉語句，可以使用帶有兩個分支的節點來表示。

基本介紹

• 中文名：語法數
• 外文名：Syntax tree
• 學科：計算機語言
• 定義：原始碼語法結構的一種抽象表示
• 形狀：樹狀
• 套用：智慧型編輯器、源程式瀏覽器

簡介

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

生成過程

詞法分析

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

語法分析

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

語義分析

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

語法樹解析方法

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

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