article

Free access

On the nonexistence of a phrase structure grammar for ALGOL 60

Author:

Robert W. FloydAuthors Info & Claims

Communications of the ACM, Volume 5, Issue 9

Pages 483 - 484

https://doi.org/10.1145/368834.368898

Published: 01 September 1962 Publication History

PDF eReader

Abstract

ALGOL 60 is defined partly by formal mechanisms of phrase structure grammar, partly by informally stated restrictions. It is shown that no formal mechanisms of the type used are sufficient to define ALGOL 60.

Cited By

View all

Tucker JRoggenbach MCerone ASchlingloff BSchneider GShaikh S(2022)Origins and Development of Formal MethodsFormal Methods for Software Engineering10.1007/978-3-030-38800-3_9(455-488)Online publication date: 23-Jun-2022
https://doi.org/10.1007/978-3-030-38800-3_9
Astarte TJones C(2019)Formal Semantics of ALGOL 60: Four Descriptions in their Historical ContextReflections on Programming Systems10.1007/978-3-319-97226-8_4(83-152)Online publication date: 11-Jan-2019
https://doi.org/10.1007/978-3-319-97226-8_4
Schmid M(2016)Characterising REGEX languages by regular languages equipped with factor-referencingInformation and Computation10.1016/j.ic.2016.02.003249:C(1-17)Online publication date: 1-Aug-2016
https://dl.acm.org/doi/10.1016/j.ic.2016.02.003
Show More Cited By

On the nonexistence of a phrase structure grammar for ALGOL 60
1. Software and its engineering
  1. Software notations and tools
    1. General programming languages

Recommendations

A translation grammar for ALGOL 68
AFIPS '70 (Spring): Proceedings of the May 5-7, 1970, spring joint computer conference

In this paper, a translation grammar is presented for a major subset of the ALGOL 68 programming language. This translation is from ALGOL 68 into an intermediate language that was originally designed for an EULER programming system. It appears that many ...
A new algorithm for parsing generalized phrase structure grammar
Parsing Head-driven Phrase Structure Grammar
ACL '85: Proceedings of the 23rd annual meeting on Association for Computational Linguistics

The Head-driven Phrase Structure Grammar project (HPSG) is an English language database query system under development at Hewlett-Packard Laboratories. Unlike other product-oriented efforts in the natural language understanding field, the HPSG system ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

Communications of the ACM Volume 5, Issue 9

Sept. 1962

33 pages

ISSN:0001-0782

EISSN:1557-7317

DOI:10.1145/368834

Editor:
C. C. Gotlieb
Univ. of Toronto, Toronto, Canada

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 September 1962

Published in CACM Volume 5, Issue 9

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

53
Total Citations
View Citations
789
Total Downloads

Downloads (Last 12 months)66
Downloads (Last 6 weeks)12

Reflects downloads up to 12 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Tucker JRoggenbach MCerone ASchlingloff BSchneider GShaikh S(2022)Origins and Development of Formal MethodsFormal Methods for Software Engineering10.1007/978-3-030-38800-3_9(455-488)Online publication date: 23-Jun-2022
https://doi.org/10.1007/978-3-030-38800-3_9
Astarte TJones C(2019)Formal Semantics of ALGOL 60: Four Descriptions in their Historical ContextReflections on Programming Systems10.1007/978-3-319-97226-8_4(83-152)Online publication date: 11-Jan-2019
https://doi.org/10.1007/978-3-319-97226-8_4
Schmid M(2016)Characterising REGEX languages by regular languages equipped with factor-referencingInformation and Computation10.1016/j.ic.2016.02.003249:C(1-17)Online publication date: 1-Aug-2016
https://dl.acm.org/doi/10.1016/j.ic.2016.02.003
Stevenson ACordy J(2015)Parse views with Boolean grammarsScience of Computer Programming10.1016/j.scico.2013.11.00797:P1(59-63)Online publication date: 1-Jan-2015
https://dl.acm.org/doi/10.1016/j.scico.2013.11.007
Schmid M(2014)Characterising REGEX Languages by Regular Languages Equipped with Factor-ReferencingDevelopments in Language Theory10.1007/978-3-319-09698-8_13(142-153)Online publication date: 2014
https://doi.org/10.1007/978-3-319-09698-8_13
Dassow JPăun GSalomaa A(2013)Grammars with Controlled DerivationsHandbook of Formal Languages10.1007/978-3-662-07675-0_3(101-154)Online publication date: 26-Mar-2013
https://doi.org/10.1007/978-3-662-07675-0_3
Maurer W(2008)SurveyComputer Science Review10.1016/j.cosrev.2008.02.0032:1(1-28)Online publication date: 1-Apr-2008
https://dl.acm.org/doi/10.1016/j.cosrev.2008.02.003
Kuppusamy LKrishna SRaghavan RMartin-Vide C(2007)Internal Contextual Grammars for Mildly Context-Sensitive LanguagesResearch on Language and Computation10.1007/s11168-007-9027-15:2(181-197)Online publication date: 26-Jul-2007
https://doi.org/10.1007/s11168-007-9027-1
Chiţu A(2005)PC grammar systems versus some non-context-free constructions from natural and artificial languagesNew Trends in Formal Languages10.1007/3-540-62844-4_20(278-287)Online publication date: 3-Jun-2005
https://doi.org/10.1007/3-540-62844-4_20
Knuth D(2005)The genesis of attribute grammarsAttribute Grammars and their Applications10.1007/3-540-53101-7_1(1-12)Online publication date: 31-May-2005
https://doi.org/10.1007/3-540-53101-7_1
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

Cited By

Recommendations

A translation grammar for ALGOL 68

A new algorithm for parsing generalized phrase structure grammar

Parsing Head-driven Phrase Structure Grammar

Comments

Information

Published In

Publisher

Publication History

Permissions

Check for updates

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