2

我想解析以下内容：

name:name

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

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

名称可以用冒号分隔，也可以在名称和冒号之间使用空格。我的规则是：

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

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

如果我将 sep 更改为：

sep = ":";

那么一切都很好。如何修改这些规则，以便解析器执行我想要的操作？

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

4

1 回答 1

10

此类问题有两种基本解决方案。

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

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

/* 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 ;

这里， for 的语法name包括任意空格和至少一个字母数字字符。当遇到第一个字母数字字符时，其位置保存在name_start. 每当字母数字字符的运行结束时，下一个字符的位置就会保存在name_end. 这<:在技术上是不必要的，但它减少了markNameEnd执行操作的频率。

请确保不要将这样的表达式放在任何空格旁边。

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

拉格尔在做什么

使用您的原始代码，假设输入如下：

你好世界：再见世界

Ragel 机器从左到右扫描，找到 a 的开头name，然后扫描字母数字字符。

你好世界：再见世界
    ↑

下一个字符是空格。因此，要么我们在单词中遇到了空格，要么在单词末尾遇到了第一个空格。拉格尔如何选择？

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

遇到空间后，你有一个NFA处于以下状态，寻找其余的name：

标识符 = alnum（空格* alnum）*；
                    ↑

主要 := 名称 sep 名称；
        ↑

第二个 NFA 处于以下状态，它假设name已经结束（并且这个 NFA fName“过早地”执行操作）：

sep = 空格* ":" 空格*;
      ↑

主要 := 名称 sep 名称；
             ↑

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

查看 Ragel 文档

以下是 的描述%：

expr % action

离开动作操作符排队一个动作以嵌入到通过最终状态离开机器的转换中。

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

于 2012-01-23T07:18:35.710 回答