7

这是语法的起点：

%%{
  machine xo;

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

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

我知道递归通常不受一台 Ragel 机器的支持。所以这行不通：

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

来自Ragel State Machine Compiler User Guide (PDF)：（为强调而添加了粗体文本）：

“一般来说，Ragel 无法处理递归结构，因为语法被解释为常规语言。但是，根据需要解析的内容，有时使用手动编码技术实现递归部分是可行的。这通常适用于递归结构的情况简单且易于识别，例如在括号的平衡中。”

“解析递归结构的一种方法是使用递增和递减计数器的操作，或者以其他方式识别递归结构的入口和出口，然后使用 fcall 和 fret 跳转到适当的机器定义。或者，可以使用语义条件来测试计数器变量。

“一种更传统的方法是在输入递归结构时调用单独的解析函数（以宿主语言表示），然后在识别到结尾时返回。”

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

  1. 使用 prepush 和 postpop 指定一个可增长的堆栈，然后使用 fcall 和 fret。

  2. 计数，然后在动作或条件中验证。

  3. 输入递归结构时调用新的解析函数（以宿主语言）。

你能给我举一个例子吗——最好使用我上面的例子——在 Ruby 中？谢谢！

4

3 回答 3

10

使用 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;

词法分析器函数应该包含stack数组，您必须手动检查top以确保没有未关闭的 '(':

stack = []
%% write init;
%% write exec;
if top > 0 
    cs = %%{ write error; }%%
end
于 2012-10-11T09:00:24.317 回答
1

我也一直在寻找关于那个 Ragel 问题的日子！

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

我在 Google 搜索 5 天后发现的唯一示例代码是：

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

查看 Ragel 堆栈需求和 fgoto() [或 fcall()]、fret() 和其他代码管理所需的 Ragel 代码开销，我（和许多其他人一样）认为 Ragel 是不是满足此类需求的简单工具。否则将有不止一 (1) 个可用的工作示例。

于 2012-08-19T12:13:29.953 回答
1

粗略地说，如果您尝试匹配括号，则解决方案将涉及以下内容：

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

查看用户指南末尾的语义条件部分。

顺便说一句：Ragel 是一个非常强大的工具，你必须了解它的基础才能真正使用它。使用 Ragel 的第一步是阅读用户指南并理解它 - 虽然仍有部分您不确定，但 Ragel 使用起来会非常令人沮丧。

于 2012-10-10T19:29:57.257 回答