c - 如何让 Ragel 解析由 (space* ":"space*) 分隔的两个名称？

Question

我想解析以下内容:

name:name

名称以字母开头和结尾，并且可以包含字母和空格的任意组合。它们也可以是空白的。我的规则是:

identifier = alnum (space* alnum)*;
name       = (identifier | zlen) >sName $pName %fName;

名称可以用冒号分隔，名称和冒号之间可以有空格。我的规则是:

sep = space* ":" space*;
main := name sep name;

这不起作用，因为 identifier 中的 space* 和 sep 中的 space* 显然混淆了解析器。我最终在名称的每个空格中执行了操作 fName。

如果我将 sep 更改为:

sep = ":";

然后一切都很好。我该如何修改这些规则，以便解析器按照我的意图进行？

此问题的源代码在这里:https://gist.github.com/1661150

Answer 1

这类问题有两种基本的解决方法。

1. 定义 Action ，使其可以安全地多次执行，
2. 更改语法，使操作只执行一次。

在这种情况下，我会选择混合方法。使用 Action 记录一个name的开始和结束位置:这些 Action 可以安全地执行多次，因为它们只是记录位置。一旦你确定你已经过了这个名字，执行一个只会执行一次的不同操作。

/* C code */
char *name_start, *name_end;

/* Ragel code */
action markNameStart { name_start = p; }
action markNameEnd { name_end = p; }
action nameAction {
    /* Clumsy since name is not nul-terminated */
    fputs("Name = ", stdout);
    fwrite(name_start, 1, name_end - name_start, stdout);
    fputc('\n', stdout);
}

name = space* %markNameStart
       (alnum+ %markNameEnd <: space*)+
       %nameAction ;
main := name ":" name ;

此处，name 的语法包括任意空格和至少一个字母数字字符。当遇到第一个字母数字字符时，其位置保存在 name_start 中。 .每当字母数字字符运行结束时，以下字符的位置将保存在 name_end 中. <:在技​​术上是不必要的，但它减少了 markNameEnd 的频率 Action 被执行。

请确保不要将此类表达式放在任何空格旁边。

我没有测试过上面的代码。你应该在使用之前看看状态机的Graphviz可视化。

拉格尔在做什么

使用您的原始代码，我们假设输入如下:

Hello world : Goodbye world

Ragel 机器从左到右扫描，找到 name 的开始, 并扫描字母数字字符。

Hello world : Goodbye world    ↑

下一个字符是一个空格。所以要么我们遇到了单词内部的空格，要么遇到了单词结尾后的第一个空格。拉格尔如何选择？

Ragel 同时选择两个选项。 这非常重要。 Ragel 试图模拟一个不确定的有限自动机，但由于您的计算机是确定性的，最简单的方法是将 NFA 转换为 DFA，它可以并行模拟无限数量的 NFA。由于 NFA 具有有限数量的状态(因此得名)，DFA 也具有有限数量的状态，因此该技术有效。

遇到空格后，你有一个NFA处于以下状态，寻找剩下的name :

identifier = alnum (space* alnum)*;                    ↑main := name sep name;        ↑

第二个 NFA 处于以下状态，它假设 name已经结束(并且此 NFA“过早地”执行了 fName 操作):

sep = space* ":" space*;      ↑main := name sep name;             ↑

这对你来说很明显，对我来说也很明显，只有第一个 NFA 是正确的。但是用 Ragel 创建的机器一次只看一个字符，它们不会向前看哪个选项是正确的。第二个 NFA 最终会在它期望看到的位置遇到一个字母数字字符 ":" ，因为这是不允许的，所以第二个 NFA 将消失。

查看 Ragel 文档

这是对 % 的描述:

expr % action

The leaving action operator queues an action for embedding into the transitions that go out of a machine via a final state.

为不一定有助于成功解析的转换执行操作。有关 Ragel 中不确定性的更多信息，请参见 Ragel 指南第 4 章“控制非确定性”，尽管第 4 章中的技术在这种特殊情况下对您没有帮助，因为您机器中的操作只能通过未绑定(bind)的前瞻来消除歧义，这在有限状态机中是不允许的。