Deterministic techniques for efficient non-deterministic parsers

Lecture notes in computer sciencePublished 1 January 1974

Bernard Lang

DOI10.1007/3-540-06841-4_65

Source URL

Citations129

SJR quartileQ2

SJR score0.35

SNIP0.55

TL;DR

A general study of parallel non-Deterministic parsing and translation a la Earley is developped formally, based on non-deterministic pushdown acceptor-transducers, and it is shown that for every family of deterministic context-free pushdown parsers there is a family of general context- free parallel parsers that have the same efficiency in most practical cases.

Abstract

A general study of parallel non-deterministic parsing and translation à la Earley is developped formally, based on non-deterministic pushdown acceptor-transducers. Several results (camplexity and efficiency) are established, same new and other previously proved only in special cases. As an application, we show that for every family of deterministic context-free pushdown parsers (e.g. precedence, LR(k), LL(k), ...) there is a family of general context-free parallel parsers that have the same efficiency in most practical cases (e.g. analysis of programming languages).

Keywords

Computer Science

The Theory of Parsing, Translation, and Compiling

1,411 Citations1972Alfred V. Aho, Jeffrey D. Ullman

It is the hope that the algorithms and concepts presented in this book will survive the next generation of computers and programming languages, and that at least some of them will be applicable to fields other than compiler writing.

Information and ControlRecognition and parsing of context-free languages in time n3

947 Citations1967D. H. Younger

A recognition algorithm is exhibited whereby an arbitrary string over a given vocabulary can be tested for containment in a given context-free language and it is shown that it is completed in a number of steps proportional to the “cube” of the number of symbols in the tested string.

Illinois Digital Environment for Access to Learning and Scholarship (University of Illinois at Urbana-Champaign)An Efficient Recognition and Syntax-Analysis Algorithm for Context-Free Languages

526 Citations1965Tadao Kasami

It is shown in this paper that a context-free language is n cubed-recognizable in the sense of Hartmanis and Stearns and it is n to the 4th power- Recognizable by a single-head single-tape Turing machine.

View PDF

Journal of Computer and System SciencesGeneral context-free recognition in less than cubic time

350 Citations1975Leslie G. Valiant

An algorithm for general context-free recognition is given that requires less than n3 time asymptotically for input strings of length n.

View PDF

DSpace@MIT (Massachusetts Institute of Technology)PRACTICAL TRANSLATORS FOR LR(K) LANGUAGES

162 Citations1969Franklin L. DeRemer

A method is presented for automatically constructing CFSTs (DPDAs) from those simple suffix transduction grammars which are based on the LR(k) Grammars, which can be defined by a deterministic push-down automation (DPDA).

View PDF

Communications of the ACMExperience with an extensible language

59 Citations1970Edgar T. Irons

An operational extensible language system is described and its base language is appraised with respect to efficiency, flexibility, and utility for different categories of users.

View PDF

Information SciencesEfficient parsing algorithms for general context-free parsers

26 Citations1975M. Bouckaert, Alain Pirotte +1 more

Empirical comparisons show the effectiveness of the new members of the family of parsing algorithms, which appear to be definitely better than Earley's algorithms, except for a few pathological grammars.

Parallel non-deterministic bottom-up parsing

4 Citations1971Bernard Lang

A type of parser that can be used with reasonable efficiency for any CF grammar, even one which is ambiguous, and is slower than most deterministic parsers, but shown to be more efficient than any other parser having the same generality.