简单的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跳转到适当的机器定义.或者,语义条件可用于测试计数器变量.

"更传统的方法是在输入递归结构时调用单独的解析函数(以主机语言表示),然后在识别结束时返回."

从嵌套括号的邮件列表讨论中,提到了相同的三种方法:

1. 使用prepush和postpop指定可增长的堆栈,然后使用fcall和fret.

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;

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

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