Send us a comment.
6.1 Well-formed substring tables 6.2 The active chart 6.3 The fundamental rule of chart parsing 6.4 Initialization 6.5 Rule invocation 6.6 Search strategy 6.7 Housekeeping 6.8 Implementing a simple bottom-up chart parser 6.9 Alternative rule invocation strategies 6.10 Implementing a simple top-down chart parser 6.11 Search strategy 6.12 Implementing flexible control 6.13 Efficiency
This chapter considers how a parser can efficiently store intermediate results to cope with certain kinds of redundancy in the parsing search space. First of all, the notion of well-formed substring table (WFST) is introduced. A WFST is a mechanism enabling a parser to keep a record of structures it has already found, so that it can avoid looking for them again. The further extension represented in charts enables a parser, in addition, to record information about goals it has adopted. Recorded goals may have been unsuccessful or may still be under exploration, but in either case it would be inefficient for the parser to start pursuing them again from scratch. The organization of a chart parser is described, as is the way in which the components of the system can be manipulated to produce different search and rule invocation strategies.
Send us a comment.