Re: Regular expression string searching & matching

On 2018-03-20, Clint O <clint.olsen@gmail.com> wrote:
> [ reposted to try to make the special characters look right ]
>
> q0: /·[*]·([^*] | [*]+·[^/])*·[*]+·/
> [/] q2
> ['\x00'-.0-ÿ] q1
> q1: ∅
> ['\x00'-ÿ] q1
> q2: [*]·([^*] | [*]+·[^/])*·[*]+·/
> [*] q3
> ['\x00'-)+-ÿ] q1
> q3: ([^*] | [*]+·[^/])*·[*]+·/
> [*] q4
> ['\x00'-)+-ÿ] q3
> q4: ([*]*·[^/]·([^*] | [*]+·[^/])*·[*]+ | [*]*)·/
> [*] q6
> ['\x00'-)+-.0-ÿ] q3
> [/] q5
> q5: ε
> ['\x00'-ÿ] q1
> q6: (([*]*·[^/] | ε)·([^*] | [*]+·[^/])*·[*]+ | [*]*)·/
> [*] q8
> ['\x00'-)+-.0-ÿ] q3
> [/] q7
> q7: ([^*] | [*]+·[^/])*·[*]+·/ | ε
> [*] q4
> ['\x00'-)+-ÿ] q3
> q8: ((([*]*·[^/] | ε)·([^*] | [*]+·[^/])* | [*]*·[^/]·([^*] | [*]+·[^/])*)·[*]+ | [*]*)·/
> [*] q8
> ['\x00'-)+-.0-ÿ] q3
> [/] q7


Thanks John for reposting this. It looks much better now.


In summary:


q5,q7 are accepting states since they contain epsilon. q2 represents the
error state.


The key to success with this algorithm is recognizing previously calculated
derivatives/expressions. When you no longer calculate unique derivatives,
the DFA construction terminates. As you can see the expressions can get
hairy pretty quickly. I don't know if you can glean much from the
successive expressions generated. It's akin to the method of walking the
parse tree but it bypasses the NFA construction entirely.


Thanks,


-Clint

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