Re: Safe user-facing pattern matching.

[Martin <eden_martin_fuhrspam@...>]

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