[發明專利]模塊化森林自動機

有效

• 申請號: 200980139411.6
• 申請日: 2009-08-20
• 公開（公告）號: CN102165434A
• 公開（公告）日: 2011-08-24
• 發明（設計）人: G·M·德拉-利貝拉;S·E·盧科
• 申請（專利權）人: 微軟公司
• 主分類號: G06F17/00
• 分類號: G06F17/00;G06F17/30
• 代理公司: 上海專利商標事務所有限公司 31100
• 代理人: 陳斌

背景

編程語言可以使用模式來區別值的類。例如，下面的兩行偽代碼定義計算一列整數的總和的函數。

Sum(nil)＝0；

Sum(cons[head，tail])＝head+Sum(tail)；

此示例中的模式有兩個目的。首先，它們區別輸入情況。其次，它們允許通過使用模式變量和類型推斷來進行簡潔值解構。

模式與結構類型緊密相關。此處所描述的正則樹模式是也可以包括變量綁定的正則樹類型。與語義動作相耦合的樹模式叫做樹變換規則。

諸如XML模式語言之類的結構類型系統定義各類別的值。編程語言常常使用結構類型系統來靜態地檢查程序安全屬性。SQL數據庫還使用主要聚焦于結構的類型系統。通過聯接所產生的表例如包含可以描述為具有匿名結構類型的元組。數據庫管理系統要求各種程序可以解釋存儲在該系統中的數據。結構類型系統幫助數據庫管理系統滿足這一要求。

分布式系統也產生對于結構類型的要求。由于等待時間，在分布式程序組件之間交換的消息常常比在對象之間交換的方法參數更大、更加復雜。

存儲在數據庫中的并且在分布式組件之間交換的值在復雜性方面介于由程序表達式操縱的簡單值和圖靈機的復雜性之間。如此處所描述的，正則樹模式被用來定義結構復雜性的這些中間級別。

表達和分析有序的和無序的正則樹模式是有用的和有益的能力。其中分析將被有利地改進的域的示例包括模型校驗和使用部分有序的樹模式的授權邏輯。諸如XML模式之類的某些現有語言可以使用部分有序的正則樹，但是當前缺乏用于進行子類型化(subtyping)的手段。此外，這樣的語言可以施加語義約束，以便在當前已知方法下支持有效的實現。

對貪婪正則表達式匹配和編程語言XStatic的某些工作已經研究了如何將正則有序的樹類型合并到面向對象的語言中。類似于XDuce，XStatic對于序列使用統一表示。這樣的工作將正則有序的樹類型映射到對象，但是使用展平處理(flattening)來支持所包括的正則語言的自然語義。最后，trx在Scheme(模式)的上下文中研究正則有序的樹類型。

對下推森林自動機(PFA)也完成了某些工作。然而，PFA卻不提供子類型化算法，或用于尋址無序的嵌套(多重集)的機制。

簡要概述

本發明的各實施例涉及模塊化森林自動機(MFA)。此處所描述的模塊化森林自動機可以被用來描述和分析正則樹模式，并可以創建可以簡明地表達帶標記的有向圖的轉換的模塊化森林轉換器(transducer)(MFT)。圖轉換是邏輯、過程模型、以及編程語言的實現中的基本成份。模塊化森林自動機的實現可以被用來支持高性能的、強類型的圖轉換。

模塊化森林自動機是用于定義、重新組織、以及轉換部分有序的、有限的、未分層級(unranked)的樹的集合的機制。MFA支持對MFA分層結構的分析和合成。MFA提供對有序的和無序的樹模式的統一處理。

此處所描述的實施例包括用于分析正則樹模式的方法、系統、以及計算機程序產品。特定實施例允許接收可以被確定或重寫為描述序列和集合兩者的模塊(機器)的數據。可以從根據接收到的數據確定的模塊創建并集。所確定的模塊和模塊的并集可以包括帶標記的接受狀態。根據帶標記的接受狀態，可以為模塊確定子類型關系。

此處所描述的其他實施例還包括用于表達正則樹模式的轉換的方法、系統、以及計算機程序產品。可以接收正則樹模式，并可以接收特定實例數據。可以從接收到的正則樹模式編譯轉換器。可以利用對應于所需轉換的指令來擴充轉換器變換。可以根據經擴充的轉換器變換和實例數據，確定正則樹模式的元素和實例數據的元素之間的對應關系。

提供本概述是為了以精簡的形式介紹將在以下詳細描述中進一步描述的一些概念。本發明內容并不旨在標識出所要求保護的主題的關鍵特征或必要特征，也不旨在用于幫助確定所要求保護的主題的范圍。

本發明的附加特征和優點將在以下描述中敘述，且其一部分根據本描述將是顯而易見的，或可通過對本發明的實踐來獲知。本發明的特征和優點可通過在所附權利要求書中特別指出的工具和組合來實現和獲得。本發明的這些和其他特征將通過以下描述和所附權利要求書變得更加顯而易見，或可通過對下文中所述的本發明的實踐來領會。

附圖簡述

為了描述可獲得本發明的上述和其它優點和特征的方式，將通過參考附圖中示出的本發明的具體實施例來呈現以上簡要描述的本發明的更具體描述。可以理解，這些附圖只描繪了本發明的各典型實施例，并且因此不被認為是對其范圍的限制，將通過使用附圖并利用附加特征和細節來描述和解釋本發明，在附圖中：