Groups > comp.compilers > #2011

Re: Regular expression string searching & matching

From	Clint O <clint.olsen@gmail.com>
Newsgroups	comp.compilers
Subject	Re: Regular expression string searching & matching
Date	2018-03-17 16:52 -0700
Organization	Compilers Central
Message-ID	<18-03-073@comp.compilers> (permalink)
References	(2 earlier) <18-03-034@comp.compilers> <18-03-035@comp.compilers> <18-03-041@comp.compilers> <18-03-045@comp.compilers> <18-03-054@comp.compilers>

Show all headers | View raw

On Tuesday, March 13, 2018 at 12:36:32 PM UTC-7, Ben Hanson wrote:
> I'd be interested to see your DFA output once you've cleaned it up a bit.
> Using derivatives is interesting too - I've seen it discussed but never
tried
> to get into that.

OK, I'm not sure how readable this will be, but here goes:

<RegexConcat [13]=0x1052672b0 0x10525acf8 0x10525aa58 'B7'>
+---<RegexConcat [11]=0x10525acf8 0x105267198 0x10525ab00 'B7'>
|   +---<RegexConcat [10]=0x105267198 0x10525a978 0x10525ad68 'B7'>
|   |   +---<RegexConcat [2]=0x10525a978 0x10525aa58 0x10525ab70 'B7'>
|   |   |   +---<RegexSym [0]=0x10525aa58 '/'>
|   |   |   `---<RegexSym [1]=0x10525ab70 '*'>
|   |   `---<RegexStar [9]=0x10525ad68 0x10525af98 '*'>
|   |       `---<RegexOr [8]=0x10525af98 0x10525add8 0x10525ae80 '|'>
|   |           +---<RegexSym [4]=0x10525add8 '^*'>
|   |           `---<RegexConcat [7]=0x10525ae80 0x10525ab00 0x105267048
'B7'>
|   |               +---<RegexPlus [5]=0x10525ab00 0x10525ab70 '+'>
|   |               |   `---<RegexSym [1]=0x10525ab70 '*'>
|   |               `---<RegexSym [6]=0x105267048 '^/'>
|   `---<RegexPlus [5]=0x10525ab00 0x10525ab70 '+'>
|       `---<RegexSym [1]=0x10525ab70 '*'>
`---<RegexSym [0]=0x10525aa58 '/'>

q0: /B7[*]B7([^*] | [*]+B7[^/])*B7[*]+B7/
    [/] q2
    ['\x00'-.0-C?] q1
q1: b
    ['\x00'-C?] q1
q2: [*]B7([^*] | [*]+B7[^/])*B7[*]+B7/
    [*] q3
    ['\x00'-)+-C?] q1
q3: ([^*] | [*]+B7[^/])*B7[*]+B7/
    [*] q4
    ['\x00'-)+-C?] q3
q4: ([*]*B7[^/]B7([^*] | [*]+B7[^/])*B7[*]+ | [*]*)B7/
    [*] q6
    ['\x00'-)+-.0-C?] q3
    [/] q5
q5: N5
    ['\x00'-C?] q1
q6: (([*]*B7[^/] | N5)B7([^*] | [*]+B7[^/])*B7[*]+ | [*]*)B7/
    [*] q8
    ['\x00'-)+-.0-C?] q3
    [/] q7
q7: ([^*] | [*]+B7[^/])*B7[*]+B7/ | N5
    [*] q4
    ['\x00'-)+-C?] q3
q8: ((([*]*B7[^/] | N5)B7([^*] | [*]+B7[^/])* | [*]*B7[^/]B7([^*] |
[*]+B7[^/])*)B7[*]+ | [*]*)B7/
    [*] q8
    ['\x00'-)+-.0-C?] q3
    [/] q7
Total DFA states: 9
Total RE instances: 35

I consolidated character classes, but I didn't do any nice reduction such as
pruning transitions to the error state.

Thanks,

-Clint

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

Thread

Regular expression string searching & matching Clint O <clint.olsen@gmail.com> - 2018-03-04 01:37 -0800
  Re: Regular expression string searching & matching Ben Hanson <jamin.hanson@googlemail.com> - 2018-03-07 11:53 -0800
    Re: Regular expression string searching & matching Ben Hanson <jamin.hanson@googlemail.com> - 2018-03-07 12:18 -0800
    Re: Regular expression string searching & matching Clint O <clint.olsen@gmail.com> - 2018-03-08 22:53 -0800
      Re: Regular expression string searching & matching Clint O <clint.olsen@gmail.com> - 2018-03-10 00:57 -0800
        Re: Regular expression string searching & matching Ben Hanson <jamin.hanson@googlemail.com> - 2018-03-11 13:52 -0700
          Re: Regular expression string searching & matching Clint O <clint.olsen@gmail.com> - 2018-03-12 14:00 -0700
            Re: Regular expression string searching & matching Ben Hanson <jamin.hanson@googlemail.com> - 2018-03-13 11:30 -0700
              Re: Regular expression string searching & matching Clint O <clint.olsen@gmail.com> - 2018-03-17 16:52 -0700
              Re: Regular expression string searching & matching Clint O <clint.olsen@gmail.com> - 2018-03-18 19:23 +0000
              Re: Regular expression string searching & matching Clint O <clint.olsen@gmail.com> - 2018-03-20 17:23 +0000
                Re: Regular expression string searching & matching Clint O <clint.olsen@gmail.com> - 2018-03-22 17:46 +0000
          Re: Regular expression string searching & matching Ben Hanson <jamin.hanson@googlemail.com> - 2018-03-12 15:46 -0700
          Re: Regular expression string searching & matching Hans-Peter Diettrich <DrDiettrich1@netscape.net> - 2018-03-13 10:53 +0100
            Re: Regular expression string searching & matching Ben Hanson <jamin.hanson@googlemail.com> - 2018-03-13 14:23 -0700
      Re: Regular expression string searching & matching Ben Hanson <jamin.hanson@googlemail.com> - 2018-03-10 03:17 -0800

csiph-web