Parallel parsing of programming languages (Q1094886)

This paper presents a new method of parallel parsing for programming languages and introduces a new model of specifying the syntax of programming languages, namely hierarchical language specifications (HLS), that covers a subclass of DCFLs. The model of HLS is based on semi-Dyck sets and \(\text{PF}(k)\) (precede-follow with \(k\) symbols) parsable sets. Efficient parallel-parsing algorithms that assume an exclusive-read exclusive-write parallel random-access machine as the model of computation, are presented. These algorithms work in \(O(\log^2n)\) time on \(O(n)\) processors, where \(n\) is the length of the program to be parsed and they do not use a stack.