模块化森林自动机

摘要

模块化森林自动机(MFA)提供部分有序的正则树模式的统一描述。MFA还提供用于这些模式的确定化、〔子类型化、交集、以及补集的简单方法。MFA支持高性能的模式分析和匹配。模块化森林转换器，结合模块化森林自动机，允许编译器对任何状态转换施加语义动作，而同时又支持带标记的有向图的高效转换。

主权项

一种计算机环境(100)中的用于分析正则树模式(200)的方法，所述计算机环境包括至少一个计算机处理器和计算机可读存储器，所述方法包括：接收包括正则树模式的数据，所述正则树模式包括序列和集合中的至少一个(810)；基于接收到的数据来确定或重写对应于所述序列的第一机器(820)；基于接收到的数据来确定或重写对应于所述集合的第二机器(830)；创建所述第一和第二机器的并集(840)；确定所述第一和第二机器的并集的一组带标记的接受状态(850)；根据所述带标记的接受状态确定所述第一和第二机器的子类型关系(860)，所述子类型关系是等效、子类型、超类型、不相交以及相交中的一个，其中如果两个机器M1和M2具有相同的接受状态，则它们是等效的；如果M1包含M2的所有接受状态但是M2不包含M1的所有接受状态，则M1是M2的超类型，M2是M1的子类型；如果M1和M2没有共同的接受状态，则M1和M2不相交；如果M1和M2共享一些接受状态，但是M1和M2中的每一个都具有没有被另一个共享的接受状态，则它们相交。