c语言 - 如何让 Ragel 解析由(空格*":"空格*)分隔的两个名称?



我想解析以下内容:

name:name

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

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

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

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

在这种情况下,我会选择一种混合方法。使用操作来记录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 ;

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

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

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

拉格尔在做什么

对于您的原始代码,让我们假设输入如下:

你好世界:再见世界

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

你好世界:再见世界↑

下一个字符是空格。因此,我们要么遇到了单词内部的空格,要么遇到了词尾后的第一个空格。拉格尔如何选择?

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

遇到空间后,您有一个NFA处于以下状态,正在查找name:的其余部分

标识符=alnum(空格*alnum)*;↑main:=name sep name;↑

第二个NFA处于以下状态,它假设name已经结束(并且该NFA"过早"执行fName操作):

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

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

查看Ragel文档

以下是%:的描述

expr % action

离开操作操作符将一个操作排队,以便嵌入到传出的转换中机器的最终状态。

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

相关内容

最新更新