Re: Regular expression string searching & matching

Clint O <clint.olsen@gmail.com>
Sat, 17 Mar 2018 16:52:04 -0700 (PDT)

          From comp.compilers
Related articles
[6 earlier articles]
Re: Regular expression string searching & matching jamin.hanson@googlemail.com (Ben Hanson) (2018-03-11)
Re: Regular expression string searching & matching clint.olsen@gmail.com (Clint O) (2018-03-12)
Re: Regular expression string searching & matching jamin.hanson@googlemail.com (Ben Hanson) (2018-03-12)
Re: Regular expression string searching & matching DrDiettrich1@netscape.net (Hans-Peter Diettrich) (2018-03-13)
Re: Regular expression string searching & matching jamin.hanson@googlemail.com (Ben Hanson) (2018-03-13)
Re: Regular expression string searching & matching jamin.hanson@googlemail.com (Ben Hanson) (2018-03-13)
Re: Regular expression string searching & matching clint.olsen@gmail.com (Clint O) (2018-03-17)
Re: Regular expression string searching & matching clint.olsen@gmail.com (Clint O) (2018-03-18)
Re: Regular expression string searching & matching clint.olsen@gmail.com (Clint O) (2018-03-20)
Re: Regular expression string searching & matching clint.olsen@gmail.com (Clint O) (2018-03-22)
| List of all articles for this month |
From: Clint O <clint.olsen@gmail.com>
Newsgroups: comp.compilers
Date: Sat, 17 Mar 2018 16:52:04 -0700 (PDT)
Organization: Compilers Central
References: 18-03-016 18-03-032 18-03-034 18-03-035 18-03-041 18-03-045 18-03-054
Injection-Info: gal.iecc.com; posting-host="news.iecc.com:2001:470:1f07:1126:0:676f:7373:6970"; logging-data="47472"; mail-complaints-to="abuse@iecc.com"
Keywords: lex, DFA
Posted-Date: 18 Mar 2018 04:25:36 EDT

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


Post a followup to this message

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