如何用递归实现SystemVerilog字符串不匹配括号检测？

核心思路 #

递归实现基于分治思想：

• 基准情况：当字符串长度n=1时，直接判断单个字符：
  • 若为右括号)，则未匹配右括号数left_out_n_unmat_close=1，未匹配左括号数right_out_n_unmat_open=0
  • 若为左括号(，则right_out_n_unmat_open=1，left_out_n_unmat_close=0
  • 其他字符则两个计数均为0
• 递归分治：当n>1时，将字符串拆分为前k个字符和后n-k个字符（取k=n/2均分），分别递归调用子模块计算两部分的未匹配计数，再合并结果：
  设左半部分结果为Lc（未匹配右括号）、Lo（未匹配左括号）；右半部分为Rc、Ro。
  左半的未匹配左括号可以抵消右半的未匹配右括号，抵消数量为min(Lo, Rc)。最终：
  • 总未匹配右括号：Lc + (Rc - 抵消数)
  • 总未匹配左括号：Ro + (Lo - 抵消数)

递归模块代码 #

`define Char_Open 4'h28   // ASCII '('
`define Char_Close 4'h29  // ASCII ')'

module pmatch_comb_recursive
  #( int n = 5, wn = $clog2(n) )
   ( output logic [wn-1:0] left_out_n_unmat_close, right_out_n_unmat_open,
     input uwire [3:0] str[0:n-1] );

  if (n == 1) begin : base_case
    always_comb begin
      left_out_n_unmat_close = 0;
      right_out_n_unmat_open = 0;
      if (str[0] == `Char_Close) begin
        left_out_n_unmat_close = 1;
      end else if (str[0] == `Char_Open) begin
        right_out_n_unmat_open = 1;
      end
    end
  end else begin : recursive_case
    localparam k = n / 2;
    localparam w_k = $clog2(k);
    localparam w_nk = $clog2(n - k);

    logic [w_k-1:0] left_Lc, left_Lo;
    logic [w_nk-1:0] right_Rc, right_Ro;
    logic [wn-1:0] cancel;

    // 递归实例化左半部分模块
    pmatch_comb_recursive #(.n(k))
      left_part (
        .left_out_n_unmat_close(left_Lc),
        .right_out_n_unmat_open(left_Lo),
        .str(str[0:k-1])
      );

    // 递归实例化右半部分模块
    pmatch_comb_recursive #(.n(n - k))
      right_part (
        .left_out_n_unmat_close(right_Rc),
        .right_out_n_unmat_open(right_Ro),
        .str(str[k:n-1])
      );

    always_comb begin
      // 计算可抵消的括号数量
      cancel = (left_Lo < right_Rc) ? left_Lo : right_Rc;
      // 合并结果
      left_out_n_unmat_close = left_Lc + (right_Rc - cancel);
      right_out_n_unmat_open = right_Ro + (left_Lo - cancel);
    end
  end

endmodule

测试用例验证 #

• 字符串"))(("（n=4）：递归拆分后左半"))"得到Lc=2, Lo=0，右半"(("得到Rc=0, Ro=2；抵消数为0，最终输出left_out_n_unmat_close=2, right_out_n_unmat_open=2，符合预期。
• 字符串"(())"（n=4）：左半"(("得到Lc=0, Lo=2，右半"))"得到Rc=2, Ro=0；抵消数为2，最终两个计数均为0，符合预期。
• 字符串"(. ())("（n=6）：拆分后递归计算各部分，最终得到left_out_n_unmat_close=0, right_out_n_unmat_open=1，符合预期。

内容的提问来源于stack exchange，提问作者Louis Wascom