An execution mechanism for nondeterministic, state-oriented programs based on a chart parser (Q1209991)

The importance of nondeterministic programming languages has long been recognized. There exist, however, only a few execution mechanisms for programs written in such languages. Thus, it may be desirable to study the execution of these programs further. Several authors have observed that context-free grammars resemble nondeterministic programs with destructive assignments. This suggests the possibility of adapting parsers to obtain execution mechanisms for such programs. We modify a top-down chart parser and derive one of these mechanisms. Our method has important advantages over a top-down mechanism with backtracking. First, there are programs for which our method terminates, that cause the backtracking method to enter a nonterminating loop. Second, our method has a time complexity that is cubic in the length of the computation. This is a substantial improvement over a top-down mechanism with backtracking, which has a time complexity that is exponential in the length of the computation.