{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,3,18]],"date-time":"2024-03-18T11:22:23Z","timestamp":1710760943164},"reference-count":13,"publisher":"Association for Computing Machinery (ACM)","issue":"5","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["SIGPLAN Not."],"published-print":{"date-parts":[[2006,5]]},"abstract":"Top-down backtracking language processors are highly modular, can handle ambiguity, and are easy to implement with clear and maintainable code. However, a widely-held, and incorrect, view is that top-down processors are inherently exponential for ambiguous grammars and cannot accommodate left-recursive productions. It has been known for many years that exponential complexity can be avoided by memoization, and that left-recursive productions can be accommodated through a variety of techniques. However, until now, memoization and techniques for handling left recursion have either been presented independently, or else attempts at their integration have compromised modularity and clarity of the code.<\/jats:p>","DOI":"10.1145\/1149982.1149988","type":"journal-article","created":{"date-parts":[[2006,10,18]],"date-time":"2006-10-18T22:35:32Z","timestamp":1161210932000},"page":"46-54","update-policy":"http:\/\/dx.doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":8,"title":["A new top-down parsing algorithm to accommodate ambiguity and left recursion in polynomial time"],"prefix":"10.1145","volume":"41","author":[{"given":"Richard A.","family":"Frost","sequence":"first","affiliation":[{"name":"University of Windsor, Windsor, Ontario Canada ON"}]},{"given":"Rahmatullah","family":"Hafiz","sequence":"additional","affiliation":[{"name":"University of Windsor, Windsor, Ontario Canada ON"}]}],"member":"320","published-online":{"date-parts":[[2006,5]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1590\/S0104-65002003000200004"},{"key":"e_1_2_1_3_1","first-page":"66","article-title":"Monadic memoization --- Towards Correctness-Preserving Reduction of Search. AI 2003 eds","volume":"2671","author":"Frost R. A.","year":"2003","journal-title":"Y. Xiang and B. Chaib-draa. LNAI"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1002\/spe.4380231006"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0956796800000411"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.5555\/216261.216269"},{"key":"e_1_2_1_7_1","first-page":"122","article-title":"Efficient combinator parsers. In Implementation of Functional Languages","volume":"1595","author":"Koopman P.","year":"1999","journal-title":"LNCS"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.5555\/79015.79016"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/364995.365689"},{"key":"e_1_2_1_10_1","unstructured":"Leermakers R. (1993) The Functional Treatment of Parsing. Kluwer Academic Publishers ISBN 0-7923-9376-7.]] Leermakers R. (1993) The Functional Treatment of Parsing. Kluwer Academic Publishers ISBN 0-7923-9376-7.]]"},{"key":"e_1_2_1_11_1","unstructured":"Lickman P. (1995) Parsing With Fixed Points. Master's Thesis University of Cambridge.]] Lickman P. (1995) Parsing With Fixed Points. Master's Thesis University of Cambridge.]]"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.5555\/971738.971743"},{"key":"e_1_2_1_15_1","doi-asserted-by":"crossref","unstructured":"Tomita M. (1985) Efficient Parsing for Natural Language. Kluwer Boston MA.]] Tomita M. (1985) Efficient Parsing for Natural Language. Kluwer Boston MA.]]","DOI":"10.1007\/978-1-4757-1885-0"},{"key":"e_1_2_1_16_1","volume-title":"P. Jouannaud (ed.) Functional Programming Languages and Computer Architectures Lecture Notes in Computer Science 201","author":"Wadler P.","year":"1985"}],"container-title":["ACM SIGPLAN Notices"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1149982.1149988","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T21:53:38Z","timestamp":1672264418000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1149982.1149988"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,5]]},"references-count":13,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2006,5]]}},"alternative-id":["10.1145\/1149982.1149988"],"URL":"https:\/\/doi.org\/10.1145\/1149982.1149988","relation":{},"ISSN":["0362-1340","1558-1160"],"issn-type":[{"value":"0362-1340","type":"print"},{"value":"1558-1160","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006,5]]},"assertion":[{"value":"2006-05-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}
