[發明專利]帶有增量改變的高效不可變句法表示

有效

• 申請號: 201080060863.8
• 申請日: 2010-12-31
• 公開（公告）號: CN102696026A
• 公開（公告）日: 2012-09-26
• 發明（設計）人: M·J·沃倫;A·Y·阿哈羅尼;M·托格森;R·帕凱;N·M·加夫特;J·帕森斯;D·N·舒艾奇;A·V·青高茲;P·戈爾德;K·皮爾希－比森;劉凱玲
• 申請（專利權）人: 微軟公司
• 主分類號: G06F17/00
• 分類號: G06F17/00;G06F17/27
• 代理公司: 上海專利商標事務所有限公司 31100
• 代理人: 蔡悅

背景技術

在計算機科學中，樹是被鏈接的節點的分層數據結構。樹是非循環連接圖，其中該樹中的每一節點具有零個或更多子節點以及最多一個父節點。節點可包含值、條件，或可表示分開的數據結構（諸如另一樹）。按照慣例，子節點在樹中位于其父母“之下”，就是說，計算機科學的樹（不像自然的樹）是向下生長而非向上生長。具有孩子的節點被稱為該孩子的父節點、其祖先或其上級節點。

樹在計算機中由存儲器中的節點以及表示該樹中邊緣的引用來表示。每一父節點具有對其子節點的引用，但并非每一子節點都具有對其父節點的引用。沒有孩子的節點被稱為葉子節點或端節點。節點的高度是從該節點至葉子的最長向下路徑的長度。根的高度是該樹的高度。節點的深度是至其根的路徑（即，其根路徑）長度。樹中最上面的節點被稱為根節點。根節點不具有父母。對樹的操作通常在根節點處開始。樹中的任何節點可通過跟隨各節點之間的指針或鏈接從根節點到達。當到達樹中特定節點時，操作被頻繁地執行。中間節點是樹中具有子節點的任何節點。由此，因為葉子節點沒有子節點，所以葉子節點不是中間節點。

樹中每一節點可被看作從該節點傳下來的子樹的根節點。術語“子樹”指的是包含樹中一節點以及樹中該節點的所有子孫的樹。對應于根節點的子樹是整個樹；對應于任何其他節點的子樹被稱為真子樹。樹可以用許多不同的方式來表示。某些常見表示將節點表示成被分配在堆（不要與堆數據結構混淆）上帶有指向其子節點、其父親、或指向子節點和父節點兩者的指針的記錄，或被表示成陣列中的項，該陣列（例如，二進制堆）具有由各節點在陣列中的位置所確定的各節點之間的關系。

可通過跟隨一系列父節點和這些父節點的子節點之間的連接或指針來對樹進行遍歷。前序遍歷在其到達父節點的子節點之前抵達該父節點。后序遍歷是其中在遍歷父節點之前遍歷該父節點的子節點的一種遍歷。

解析樹或句法樹通常是根據某些形式語法來表示串的句法結構的有序的有根樹。在解析樹中，內部節點由語法的非終端來標記，而葉子節點由語法的終端來標記。產生這些樹的一種類型的程序被稱為解析器。解析樹或句法樹經常在計算機編程語言的處理期間被生成。

發明內容

不可變的樹可允許多線程上的多個客戶機使用同一樹，而不會有觀察到由其他線程同時造成的改變的風險。此外，能夠使用并重復使用樹的各部分使得處理更為高效，因為當只有樹的小部分被改變時整個樹不必一次又一次地被創建。部分的樹可在單向樹中被重復使用，單向樹是其中該樹的節點僅指向或是直接在其之下或是直接在其之上的一個或多個節點的一種樹。即，在只在一個方向上具有指針的樹中，根可指向直接在其之下的節點，且這些節點中的每一個可指向直接在其之下的一個或多個節點（依次類推），但樹中任何節點都不指向其父節點和其子節點兩者。這是通常情況，然而，在兩個方向上都具有指針（雙向指針）的樹比具有單向指針的樹有用得多。傳統的具有雙向指針的樹不能重復使用，而不能重復使用的樹在處理資源方面成本較高，且因此通常較不高效。

為使消費者能夠創建由多個消費者使用的新版本的樹而不犧牲高效性或數據完整性，創建了包括第一不可變私人樹和第二公共樹的數據結構。公共樹控制對私人樹的訪問。私人樹和公共樹的結合使得數據結構中能夠存在向上引用和向下引用，且使得不可變（只讀或不能改變的）和可改變的特性能夠在同一數據結構中共存。數據結構的部分可在其他樹數據結構中被重復使用。私人樹保留了允許其被重新組裝和重復使用的相對信息。公共樹保留了消費者專用信息，且使得工具能夠搜索并將私人樹中的子樹定位目標。公共樹（除根節點之外）的構建可被推遲，直到公共樹中的節點被請求。響應于對訪問私人樹中節點的消費者請求，可按需構建公共樹。

上述數據結構可用于以允許雙向指針的方式來呈現編譯器生成的諸如解析樹、句法樹、語義樹和綁定樹之類的樹，要呈現的消費者專用且相對的位置是不可變的但是允許樹的高效創建和進化，從而創建數據結構的只讀樹的新版本而無需重新創建整個樹。

提供本概述以便以簡化形式介紹將在以下詳細描述中進一步描述的一些概念。本概述并不旨在標識所要求保護主題的關鍵特征或必要特征，也不旨在用于限制所要求保護主題的范圍。

附圖說明

在附圖中：

圖1a是本領域已知的樹數據結構的示例的框圖；

圖1b是本領域已知的樹數據結構的另一示例的框圖；

圖1c是本領域已知的樹數據結構的另一示例的框圖；

圖1d示出了根據此處所公開的主題的各方面的用于帶有增量改變的高效不可變句法表示的系統100的示例；