stupidedi icon indicating copy to clipboard operation
stupidedi copied to clipboard

Consider removing support for non-determinism

Open kputnam opened this issue 5 years ago • 0 comments

The reason behind having a parser than can handle non-determinism (see GLR parser), was that it wasn't known if X12 specifications forbid ambiguous grammars, either implicitly or explicitly, or if the issue was even considered by X12.

Even being certain that ambiguity is present was difficult because much of the parser is built from assumptions that aren't explicitly confirmed in any X12 documents. So being able to accommodate ambiguous grammars ensured stupidedi could work in unforeseen circumstances. Even if dealing with the resulting collection of parse trees was cumbersome, it wasn't impossible.

In hindsight however, it seems there isn't a compelling case for supporting ambiguity, and so far every case of ambiguity has been due to a subtle error in transcribing the grammar. The cost of this feature is pushed onto users by making methods like Navigation#zipper return an Either<AbstractCursor> instead of simply AbstractCursor. It might be possible that other methods like Navigation#distance, #segment, #segmentn, #element, and #elementn, #first, #last, and maybe others could return non-Either values too.

There is further (unmeasured) cost in the implementation of many parts of StateMachine, because every action has to be done across each element of @active. Even though this is a single-element array (assuming #deterministic?), it's less efficient than operating on the one item directly.

Overall, removing support for ambiguity would simplify the implementation, make the interface more user-friendly, and potentially improve performance. The downside is it could be a breaking change if the return types of methods changed from Either<x> to only x.

kputnam avatar Jan 13 '19 07:01 kputnam