Wed, 19 Jan 1994 10:25:03 GMT

Related articles |
---|

Parallel balanced parenthesis matching rockwell@nova.umd.edu (Raul Deluth Miller) (1994-01-16) |

Re: Parallel balanced parenthesis matching rockwell@nova.umd.edu (1994-01-18) |

Re: Parallel balanced parenthesis matching torbenm@diku.dk (1994-01-19) |

Re: Parallel balanced parenthesis matching Jon.Hill@dcs.qmw.ac.uk (Jon Hill) (1994-01-20) |

Newsgroups: | comp.compilers,comp.parallel |

From: | torbenm@diku.dk (Torben AEgidius Mogensen) |

Keywords: | parallel, parse, comment |

Organization: | Department of Computer Science, U of Copenhagen |

References: | 94-01-061 |

Date: | Wed, 19 Jan 1994 10:25:03 GMT |

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]

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.