article

Free access

Syntax-Directed Transduction

Authors:

P. M. Lewis, II,

R. E. StearnsAuthors Info & Claims

Journal of the ACM (JACM), Volume 15, Issue 3

Pages 465 - 488

https://doi.org/10.1145/321466.321477

Published: 01 July 1968 Publication History

PDF eReader

Abstract

A transduction is a mapping from one set of sequences to another. A syntax-directed transduction is a particular type of transduction which is defined on the grammar of a context-free language and which is meant to be a model of part of the translation process used in many compilers. The transduction is considered from an automata theory viewpoint as specifying the input-output relation of a machine. Special consideration is given to machines called translators which both transduce and recognize. In particular, some special conditions are investigated under which syntax-directed translations can be performed on (deterministic) pushdown machines. In addition, some time bounds for translations on Turing machines are derived.

References

[1]

IRONS, E .T . A syntax directed compiler for ALGOL 60. Comm. ACM 4, 1 (Jan. 1961), 51-55.

Crossref

Google Scholar

[2]

PETRONE, LUIGI. Syntactic mappings of context-free languages. Proc. IFIP Congress, 1965, Vol. 2, pp. 590-591.

Google Scholar

[3]

CULlK, K. Well-translatable grammars and ALGOL-like languages. In Steel, T. B., Jr. (Ed.), Proc. IFIP Working Conference on Formal Language Description Languages, North-Holland, Amsterdam, 1966, pp. 76--85.

Google Scholar

[4]

KoPmvA, Jim. Realization of generalized good translation algorithm on computer. Kybernelika Cislo 5, Rocnik 3 (1967), 419-429.

Google Scholar

[5]

YOUNGER, D. H. Recognition and parsing of context-free languages in time n . Inform. Contr. 10, 2 (Feb. 1967), 189-208.

Google Scholar

[6]

KNUTR, D.E. On the translation of languages from left to right. Inform. Contr. 8, 6 (Dec. 1965), 607-639.

Google Scholar

[7]

OETTINGER, A. Automatic syntuctic analysis and the pushdown store. In Jacobson, R. (Ed.), Structure of Language and Its Mathematical Concepts, Proc. 12th Symposium in Appl. Math., Amer. Math. Soc., Providence, R. I., 1961, pp. 104-129.

Google Scholar

[8]

CHOMSKY, N. Context-free grammars and pushdown storage. RLE Quart. Progr. Rep. No. 65, Research Lab. of Electronics, M.I.T., Cambridge, Mass., March 1962.

Google Scholar

[9]

HARTMANIS, J., AND STEARNS, R. E. On the computational complexity of algorithms. Trans. Amer. Math. Soc. 117, 5 (May 1965), 285-306.

Google Scholar

Cited By

View all

Slivnik BMernik M(2023)On Parsing Programming Languages with Turing-Complete ParserMathematics10.3390/math1107159411:7(1594)Online publication date: 25-Mar-2023
https://doi.org/10.3390/math11071594
(2023)BibliographyEngineering a Compiler10.1016/B978-0-12-815412-0.00023-1(793-813)Online publication date: 2023
https://doi.org/10.1016/B978-0-12-815412-0.00023-1
Cooper KTorczon L(2023)ParsersEngineering a Compiler10.1016/B978-0-12-815412-0.00009-7(85-157)Online publication date: 2023
https://doi.org/10.1016/B978-0-12-815412-0.00009-7
Show More Cited By

Index Terms

Syntax-Directed Transduction
1. Theory of computation

Recommendations

Syntax directed transduction
SWAT '66: Proceedings of the 7th Annual Symposium on Switching and Automata Theory (swat 1966)

A transduction is a mapping from one set of sequences to another. A syntax directed transduction is a particular type of transduction which is defined on the grammar of a context free language and which is meant to be a model of part of the translation ...
Syntax augmented inversion transduction grammars for machine translation
CICLing'10: Proceedings of the 11th international conference on Computational Linguistics and Intelligent Text Processing

