Derivation of a Parallel Bottom-Up Parser from a Sequential Parser

Kazuko TAKAHASHI

Derivation of a Parallel Bottom-Up Parser from a Sequential Parser

Kazuko TAKAHASHI

Full Text Views

0

Cite this

Summary :

This paper describes the derivation of a parallel program from a nondeterministic sequential program using a bottom-up parser as an example. The derivation procedure consists of two stages: exploitation of AND-parallelism and exploitation of OR-parallelism. An interpreter of the sequential parser BUP is first transformed so that processes for the nodes in a parsing tree can run in parallel. Then, the resultant program is transformed so that a nondeterministic search of a parsing tree can be done in parallel. The former stage is performed by hand-simulation, and the latter is accomplished by the compiler of ANDOR-, which is an AND/OR parallel logic programming language. The program finally derived, written in KL1 (Kernel Language of the FGCS Project), achieves an all-solution search without side effects. The program generated corresponds to an interpreter of PAX, a revised parallel version of BUP. This correspondence shows that the derivation method proposed in this paper is effective for creating efficient parallel programs.

Publication: IEICE TRANSACTIONS on Information Vol.E75-D No.6 pp.852-860

Publication Date: 1992/11/25

Publicized

Online ISSN

DOI

Type of Manuscript: PAPER

Category: Software Theory

Cite this

Copy

Kazuko TAKAHASHI, "Derivation of a Parallel Bottom-Up Parser from a Sequential Parser" in IEICE TRANSACTIONS on Information, vol. E75-D, no. 6, pp. 852-860, November 1992, doi: .
Abstract: This paper describes the derivation of a parallel program from a nondeterministic sequential program using a bottom-up parser as an example. The derivation procedure consists of two stages: exploitation of AND-parallelism and exploitation of OR-parallelism. An interpreter of the sequential parser BUP is first transformed so that processes for the nodes in a parsing tree can run in parallel. Then, the resultant program is transformed so that a nondeterministic search of a parsing tree can be done in parallel. The former stage is performed by hand-simulation, and the latter is accomplished by the compiler of ANDOR-, which is an AND/OR parallel logic programming language. The program finally derived, written in KL1 (Kernel Language of the FGCS Project), achieves an all-solution search without side effects. The program generated corresponds to an interpreter of PAX, a revised parallel version of BUP. This correspondence shows that the derivation method proposed in this paper is effective for creating efficient parallel programs.
URL: https://global.ieice.org/en_transactions/information/10.1587/e75-d_6_852/_p

Copy

@ARTICLE{e75-d_6_852,
author={Kazuko TAKAHASHI, },
journal={IEICE TRANSACTIONS on Information},
title={Derivation of a Parallel Bottom-Up Parser from a Sequential Parser},
year={1992},
volume={E75-D},
number={6},
pages={852-860},
abstract={This paper describes the derivation of a parallel program from a nondeterministic sequential program using a bottom-up parser as an example. The derivation procedure consists of two stages: exploitation of AND-parallelism and exploitation of OR-parallelism. An interpreter of the sequential parser BUP is first transformed so that processes for the nodes in a parsing tree can run in parallel. Then, the resultant program is transformed so that a nondeterministic search of a parsing tree can be done in parallel. The former stage is performed by hand-simulation, and the latter is accomplished by the compiler of ANDOR-, which is an AND/OR parallel logic programming language. The program finally derived, written in KL1 (Kernel Language of the FGCS Project), achieves an all-solution search without side effects. The program generated corresponds to an interpreter of PAX, a revised parallel version of BUP. This correspondence shows that the derivation method proposed in this paper is effective for creating efficient parallel programs.},
keywords={},
doi={},
ISSN={},
month={November},}

Copy

TY - JOUR
TI - Derivation of a Parallel Bottom-Up Parser from a Sequential Parser
T2 - IEICE TRANSACTIONS on Information
SP - 852
EP - 860
AU - Kazuko TAKAHASHI
PY - 1992
DO -
JO - IEICE TRANSACTIONS on Information
SN -
VL - E75-D
IS - 6
JA - IEICE TRANSACTIONS on Information
Y1 - November 1992
AB - This paper describes the derivation of a parallel program from a nondeterministic sequential program using a bottom-up parser as an example. The derivation procedure consists of two stages: exploitation of AND-parallelism and exploitation of OR-parallelism. An interpreter of the sequential parser BUP is first transformed so that processes for the nodes in a parsing tree can run in parallel. Then, the resultant program is transformed so that a nondeterministic search of a parsing tree can be done in parallel. The former stage is performed by hand-simulation, and the latter is accomplished by the compiler of ANDOR-, which is an AND/OR parallel logic programming language. The program finally derived, written in KL1 (Kernel Language of the FGCS Project), achieves an all-solution search without side effects. The program generated corresponds to an interpreter of PAX, a revised parallel version of BUP. This correspondence shows that the derivation method proposed in this paper is effective for creating efficient parallel programs.
ER -