GitLab

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...