In this paper we propose a novel method for inferring an Inversion Transduction Grammar (ITG) from a bilingual parallel corpus with linguistic information from the source or target language. Our method combines bilingual ITG parse trees with monolingual ...
On syntax-directed transduction and tree transducers
STOC '70: Proceedings of the second annual ACM symposium on Theory of computing

Several topics of theoretical and practical importance to the field of translator writing systems are presented in this paper. These are

(1). implementation of generalized syntax-directed transduction (GSDT) on a finite-state tree transducer;

(2). ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

Journal of the ACM Volume 15, Issue 3

July 1968

149 pages

ISSN:0004-5411

EISSN:1557-735X

DOI:10.1145/321466

Issue’s Table of Contents

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 July 1968

Published in JACM Volume 15, Issue 3

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

226
Total Citations
View Citations
1,463
Total Downloads

Downloads (Last 12 months)143
Downloads (Last 6 weeks)17

Reflects downloads up to 13 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Slivnik BMernik M(2023)On Parsing Programming Languages with Turing-Complete ParserMathematics10.3390/math1107159411:7(1594)Online publication date: 25-Mar-2023
https://doi.org/10.3390/math11071594
(2023)BibliographyEngineering a Compiler10.1016/B978-0-12-815412-0.00023-1(793-813)Online publication date: 2023
https://doi.org/10.1016/B978-0-12-815412-0.00023-1
Cooper KTorczon L(2023)ParsersEngineering a Compiler10.1016/B978-0-12-815412-0.00009-7(85-157)Online publication date: 2023
https://doi.org/10.1016/B978-0-12-815412-0.00009-7
Flasiński MJurek J(2023)A Novel Approach of Multi-string Parsing for Syntactic Pattern RecognitionProgress on Pattern Classification, Image Processing and Communications10.1007/978-3-031-41630-9_1(3-13)Online publication date: 1-Dec-2023
https://doi.org/10.1007/978-3-031-41630-9_1
Kutrib MMeyer U(2022)Reversible Top-Down Syntax AnalysisInternational Journal of Foundations of Computer Science10.1142/S012905412244004X34:02n03(225-251)Online publication date: 16-Nov-2022
https://doi.org/10.1142/S012905412244004X
Kalita PSingal DAgarwal PJhunjhunwala SRoy S(2022)Symbolic encoding of LL(1) parsing and its applicationsFormal Methods in System Design10.1007/s10703-023-00420-361:2-3(338-379)Online publication date: 1-Dec-2022
https://dl.acm.org/doi/10.1007/s10703-023-00420-3
Flasiński MJurek JPeszek T(2022)On the learning of vague languages for syntactic pattern recognitionPattern Analysis & Applications10.1007/s10044-022-01120-026:2(605-615)Online publication date: 23-Nov-2022
https://dl.acm.org/doi/10.1007/s10044-022-01120-0
Olkhovsky IOkhotin A(2022)On the Transformation of LL(k)-linear to LL(1)-linear GrammarsTheory of Computing Systems10.1007/s00224-022-10108-667:2(234-262)Online publication date: 1-Dec-2022
https://dl.acm.org/doi/10.1007/s00224-022-10108-6
Lasser SCasinghino CFisher KRoux CFreund SYahav E(2021)CoStar: a verified ALL(*) parserProceedings of the 42nd ACM SIGPLAN International Conference on Programming Language Design and Implementation10.1145/3453483.3454053(420-434)Online publication date: 19-Jun-2021
https://dl.acm.org/doi/10.1145/3453483.3454053
Saffran JBarbosa HPereira FVladamani S(2021)On-line synthesis of parsers for string eventsJournal of Computer Languages10.1016/j.cola.2021.101022(101022)Online publication date: Feb-2021
https://doi.org/10.1016/j.cola.2021.101022
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