{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T22:53:41Z","timestamp":1725663221093},"publisher-location":"Berlin, Heidelberg","reference-count":49,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540083429"},{"type":"electronic","value":"9783540373056"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1977]]},"DOI":"10.1007\/3-540-08342-1_1","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T11:21:14Z","timestamp":1330168874000},"page":"1-15","source":"Crossref","is-referenced-by-count":2,"title":["How hard is compiler code generation?"],"prefix":"10.1007","author":[{"given":"Alfred V.","family":"Aho","sequence":"first","affiliation":[]},{"given":"Ravi","family":"Sethi","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,5,24]]},"reference":[{"key":"1_CR1","unstructured":"Abdel-Wahab, H. M., and T. Kameda [1977]. Scheduling to minimize maximum cumulative cost subject to series-parallel precedence constraints, Operations Research, to appear."},{"key":"1_CR2","volume-title":"The Design and Analysis of Computer Algorithms","author":"A. V. Aho","year":"1974","unstructured":"Aho, A. V., J. E. Hopcroft, and J. D. Ullman [1974]. The Design and Analysis of Computer Algorithms, Addison-Wesley, Reading, Mass."},{"issue":"3","key":"1_CR3","doi-asserted-by":"crossref","first-page":"488","DOI":"10.1145\/321958.321970","volume":"23","author":"A. V. Aho","year":"1976","unstructured":"Aho, A. V., and S. C. Johnson [1976]. Optimal code generation for expression trees, J. ACM\n23:3, 488\u2013501.","journal-title":"J. ACM"},{"key":"1_CR4","doi-asserted-by":"crossref","unstructured":"Aho, A. V., S. C. Johnson, and J. D. Ullman [1977a]. Code generation for machines with multiregister operations, Proc. Fourth ACM Symposium on Principles of Programming Languages, pp. 21\u201328.","DOI":"10.1145\/512950.512953"},{"issue":"1","key":"1_CR5","doi-asserted-by":"crossref","first-page":"146","DOI":"10.1145\/321992.322001","volume":"24","author":"A. V. Aho","year":"1977","unstructured":"Aho, A. V., S. C. Johnson, and J. D. Ullman [1977b]. Code generation for expressions with common subexpressions, J. ACM\n24:1, 146\u2013160.","journal-title":"J. ACM"},{"issue":"1","key":"1_CR6","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1137\/0201002","volume":"1","author":"A. V. Aho","year":"1972","unstructured":"Aho, A. V., and J. D. Ullman [1972]. Optimization of straight-line programs, SIAM J. Computing\n1:1, 1\u201319.","journal-title":"SIAM J. Computing"},{"key":"1_CR7","volume-title":"The Theory of Parsing, Translation, and Compiling. Vol. 2: Compiling","author":"A. V. Aho","year":"1973","unstructured":"Aho, A. V., and J. D. Ullman [1973]. The Theory of Parsing, Translation, and Compiling. Vol. 2: Compiling, Prentice-Hall, Englewood Cliffs, N. J."},{"key":"1_CR8","volume-title":"Principles of Compiler Design","author":"A. V. Aho","year":"1977","unstructured":"Aho, A. V., and J. D. Ullman [1977]. Principles of Compiler Design, Addison-Wesley, Reading, Mass."},{"issue":"3","key":"1_CR9","doi-asserted-by":"crossref","first-page":"149","DOI":"10.1145\/363958.363976","volume":"7","author":"J. P. Anderson","year":"1964","unstructured":"Anderson, J. P. [1964]. A note on some compiling algorithms. Comm. ACM\n7:3, 149\u2013150.","journal-title":"Comm. ACM"},{"issue":"4","key":"1_CR10","doi-asserted-by":"crossref","first-page":"613","DOI":"10.1145\/321724.321728","volume":"19","author":"J. C. Beatty","year":"1972","unstructured":"Beatty, J. C. [1972]. An axiomatic approach to code optimization for expressions, J. ACM\n19:4, 613\u2013640. Errata, 20:1 (Jan. 1973) 188, and 20:3 (July 1973) 538.","journal-title":"J. ACM"},{"issue":"1","key":"1_CR11","doi-asserted-by":"crossref","first-page":"20","DOI":"10.1147\/rd.181.0020","volume":"18","author":"J. C. Beatty","year":"1974","unstructured":"Beatty, J. C. [1974]. Register assignment algorithm for generation of highly optimized object code, IBM J. Res. Develop.\n18:1, 20\u201339.","journal-title":"IBM J. Res. Develop."},{"issue":"2","key":"1_CR12","doi-asserted-by":"crossref","first-page":"78","DOI":"10.1147\/sj.52.0078","volume":"5","author":"L. A. Belady","year":"1966","unstructured":"Belady, L. A. [1966]. A study of replacement algorithms for a virtual storage computer, IBM Systems J.\n5:2, 78\u2013101.","journal-title":"IBM Systems J."},{"issue":"3","key":"1_CR13","doi-asserted-by":"crossref","first-page":"382","DOI":"10.1145\/321892.321901","volume":"22","author":"J. Bruno","year":"1975","unstructured":"Bruno, J., and T. Lassagne [1975]. The generation of optimal code for stack machines, J. ACM\n22:3, 382\u2013396.","journal-title":"J. ACM"},{"issue":"3","key":"1_CR14","doi-asserted-by":"crossref","first-page":"502","DOI":"10.1145\/321958.321971","volume":"23","author":"J. Bruno","year":"1976","unstructured":"Bruno, J., and R. Sethi [1976]. Code generation for a one-register machine, J. ACM\n23:3, 502\u2013510.","journal-title":"J. ACM"},{"key":"1_CR15","first-page":"178","volume":"TA-3","author":"G. Chroust","year":"1971","unstructured":"Chroust, G. [1971]. Scope conserving expression evaluation, IFIP71, TA-3, 178\u2013182.","journal-title":"IFIP71"},{"key":"1_CR16","volume-title":"Programming Languages and Their Compilers, Preliminary Notes","author":"J. Cocke","year":"1970","unstructured":"Cocke, J., and J. T. Schwartz [1970]. Programming Languages and Their Compilers, Preliminary Notes, Second Revised Version, Courant Institute of Mathematical Sciences, New York.","edition":"Second Revised"},{"issue":"3","key":"1_CR17","first-page":"308","volume":"9","author":"S. A. Cook","year":"1974","unstructured":"Cook, S. A. [1974]. An observation on time-storage tradeoff, JCSS\n9:3, 308\u2013316.","journal-title":"JCSS"},{"issue":"1","key":"1_CR18","first-page":"25","volume":"13","author":"S. A. Cook","year":"1976","unstructured":"Cook, S. A., and R. Sethi [1976]. Storage requirements for deterministic polynomial time recognizable languages, JCSS\n13:1, 25\u201337.","journal-title":"JCSS"},{"issue":"4","key":"1_CR19","doi-asserted-by":"crossref","first-page":"281","DOI":"10.1147\/sj.94.0281","volume":"9","author":"W. H. E. E. Day","year":"1970","unstructured":"Day, W. H. E. [1970]. Compiler assignment of data items to registers, IBM Systems J.\n9:4, 281\u2013317.","journal-title":"IBM Systems J."},{"key":"1_CR20","volume-title":"An approach to the automatic generation of code generators, Laboratory for Computer Science and Engineering","author":"M. K. Donegan","year":"1973","unstructured":"Donegan, M. K. [1973]. An approach to the automatic generation of code generators, Laboratory for Computer Science and Engineering, Rice University, Houston, Texas."},{"issue":"8","key":"1_CR21","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1145\/368892.368907","volume":"1","author":"A. P. Ershov","year":"1958","unstructured":"Ershov, A. P. [1958]. On programming of arithmetic operations, Comm. ACM\n1:8, 3\u20136.","journal-title":"Comm. ACM"},{"key":"1_CR22","volume-title":"A class of register allocation algorithms, RC-5342, IBM Thomas J","author":"W. Harrison","year":"1975","unstructured":"Harrison, W. [1975]. A class of register allocation algorithms, RC-5342, IBM Thomas J. Watson Research Center, Yorktown Heights, New York."},{"key":"1_CR23","doi-asserted-by":"crossref","unstructured":"Hopcroft, J. E., W. J. Paul, and L. G. Valiant [1975]. On time versus space and related problems, Proc. 16th Annual Symposium on Foundations of Computer Science, pp. 57\u201364.","DOI":"10.1109\/SFCS.1975.23"},{"issue":"1","key":"1_CR24","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1145\/321312.321317","volume":"13","author":"L. P. Horowitz","year":"1966","unstructured":"Horowitz, L. P., R. M. Karp, R. E. Miller, and S. Winograd [1966]. Index register allocation, J. ACM\n13:1, 43\u201361.","journal-title":"J. ACM"},{"key":"1_CR25","volume-title":"YACC\u2014yet another compiler-compiler, CSTR-32","author":"S. C. Johnson","year":"1975","unstructured":"Johnson, S. C. [1975]. YACC\u2014yet another compiler-compiler, CSTR-32, Bell Laboratories, Murray Hill, N. J."},{"key":"1_CR26","first-page":"51","volume-title":"Design and Optimization of Compilers","author":"K. W. Kennedy","year":"1972","unstructured":"Kennedy, K. W. [1972]. Index register allocation in straight-line code and simple loops, in Rustin, R. (ed.) Design and Optimization of Compilers, Prentice-Hall, Englewood Cliffs, N. J., pp. 51\u201364."},{"key":"1_CR27","volume-title":"Register assignment algorithm \u2014 II, Report RC","author":"J. Kim","year":"1976","unstructured":"Kim, J., and C. J. Tan [1976]. Register assignment algorithm \u2014 II, Report RC 6262, IBM Thomas J. Watson Research Center, Yorktown Heights, New York."},{"key":"1_CR28","unstructured":"Knuth, D. E. [1977]. A generalization of Dijkstra's algorithm, Dept. of Computer Science, Stanford University."},{"key":"1_CR29","volume-title":"LEX\u2014a lexical analyzer generator, CSTR-39","author":"M. E. Lesk","year":"1975","unstructured":"Lesk, M. E. [1975]. LEX\u2014a lexical analyzer generator, CSTR-39, Bell Laboratories, Murray Hill, N. J."},{"issue":"1","key":"1_CR30","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1145\/362835.362838","volume":"12","author":"E. S. Lowry","year":"1969","unstructured":"Lowry, E. S., and C. W. Medlock [1969]. Object code optimization, Comm. ACM\n12:1, 13\u201322.","journal-title":"Comm. ACM"},{"issue":"9","key":"1_CR31","doi-asserted-by":"crossref","first-page":"572","DOI":"10.1145\/363566.363694","volume":"10","author":"F. Luccio","year":"1969","unstructured":"Luccio, F. [1969] A comment on index register allocation, Comm. ACM\n10:9, 572\u2013574.","journal-title":"Comm. ACM"},{"issue":"2","key":"1_CR32","doi-asserted-by":"crossref","first-page":"173","DOI":"10.1109\/TEC.1962.5219350","volume":"EC-11","author":"T. Marrill","year":"1962","unstructured":"Marrill, T. [1962]. Computational chains and the simplification of computer programs, IRE Trans. on Electronic Computers, EC-11:2, 173\u2013180.","journal-title":"IRE Trans. on Electronic Computers"},{"key":"1_CR33","volume-title":"Automatic Code-Generation from an Object-Machine Description, MAC TM 18","author":"P. L. Miller","year":"1970","unstructured":"Miller, P. L. [1970]. Automatic Code-Generation from an Object-Machine Description, MAC TM 18, Massachusetts Institute of Technology, Cambridge, Mass."},{"issue":"8","key":"1_CR34","doi-asserted-by":"crossref","first-page":"492","DOI":"10.1145\/363534.363549","volume":"10","author":"I. Nakata","year":"1967","unstructured":"Nakata, I. [1967]. On compiling algorithms for arithmetic expressions, Comm. ACM\n10:8, 492\u2013494.","journal-title":"Comm. ACM"},{"key":"1_CR35","unstructured":"Newcomer, J. M. [1975]. Machine-independent generation of optimal local code, Ph. D. Thesis, Computer Science Department, Carnegie-Mellon University."},{"key":"1_CR36","unstructured":"Paterson, M. S., and C. E. Hewitt [1970]. Comparative schematology, Record of Project MAC Conference on Concurrent Systems and Parallel Computation, pp. 119\u2013128."},{"key":"1_CR37","doi-asserted-by":"crossref","unstructured":"Paul, W. J., R. E. Tarjan, and J. R. Celoni [1976]. Space bounds for a game on graphs, Proc. 8th Annual ACM Symposium on Theory of Computing, pp. 149\u2013160.","DOI":"10.1145\/800113.803643"},{"key":"1_CR38","doi-asserted-by":"crossref","unstructured":"Prabhala, B., and R. Sethi [1977]. A comparison of instruction sets for stack machines, Proc. 9th Annual Symposium on Theory of Computing.","DOI":"10.1145\/800105.803403"},{"issue":"2","key":"1_CR39","doi-asserted-by":"crossref","first-page":"81","DOI":"10.1145\/362848.362859","volume":"12","author":"R. R. Redziejowski","year":"1969","unstructured":"Redziejowski, R. R. [1969]. On arithmetic expressions and trees, Comm. ACM\n12:2, 81\u201384.","journal-title":"Comm. ACM"},{"issue":"1","key":"1_CR40","doi-asserted-by":"crossref","first-page":"84","DOI":"10.1007\/BF01935328","volume":"11","author":"V. B. Schneider","year":"1971","unstructured":"Schneider, V. B. [1971]. On the number of registers needed to evaluate arithmetic expressions, BIT\n11:1, 84\u201393.","journal-title":"BIT"},{"issue":"3","key":"1_CR41","doi-asserted-by":"crossref","first-page":"226","DOI":"10.1137\/0204020","volume":"4","author":"R. Sethi","year":"1975","unstructured":"Sethi, R. [1975]. Complete register allocation problems, SIAM J. Computing\n4:3, 226\u2013248.","journal-title":"SIAM J. Computing"},{"issue":"4","key":"1_CR42","doi-asserted-by":"crossref","first-page":"715","DOI":"10.1145\/321607.321620","volume":"17","author":"R. Sethi","year":"1970","unstructured":"Sethi, R., and J. D. Ullman [1970]. The generation of optimal code for arithmetic expressions, J. ACM\n17:4, 715\u2013728.","journal-title":"J. ACM"},{"issue":"3","key":"1_CR43","doi-asserted-by":"crossref","first-page":"354","DOI":"10.1145\/321650.321653","volume":"18","author":"R. Simon","year":"1971","unstructured":"Simon, R., and R. C. T. Lee [1971]. On the optimal solution to AND\/OR series-parallel graphs, J. ACM\n18:3, 354\u2013372.","journal-title":"J. ACM"},{"issue":"6","key":"1_CR44","doi-asserted-by":"crossref","first-page":"353","DOI":"10.1145\/362248.362260","volume":"16","author":"P. F. Stockhausen","year":"1973","unstructured":"Stockhausen, P. F. [1973]. Adapting optimal code generation for arithmetic expressions to the instruction sets available on present-day computers, Comm. ACM\n16:6, 353\u2013354. Errata,\n17:10 (Oct. 1974) 591.","journal-title":"Comm. ACM"},{"key":"1_CR45","first-page":"53","volume-title":"Algorithms and Complexity","author":"J. D. Ullman","year":"1976","unstructured":"Ullman, J. D. [1976]. The complexity of code generation, in J. F. Traub (ed.) Algorithms and Complexity, Academic Press, New York, pp. 53\u201370."},{"key":"1_CR46","doi-asserted-by":"crossref","first-page":"549","DOI":"10.1007\/978-3-662-21549-4_21","volume-title":"Compiler Construction: An Advanced Course","author":"W. M. Waite","year":"1974","unstructured":"Waite, W. M. [1974]. Optimization, in Bauer and Eickel (eds.) Compiler Construction: An Advanced Course, Springer-Verlag, New York, pp. 549\u2013602."},{"issue":"4","key":"1_CR47","first-page":"404","volume":"7","author":"S. A. Walker","year":"1973","unstructured":"Walker, S. A., and H. R. Strong [1973]. Characterization of flowchartable recursions, JCSS\n7:4, 404\u2013447.","journal-title":"JCSS"},{"key":"1_CR48","volume-title":"A compiler-writing system with optimization capabilities for complex order structures","author":"S. G. Wasilew","year":"1971","unstructured":"Wasilew, S. G. [1971]. A compiler-writing system with optimization capabilities for complex order structures, Ph. D. Thesis, Northwestern University, Evanston, Ill."},{"key":"1_CR49","volume-title":"General register assignment in presence of data flow, RC-5645, IBM Thomas J","author":"E. F. Yhap","year":"1975","unstructured":"Yhap, E. F. [1975]. General register assignment in presence of data flow, RC-5645, IBM Thomas J. Watson Research Center, Yorktown Heights, New York."}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-08342-1_1.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T16:51:54Z","timestamp":1619542314000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-08342-1_1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1977]]},"ISBN":["9783540083429","9783540373056"],"references-count":49,"URL":"https:\/\/doi.org\/10.1007\/3-540-08342-1_1","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1977]]}}}