Skip to content

Consider removing support for non-determinism #167

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Open
kputnam opened this issue Jan 13, 2019 · 0 comments
Open

Consider removing support for non-determinism #167

kputnam opened this issue Jan 13, 2019 · 0 comments
Labels

Comments

@kputnam
Copy link
Owner

kputnam commented Jan 13, 2019

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.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
Projects
None yet
Development

No branches or pull requests

1 participant