Article

Free access

PLAN2D - syntactic analysis of precedence graph grammars

Author:

Reinhold FranckAuthors Info & Claims

POPL '76: Proceedings of the 3rd ACM SIGACT-SIGPLAN symposium on Principles on programming languages

Pages 134 - 139

https://doi.org/10.1145/800168.811547

Published: 01 January 1976 Publication History

PDF eReader

Abstract

The syntactical analysis of pictures derived by a context-free graph-grammar is a rather complicated algorithm. Analogously to the development for Chomsky-grammars ten years ago we define the precedence-graph-grammars as a subclass of the context-free graph-grammars allowing for easier parsing algorithms. By table-lookup we can decide locally if an edge or a node is part of a handle and if it isn't in which direction to proceed to reach one.

References

[1]

Denert,E.: PLAN2D - Konzept und Syntax einer zweidimensionalen Programmier-Sprache. Dissertation, Fachbereich Kybernetik, Technische Universität Berlin, 1975

Google Scholar

[2]

Denert,E., Franck,R., Streng,W.: PLAN2D - Towards a two-dimensional Programming Language. Lecture Notes in Comp. Sciences No 26, Springer Verlag, pp. 202 - 213

Digital Library

Google Scholar

[3]

Ehrig,H., Pfender,H., Schneider, H.J.: Graph Grammars: An Algebraic Approach. Proc. 14th Annual Conf. on Switching and Automata Theory 1973, pp. 167-180

Digital Library

Google Scholar

[4]

Franck,R.: PLAN2D - Syntaxanalyse von Präzedenz-Graph-Grammatiken. Dissertation, Fachbereich Kybernetik, Technische Universität Berlin, 1975

Google Scholar

[5]

Schneider,H.J.: Chomsky-Systeme für partielle Ordnungen. Arbeitsberichte des Instituts für Math. Maschinen und Datenverarbeitung, Band 3, Nr.3, Erlangen, August 1970

Google Scholar

[6]

Streng,W.: PLAN2D - Semantik einer zweidimensionalen Programmiersprache. Dissertation, Fachbereich Kybernetik, Technische Universität Berlin, 1975

Google Scholar

Cited By

View all

Franck R(2019)A class of linearly parsable graph grammarsActa Informatica10.1007/BF0028915510:2(175-201)Online publication date: 2-Jan-2019
https://dl.acm.org/doi/10.1007/BF00289155
Schneider HErlangen (2005)Graph grammarsFundamentals of Computation Theory10.1007/3-540-08442-8_99(314-331)Online publication date: 24-May-2005
https://doi.org/10.1007/3-540-08442-8_99
Kreowski H(2005)Transformations of derivation sequences in graph grammarsFundamentals of Computation Theory10.1007/3-540-08442-8_94(275-286)Online publication date: 24-May-2005
https://doi.org/10.1007/3-540-08442-8_94
Show More Cited By

Index Terms

PLAN2D - syntactic analysis of precedence graph grammars
1. Software and its engineering
  1. Software notations and tools
    1. General programming languages
2. Theory of computation
  1. Formal languages and automata theory
    1. Grammars and context-free languages
  2. Semantics and reasoning
    1. Program reasoning
      1. Parsing

Recommendations

Epsilon precedence grammars and languages
Partial precedence of context-sensitive graph grammars
VINCI '17: Proceedings of the 10th International Symposium on Visual Information Communication and Interaction

Context-sensitive graph grammars have been rigorous formalisms for specifying visual programming languages, as they possess sufficient expressive powers and intuitive forms. Efficient parsing mechanisms are essential to these formalisms. However, the ...
Inference of Parsable Graph Grammars for Syntactic Pattern Recognition

A research into a syntactic pattern recognition model based on (edNLC) graph grammars (introduced and investigated in Janssens and Rozenberg Inform. Sci. 20 (1980), 191-216, and Janssens, Rozenberg and Verraedt Comp. Vis. Graph. Image Process. 18 (1982),...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

POPL '76: Proceedings of the 3rd ACM SIGACT-SIGPLAN symposium on Principles on programming languages

January 1976

224 pages

ISBN:9781450374774

DOI:10.1145/800168

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 January 1976

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Acceptance Rates

POPL '76 Paper Acceptance Rate 20 of 90 submissions, 22%;

Overall Acceptance Rate 824 of 4,130 submissions, 20%

Upcoming Conference

POPL '25

Sponsor:
sigplan

The 52nd Annual ACM SIGPLAN Symposium on Principles of Programming Languages

January 19 - 25, 2025

Denver , CO , USA

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

8
Total Citations
View Citations
346
Total Downloads

Downloads (Last 12 months)46
Downloads (Last 6 weeks)9

Reflects downloads up to 05 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Franck R(2019)A class of linearly parsable graph grammarsActa Informatica10.1007/BF0028915510:2(175-201)Online publication date: 2-Jan-2019
https://dl.acm.org/doi/10.1007/BF00289155
Schneider HErlangen (2005)Graph grammarsFundamentals of Computation Theory10.1007/3-540-08442-8_99(314-331)Online publication date: 24-May-2005
https://doi.org/10.1007/3-540-08442-8_99
Kreowski H(2005)Transformations of derivation sequences in graph grammarsFundamentals of Computation Theory10.1007/3-540-08442-8_94(275-286)Online publication date: 24-May-2005
https://doi.org/10.1007/3-540-08442-8_94
Ehrig H(2005)Embedding theorems in the algebraic theory of graph grammarsFundamentals of Computation Theory10.1007/3-540-08442-8_91(245-255)Online publication date: 24-May-2005
https://doi.org/10.1007/3-540-08442-8_91
Nagl M(1979)A tutorial and bibliographical survey on graph grammarsGraph-Grammars and Their Application to Computer Science and Biology10.1007/BFb0025715(70-126)Online publication date: 1979
https://doi.org/10.1007/BFb0025715
Schneider H(1977)Graph GrammarsFundamentals of Computation Theory10.1007/978-3-662-40153-8_36(314-331)Online publication date: 1977
https://doi.org/10.1007/978-3-662-40153-8_36
Kreowski H(1977)Transformations of Derivation Sequences in Graph GrammarsFundamentals of Computation Theory10.1007/978-3-662-40153-8_31(275-286)Online publication date: 1977
https://doi.org/10.1007/978-3-662-40153-8_31
Ehrig H(1977)Embedding Theorems in the Algebraic Theory of Graph GrammarsFundamentals of Computation Theory10.1007/978-3-662-40153-8_28(245-255)Online publication date: 1977
https://doi.org/10.1007/978-3-662-40153-8_28

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.

Cited By

Index Terms

Recommendations

Epsilon precedence grammars and languages

Partial precedence of context-sensitive graph grammars

Inference of Parsable Graph Grammars for Syntactic Pattern Recognition