Re: Parallel balanced parenthesis matching

> [ 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]


In the tech. report ``List Homomorphic parallel algorithms for bracket
matching'' [1], Murray Cole develops a parallel algorithm that solves the
problem of matching brackets such as ({[]}) [its an interesting paper,
well worth getting :-]


Another approach would be to use a parallel LL(1) parser [2,3,4] to solve
the problem. The solution Murray gives to the bracket problem looks very
similar to a technique I used in an implementation of a parallel LL(1)
parser[3,4]---but maybe thats because we both use a higher order
functional language, and the algorithms decompose into the scanning of a
similar function across the input to be matched ??


                                                                                Jon....


[1] @techreport{cole:bracket,
      author = {Cole, Murray},
      institution = {Dept. of Computer Science, University of Edinburgh},
      number = {CSR-29-93},
      title = {List homomorphic parallel algorithms for bracket matching.},
      year = {1993}
}


[2] @article{barnard:parse,
      author = {Barnard, D. B. and Skillicorn, D. T.},
      journal = {Information Processing letters},
      month = may,
      title = {Parallel parsing on the {C}onnection {M}achine},
      year = {1989}
}


[3] @article{hill:parse,
      author = {Hill, Jonathan. M. D.},
      journal = {Parallel Computing},
      month = jul,
      number = {6},
      pages = {699-714},
      title = {Parallel lexical analysis and parsing on the
                        {AMT} {D}istributed {A}rray {P}rocessor},
      volume = {18},
      year = {1992}
}


[4] @techreport{hill:dpGlue,
      author = {Hill, Jonathan. M. D.},
      institution = {{QMW CS}},
      month = dec,
      note = {Available by {FTP} from ftp.dcs.qmw.ac.uk
                      in {/pub/cpc/jon\_hill/dpGlue.ps}},
      number = {611},
      title = {{D}ata {P}arallel {H}askell: {M}ixing old and new glue},
      year = {1992}
}




--
          Jonathan Hill | Email : hilly@dcs.qmw.ac.uk
          Department of Computer Science |
          Queen Mary & Westfield College | Phone : 071-975-5230
          University of London |
--

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