Re: StringBuilder Extension: IsQuotedBy

>>  But I expect a Regex
>> implementation to create a unique FSM from every input signature.
> > P
>
> I don't understand your last sentence. The FSM is constructed for the
> regex, not for the sentence to be matched.
>

By input signature, I mean the signature of the machine to be created (ie:
the expression or regex).


> Also, I don't see how this is relevant to why one wouldn't "still"
> hand-write a DFA.
>
> -- Barry


The point is that a finite state machine is a DFA and is generated by every
Regex engine implementation from the first input tape (ie: the regex) and
then moves over the second tape (input string to evaluate it. The input
string passes if the machine gets to a finish state and there will be many
of them in most real cases). I don't agree that whipping up a new custom
parser is guaranteed to do the job faster until we see some real theoretical
analysis or empirical data. I also don't buy the claim that it's as trivial
a task as to require 1 hour of a developer's time (not to mention testing
time). Of course, the dragon book has a 100-line lexer (I hope we all
remember that enticing chapter).
I hope you now see the relevance Barry. I probably didn't make the
connection clear the first time.
P


--------------------------------------------------
From: "Barry Kelly" <[email protected]>
Sent: Friday, February 15, 2008 10:05 AM
To: <[email protected]>
Subject: Re: [DOTNET-CLR] StringBuilder Extension: IsQuotedBy

> Peter Obiefuna <[email protected]> wrote:
>
>> > Any single given regex terminates in a single state, "matched". A
>> > tokenizer has multiple ending states, one for each token. This is the
>> > key difference between most third-party regex libraries and the
>> > requirements of people writing parsers for well-defined languages.
>> >
>> > -- Barry
>>
>> I would expect a regex implementation to construct a FSM from it's
>> expression string. Meaning that a "single given regex" could terminate in
>> multiple states, each of which is a "matched" state.
>
> Yes; but most third-party regex implementations don't distinguish
> between matched states in the API, so in effect, all the matched states
> are the same state. You'd need to extend a regex language to distinguish
> between them.
>
> In other words, for some regex R:
>
>  R ::= 'a' | 'b' | 'c' .
>
> We'd usually construct:
>
>  s0 - start state
>  s0 -'a'-> s1
>  s0 -'b'-> s1
>  s0 -'c'-> s1
>  s1 - finish state
>
> ... and have slight difficulty in finding out which of a, b, or c we
> saw.
>
>> If it keeps hitting a
>> matched state until the input buffer is finished, then, the string
>> 'qualifies'. That, in my mind, is the difference between  a state engine
>> and
>> a collation engine like strcomp (never mind that you can illustrate FSM
>> graphically by pointing to a final dot on paper). But I expect a Regex
>> implementation to create a unique FSM from every input signature.
>
> I don't understand your last sentence. The FSM is constructed for the
> regex, not for the sentence to be matched.
>
> Also, I don't see how this is relevant to why one wouldn't "still"
> hand-write a DFA.
>
> -- Barry
>
> --
> http://barrkel.blogspot.com/
>
> ===================================
> This list is hosted by DevelopMentor®  http://www.develop.com
>
> View archives and manage your subscription(s) at
> http://discuss.develop.com
>

===================================
This list is hosted by DevelopMentor®  http://www.develop.com

View archives and manage your subscription(s) at http://discuss.develop.com