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

发布时间：2020-12-17 04:13:49 所属栏目：百科来源：网络整理

导读：这是语法的起点： %%{ machine xo; char = "x" | "o"; group = "(" char* ")"; main := group;}%% 例如,它处理(xxxx(oo)()xx).如何扩展它以允许嵌套组;例如(XXXX(O(X)O)()XX？我知道递归通常不是由一台Ragel机器支持的.所以这不起作用： group = "(" ( char

这是语法的起点：

%%{
  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开始,提到了相同的三种方法：

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

Counting and then verify in actions or conditions.

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

你能在Ruby中指出我的每个例子 – 最好是使用上面的例子吗？谢谢！

解决方法

使用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 = []
%% write init;
%% write exec;
if top > 0 
    cs = %%{ write error; }%%
end

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!