{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:29:32Z","timestamp":1787340572477,"version":"build-2736575974"},"reference-count":12,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[1985,11]]},"abstract":"<jats:p>The generally used pass oriented evaluation strategies for attribute grammars, where different instances of the same attribute in any derivation tree are restricted to be evaluated in one left-to-right or right-to-left pass with for each derivation tree the same pass number, are referred to as simple multi-pass strategies.<\/jats:p>\n                  <jats:p>The determination of a shortest sequence of pass directions, such that an associated distribution of the attributes over the passes meets the simple multi-pass requirements, is known to be NP-complete.<\/jats:p>\n                  <jats:p>A polynomial time algorithm is discussed that delivers a shortest sequence of pass directions for several simple multi-pass grammars. It starts from a given sequence of pass directions and tries to find a shorter one by considering possible distributions of the attributes over the passes and crossing out empty passes. An extension of the algorithm also reconsiders and possibly changes directions in order to find passes that become empty. The resulting sequences of pass directions are minimal with respect to the subsequence ordering, i.e., no subsequence exists for which an associated distribution of the attributes over the passes meets the simple multi-pass requirements.<\/jats:p>\n                  <jats:p>The algorithms discussed in this paper proved to be successful in delivering sequences of pass directions of minimal length for several practical example grammars.<\/jats:p>","DOI":"10.1137\/0214063","type":"journal-article","created":{"date-parts":[[2005,2,24]],"date-time":"2005-02-24T06:25:35Z","timestamp":1109226335000},"page":"889-914","source":"Crossref","is-referenced-by-count":2,"title":["Finding Minimal Pass Sequences for Attribute Grammars"],"prefix":"10.1137","volume":"14","author":[{"given":"Henk","family":"Alblas","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,13]]},"reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00264495"},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1145\/359997.359999"},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(78)90017-0"},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1145\/357146.357148"},{"key":"R5","doi-asserted-by":"crossref","unstructured":"M. Jazayeri, K. G. Walter,  Alternating semantic evaluator,  Proc. ACM 1975 Annual Conference,  1975,  230\u2013234","DOI":"10.1145\/800181.810328"},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1007\/BF01692511"},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0059699"},{"key":"R8","unstructured":"K.J. Raiha,  On attribute grammars and their use in a compiler writing system, Report, A-1977-4, Dept. Computer Science, Univ. of Helsinki,  1977"},{"key":"R9","doi-asserted-by":"crossref","unstructured":"K.J. R\u00e4ih\u00e4, M. Saarinen, Developments in compiler writing systems, GI-6 Jahrestagung, Informatik Fachberichte 5, Springer-Verlag, Berlin\u2013Heidelberg\u2013New York, 1976, 164\u20131780356.68008","DOI":"10.1007\/978-3-642-95289-0_13"},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-10003-2_94"},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.1137\/0210060"},{"key":"R12","first-page":"123","volume":"2","author":"Wilhelm R.","year":"1979","journal-title":"Informatik-Spektrum"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/0214063","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:39:58Z","timestamp":1787337598000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/0214063"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1985,11]]},"references-count":12,"journal-issue":{"issue":"4","published-print":{"date-parts":[[1985,11]]}},"alternative-id":["10.1137\/0214063"],"URL":"https:\/\/doi.org\/10.1137\/0214063","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[1985,11]]}}}