介绍 Semtrex
5.00/5 (12投票s)
Semtrex 是一个语义树表达式求值器
源代码
本文中讨论的 C 和 C# 代码可以在这里找到
https://github.com/zippy/ceptr
一篇关于 Ceptr 和 Semtrex 概念的优秀博客文章（包括几个视频！）可以在这里找到
http://ceptr.org/2015/04/06/semantic-trees/
引言
在本文中，我想向大家介绍 Eric Harris-Braun 和 Arthur Brock 的工作。他们一直在研究一个他们称之为“Semtrex”的概念——一个语义树正则表达式匹配器，作为名为“Ceptr”的更大项目的一部分。
Ceptr 概念的两个基石是
- 数据总是携带着它的语义，换句话说，赋予数据意义的性质
- 事物的意义（语义）以树形结构自然地表达
由于这些前提，很明显，与我们为一维字符串提供正则表达式 (Regex) 匹配器类似，需要一个树表达式匹配器用于二维或更多维的树。此外，由于树包含意义（语义），树表达式匹配器必须是一个**语义**树正则表达式匹配器。这里我们看到了与 Regex 的另一个区别——Semtrex 匹配数据的语义以及字面值，而 Regex，因为它没有匹配的语义概念，只能匹配字面值。
这给模式匹配引入了一些新的有趣行为——不仅匹配数据的字面值，还匹配数据的语义意义。因此，虽然“42”匹配字面值“42”，但“42 years old”不匹配“42 is the answer to the ultimate question of life, the universe, and everything。”
自然的本质
让我们思考一下为什么语义树很重要，并且，大胆地说，对于计算、通信和数据交换的未来发展来说，它们实际上是必不可少的。既有哲学上的原因，也有具体的计算原因，它们在理解上相互指导。我们将考虑自然界中的一切（尽管我们的重点是数据）如何具有两个特征：意义和结构（关系）。
意义的本质
“语义学是研究意义的学科。”1 为了使信息有价值，该信息必须具有意义。“价值”一词可以解释为“有价值”和“可计算”。信息除非有意义，否则就没有**价值**。信息具有可作为计算基础的价值。因此，通过价值，我们部分地指可以在该值上执行计算，或者该值本身是涉及许多其他值的计算的一部分，并且我们认为这些值和计算都**有价值**。例如，语义网3“提供了一个通用框架，允许数据在应用程序、企业和社区边界之间共享和重用。”3 请注意，该术语本身是由 Tim Berners-Lee4 创造的，用于指代可由机器处理的数据网络。5
自然的意义
自然界是关系性的——从量子物理学最基本的理论模型到物理星系最大的宏观尺度，我们不断地看到“事物”与其他“事物”之间存在关系。此外，这些关系具有结构，我们人类经常将其映射到分层、树状空间中。我们通过组织结构图、系统发育和家谱来做到这一点。我们使用解析树7来解析上下文无关语法。编译器将我们的线性代码解析成 BNF8 树，以生成（再次是线性的）机器代码。
结构（值之间的关系）也是意义以及计算的必要组成部分。就像你不能在没有至少对该值的隐式语义理解的情况下对一个值执行计算一样，你也不能在没有定义结构来关联这些值的情况下对一组值执行计算。此外，这种结构（关系的定义）本身会产生新的意义。
意义：符号与结构
Eric Harris-Braun：“意义来自于在一个社会语境中，符号被应用于具体的形态（结构！）”
Arthur Brock：“意义来自于理解符号在特定语境中的使用。语境意味着以特定方式使用的符号集合。”
例如，这是一个用作椅子、脚凳和桌子的软垫长凳。
（Arthur Brock 在工作、放松，并与 Eric Harris-Braun 下棋）
上下文为“软垫长凳”这个符号提供了重要的额外意义。
结构（关系的定义）创造新意义是一个关键点，虽然它是（并且实际上必须是）自反的或“分形的”，但它解释了我们为什么明确地（或隐式地）创建层次结构。例如，给定我们想要测量的事物，我们给它一个符号——英寸、英尺、千克、光年。这给测量一个语义上下文。我们看到这个“事物”与其他也具有语义意义的“事物”之间的关系，所以我们创建了一个映射这些“事物”之间关系的结构。该结构本身被赋予了一个语义意义，依此类推，以分形方式向上或向下递归我们正在创建的层次结构，从而使我们能够表达越来越复杂和有趣的概念以及这些概念之间的关系。
Eric Harris-Braun：“这是现实世界和编程中一个重要的模式（‘拥有’关系）。这种交替模式是一个基本模式（编程语言、现实世界等），我们在 Ceptr 中试图做的就是使这种基本模式明确化，并对我们正在做的事情有一些自我认知。”
Arthur Brock：“我们在 Ceptr 中所做的是……当你编程时，程序员必须将这些东西视为有意义的单元（变量名），但当我们编译它时，所有这些都消失了，坍缩为内存地址中的结构化数据。然后我们很难共享意义，我们必须构建一个语义层，将意义‘水合’回结构中。”
活着的意义
意义并非静态，这是软件过时的主要原因：软件无法适应意义的变化，超出了某个限制。
- 值会变化——它们被创建、销毁和改变。这种情况发生得最频繁，也是现代软件通常处理得很好的唯一变化（无需程序员干预）。
- 值之间的关系会改变——旧的关系变得“无意义”，新值之间需要新的关系。虽然这发生得较慢，但可以说这是软件需要更新并最终被替换的主要原因。例如，关系数据库（它在表和外键中表达固定关系）的生命周期受限于适应新关系的能力（新表、外键的更改等）。
- 意义本身会改变，尽管时间流逝得很慢。例如，思考“gay”这个词的意义是如何随时间变化的。
- 形成了新的结构并赋予了语义意义。人们可以观察到计算机语言是如何演变的，因为新的结构被整合到语言中，例如 lambda 表达式、匿名方法和 C# 的 async/await 关键字，所有这些都以更高效的语义表达了旧的概念。
Semtrex
认识到意义涉及语义和结构，Semtrex 是我们当前所处计算空间进行更大规模“重写”的基石。目前，我们的计算空间接收语义结构化数据，将语义意义和结构解耦为原始数据流或存储（带或不带单独的模式），然后将这些数据重新组装成相同或不同的语义结构。具有讽刺意味的是，这正是信息和计算机科学新领域本体工程的推动力，它“研究构建本体的方法和方法论：领域内一组概念及其之间关系的正式表示。”9
例如，SMTP 规范10定义了（除其他外）电子邮件地址的结构和语义。当我们写“foo@biz.eu”时，我们剥离了结构和语义意义，实际上存储和传输的电子邮件地址不带其任何原始结构或语义。当我们编写邮件服务器时，我们必须“解析”电子邮件地址，“水合”其结构和其组成部分的语义，以便我们可以对地址执行计算，例如验证、校验、检查白名单、黑名单、执行计费等等。此外，系统非常僵化。例如，我们无法向可以由物理打印和邮寄内容的系统处理的物理地址发送电子邮件。我们无法向电话号码发送电子邮件，然后该电话将拨打电话并通过文本到语音合成读取内容。我们无法向移动电话的短信服务发送电子邮件。为什么？因为邮件服务器必须**假定**“邮件接收者”槽中的值具有特定的语义意义——它必须是电子邮件地址——因为“邮件接收者”槽不携带其值的语义。
边缘空间
Ceptr **架构**的基石是它完全使用语义数据，因此也使用语义树。从更广泛的角度来看，Ceptr 提供了一种在虚拟机“接收器”中处理语义数据的方法。数据以语义包或信号的形式进出接收器，这些语义包或信号当然包含数据和与该数据对应的语义。通过这种方式，接收器只处理对它们有语义意义的事物。
然而，世界上其他地方通常不交换语义信息——相反，它通常是原始二进制数据或人类可读的 ASCII 字符串（就像本文一样）。我们看到 XML 和 JSON 数据包中引入了一些语义意义，它们都能够结构化数据并将属性名称（或键）与数据关联起来。然而，即使对于 XML 和 JSON，属性和键也通常是高级抽象，例如“地址”或“全名”，或者是特定领域的，例如“住所”和“娘家姓”。在前一种情况下，解析数据的程序不知道“地址”在语义上实际上是指家庭地址、度假地址还是公司地址（多种选择之一），在后一种情况下，解析键“domicile”（可能对编写 XML 或 JSON 的程序员具有语义意义）的程序可能需要“翻译”成语义意义“家庭地址”。
虽然这使得世界几乎无限需要程序员不断将一种语义贫乏的数据结构重构为另一种同样贫乏的语义数据结构，但它仍然给我们留下了一个现实世界的问题，即这个问题确实存在。这就是“边缘空间”，外部世界的“数据”和 Ceptr 内部的语义数据在这里进行转换。
从一个例子开始
Marc Clifton 围绕 C 代码构建了一个简单的 IDE（用 C# 实现），为使用 Semtrex 表达式匹配提供了一个实验平台。我们以从 ASCII 字符串解析经纬度到 Semtrex 并对其执行一些匹配测试为例。
构建符号和结构树
第一步是定义结构及其符号。当我们启动 IDE 时，会显示一个空的符号树。让我们为我们的经纬度演示符号和结构创建一个容器
点击“Symbol Namespace”并为容器提供一个名称。这里，我使用“latlon demo”
右键单击“latlon demo”容器，从弹出菜单中选择“Add Symbol”
我们现在可以在属性窗格中定义符号和结构名称
我们假设这是一个“家庭位置”，所以我们给**符号**命名为“HomeLocation”，并指定**结构**是“latlon”
我们还会在“Symbols”和“Structures”窗格中看到列出的符号和结构
接下来，我们定义“latlon”结构。该结构由两个结构为“float”的符号组成
如上图所示，有一小部分内置结构可供选择。请记住，我们甚至可以定义“float”结构的含义——事实上，我们可以将其定义为两个整数（再次是比特结构），带有“mantissa”和“exponent”符号。这个过程可以重复到内存单元中电容电荷的原子级别（甚至更深）。
我们现在已经定义了用于解析经纬度字符串的符号和结构。
将字符串转换为 ASCII 树
由于 Semtrex 是一个**树表达式匹配器**，任何输入字符串都必须转换为 ASCII 树。这是有意为之，因为它使解析器代码保持统一，因为它始终处理树。一个“ASCII 树”，它仅由一个根节点组成，并且每个子节点都是字符串中的单个字符，对于将字符串转换为 Semtrex 可以操作的树结构是必需的。虽然这听起来很傻，但它允许我们停留在语义树的统一世界中作为 Semtrex 的输入。另一种说法是，我们正在尽可能多地用语义描述字符串：“一个 ASCII 字符字符串”，我们将其封装在 ASCII 树**表示**中。我们不知道字符串是什么或它包含什么，但既然我们已经将其放入树结构中，我们就可以解析它了。
给定一个经纬度输入字符串
我们可以通过点击“Parse to ASCII Tree”将其解析成一个 ASCII 树。结果显示在 Semtrex Tree 文本框中（这里只显示了一部分，您应该明白意思）
或者，用 D3 树可视化（显示片段）
树的根是一个符号“ASCII_CHARS”，树的每个元素都是一个结构-值对“ASCII_CHAR”和字符的值。
匹配 ASCII 树
现在我们已经将字符串表示为树，我们可以编写一个 Semtrex 表达式来匹配该树
/ASCII_CHARS/<HomeLocation:<lat:ASCII_CHAR+>,ASCII_CHAR=',',<lon:ASCII_CHAR+>>
请注意，这个表达式不仅匹配输入字符串的格式，还指定了与树状字符串的结构组件关联的符号。
上述 Semtrex 表达式的作用如下：
- 尖括号表示我们正在动态命名（或分配语义符号）输入字符串的匹配部分。
- 在这种情况下，我们正在创建一个符号：“lat”，它将保存逗号之前的 ASCII_CHARS，以及一个名为“lon”的符号，它将保存逗号之后的符号。
- 然后“HomeLocation”是一个符号树，其中“lat”和“lon”是它的两个子节点。
- 这些命名符号（假设系统中存在其结构定义）可以在后续的 Semtrex 匹配中用于它们产生的匹配输出。
我们在下一行输入 Semtrex 表达式并单击 Parse
我们为什么要这样做？因为我们已经将 Semtrex 表达式指定为一个字符串，它本身必须首先转换为树！所以你可以在这里看到模式：输入是语义树，表达式是语义树，Semtrex 将输入树与表达式树进行匹配。事实上，Semtrex 的所有输出也都是语义树。
解析操作的结果也可以查看，这里完整显示
(
SEMTREX_SYMBOL_LITERAL
(
SEMTREX_SYMBOL:ASCII_CHARS
)
(
SEMTREX_GROUP:HomeLocation
(
SEMTREX_SEQUENCE
(
SEMTREX_GROUP:lat
(
SEMTREX_ONE_OR_MORE
(
SEMTREX_SYMBOL_LITERAL
(
SEMTREX_SYMBOL:ASCII_CHAR
)
)
)
)
(
SEMTREX_VALUE_LITERAL
(
ASCII_CHAR:','
)
)
(
SEMTREX_GROUP:NULL_SYMBOL
(
SEMTREX_ONE_OR_MORE
(
SEMTREX_SYMBOL_LITERAL
(
SEMTREX_SYMBOL:ASCII_CHAR
)
)
)
)
)
)
)
再次，作为一个 D3 树
输入是否匹配？
现在我们可以问：“输入树是否匹配 Semtrex 匹配表达式指定的预期格式？” 我们通过点击“匹配？”按钮来提问。
答案是 True
此外，我们还可以询问 Semtrex **如何**匹配，这本身也是一个树
(
SEMTREX_MATCH:1
(
SEMTREX_MATCH_SYMBOL:HomeLocation
)
(
SEMTREX_MATCH_PATH:/1
)
(
SEMTREX_MATCH_SIBLINGS_COUNT:11
)
(
SEMTREX_MATCH:3
(
SEMTREX_MATCH_SYMBOL:lat
)
(
SEMTREX_MATCH_PATH:/1
)
(
SEMTREX_MATCH_SIBLINGS_COUNT:5
)
)
(
SEMTREX_MATCH:2
(
SEMTREX_MATCH_SYMBOL:lon
)
(
SEMTREX_MATCH_PATH:/7
)
(
SEMTREX_MATCH_SIBLINGS_COUNT:5
)
)
)
在 D3 中
请注意，上述匹配结果表达式告诉我们结构及其数据与哪个符号关联。
具象化
我们现在可以将符号与其值“具象化”。我们现在有了一个有意义的结构——一个语义结构。我们通过点击“Embody”按钮来完成此操作。
我们看到了结果
再次，作为一个 D3 树
匹配具象化树
上面所有的步骤实际上都只是将输入字符串转换为语义树所必需的。巧妙之处在于，这是通过 Semtrex 本身完成的。然而，现在我们来到问题的核心。假设数据始终是语义的——换句话说，您收到的输入不是一个相对无意义的字符串（尽管经过一些训练可能人类可读），而是一个对**机器**有意义的结构。这个
对机器有意义。我们现在可以要求机器对其进行匹配，包括结构和它所包含的值。这是一个匹配的 Semtrex 表达式。
/%HomeLocation/(lat=42.25,lon=73.25)
我们可以用“匹配？”按钮测试它，它会返回 true。细心的读者会说，等等！那个输入是一个字符串，必须像之前的匹配表达式一样，首先转换成一个 Semtrex 表达式！你是对的，这就是为什么我们必须首先将（某种）人类可读的输入字符串解析成一个 Semtrex 表达式。
(
SEMTREX_WALK
(
SEMTREX_SYMBOL_LITERAL
(
SEMTREX_SYMBOL:HomeLocation
)
(
SEMTREX_SEQUENCE
(
SEMTREX_VALUE_LITERAL
(
lat:42.250000
)
)
(
SEMTREX_VALUE_LITERAL
(
lon:73.250000
)
)
)
)
)
以及最后的 D3 图形渲染
所以你终于看到了整个操场
构建 Semtrex C 代码
Semtrex（解析器、规范和符号管理）是用 C 语言编写的。Eric 选择 C 语言是因为它在各种平台上都很普遍，从 Arduino 到 Windows 和 Linux，当然也包括它们。
编译 C 代码
构建 C 代码最简单的方法是下载 Eclipse 并打开 Ceptr GitHub 仓库中的 Eclipse 项目。生成的 dll 文件可以复制到 C# 的 bin\Debug 或 bin\Release 文件夹中。
C# IDE
IDE 分为两个项目——“csharp-ide”是 IDE UI。读者可能熟悉 Marc Clifton 编写的其他文章，这些文章利用了相同的方法。
- WeifenLuo 的停靠管理器。
- MycroParser 用于 UI 定义和事件连接。
- MVC 模式用于分离每个可停靠窗格的模型、视图和控制器。
- XTree - 一个通用树构建器。
第二个项目（“ceptrlib”）是与 Eric 的 C 代码的接口，该项目必须使用“允许不安全代码”选项构建。有几个结构，例如：
[StructLayout(LayoutKind.Sequential, Pack = 1), Serializable]
public unsafe struct Defs
{
public TreeNode *structures;
public TreeNode *symbols;
public TreeNode *processes;
public TreeNode *scapes;
};
这些必须标记为不安全以修复错误“指针和固定大小缓冲区只能在不安全上下文中使用。”
C# / C 接口
C 函数调用使用 DllImport 属性。有几个：
// Initialize the the 'C' library.
[DllImport("libceptrlib.dll", CallingConvention = CallingConvention.Cdecl)]
extern static void def_sys();
// Free any allocated memory.
[DllImport("libceptrlib.dll", CallingConvention = CallingConvention.Cdecl)]
extern static void sys_free();
// Create the root of a tree.
[DllImport("libceptrlib.dll", CallingConvention = CallingConvention.Cdecl)]
extern static unsafe TreeNode* _t_new_root(SemanticID sid);
// Declare a symbol.
[DllImport("libceptrlib.dll", CallingConvention = CallingConvention.Cdecl)]
extern static unsafe SemanticID _d_declare_symbol(TreeNode* symbols, SemanticID sid, string label, UInt16 context);
// Define a structure with a variable # of parameters.
[DllImport("libceptrlib.dll", CallingConvention = CallingConvention.Cdecl)]
extern static unsafe SemanticID _dv_define_structure(TreeNode* structures, [MarshalAs(UnmanagedType.LPStr)] string label, int num_params, __arglist);
// Return the number of children in a node.
[DllImport("libceptrlib.dll", CallingConvention = CallingConvention.Cdecl)]
extern static unsafe int _t_children(TreeNode* structures);
// Generate a human-readable dump of a tree.
[DllImport("libceptrlib.dll", CallingConvention = CallingConvention.Cdecl)]
// [return: MarshalAs(UnmanagedType.LPStr)]
extern static unsafe void __t_dump(Defs* defs, TreeNode* t, int level, char* buf);
// Create an ASCII tree from an input string.
[DllImport("libceptrlib.dll", CallingConvention = CallingConvention.Cdecl)]
extern static unsafe TreeNode* makeASCIITree(string stx);
// Parse a Semtrex string into a Semtrex tree.
[DllImport("libceptrlib.dll", CallingConvention = CallingConvention.Cdecl)]
extern static unsafe TreeNode* parseSemtrex(Defs* d, string stx);
[DllImport("libceptrlib.dll", CallingConvention = CallingConvention.Cdecl)]
extern static unsafe int _t_match(TreeNode* semtrex, TreeNode* matchAgainst);
[DllImport("libceptrlib.dll", CallingConvention = CallingConvention.Cdecl)]
extern static unsafe int _t_matchr(TreeNode* semtrex, TreeNode* matchAgainst, TreeNode** matchResult);
[DllImport("libceptrlib.dll", CallingConvention = CallingConvention.Cdecl)]
extern static unsafe TreeNode* _t_embody_from_match(Defs* d, TreeNode* matchResult, TreeNode* semtrex);
初始化和终止
有了上述必要的导入“C”函数，我们可以实现初始化和终止“C”库所需的所有功能。
public unsafe void Initialize()
{
def_sys();
}
public unsafe void Terminate()
{
sys_free();
}
初始化结构和符号树
这些被存储为独立的树，我们用以下方法初始化它们：
public void CreateStructureAndSymbolNodes()
{
Structures = new SemanticID()
{
context = (UInt16)SemanticContexts.SYS_CONTEXT,
flags = (UInt16)SemanticTypes.SEM_TYPE_SYMBOL,
id = (UInt32)SystemSymbolIDs.STRUCTURES_ID
};
Symbols = new SemanticID()
{
context = (UInt16)SemanticContexts.SYS_CONTEXT,
flags = (UInt16)SemanticTypes.SEM_TYPE_SYMBOL,
id = (UInt32)SystemSymbolIDs.SYMBOLS_ID
};
RootStructuresNode = CreateRootNode(Structures);
RootSymbolsNode = CreateRootNode(Symbols);
}
在 C 语言实现中，SemanticID 由以下部分组成：
- 定义它的上下文（16 位）。这可以指定一个本地接收器、安装在系统中的代码或代码和接收器的复合体。
- 标志是中间的 16 位，保留用于符号的标志。
- ID 是该上下文和类型的唯一标识符。
换句话说，一个符号 ID 是 64 位。其中 16 位用于识别标识符的上下文，16 位用于标记符号类型（例如它是一个进程、结构还是符号，或者是范围还是接收器或其他），32 位用于该上下文和类型唯一的标识符，例如结构 ID 或符号 ID。请注意，一个令人困惑的地方是有一个符号 SYMBOLS_ID（复数形式），它包含所有 SYMBOL_ID 的列表。
从 C# 的角度来看，并且不希望每个引用此接口程序集的程序集都要求不安全支持，C 指针被映射到 GUID
public unsafe Guid CreateRootNode(SemanticID structures)
{
TreeNode *node = _t_new_root(structures);
Guid guid = RegisterNode(node);
return guid;
}
protected unsafe Guid RegisterNode(TreeNode* node)
{
Guid guid = Guid.NewGuid();
nodes[guid] = (IntPtr)node;
return guid;
}
这样，所有其他程序集都可以使用 Guid 而不是 C 风格的 TreeNode* 来引用树节点。任何节点，给定 Guid，都可以在此程序集中恢复为 TreeNode*。
protected unsafe TreeNode* GetNode(Guid id)
{
return (TreeNode*)nodes[id];
}
内部类型
当然，一个人能实际深入到符号-结构空间的程度是有限的，因此有几种内部值类型来表示机器可理解的基本类型。请记住，您在这里看到的是 C 代码的接口，而 C 没有泛型或反射之类的概念，所以所有的意义（有趣的是，我们同时在语义层面和代码层面讨论意义）都必须通过结构和枚举来表达。
public SemanticID GetFloat()
{
SemanticID sid = new SemanticID()
{
context = (UInt16)SemanticContexts.SYS_CONTEXT,
flags = (UInt16)SemanticTypes.SEM_TYPE_STRUCTURE,
id = (UInt32)SystemStructureID.FLOAT_ID
};
return sid;
}
public SemanticID GetString()
{
SemanticID sid = new SemanticID()
{
context = (UInt16)SemanticContexts.SYS_CONTEXT,
flags = (UInt16)SemanticTypes.SEM_TYPE_STRUCTURE,
id = (UInt32)SystemStructureID.CSTRING_ID
};
return sid;
}
public SemanticID GetInteger()
{
SemanticID sid = new SemanticID()
{
context = (UInt16)SemanticContexts.SYS_CONTEXT,
flags = (UInt16)SemanticTypes.SEM_TYPE_STRUCTURE,
id = (UInt32)SystemStructureID.INTEGER_ID
};
return sid;
}
public SemanticID GetList()
{
SemanticID sid = new SemanticID()
{
context = (UInt16)SemanticContexts.SYS_CONTEXT,
flags = (UInt16)SemanticTypes.SEM_TYPE_STRUCTURE,
id = (UInt32)SystemStructureID.LIST_ID
};
return sid;
}
声明符号和结构
我们在此声明一个符号
public unsafe SemanticID DeclareSymbol(Guid symbols, SemanticID st, string label, SemanticContexts sc = SemanticContexts.RECEPTOR_CONTEXT)
{
TreeNode *pnode = (TreeNode*)nodes[symbols];
SemanticID symbol = _d_declare_symbol(pnode, st, label, (UInt16)sc);
return symbol;
}
和一个结构
public unsafe SemanticID DefineStructure(Guid structures, string name, SemanticID[] symbolArray, SemanticContexts sc = SemanticContexts.RECEPTOR_CONTEXT)
{
TreeNode *structs = (TreeNode*)nodes[structures];
_dv_define_structure(structs, name, symbolArray.Length, __arglist(symbolArray));
SemanticID st = new SemanticID() { context = (ushort)sc, flags = (ushort)SemanticTypes.SEM_TYPE_STRUCTURE, id = (uint)_t_children(structs) };
return st;
}
请记住，一个结构（如“latlon”）实际上是符号（“lat”和“lon”）的集合，因此我们传入组成该结构的符号。
您应该开始在这里看到一个模式——每一个符号和结构的片段都是 SemanticID 的一个实例，无论是用户定义的符号/结构还是系统定义的符号/结构。
将字符串转换为 ASCII 树
现在这是一个简单的过程
public unsafe Guid GetTree(string str)
{
TreeNode* node = makeASCIITree(str);
Guid nodeID = RegisterNode(node);
return nodeID;
}
解析 Semtrex 表达式
public unsafe Guid ParseSemtrex(Guid g_symbols, Guid g_structures, string expression)
{
Defs defs = CreateDefs(g_symbols, g_structures);
TreeNode* node = parseSemtrex(&defs, expression);
Guid nodeID = RegisterNode(node);
return nodeID;
}
具象化匹配结果
public unsafe Guid Embody(Guid g_symbols, Guid g_structures, Guid matchID, Guid semtrexID)
{
Defs defs = CreateDefs(g_symbols, g_structures);
TreeNode* match = GetNode(matchID);
TreeNode* semtrex = GetNode(semtrexID);
TreeNode* resultTree = _t_embody_from_match(&defs, match, semtrex);
return RegisterNode(resultTree);
}
匹配一棵树
public unsafe Tuple<bool, Guid> Match(Guid semtrexID, Guid treeToMatchID)
{
TreeNode* semtrex = GetNode(semtrexID);
TreeNode* treeToMatch = GetNode(treeToMatchID);
TreeNode* resultTree;
int matchState = _t_matchr(semtrex, treeToMatch, &resultTree);
Guid guid = Guid.Empty;
if (matchState == 1)
{
guid = RegisterNode(resultTree);
}
return new Tuple<bool, Guid>(matchState == 1, guid);
}
测试匹配
public unsafe bool MatchTest(Guid semtrexID, Guid matchAgainstID)
{
TreeNode* semtrex = GetNode(semtrexID);
TreeNode* matchAgainst = GetNode(matchAgainstID);
int ret = _t_match(semtrex, matchAgainst);
return ret == 1;
}
整合各部分
在 SemanticUIController.cs 中，您可以看到在处理 UI 事件时所有这些部分是如何组合在一起的。
将字符串解析为 ASCII 树
public void CreateStructuresAndSymbols()
{
symbolMap = new Dictionary<string, SemanticID>();
structureMap = new Dictionary<string, SemanticID>();
ApplicationController.CeptrInterface.CreateStructureAndSymbolNodes();
foreach (string symbolName in ApplicationModel.SymbolRefCount.Keys)
{
if (!symbolMap.ContainsKey(symbolName))
{
// Find the symbol in the tree.
Symbol symbol = FindSymbolInTree(symbolName, ApplicationController.SymbolEditorController.View.TreeView.Nodes);
if (symbol == null)
{
throw new Exception("The symbol " + symbolName + " should have been found in the tree.");
}
SemanticID topStructure = ApplicationController.Recurse(symbol, structureMap, symbolMap);
SemanticID symbolID = ApplicationController.CeptrInterface.DeclareSymbol(
ApplicationController.CeptrInterface.RootSymbolsNode, topStructure, symbolName);
symbolMap[symbolName] = symbolID;
}
}
}
// Convert a string to an ASCII tree.
public void ToTree(object sender, EventArgs args)
{
CreateStructuresAndSymbols();
asciiTreeID = ApplicationController.CeptrInterface.GetTree(View.tbInputString.Text);
DumpOutput(asciiTreeID);
}
上述代码将符号树（由 .NET 的 TreeView 控件简单管理）映射到一个符号和结构字典，适合 C 代码处理。一旦符号和结构被初始化，就调用接口函数 GetTree 返回 ASCII 树的 Guid。
从 ASCII 字符串创建 Semtrex 树
public void ToSemtrex(object sender, EventArgs args)
{
parseExprID = ApplicationController.CeptrInterface.ParseSemtrex(
ApplicationController.CeptrInterface.RootSymbolsNode,
ApplicationController.CeptrInterface.RootStructuresNode,
View.tbParseExpr.Text
);
DumpOutput(parseExprID);
}
匹配 ASCII 输入字符串
使用从上述方法获得的树 ID，我们将经纬度输入字符串与解析后的 Semtrex 树进行匹配。
public void Match(object sender, EventArgs args)
{
Tuple<bool, Guid> result = ApplicationController.CeptrInterface.Match(parseExprID, asciiTreeID);
if (result.Item1)
{
View.tbMatchResult.Text = "True";
matchResultTreeID = result.Item2;
DumpOutput(matchResultTreeID);
}
else
{
View.tbMatchResult.Text = "False";
View.tbSemtrexTree.Text = "";
}
}
具象化结果
我们用输入值具象化匹配结果树
public void Embody(object sender, EventArgs args)
{
embodyID = ApplicationController.CeptrInterface.Embody(
ApplicationController.CeptrInterface.RootSymbolsNode,
ApplicationController.CeptrInterface.RootStructuresNode,
matchResultTreeID,
asciiTreeID
);
DumpOutput(embodyID);
}
解析匹配字符串
如前所述，我们再次需要将表示我们匹配表达式的人类可读字符串解析为 Semtrex 表达式。
public void ToMatchAgainst(object sender, EventArgs args)
{
matchAgainstID = ApplicationController.CeptrInterface.ParseSemtrex(
ApplicationController.CeptrInterface.RootSymbolsNode,
ApplicationController.CeptrInterface.RootStructuresNode,
View.tbMatchAgainst.Text
);
DumpOutput(matchAgainstID);
}
匹配已具象化的 Semtrex
最后，在我们的最后一步中，我们使用上述的 embodyID 以及 matchAgainstID 将具象化树与 Semtrex 匹配表达式进行匹配
public void MatchAgainstMatches(object sender, EventArgs args)
{
bool ret = ApplicationController.CeptrInterface.MatchTest(matchAgainstID, embodyID);
View.tbMatchResult2.Text=(ret ? "True" : "False");
}
在 'C' 端
如引言中所述，Eric 在 C 中实现了实际算法，以实现可移植性和性能。他还编写了一大套单元测试，我们也将提供一个示例。
Semtrex 解析
部分 Semtrex 解析的灵感来自 Russ Cox 的文章《正则表达式匹配可以简单而快速》，特别是将非确定性有限自动机（NFA）扁平化为确定性有限自动机的算法。例如，这是创建有限自动机的 C 代码。
/**
* Given a Semtrex tree, build a partial FSA (returned via in as a pointer to the starting state, a list of output states, and a count of the total number of states created).
*/
char * __stx_makeFA(T *t,SState **in,Ptrlist **out,int level,int *statesP) {
SState *s,*i,*last,*s1,*s2;
Ptrlist *o,*o1;
char *err;
int state_type = -1;
int x;
SemanticID group_symbol;
int group_id;
T *v;
int c = _t_children(t);
Symbol sym = _t_symbol(t);
switch(sym.id) {
case SEMTREX_VALUE_LITERAL_ID:
case SEMTREX_VALUE_LITERAL_NOT_ID:
state_type = StateValue;
s = state(state_type,statesP);
s->data.value.flags = (sym.id == SEMTREX_VALUE_LITERAL_NOT_ID) ? LITERAL_NOT : 0;
// copy the value set (which must be the first child) from the semtrex into the state
v = _t_child(t,1);
if (!v) {
raise_error0("expecting value or SEMTREX_VALUE_SET as first child of SEMTREX_VALUE_LITERAL");
}
if (semeq(_t_symbol(v),SEMTREX_VALUE_SET)) s->data.value.flags |= LITERAL_SET;
s->data.value.values = _t_clone(v);
*in = s;
s->transition = level;
*out = list1(&s->out);
break;
case SEMTREX_SYMBOL_LITERAL_ID:
case SEMTREX_SYMBOL_LITERAL_NOT_ID:
state_type = StateSymbol;
v = _t_child(t,1);
int is_set;
Symbol vsym = _t_symbol(v);
if (!v || !((is_set = semeq(SEMTREX_SYMBOL_SET,vsym)) || semeq(SEMTREX_SYMBOL,vsym))) {
raise_error0("expecting SEMTREX_SYMBOL_SET or SEMTREX_SYMBOL as first child of SEMTREX_SYMBOL_LITERAL");
}
if (c > 2) return "Symbol literal must have 0 or 1 children other than the symbol/set";
s = state(state_type,statesP);
s->data.symbol.flags = (sym.id == SEMTREX_SYMBOL_LITERAL_NOT_ID) ? LITERAL_NOT : 0;
if (is_set) s->data.symbol.flags |= LITERAL_SET;
s->data.symbol.symbols = _t_clone(v);
*in = s;
if (c > 1) {
s->transition = TransitionDown;
err = __stx_makeFA(_t_child(t,2),&i,&o,level-1,statesP);
if (err) return err;
s->out = i;
*out = o;
}
else {
s->transition = level;
*out = list1(&s->out);
}
break;
case SEMTREX_SYMBOL_ANY_ID:
state_type = StateAny;
if (c > 1) return "Symbol any must have 0 or 1 children";
s = state(state_type,statesP);
*in = s;
if (c > 0) {
s->transition = TransitionDown;
err = __stx_makeFA(_t_child(t,1),&i,&o,level-1,statesP);
if (err) return err;
s->out = i;
*out = o;
}
else {
s->transition = level;
*out = list1(&s->out);
}
break;
case SEMTREX_SEQUENCE_ID:
if (c == 0) return "Sequence must have children";
last = 0;
for(x=c;x>=1;x--) {
err = __stx_makeFA(_t_child(t,x),&i,&o,level,statesP);
if (err) return err;
if (last) patch(o,last,level);
else *out = o;
last = i;
*in = i;
}
break;
case SEMTREX_OR_ID:
if (c != 2) return "Or must have 2 children";
s = state(StateSplit,statesP);
*in = s;
err = __stx_makeFA(_t_child(t,1),&i,&o,level,statesP);
if (err) return err;
s->out = i;
err = __stx_makeFA(_t_child(t,2),&i,&o1,level,statesP);
if (err) return err;
s->out1 = i;
*out = append(o,o1);
break;
case SEMTREX_ZERO_OR_MORE_ID:
if (c != 1) return "Star must have 1 child";
s = state(StateSplit,statesP);
*in = s;
err = __stx_makeFA(_t_child(t,1),&i,&o,level,statesP);
if (err) return err;
s->out = i;
patch(o,s,level);
*out = list1(&s->out1);
break;
case SEMTREX_ONE_OR_MORE_ID:
if (c != 1) return "Plus must have 1 child";
s = state(StateSplit,statesP);
err = __stx_makeFA(_t_child(t,1),&i,&o,level,statesP);
if (err) return err;
*in = i;
s->out = i;
patch(o,s,level);
*out = list1(&s->out1);
break;
case SEMTREX_ZERO_OR_ONE_ID:
if (c != 1) return "Question must have 1 child";
s = state(StateSplit,statesP);
*in = s;
err = __stx_makeFA(_t_child(t,1),&i,&o,level,statesP);
if (err) return err;
s->out = i;
*out = append(o,list1(&s->out1));
break;
case SEMTREX_GROUP_ID:
if (c != 1) return "Group must have 1 child";
s = state(StateGroupOpen,statesP);
*in = s;
group_symbol = *(SemanticID *)_t_surface(t);
group_id = ++G_group_id;
s->data.groupo.symbol = group_symbol;
s->data.groupo.uid = group_id;
err = __stx_makeFA(_t_child(t,1),&i,&o,level,statesP);
if (err) return err;
s->out = i;
s1 = state(StateGroupClose,statesP);
patch(o,s1,level);
s1->data.groupc.openP = s;
*out = list1(&s1->out);
break;
case SEMTREX_DESCEND_ID:
if (c != 1) return "Descend must have 1 child";
s = state(StateDescend,statesP);
*in = s;
err = __stx_makeFA(_t_child(t,1),&i,&o,level-1,statesP);
if (err) return err;
s->out = i;
*out = o;
break;
case SEMTREX_NOT_ID:
if (c != 1) return "Not must have 1 child";
s = state(StateNot,statesP);
*in = s;
err = __stx_makeFA(_t_child(t,1),&i,&o,level,statesP);
if (err) return err;
s->out = i;
*out = append(o,list1(&s->out1));
break;
case SEMTREX_WALK_ID:
if (c != 1) return "Walk must have 1 child";
s = state(StateWalk,statesP);
*in = s;
err = __stx_makeFA(_t_child(t,1),&i,&o,level,statesP);
if (err) return err;
s->out = i;
*out = o;
break;
default:
return "Unknown SEMTREX SYMBOL";
}
return 0;
}
/**
* wrapper function for building the finite state automata recursively and patching it to the final match state
*/
SState * _stx_makeFA(T *t,int *statesP) {
SState *in;
Ptrlist *o;
G_group_id = 0;
char *err = __stx_makeFA(t,&in,&o,0,statesP);
if (err != 0) {raise_error0(err);}
patch(o,&matchstate,0);
return in;
}
单元测试
我们将查看上述代码的单元测试。首先，两个宏。
/// macro to add a single symbol literal to semtrex tree #define _sl(t,s) __sl(t,0,1,s) /// macro to add a single symbol literal not to semtrex tree #define _sln(t,s) __sl(t,1,1,s)
这些是用于调用函数以创建 Semtrex 符号集的辅助函数
/**
* utility function to create a semtrex litteral symbol set
*/
T *__sl(T *p, int not,int count, ...) {
va_list symbols;
T *t = _t_newr(p,not ? SEMTREX_SYMBOL_LITERAL_NOT : SEMTREX_SYMBOL_LITERAL);
T *ss = count > 1 ? _t_newr(t,SEMTREX_SYMBOL_SET) : t;
va_start(symbols,count);
int i;
for(i=0;i<count;i++) {
_t_news(ss,SEMTREX_SYMBOL,va_arg(symbols,Symbol));
}
va_end(symbols);
return t;
}
这在创建测试 Semtrex 的函数中被使用
T *_makeTestSemtrex1() {
// /TEST_STR_SYMBOL/(1/11/111),2,3
T *s = _sl(0,TEST_STR_SYMBOL);
T *ss = _t_newi(s,SEMTREX_SEQUENCE,0);
T *s1 = _sl(ss,sy1);
T *s11 = _sl(s1,sy11);
T *s111 = _sl(s11,sy111);
T *s2 = _sl(ss,sy2);
T *s3 = _sl(ss,sy3);
return s;
}
由测试函数使用
void testMakeFA() {
SState *s1, *s2, *s3, *s4, *s5, *s6;
T *s = _makeTestSemtrex1();
int states = 0;
SState *sa = _stx_makeFA(s,&states);
spec_is_equal(states,6);
spec_state_equal(sa,StateSymbol,TransitionDown,TEST_STR_SYMBOL);
s1 = sa->out;
spec_state_equal(s1,StateSymbol,TransitionDown,sy1);
s2 = s1->out;
spec_state_equal(s2,StateSymbol,TransitionDown,sy11);
s3 = s2->out;
spec_state_equal(s3,StateSymbol,-2,sy111);
s4 = s3->out;
spec_state_equal(s4,StateSymbol,TransitionNextChild,sy2);
s5 = s4->out;
spec_state_equal(s5,StateSymbol,TransitionUp,sy3);
s6 = s5->out;
spec_is_equal(s6->type,StateMatch);
spec_is_ptr_equal(s6->out,NULL);
_stx_freeFA(sa);
_t_free(s);
}
Semtrex 令牌 - 正则表达式极客的详细部分
本节的格式描述了每个
- 语义符号（本节的副标题）
- 其文本表示
- 它匹配什么
- 示例
- 附加说明
SEMTREX_SYMBOL_LITERAL
它匹配的符号名称
它匹配特定符号的树节点
/%HomeLocation/(lat=42.25,lon=73.25)
HomeLocation 是符号字面量
SEMTREX_VALUE_LITERAL
符号名称 = 值（从文本中引用）
它匹配给定符号和特定值的树节点
/%HomeLocation/(lat=42.25,lon=73.25)
lat=42.25 匹配符号“lat”和值“42.25”
SEMTREX_SYMBOL_LITERAL_NOT
! 后跟符号名称
它匹配除给定符号之外的任何符号的树节点
!PUNCTUATION
SEMTREX_VALUE_LITERAL_NOT
符号名称 != 值
它匹配给定符号的树节点和任何不匹配该值的值
ASCII_CHAR!=' '+
匹配值不等于空格的任何 ASCII 字符节点
SEMTREX_SYMBOL_SET
{逗号分隔的符号}
它匹配给定符号集中的树节点
{lat, lon}
匹配一个 lat 或 lon 节点
SEMTREX_VALUE_SET
符号 = {逗号分隔的值}
符号 != {逗号分隔的值}
它匹配一个树节点，该树节点的符号是给定类型，并且其值与集合中的值匹配（或不匹配）。
ASCII_CHAR!={'/','?',' '}
匹配包含 /, ?, 或空格之一的 ASCII 字符
SEMTREX_ZERO_OR_MORE
文本表示为 *（星号）
它匹配零个或多个同级节点
ASCII_CHAR!={'/','?',' '}*
匹配零个或多个其值不在 /, ?, 和空格集合中的 ASCII 字符节点
SEMTREX_ONE_OR_MORE
文本表示为 +（加号）
它匹配一个或多个同级节点
ASCII_CHAR!={'/','?',' '}+
匹配一个或多个其值不在 /, ?, 和空格集合中的 ASCII 字符节点
SEMTREX_ZERO_OR_ONE
文本表示为 ? (问号)
它匹配零个或一个同级节点
ASCII_CHAR!={'/','?',' '}?
匹配零个或一个其值不在 /, ?, 和空格集合中的 ASCII 字符节点
SEMTREX_SYMBOL_ANY
文本表示为 .（点）
它匹配任何符号的树节点
.*
零个或更多任意符号
SEMTREX_OR
文本表示为 | (管道符)
它匹配一个与一个表达式或另一个表达式匹配的树。或的任何一侧都可以是任何 Semtrex 表达式。
lon=72.25 | lon=68.32 HomeLocation | BusinessLocation
上面说明了匹配两个不同的表达式。第一个是值字面量匹配，第二个是符号匹配。
SEMTREX_SEQUENCE
文本表示为 , (逗号)
匹配一个同级树，后跟另一个同级树，依此类推。
ASCII_CHAR='H',ASCII_CHAR='T',ASCII_CHAR='T',ASCII_CHAR='P'
匹配四个 ASCII 字符 HTTP
SEMTREX_GROUP
<名称 : 表达式>
允许您将符号名称与匹配内容关联，或将更大的表达式分组以用作其他 semtrex 表达式的一部分。
<HomeLocation:<lat:ASCII_CHAR+>,ASCII_CHAR=',',<lon:ASCII_CHAR+>>
这是一个命名序列，包含一个命名组、一个逗号和另一个命名组。
SEMTREX_WALK
文本表示为 % (百分号)
以下 Semtrex 表达式可以在树中的任何位置匹配，而不是当前匹配节点的位置。
/%HomeLocation/(lat=42.25,lon=73.25)
这将在树的某个位置（本例中）匹配特定的家庭位置，而不是在根部。
同级
() 括号用于区分同级和子级。因为树直接编码了这些信息，所以没有相应的 Semtrex 符号。
参考文献
1. http://en.wikipedia.org/wiki/Semantics
2. http://en.wikipedia.org/wiki/Great-circle_distance
3. "W3C 语义网络活动". 万维网联盟 (W3C). 2011年11月7日. 检索于 2011年11月26日.
4. http://en.wikipedia.org/wiki/Tim_Berners-Lee
5. 伯纳斯-李，蒂姆；詹姆斯·亨德勒；奥拉·拉斯西拉 (2001年5月17日)。 “语义网络”。 科学美国人杂志。检索于 2008年3月26日。
6. http://dictionary.reference.com/browse/Phylogeny
7. http://en.wikipedia.org/wiki/Parse_tree
8. http://en.wikipedia.org/wiki/Backus%E2%80%93Naur_Form
9. http://en.wikipedia.org/wiki/Ontology_engineering
10. http://tools.ietf.org/html/rfc5321
11. http://json.org/