The University of Edinburgh -
Division of Informatics
Forrest Hill & 80 South Bridge

MSc Thesis #9683

Title:Exploring Chart Parsing Mechanisms
Date: 1996
Abstract:This project investigates various proposals which have been made to improve the efficiency of a chart parser. Steel and De Roeck suggest that the efficiency of a parser could be improved if the grammar-writer is allowed to mark certain rules in the grammar to be used top-down and others to be used bottom-up, bidirectional algorithm which reduces the number of redundant edges added to a chart during parsing. We describe the necessary formalisms for the different parsing mechanisms and propose an extension to the redundancy checking parser to allow mixed strategy parsing with redundancy checking. Following successful implementations of the ideas presented, we then give some limited evaluation which indicates that an improvement in efficiency of between 10 and 100 percent can be found for bottom-up bidirectional parsing, while mixed strategy parsing and redundancy checking do not generally give good results.

[Search These Pages] [DAI Home Page] [Comment]