Catalogue of Artificial Intelligence Techniques
Keywords: RTN, Recursive Transition Network, active edge, context-free rules, inactive edge, non-deterministic parsing, parsing, well-formed substring table
Categories: Natural Language
Author(s): Henry Thompson
Chart parsing is an approach to non-deterministic parsing developed by Kay and Kaplan based on earlier work by Earley, Kay and Colmerauer. In contrast to that earlier work, in which the chart was a (in some cases enriched) well-formed substring table for recording intermediate results, the later systems use the chart as the active agent in the parsing process. The chart is a directed graph, with two sorts of edges--active and inactive. Inactive edges record the existence of complete constituents. Active edges record hypothesised incomplete constituents. The parsing process itself consists of adding new edges in response to the meeting of active with inactive edges. As a record of an incomplete constituent, an active edge must carry some indication of how it may be extended, e.g., a dotted context-free rule or a state in a network grammar, such as Recursive Transition Network (RTN) or ATN. When an active edge and an inactive edge meet for the first time, if the inactive edge satisfies the active edge's conditions for extension, then a new edge will be constructed. If initial hypotheses about constituents are keyed by active edges and their needs, parsing will be top-down (see Top-down Parsing). If on the other hand these hypotheses are keyed by inactive edges, parsing will be bottom-up (see Bottom-up Parsing). One of the principal advantages of the chart parsing methodology is that it easily supports a variety of grammatical formalisms, rule invocation strategies, and control regimes. See (Thompson and Ritchie 1984) for an elementary introduction, and (Kay 1986) for a detailed theoretical analysis.
- Thompson, H.S and Ritchie, G.D., Natural Language Processing, Artificial Intelligence: Tools, Techniques, and Applications (O'Shea, T. and Eisenstadt, M., eds.), Harper and Row, New York, 1984, pp.358--388.
- Kay, M., Algorithm schemata and data structures in syntactic processing, Readings in Natural Language Processing (Grosz, B.J., Spärck Jones, K. and Webber, B.L., eds.), Morgan Kaufmann, Los Altos, 1986, pp.35--70.