Re: Safe user-facing pattern matching.

[Gé Weijers <ge@...>]

On Mon, Apr 10, 2017 at 13:38 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

A regular _expression_ like ".*%b()" will match "(((((((())", which your automaton will not unless it's a nondeterministic one. 

You cannot know how many '('s are matched by ".*" until you get to the end of the string.

I don't think there's a linear time algorithm to match expressions like this in the general case. You either backtrack, or your deterministic state representation is a list only bounded by the input size. 

Gé

--

-- Gė