article

Free access

A new method for determining linear precedence functions for precedence grammars

Author:

James R. BellAuthors Info & Claims

Communications of the ACM, Volume 12, Issue 10

Pages 567 - 569

https://doi.org/10.1145/363235.363255

Published: 01 October 1969 Publication History

PDF eReader

Abstract

The precedence relations of a precedence grammar can be precisely described by a two-dimensional precedence matrix. Often the information in the matrix can be represented more concisely by a pair of vectors, called linear precedence functions. A new algorithm is presented for obtaining the linear precedence functions when given the precedence matrix; this algorithm is shown to possess several computational adavantages.

References

[1]

WIRTH, N. AND WEBER, H. EULER-a generalization of ALGOL and its formal definition. Pt. 1 and Pt. 2. Comm. ACM 9, 2-3, (Jan-Feb. 1966), 13-23 and 89-99.

Digital Library

Google Scholar

[2]

FELDMAN, J., AND CRIES, D. Translator writing systems. Comm. ACM 11, 2, (Feb. 1968), 77-113.

Digital Library

Google Scholar

[3]

KcKEEMAN, W. M. An approach to computer language design. Tech. Rep. CS 48, Computer Science Dept., Stanford U., Stanford, Calif., Aug. 1966.

Google Scholar

[4]

FLOYD, R. W. Syntactic analysis and operator precedence. J. ACM 10, 3 (July 1963), 316-333.

Digital Library

Google Scholar

[5]

WIRTH, N. Algorithm 265: Find precedence functions. Comm. ACM 8, 10 (Oct. 1965) 604-605.

Digital Library

Google Scholar

[6]

WARSHALL, S. A theorem on Boolean matrices. J. ACM, 9, 1 (Jan. 1962), 11-12.

Digital Library

Google Scholar

[7]

FLOYD, R. W. Algorithm 96: Ancestor. Comm. ACM 5, 6 (June 1962), 344-345.

Digital Library

Google Scholar

Cited By

View all

Aucher G(2016)Dynamic epistemic logic in update logicJournal of Logic and Computation10.1093/logcom/exw00226:6(1913-1960)Online publication date: 7-Mar-2016
https://doi.org/10.1093/logcom/exw002
Broy MHavelund KKumar R(2016)Towards a Unified View of Modeling and ProgrammingLeveraging Applications of Formal Methods, Verification and Validation: Discussion, Dissemination, Applications10.1007/978-3-319-47169-3_17(238-257)Online publication date: 5-Oct-2016
https://doi.org/10.1007/978-3-319-47169-3_17
Turner D(2016)Recursion Equations as a Programming LanguageA List of Successes That Can Change the World10.1007/978-3-319-30936-1_24(459-478)Online publication date: 25-Mar-2016
https://doi.org/10.1007/978-3-319-30936-1_24
Show More Cited By

Index Terms

A new method for determining linear precedence functions for precedence grammars

Recommendations

A Boolean matrix method for the computation of linear precedence functions

A modified version of Bell's Boolean matrix method for the computation of linear precedence functions associated with a conflict-free matrix of precedence relations is given. This algorithm not only detects when the precedence functions do not exist, ...
New Precedence Theorems for One-Machine Weighted Tardiness

In an earlier paper by Emmons [Emmons, H. 1969. One-machine sequencing to minimize certain functions of job tardiness. Oper. Res.17 701--715], the problem of sequencing jobs on a single machine in order to minimize total tardiness was analyzed. Emmons ...
Online Scheduling of Precedence Constrained Tasks

A fundamental problem in scheduling theory is that of scheduling a set of n tasks, with precedence constraints, on $m \ge 1$ identical and parallel processors so as to minimize the makespan (schedule length). In the past, research has focused on the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

Communications of the ACM Volume 12, Issue 10

Oct. 1969

69 pages

ISSN:0001-0782

EISSN:1557-7317

DOI:10.1145/363235

Editor:
M. Stuart Lynn
IBM Scientific Center, Houston, TX

Issue’s Table of Contents

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 October 1969

Published in CACM Volume 12, Issue 10

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

18
Total Citations
View Citations
647
Total Downloads

Downloads (Last 12 months)368
Downloads (Last 6 weeks)21

Reflects downloads up to 13 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Aucher G(2016)Dynamic epistemic logic in update logicJournal of Logic and Computation10.1093/logcom/exw00226:6(1913-1960)Online publication date: 7-Mar-2016
https://doi.org/10.1093/logcom/exw002
Broy MHavelund KKumar R(2016)Towards a Unified View of Modeling and ProgrammingLeveraging Applications of Formal Methods, Verification and Validation: Discussion, Dissemination, Applications10.1007/978-3-319-47169-3_17(238-257)Online publication date: 5-Oct-2016
https://doi.org/10.1007/978-3-319-47169-3_17
Turner D(2016)Recursion Equations as a Programming LanguageA List of Successes That Can Change the World10.1007/978-3-319-30936-1_24(459-478)Online publication date: 25-Mar-2016
https://doi.org/10.1007/978-3-319-30936-1_24
Aho AUllman J(2010)Linear precedence functions for weak precedence grammarsInternational Journal of Computer Mathematics10.1080/002071672088030593:1-4(149-155)Online publication date: 21-Dec-2010
https://doi.org/10.1080/00207167208803059
de Boer F(2005)A proof system for the language POOLFoundations of Object-Oriented Languages10.1007/BFb0019442(124-150)Online publication date: 9-Jun-2005
https://doi.org/10.1007/BFb0019442
Benjamins RAben M(2005)A conceptual and formal model of a diagnostic reasonerAdvances in Knowledge Acquisition10.1007/3-540-61273-4_6(82-97)Online publication date: 1-Jun-2005
https://doi.org/10.1007/3-540-61273-4_6
Antoniou GSperschneider V(2005)On the verification of modulesCSL '8910.1007/3-540-52753-2_30(16-35)Online publication date: 8-Jun-2005
https://doi.org/10.1007/3-540-52753-2_30
van Eijck Jde Vries F(1995)Reasoning about update logicJournal of Philosophical Logic10.1007/BF0105272924:1(19-45)Online publication date: Feb-1995
https://doi.org/10.1007/BF01052729
Antoniou G(1994)The verification of modulesFormal Aspects of Computing10.1007/BF012211006:2(223-244)Online publication date: Mar-1994
https://doi.org/10.1007/BF01221100
America Pde Boer F(1994)Reasoning about dynamically evolving process structuresFormal Aspects of Computing10.1007/BF012154086:3(269-316)Online publication date: May-1994
https://doi.org/10.1007/BF01215408
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Abstract

References

Cited By

Index Terms

Recommendations

A Boolean matrix method for the computation of linear precedence functions

New Precedence Theorems for One-Machine Weighted Tardiness

Online Scheduling of Precedence Constrained Tasks

Comments

Information

Published In

Publisher

Publication History

Permissions

Check for updates

Author Tags

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

PDF

eReader

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations