Optimal parallel parsing of bracket languages

DOI10.1016/0304-3975(87)90070-3MaRDI QIDQ1093379zbMATH OpenOpenAlexFDO

Authors Wojciech Rytter, R. Giancarlo

Publication date 1987

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL http://wrap.warwick.ac.uk/60781/12/WRAP_cs-rr-085.pdf

zbMATH Keywords

bracket context-free languagesoptimal parallel algorithmparallel random access machinetree compression

Mathematics Subject Classification ID

Theory of compilers and interpreters (68N20)

Review text

We prove that the parsing problem for bracket context-free languages can be solved in log n time using n/log n processors on a parallel random access machine without write conflicts (P-RAM). On the way we develop a new general technique for tree compression based on the bracket structure of the tree.

Recommendations

• On the complexity of parallel parsing of general context-free languages
• scientific article; zbMATH DE number 4119661
• A parallel parsing algorithm for arbitrary context-free grammars
• On optimal parallel computations for sequences of brackets
• scientific article; zbMATH DE number 176524

Cites work

• An application of Mehlhorn's algorithm for bracket languages to log(n) space recognition of input-driven languages
• Bracket-languages are recognizable in logarithmic space
• scientific article; zbMATH DE number 3917742 (Why is no real title available?)
• scientific article; zbMATH DE number 3926247 (Why is no real title available?)
• scientific article; zbMATH DE number 3978426 (Why is no real title available?)
• scientific article; zbMATH DE number 4011928 (Why is no real title available?)
• scientific article; zbMATH DE number 3637281 (Why is no real title available?)
• On the complexity of parallel parsing of general context-free languages
• Optimal parallel generation of a computation tree form
• Parallelism in random access machines

Cited in

(9)

• Parallel parsing of programming languages
• On the complexity of parallel parsing of general context-free languages
• An Optimal Linear-Time Parallel Parser for Tree Adjoining Languages
• scientific article; zbMATH DE number 3919857 (Why is no real title available?)
• scientific article; zbMATH DE number 176524 (Why is no real title available?)
• scientific article; zbMATH DE number 4126700 (Why is no real title available?)
• Parallel recognition and ranking of context-free languages
• Efficient parallel and incremental parsing of practical context-free languages
• On optimal parallel computations for sequences of brackets

This page was built for publication: Optimal parallel parsing of bracket languages

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1093379)