Parallel parsing of programming languages (Q1094886)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Parallel parsing of programming languages |
scientific article |
Statements
Parallel parsing of programming languages (English)
0 references
1987
0 references
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.
0 references
parallel algorithms
0 references
deterministic context-free languages
0 references
parallel parsing
0 references
programming languages
0 references
syntax
0 references
hierarchical language specifications
0 references
semi-Dyck sets
0 references
parallel random-access machine
0 references
