Re: Parallel balanced parenthesis matching

Raul Deluth Miller <rockwell@nova.umd.edu> writes:


>Balanced parenthesis matching is a cannonical example of a problem outside
>the scope of regular expressions. Matching is normally accomplished using
>a "FSM" in conjunction with a stack.


>I was wondering if anyone has approached the problem with a massively
>parallel machine [one machine per language element] and attempted to
>minimize communication between machines. Of course, the problem changes
>drastically, depending on the communication model. But I'm hoping to find
>someone familiar with this kind of work.


I haven't done any work in this area, but it seems obvious to use a
parallel scan algorithm. Or simpler yet, imagine a binary tree of
processors, where the leaves contain the symbols in the input. The first
step takes each parenthesis and produces a pair of numbers in the same
processor. This table shows the calculation:


( |-> 0,1
) |-> 1,0


The left number in the pair shows the number of unmatched closing
parenthesis in a sequence and the right number shows the number of
unmatched opening parenthesis. The remaining steps propagate two pairs of
numbers up to the next processer, which produces a new pair of numbers
etc. until a single pair of numbers is found at the root processor. If
this pair is 0,0 the parenthesis are balanced. Otherwise the numbers show
the number of unmatched closing and opening parenthesis. The calculation
of a new pair of numbers from two inputs is done as follows


a,b , c,d |-> a,d+b-c if b>=c
a,b , c,d |-> a+c-b,d if b<c


The reasoning should be obvious.


Torben Mogensen (torbenm@diku.dk)
[In a later note, the author said he needed to match multiple kinds of
brackets, e.g. \begin {[()]} \end. I'd guess that you could come up with
a sort of NxN matrix to pass around the nesting in each chunk but don't
know the details. -John]
--

Return to the comp.compilers page.
Search the comp.compilers archives again.