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

Question

我想解析以下内容:

name:name

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

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

名称可以用冒号分隔,也可以选择名称和冒号之间的空格.我的规则是:

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

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

如果我将sep更改为:

sep = ":";

一切都很好.如何修改这些规则以使解析器完成我想要的操作？

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

Answer 1

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

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 ;

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

请务必不要在任何空格旁边放置这样的表达式.

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

Ragel正在做什么

使用原始代码,我们假设输入如下:

Hello world : Goodbye world

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

Hello world : Goodbye world
    ?

下一个字符是一个空格.所以要么我们在单词内部遇到空格,要么在单词结尾后遇到第一个空格.Ragel如何选择？

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

离开动作操作符将一个动作排队,以嵌入通过最终状态离开机器的过渡.

对于不一定有助于成功解析的转换执行操作.看到Ragel指南,第4章,"控制非确定性"有关Ragel确定性的更多信息,但在第4章的技术不会帮助你在这个特殊的情况,因为在你的机器的操作只能用绑定先行,这消除歧义在有限状态机中是不允许的.