简单的Ragel例子，平衡父母？

Question

这里是语法的起点：

%%{
  machine xo;

  char = "x" | "o";
  group = "(" char* ")";
  main := group;
}%%

例如，它处理(xxxx(oo)()xx)。如何将其扩展为允许嵌套组；例如，(xxxx(o(x)o)()xx

我知道递归通常不是由一个Ragel机器支持的。所以这是行不通的

group = "(" ( char | group )* ")";

来自Ragel状态机编译器用户指南(PDF)：(为强调添加的粗体文本)：

“一般来说，Ragel不能处理递归结构，因为语法被解释为一种常规语言。然而，根据需要解析的内容，使用手动编码技术实现递归部件有时是可行的。在递归结构简单且易于识别的情况下，例如在括号的平衡方面，这通常是可行的。” “解析递归结构的一种方法是使用增量和递减计数器的操作，或以其他方式识别递归结构的输入和退出，然后使用fcall和fret跳转到适当的计算机缺陷。或者，语义条件可以用来测试计数器变量。 “更传统的方法是在输入递归结构时调用单独的解析函数(用主机lan表示)，然后在识别结束时返回。”

在关于嵌套括号的邮件列表讨论中，提到了同样的三种方法：

1. 使用use和postpop指定一个可增长的堆栈，然后使用fcall。
2. 计数，然后在操作或条件中进行验证。
3. 在输入递归结构时调用一个新的解析函数(在宿主语言中)。

你能给我举一个例子吗-最好用上面的例子--在Ruby里？谢谢!

Answer 1

使用fcall/fret的一般模式如下：

balanced = [^(){}\[\]] |
               '(' @{ fcall balancedTokensParen; } |
               '[' @{ fcall balancedTokensBracket; } |
               '{' @{ fcall balancedTokensBrace; };
balancedTokensParen   := balanced* ')' @{ fret; };
balancedTokensBracket := balanced* ']' @{ fret; };
balancedTokensBrace   := balanced* '}' @{ fret; };

所以你的案子可以作为

  char = [xo];
  group = '(' @{ fcall group_rest; };
  group_rest := (char|group)* ')' @{ fret; };

  main := group;

lexer函数应该包含stack数组，您必须手动检查top，以确保没有未关闭的'('：

stack = []
%% write init;
%% write exec;
if top > 0 
    cs = %%{ write error; }%%
end

Answer 2

我也一直在寻找关于拉格尔问题的几天！

对于传递递归嵌套括号等需求，Ragel没有得到很好的记录。

经过5天的Google搜索，我找到的唯一示例代码是：

https://bitbucket.org/mitsuhiko/arana-main/src/289ad1a6f083/arana/lexnparse.rl

考虑到Ragel堆栈需求和fgoto()或fcall()、fret()和其他代码管理所需的Ragel代码，我(和其他许多人一样)认为Ragel不是满足这些需求的简单工具。否则，就会有一个以上的工作示例可用。

Answer 3

粗略地说，如果您试图匹配父母，解决方案将涉及以下内容：

open_paren = '(' @{ @paren_count += 1}
close_paren = (')' when @paren_count > 0) @{ @parent_count -= 1}

请查看“用户指南”中关于语义条件的部分。

顺便说一句: Ragel是一个非常强大的工具，你必须了解它的基础才能真正利用它。使用Ragel的第一步是阅读“用户指南”并理解它--尽管仍有一些部分您不确定，但Ragel的使用将非常令人沮丧。