AN EXTENDED LR PARSER FOR THE ENGLISH LANGUAGE

Abstract

This thesis describes on English language parser and the associated parsing table generator developed as an extension of the LR parser. A context-free grammar for a subset of English has been prepared to test the working of the parser. The parsing table generated for the sample grammar has some entries multiply defined since natural languages are inherently ambiguous. The extended ~ar.ser tackles the multiple entries with the help of a graph structured stack. The key feature of the extended parser is its ability to generate all the )OS ible parses for an ambiguous sentence and store them for later disambiguation. For storing all possible parses an efficient representation called shared packed forest is used. It involves two techniques viz., sub-tree sharing and local ambiguity packing. The extended LR parser and the associated parsing table generator are implemented in C in the UNIX environment.