Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.compilers > #2386 > unrolled thread

How make multifinished DFA for merged regexps?

Back to article view | Back to comp.compilers

Contents

  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

#2386 — How make multifinished DFA for merged regexps?

I can create DFA direct from regexp.
But for language lexer I must have DFA for couple regexp.
One solution is crating DFA with multi finished states.
For example
r0 = ab
r1 = ac

  | 0 | 1
a | 1 |
b |   | 2(F)
c |   | 3(F)

How to check if r0 and r1 are disjoint?

[toc] | [next] | [standalone]

#2387

On 2019-12-20, Andy <borucki.andrzej@gmail.com> wrote:
> I can create DFA direct from regexp.
> But for language lexer I must have DFA for couple regexp.

These are just combined as if with |, in some way that retains the
association between acceptance states an rules.

If we go NFA to DFA, what we can do is compile the individual regexes to
NFA, and then combine them into a big NFA.  Each of the little baby
NFA's has its own NFA acceptance state(s), We associate those state with the
original regex rule.

When we go to DFA, we are now looking at subsets of NFA states.  A state
of the DFA is a set of the states of the NFA.

Thus a DFA state can potentially contain one or more NFA acceptance
states. Since those NFA states are each associated with a lexer rules,
that means that, transitively, a DFA acceptance state is associated with
one or more rules.

If a DFA acceptance state is associated with more than one rule, we can
trim away all but the topmost rule. When that state occurs (that token
is matched) we trigger the first rule, ignoring the others.
That's how it is in Lex: if two or more rules match the same input, the
first rule appearing in the Lex program dominates.

Furthermore, after trimming away the superfluous rules, we can identify
all rules that are then no longer attached to the DFA and warn the
programmer about them.

[toc] | [prev] | [next] | [standalone]

#2391

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? I want avoid backtracking. Maybe after backtracking we must
read chars from auxiliary token buffer instead of stream up to previous
position? But this complicated parsing.

[toc] | [prev] | [next] | [standalone]

#2392

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

[toc] | [prev] | [next] | [standalone]

#2407

Am 21.12.2019 um 01:29 schrieb Andy:
> 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?

Why should "123." not form a valid float number? In fact it's the C way
to force a possibly int number into a float.

If your lexer requires backtracking, because it e.g. is LR(n), then this
is the only solution. Unlike parsers, which may work based on
shift/reduce actions, a scanner should be made simpler.

> I want avoid backtracking. Maybe after backtracking we must
> read chars from auxiliary token buffer instead of stream up to previous
> position? But this complicated parsing.

Parsers require a lookahead of at least one token. So scanners should
implement at least a lookahead of one character, depending on the
complexity or weirdness of a language definition.

DoDi

[toc] | [prev] | [next] | [standalone]

#2409

On Thursday, 19 December 2019 23:01:24 UTC-5, Andy  wrote:
> I can create DFA direct from regexp.
> But for language lexer I must have DFA for couple regexp.
> One solution is crating DFA with multi finished states.
> For example
> r0 = ab
> r1 = ac
>
>   | 0 | 1
> a | 1 |
> b |   | 2(F)
> c |   | 3(F)
>
> How to check if r0 and r1 are disjoint?

You build the NFA with a different kind of accepting state for each
rule.  When you build the DFA with subset construction, each DFA state
will correspond to a set of NFA states, and therefore each accepting
state will correspond to a *set* of rules.

The rules are all disjoint if all those sets are singletons.

If you do Hopcroft minimization, then your initial partition puts each
distinct set of accepted rules in its own partition.

I have an open source project that does this if it helps: https://github.com/mtimmerm/dfalex

[toc] | [prev] | [next] | [standalone]

#2414

On Thursday, December 19, 2019 at 10:01:24 PM UTC-6, Andy wrote:
> I can create DFA direct from regexp.
> But for language lexer I must have DFA for couple regexp.
> One solution is crating DFA with multi finished states.
> For example
> r0 = ab
> r1 = ac
>
>   | 0 | 1
> a | 1 |
> b |   | 2(F)
> c |   | 3(F)
>
> How to check if r0 and r1 are disjoint?

