Browse Theses

This thesis describes the design and development of a parsing algorithm for context-free grammars. The parsing algorithm is a mixture of top down parsing techniques and bottom up parsing methods combined with chart parser techniques. The result is a fast parser that handles ambiguous grammars. The parser avoids the limitations of top down parsers, i.e. it can handle left recursive nonterminals. It can handle grammars with thousands of rules and nonterminals.

An interactive natural language environment requires that the errors be detected and corrected without user intervention. By interleaving the parser with the process of spelling error correction, and extending the three way match algorithm to four way match, the thesis introduces an efficient, intelligent, and reliable spelling corrector. This method, which is based on the goal of using the context for spelling correction, is very powerful.

Enforcement of semantic rules is based on Lexical Functional Grammar theory. The grammar and the lexicon are augmented with LFG annotation rules. After successfully parsing the user input, the system builds the LFG f-structure, which is turned into a logical form to be used by the input understander of the tutoring system.