Valid parentheses sequence

SystemVerilog
,
1

Hi,
How can we generate valid parenthesis sequence using SystemVerilog constraints?
Example: If length is 6, all of these valid combinations must be generated ()()(), ((())), (())(), ()(())

2

In reply to akshataudpi:

This is a fun interview question

module top;
  class P;
    rand bit signed [1:0] parens[];
    function new;
      parens = new[6];
    endfunction
    constraint c {
      foreach(parens[i]){
        // 1 is open, -1 is close parenthesis
        parens[i] inside {1,-1};
        // can never have more close than open parenthesis in sequence
        parens.sum() with(item.index<=i? int'(item) : 0) >= 0;
      }
      // number of open and close parenthesis must be equal
      parens.sum() with (int'(item)) == 0;

    }
    function void print;
      foreach(parens[i]) if (parens[i] > 0)
        $write("(");
      else
        $write(")");
      $display;
    endfunction
 endclass
  P p=new;
      initial repeat(10) begin
    assert(p.randomize);
    p.print;
  end
endmodule
3

In reply to dave_59:

Hi Dave,
which constraint can be used to avoid such as )(, )))(((, ()))(( ?

4

In reply to VE:

// can never have more close than open parenthesis in sequence
        parens.sum() with(item.index<=i? int'(item) : 0) >= 0;
5

In reply to dave_59:

Dave,

Why are you using int’(item) and not just item? TIA.

6

In reply to Verif Engg:

It’s not strictly necessary as it is already implicit because of the RHS 0 in the conditional expression, but being explicit never hurts and is a good habit to keep.

7

In reply to dave_59:

Hi Dave,

Could you please elaborate on how this is expanded into an equation? Isnt item.index is same as i?

Thanks.

8

In reply to sjain12:
They are not always the same. item.index is a nested iterator within i.

The constraint

    constraint c {
      foreach(parens[i]){
        // can never have more close than open parenthesis in sequence
        parens.sum() with(item.index<=i? int'(item) : 0) >= 0;
      }
    }

expands to

        parens.sum() with(item.index<=0? int'(item) : 0) >= 0;
        parens.sum() with(item.index<=1? int'(item) : 0) >= 0;
        parens.sum() with(item.index<=2? int'(item) : 0) >= 0;
        parens.sum() with(item.index<=3? int'(item) : 0) >= 0;
        parens.sum() with(item.index<=4? int'(item) : 0) >= 0;
        parens.sum() with(item.index<=5? int'(item) : 0) >= 0;

Then the first sum() when i = 0 expands to

(0<=0? int'(parens[0]) : 0) + // item.index = 0 item = parens[0]
(1<=0? int'(parens[1]) : 0) + // item.index = 1 item = parens[1]
(2<=0? int'(parens[2]) : 0) + // item.index = 2 item = parens[2]
(3<=0? int'(parens[3]) : 0) + // item.index = 3 item = parens[3]
(4<=0? int'(parens[4]) : 0) + // item.index = 4 item = parens[4]
(5<=0? int'(parens[5]) : 0)   // item.index = 5 item = parens[5]

which collapses down to

int'(parens[0]) + 0 + 0 + 0 + 0 + 0

So the entire set of constraint equations becomes

parens[0] >= 0; // i = 0
parens[0] + parens[1] >= 0; // i = 1
parens[0] + parens[1] + parens[2] >= 0; // i = 2
parens[0] + parens[1] + parens[2] + parens[3] >= 0; // i = 3
parens[0] + parens[1] + parens[2] + parens[3] + parens[4]>= 0; // i = 4
parens[0] + parens[1] + parens[2] + parens[3] + parens[4] + parens[5]>= 0; // i = 5

For clarity, I removed the cast to int’() around each element.

9

You have an amazing thought process!!

Thanks for sharing the knowledge.