Re: Parallel balanced parenthesis matching

Jon Hill <Jon.Hill@dcs.qmw.ac.uk>
Thu, 20 Jan 1994 12:16:19 GMT

          From comp.compilers

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)
| List of all articles for this month |

Newsgroups: comp.compilers,comp.parallel
From: Jon Hill <Jon.Hill@dcs.qmw.ac.uk>
Keywords: parallel, parse, bibliography
Organisation: Comp Sci Dept, Queen Mary and Westfield College, London
Organization: Compilers Central
References: 94-01-061 94-01-068
Date: Thu, 20 Jan 1994 12:16:19 GMT

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


Post a followup to this message

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