In a day or so, I'll put back up on GitHub our regex utilities that had once
been up on the comp.compilers archive. The "DFA" program can process boolean
operations - including intersection and relative compliment. (The "NFA"
program produces efficient linear-sized near-deterministic FA, "REX" is like
GREP except it can process boolean combinations too, and "FSC" is a "finite
state classifier"). I'll post a link when it's up on GitHub.

Denote intersection by &. The regular expressions ab, ac are the least
fixed-point solutions to the following systems
[0] = ab >= a[1]
[1] = b >= b[2]
[2] = 1

[3] = ac >= a[4]
[4] = c >= c[5]
[5] = 1

The system for the intersection is obtained by distributivity:
[0]&[3] >= a([1]&[4])
[1]&[4] >= (b[2] | c0) & (b0 | c[2]) = b([2]&0) | c(0&[2]) = b0 | c0 = 0
The least fixed-point solution is [1]&[4] = 0, [0]&[3] = a0 = 0.
So, there's 0 intersection.

A more interesting example with relative compliment "-":
(a|b)* - (a|b)*(aa|bb)(a|b)*

The first term (a|b)* has the following right-linear system
[0] = (a|b)* = 1 | (a|b)(a|b)* = 1 | a(a|b)* | b(a|b)* >= 1 | a[0] | b[0]

The second term (a|b)*(aa|bb)(a|b)* has the following:
[1] = (a|b)*(aa|bb)(a|b)* = (aa|bb)(a|b)* | a[1] | b[1]
   = a(a(a|b)* | [1]) | b(b(a|b)* | [1])
   >= a[2] | b[3]
[2] = a(a|b)* | [1] = a(a|b)* | 1 | a[1] | b[1] = 1 | a((a|b)* | [1]) | b[1]
   >= 1 | a[4] | b[1]
[3] = b(a|b)* | [1] = b(a|b)* | 1 | a[1] | b[1] = 1 | a[1] | b((a|b)* | [1])
   >= 1 | a[1] | b[4]
[4] = (a|b)* | [1] = 1 | (a|b)(a|b)* | 1 | a[1] | b[1]
   = 1 | 1 | a((a|b)* | [1]) | b((a|b)* | [1])
   >= 1 | a[4] | b[4]

The system for the relative compliment can be found by distributivity:
[0]-[1] >= (1|a[0]|b[0]) - (0|a[2]|b[3])
   = 1-0 | a([0]-[2]) | b([0]-[3])
   = 1 | a([0]-[2]) | b([0]-[3])
[0]-[2] >= (1-1) | a([0]-[4]) | b([0]-[1]) = a([0]-[4]) | b([0]-[1])
[0]-[3] >= (1-1) | a([0]-[1]) | b([0]-[4]) = a([0]-[1]) | b([0]-[4])
[0]-[4] >= (1-1) | a([0]-[4]) | b([0]-[4]) = a([0]-[4]) | b([0]-[4])

The least fixed-point solution x >= ax | bx is x = 0, so for the last item, it
is [0]-[4] = 0. For the remaining items, the system therefore reduces to
[0]-[1] >= 1 | a([0]-[2]) | b([0]-[3])
[0]-[2] >= a0 | b([0]-[1]) = b([0]-[1])
[0]-[3] >= a([0]-[1]) | b0 = a([0]-[1])
which upon substitution reduces to a single inequality
[0]-[1] >= 1 | ab([0]-[1]) | ba([0]-[1]) = 1 | (ab|ba)([0]-[1]).

The least fixed point solution to x >= 1 | cx is x = c*. Thus, for [0]-[1], it
is
[0]-[1] = (ab|ba)*
Therefore, the relative compliment evaluates to:
(a|b)* - (a|b)*(aa|bb)(a|b)* = (ab|ba)*.

[toc] | [prev] | [standalone]

Back to top | Article view | comp.compilers

csiph-web