A development of deterministic parser using data-directed grammar

Abstract

There are two distinct concepts in parsing techniques; top-down and bottom-up parasigms. Both of them reflect two important insights; the rationalist tradition or goal-directed which focuses on the prior knowlege, and the empirical tradition or data-directed which focuses on the data. Generally, each parsing technique will have its own grammar formalisms including addaitional information to help in parsing. Sometimes, those grammars may have been written in the form that could case ambiguous results in parsing despite in fact, they were not intended to be. This is becasue those grammars were not written in the form which is explicity enough to avoid ambiguous resluts. In this thesis, we present a new deterministic botton-up parsing technique called data-directed parser which runs in time complexity equals to O(n). It requires only grammar rules defined in a new grammar formalism called Chulalongkorn University Normal Form (CUNF) grammars. CUNF is derived form Chomsky Normal Form (CNF). It has a generative power equals to context-free grammars, and can be used to represent a large calss of grammars in an unambiguous form. In the thesis, we have also demonstrated how to apply CUNF with various ambiguous grammars including the syntax of Hyper Text Markup Language (HTML) version 3.2.