Re: How make multifinished DFA for merged regexps?

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

Return to the comp.compilers page.
Search the comp.compilers archives again.