A Comparison Between Packrat Parsing and Conventional Shift-Reduce Parsing on Real-World Grammars and Inputs
作者： Daniel Flodin
DOI:
关键词: Parsing 、 Computer science 、 Parser combinator 、 Memoization 、 Top-down parsing 、 S-attributed grammar 、 Artificial intelligence 、 Natural language processing 、 Parsing expression grammar 、 Top-down parsing language 、 Bottom-up parsing
摘要: Packrat parsing is a top-down, recursive descent technique that uses backtracking and has guaranteed linear parse time. Conventional parsers suffer from exponential tim ...
参考文章(21)
Terence J. Parr, Russell W. Quong, Adding Semantic and Syntactic Predicates To LL(k): pred-LL(k) compiler construction. pp. 263- 277 ,(1994) , 10.1007/3-540-57877-3_18
Ravi Sethi, Jeffrey D. Ullman, Alfred V. Aho, Compilers: Principles, Techniques, and Tools ,(1986)
Ralph Becket, Zoltan Somogyi, DCGs + memoing = packrat parsing but is it worth it? practical aspects of declarative languages. pp. 182- 196 ,(2008) , 10.1007/978-3-540-77442-6_13
Roman R. Redziejowski, Parsing Expression Grammar as a Primitive Recursive-Descent Parser with Backtracking Fundamenta Informaticae. ,vol. 79, pp. 513- 524 ,(2007)
Scott McPeak, George C. Necula, Elkhound: A Fast, Practical GLR Parser Generator compiler construction. ,vol. 2985, pp. 73- 88 ,(2003) , 10.1007/978-3-540-24723-4_6
Claus Brabrand, Michael I. Schwartzbach, Mads Vanggaard, The METAFRONT System: Extensible Parsing and Transformation Electronic Notes in Theoretical Computer Science. ,vol. 82, pp. 592- 611 ,(2003) , 10.1016/S1571-0661(05)82630-1
Jeffrey D. Ullman, Alfred V. Aho, The Theory of Parsing, Translation, and Compiling ,(1972)
J. Weidendorfer, N. Nethercote, J. Seward, Valgrind 3.3 - Advanced Debugging and Profiling for Gnu/Linux Applications ,(2008)
DONALD MICHIE, “Memo” Functions and Machine Learning Nature. ,vol. 218, pp. 19- 22 ,(1968) , 10.1038/218019A0
Bryan Ford, Packrat parsing: simple, powerful, lazy, linear time, functional pearl international conference on functional programming. ,vol. 37, pp. 36- 47 ,(2002) , 10.1145/581478.581483