Re: Safe user-facing pattern matching.

[Coda Highland <chighland@...>]

On Mon, Apr 10, 2017 at 11:37 PM, Martin <eden_martin_fuhrspam@gmx.de> wrote:
> On 04/05/2017 06:14 PM, Gé Weijers wrote:
>> I don't yet see how to do this in linear time by bolting a recognizer
>> for the "%b()" pattern onto a finite state automaton.
>
> I think this is impossible for canonic finite state automata (which is
> just a series of triples (state, cur_char, next_state) from limited
> alphabet).
>
> But is possible if we add some "condition" and "action" fields
> that contain functions and procedures:
>
> FSA (finite state automata):
>
>  state | cur_char |   cond   |            action          | next_state
> -------+----------+----------+----------------------------+-----------
>  SCAN  |   EOL    |          |                                 | DONE
>  SCAN  |    (     |          | starts[++deep] = POS            | SCAN
>  SCAN  |    )     | deep > 0 | capt = seg(starts[deep--], POS) | SCAN
>  SCAN  |    )     |          |                                 | SCAN
>  SCAN  |   ANY    |          |                                 | SCAN
>
> Surely by allowing this extension we multiply execution time by
> some constant factor (as we may no longer get new state just by
> referencing FSA[state][cur_char].next_state, we have to scan entries
> of FSA[state][cur_char] checking conditions).
>
> -- Martin

I would have implemented this as a four-state FSA with an action that
happens to include a conditional in it. Doing that doesn't actually
impact the design of the FSA itself and therefore carries no more
overhead than just supporting actions at all would.

That said, usually when I implement this kind of thing I dispense with
the strictness of the formalism and I instead have the actions return
the next state instead of having next_state as a distinct, fixed
entity.

/s/ Adam