Parallel parsing of programming languages
type: Item
instance of: scholarly article
title: Parallel parsing of programming languages
zbMATH Open document ID: 0631.68071
DOI: 10.1016/0020-0255(87)90031-4
author: Y. N. Srikant
author: Priti Shankar
published in: Information Sciences
publication date: 1987-01-01T00:00:00Z
review text: 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.
reviewed by: Marian Gheorghe
Mathematics Subject Classification ID: 68N20
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 4026857
zbMATH Keywords: parallel algorithms
zbMATH Keywords: deterministic context-free languages
zbMATH Keywords: parallel parsing
zbMATH Keywords: programming languages
zbMATH Keywords: syntax
zbMATH Keywords: hierarchical language specifications
zbMATH Keywords: semi-Dyck sets
zbMATH Keywords: parallel random-access machine
MaRDI profile type: Publication
full work available at URL: 0020-0255(87)90031-4
OpenAlex ID: W1996734455
cites work: A Multiprocessing Approach to Compile-Time Symbol Resolution
cites work: Optimal parallel generation of a computation tree form
cites work: Parallel Generation of Postfix and Tree Forms
cites work: Q4198075
cites work: Q5592246
cites work: New Parallel-Sorting Schemes
cites work: Q3742751
cites work: A parallel algorithm for the minimization of finite state automata
cites work: A new parallel algorithm for parsing arithmetic infix expressions
Recommended article: FUNCTIONAL PEARL Parallel Parsing Processes
Recommended article: Parallel \(LL\) parsing
Recommended article: Some theoretical aspects of parallel parsing
Recommended article: Q4733436
Recommended article: Q3832067
Recommended article: Q3327741
Recommended article: Parallel parsing of operator precedence grammars
Recommended article: Q2763162
Recommended article: Optimal parallel parsing of bracket languages
Recommended article: Q3765260
description: scientific article; zbMATH DE number 4026857