Re: StringBuilder Extension: IsQuotedBy

A much more appropriate tool for parsing complex languages would be a
LALR parser such as the one I mentionned before.

http://www.devincook.com/goldparser/

Having a grammar file clearly laid out and used to generate the
parsing code is much more maintainable than some contorted monster
regexp. As others have pointed out, you also cannot visit the parse
tree ...

Sébastien

On 2/15/08, Peter Obiefuna <[email protected]> wrote:
> >>  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(R)  http://www.develop.com
>  >
>  > View archives and manage your subscription(s) at
>  > http://discuss.develop.com
>  >
>
>  ===================================
>  This list is hosted by DevelopMentor(R)  http://www.develop.com
>
>  View archives and manage your subscription(s) at http://discuss.develop.com
>


-- 
Sébastien
www.sebastienlorion.com

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

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