Exploring Interactive Chart Parsing

This work explores the problem of incremental analysis in the context of chart parsing, probably the most commonly used framework for the analysis of natural Language. Incrementality here means that syntax correctness of a text is checked dynamically as the text is edited, changing the internal representation of the analysis rather than generating an entirely new one. This implies that the system then may interact with the user in order to resolve problems that occur. As a consequence, these kinds of techniques can be used to develop highly interactive and reactive natural language processors.

The kernel of the work is an incremental parsing algorithm that analyses arbitrary changes of a text, allowing competing analysis to be developed in parallel.

Key Words: Chart Parsing, Dynamic Programming, Incremental Parsing, Interactive Processing, Push-Down Automata.