Re: How make multifinished DFA for merged regexps?

From	Kaz Kylheku <493-878-3164@kylheku.com>
Newsgroups	comp.compilers
Subject	Re: How make multifinished DFA for merged regexps?
Date	2019-12-21 04:04 +0000
Organization	Aioe.org NNTP Server
Message-ID	<19-12-011@comp.compilers> (permalink)
References	<19-12-005@comp.compilers> <19-12-010@comp.compilers>

Show all headers | View raw

On 2019-12-21, Andy <borucki.andrzej@gmail.com> wrote:
> Greedy algorithms match longest regexp. For example operators "+" and "++",
> int numbers "123" and float numbers "123.456e3".
> On '.' will finish state of number, but we will inside automata for float
> number. But can be errors: after '.' will 'a'. We must backtrack to last
> finished state?

Yes, in general, to recognize the longest prefix of the input which
matches a regex, we must "backtrack". But this is nothing expensive like
recursive backtracking in pattern matching or logic programming.

Basically when we hit the situation that the input is exhausted, or
there are no transitions possible on the next character, we must jump
back to the position where the automaton most recently found itself in
an acceptance state.  That's it; there is no further history: just one
item to remember. Whenever the machine is in an acceptance state after
consuming a symbol, then it records the position, overwriting the
previously recorded position.

The token is then formed up to that acceptance position, and material
after that is pushed back into the input; it's likely the start of
another token.

--
TXR Programming Lanuage: http://nongnu.org/txr
Music DIY Mailing List:  http://www.kylheku.com/diy
ADA MP-1 Mailing List:   http://www.kylheku.com/mp1

Back to comp.compilers | Previous | Next — Previous in thread | Next in thread | Find similar

Thread

How make multifinished DFA for merged regexps? Andy <borucki.andrzej@gmail.com> - 2019-12-19 18:19 -0800
  Re: How make multifinished DFA for merged regexps? Kaz Kylheku <493-878-3164@kylheku.com> - 2019-12-20 05:54 +0000
  Re: How make multifinished DFA for merged regexps? Andy <borucki.andrzej@gmail.com> - 2019-12-20 16:29 -0800
    Re: How make multifinished DFA for merged regexps? Kaz Kylheku <493-878-3164@kylheku.com> - 2019-12-21 04:04 +0000
    Re: How make multifinished DFA for merged regexps? Hans-Peter Diettrich <DrDiettrich1@netscape.net> - 2019-12-24 02:15 +0100
  Re: How make multifinished DFA for merged regexps? Matt Timmermans <matt.timmermans@gmail.com> - 2019-12-23 22:29 -0800
  Re: How make multifinished DFA for merged regexps? rockbrentwood@gmail.com - 2019-12-29 20:56 -0800

csiph-web