The bracket matching problem deals with parentheses (), square brackets [], braces {} and other syntactic elements that provide for nested syntactic structures with balanced sets of delimiters.

To tackle bracket matching with Parabix methods, a key concept is that of a Nesting Depth BixNum. This is a representation of the nesting depth of syntactic elements at each position in an input stream. The following example shows an input stream with square brackets and braces, the corresponding nesting depth of each element in the data stream and the nesting depth bixnum (ND) as a set of 3 parallel bit streams (giving a 3-bit number at each character position).

Bracket Stream   ...[..{.}..{...[.[]..]..}...]...
Nesting Depth    00011122211222233443332221111000
ND BixNum[2]     .................11.............
ND BixNum[1]     ......111..111111..111111.......
ND BixNum[0]     ...111...11....11..111...1111...

NestingDepth Kernel

The NestingDepth kernel is a Parabix kernel (to be implemented) that can compute the nesting depth of characters in an input stream, given two character class bit streams L identifying all the left or opening delimiters and R identifying all the right or closing delimiters. For our example bracket stream above, L and R are shown below.

Bracket Stream   ...[..{.}..{...[.[]..]..}...]...
L                ...1..1....1...1.1..............
R                ........1.........1..1..1...1...

The NestingDepth Kernel also takes a parameter 'MaxDepth` identifying the maximum nesting depth expected for an input source. The number of bit streams in the NestingDepth BixNum must be equal to ceillog2(MaxDepth + 1).