| Language-processors, that are constructed using top-down recursive-descent search with backtracking parsing technique, 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---this leads to the fact that there exists no perfect environment for investigating many NLP-related theories. This thesis solves these shortcomings by proposing a new combinator-parsing algorithm, which is efficient, modular, accommodates all forms of CFG and represents all possible resulting parse-trees in a densely-compact format. |
