chou@lanai.cs.ucla.edu (Ching-Tsun Chou) (10/16/90)
Does anyone know of any works, either theoretical or practical, on parsing context-free languages with parallel algorithms? I would greatly appreciate any pointers and will post a summary of responses. Please mail your response to <chou@cs.ucla.edu>. - Ching Tsun
hoover@cs.UAlberta.CA (Jim Hoover) (10/16/90)
In article <40171@shemp.CS.UCLA.EDU> chou@lanai.cs.ucla.edu (Ching-Tsun Chou) writes: > >Does anyone know of any works, either theoretical or practical, on >parsing context-free languages with parallel algorithms? >I would greatly appreciate any pointers and will post a summary of responses. > >Please mail your response to <chou@cs.ucla.edu>. > >- Ching Tsun You wouldn't know it from the title, but Larry Ruzzo's paper: Walter L. Ruzzo, "Tree-Size Bounded Alternation", J. Computer and System Sciences, 21, 1980, pp 218-235. shows that CFL recognition can be done in O(log n)^2 time with a polynomial number of processors. There may be an efficient parser lurking in the proofs. -- Prof. Jim Hoover | Office +1 403 492 5401 or 5290 Dept. of Computing Science | FAX +1 403 492 1071 University of Alberta | hoover@cs.ualberta.ca Edmonton, Alberta, Canada T6G 2H1 |
hubert@vega.ucsb.edu (Hung-Hsien Hubert Chang) (10/19/90)
In article <40171@shemp.CS.UCLA.EDU> chou@lanai.cs.ucla.edu (Ching-Tsun Chou) writes: > >Does anyone know of any works, either theoretical or practical, on >parsing context-free languages with parallel algorithms? >I would greatly appreciate any pointers and will post a summary of responses. > >Please mail your response to <chou@cs.ucla.edu>. > >- Ching Tsun Baer, Ellis: Model , Desgin , and Evaluation of a compiler for a parallel processing enviornment IEEE trans. on Soft Eng V.3 N.5 Nov 1977 Cohen , Hickey: Upper bounds for speedup in parallel parsing JACM v.29 N2. Apr 1982 Cohen , Kolodner Estimating the speedup in parallel parsing IEEE trans Soft Eng V.11 N.1 Jan 1985 Dekel, Sahni: parallel generation of postfix and tree-forms ACM tran Prog lang syst V.5 N.3 July 1983 Donegan, Katzke : lexical analysisi and parsing techniques fro a vector machine Proc Conf Prog. Lang and Compilers for paralle and vector machines. ACM -SIGPLAN notics V.10 Mar 1975 Ellis: parallel compilign techniques Proc. ACM 26th Nat. Conf 1971 Fisher: On parsing context-free languages in parallel enviornmets Ph.D dissertation , Dep of computer science , Cornell Univ Krohn: a prallel approach to code generation fro Fortran-like compilers Proc. Conf. Prog. Lang and compilers for paralle and vector machines ACM-SIGPLAN notices V.10 Mar 1975 Ligett, McCluskey, and McKeeman: parallel LR parsing Wagn Institute of Gradaute studies, School of information technology, technical report TR 82-03 1982 Mickunas, Schell: parallel compilation in a multiprocessor enviornment Proc ACM 1987 Hope it helps. Hubert Hung-Hsien Chang Sincerely yours,