[Date Prev][Date Next][Thread Prev][Thread Next]
[Date Index]
[Thread Index]
- Subject: Re: Safe user-facing pattern matching.
- From: Martin <eden_martin_fuhrspam@...>
- Date: Mon, 10 Apr 2017 23:37:25 -0700
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