ruby - 平衡括号的简单 Ragel 示例？

Question

这是语法的起点:

%%{
  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) :(为强调而添加的粗体文本):

"In general Ragel cannot handle recursive structures because the grammar is interpreted as a regular language. However, depending on what needs to be parsed it is sometimes practical to implement the recursive parts using manual coding techniques. This often works in cases where the recursive structures are simple and easy to recognize, such as in the balancing of parentheses."

"One approach to parsing recursive structures is to use actions that increment and decrement counters or otherwise recognize the entry to and exit from recursive structures and then jump to the appropriate machine defnition using fcall and fret. Alternatively, semantic conditions can be used to test counter variables.

"A more traditional approach is to call a separate parsing function (expressed in the host lan- guage) when a recursive structure is entered, then later return when the end is recognized."

来自 a mailing list discussion on nested brackets , 提到了相同的三种方法:

1. Specify a growable stack using prepush and postpop and then use fcall and fret.

2. Counting and then verify in actions or conditions.

3. Call a new parsing function (in the host language) when the recursive structure is entered.

您能否指出每个示例(最好使用我上面的示例)在 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