 |
 |
|
 |
|
 |
|  |
|  |
|
 |
|
 |
|  |
|  |
|
 |
Darren New wrote:
> http://swtch.com/~rsc/regexp/regexp1.html
Oh, and given that .NET compiles regular expression matches down to machine
code, I was really rather surprised to discover that it too exhibits
exponential runtime for the shown test expressions, even tho it doesn't need
to. I can't imagine why you'd go to the effort of having an option to
compile the thing to machine code if you're going to be too lazy to do the
trivial check it takes to determine whether you need a linear or exponential
algorithm.
--
Darren New, San Diego CA, USA (PST)
Serving Suggestion:
"Don't serve this any more. It's awful."
Post a reply to this message
|
 |
|  |
|  |
|
 |
|
 |
|  |
|  |
|
 |
>> The basics of mathematical notation are so ubiquitous throughout the
>> Western world
>
> And the basics of regexp notation is mathematical. As well as being
> ubiquitous throughout the programming world. Which is why we're equating
> the two.
Apparently you have a radically different idea of "ubiquitous" than I do...
Post a reply to this message
|
 |
|  |
|  |
|
 |
|
 |
|  |
|  |
|
 |
>> Do you have a concrete example?
>
> http://swtch.com/~rsc/regexp/regexp1.html
>
> Or, in your language
> many (char 'a')
> many (char 'a')
> many (char 'a')
> char 'a'
> char 'a'
> char 'a'
> Now match that against "aaaaaa".
>
> The problem is the first "many (char 'a')" eats the whole string.
>
> Without backtracking, you claim the string fails to match.
> *With* backtracking, you're now taking an exponential amount of time to
> match something you could match in six comparisons.
I don't understand the specification.
Post a reply to this message
|
 |
|  |
|  |
|
 |
|
 |
|  |
|  |
|
 |
Invisible wrote:
>>> Semantic correctness is impossible to guarantee.
>>
>> Yes, and that's my point. Even with your syntactic correctness, you got
>> the parser for the numbers wrong.
>
> So because you can't find /all/ bugs automatically, it's pointless to
> try to find /any/ bugs automatically?
No. Because you can't find semantic bugs, it's pointless to moan about a
simple reliable bug that gets reproduced the first time you run the code, if
not sooner. It's almost as silly to complain about a regexp library not
ensuring syntactic correctness before you invoke the library as it is to
complain about a compiler that doesn't issue error messages until you try to
compile something.
For a regexp literal, it's trivial to check it's syntactically valid,
*because* it doesn't depend on the rest of the program.
>>> It's a bit like trying to build an
>>> XML file by string manipulation. Yes, it can be done. Yes, you can
>>> make it work. And yes, it's incredibly fragile.
>>
>> No it's not.
>
> I give up.
<Yoda> And that is why you fail. </Yoda>
You're making assertions with no experience. You've already admitted you
don't know how regular expressions work, yet here you are telling *me* that
building them programatically is "incredibly fragile". You're talking out
your ass, my dear.
> I have yet to see anybody construct a regex in any way other than typing
> it out by hand, or gluing strings together by hand.
You don't even know how they work, so I am not at all surprised you haven't
seen the more sophisticated mechanisms. Just off the top of my head,
GUI-wise that you may have seen, there's Agent Ransack's expression builder.
http://www.cs.uiuc.edu/class/fa05/cs475/Lectures/new/lec05.pdf
http://www.physicsforums.com/showthread.php?t=265064
There are also any number of systems that'll build lexers for you.
(I'd like you to note that some of these are college lecture course notes.
This is basic fundamental stuff that everyone with a degree in CS should
know. So it's not like we're pushing some bizarre esoteric edge-case at you.)
In any case, a regexp is generally not powerful enough that you need to
build it programatically. Indeed, that's precisely the point.
--
Darren New, San Diego CA, USA (PST)
Serving Suggestion:
"Don't serve this any more. It's awful."
Post a reply to this message
|
 |
|  |
|  |
|
 |
|
 |
|  |
|  |
|
 |
Invisible wrote:
> Apparently you have a radically different idea of "ubiquitous" than I do...
Regular expressions are the same as state machines.
Let me list a few of the programs I use every day that support and use
regular expressions:
.NET
VI
EMacs
Grep
Find
Bash
Perl
Awk
Sed
Flex
javascript
Tcl
Haskell
Pretty much every editor above the level of notepad
Pretty much every programming language since COBOL
Let me list a few of the programs that support the parser you prefer:
Haskell
So, yeah, the fact that your education sucks doesn't mean bupkiss about what
actually goes on in the real world. :-)
--
Darren New, San Diego CA, USA (PST)
Serving Suggestion:
"Don't serve this any more. It's awful."
Post a reply to this message
|
 |
|  |
|  |
|
 |
|
 |
|  |
|  |
|
 |
Invisible wrote:
>>> Do you have a concrete example?
>>
>> http://swtch.com/~rsc/regexp/regexp1.html
>>
>> Or, in your language
>> many (char 'a')
>> many (char 'a')
>> many (char 'a')
>> char 'a'
>> char 'a'
>> char 'a'
>> Now match that against "aaaaaa".
>>
>> The problem is the first "many (char 'a')" eats the whole string.
>>
>> Without backtracking, you claim the string fails to match.
>> *With* backtracking, you're now taking an exponential amount of time to
>> match something you could match in six comparisons.
>
> I don't understand the specification.
I even expressed it in Haskell-ish syntax.
"Zero or more A's, followed by zero or more A's, followed by zero or more
A's, followed by three A's."
The fact that you can't read the link I provided is screaming out that you
need to learn how to read that link. Not knowing even the basics of regular
expressions is like not knowing even the basics of TCP.
--
Darren New, San Diego CA, USA (PST)
Serving Suggestion:
"Don't serve this any more. It's awful."
Post a reply to this message
|
 |
|  |
|  |
|
 |
|
 |
|  |
|  |
|
 |
Invisible wrote:
> I have yet to see anybody construct a regex in any way other than typing
> it out by hand, or gluing strings together by hand.
And you didn't actually google for something like "programatically construct
regular expressions", right?
http://www.phpclasses.org/package/5776-PHP-Build-regular-expressions-programmatically.html#description
--
Darren New, San Diego CA, USA (PST)
Serving Suggestion:
"Don't serve this any more. It's awful."
Post a reply to this message
|
 |
|  |
|  |
|
 |
|
 |
|  |
|  |
|
 |
"Haskell was developed by Isaac Newton in the 15th Century as a tool to
help his investigations into the Alchemic arts. It was rediscovered in
the 1980s by three Cambridge undergraduates who were browsing through
Newton's laboratory notebooks looking for smutty jokes in the margins,
and has since developed into an elaborate joke perpetrated by elite
computer scientists who believe that predictable order of execution is
contrary to natural law. The current version of Haskell is Haskell 1714,
which adds syntactic sugar for Zygohistomorphic Premorphisms to the
original language definition of 1693."
Post a reply to this message
|
 |
|  |
|  |
|
 |
|
 |
|  |
|  |
|
 |
Other amusing quotes of the week:
"Also [scripting languages] 'don't scale well', which I guess means that
they don't make it inconvenient to design badly."
"someday we'll need meta-software that converts from obsolete languages
into modern ones"
"Don't we call that compilers?"
[Actually that's kinda backwards, isn't it?]
"how about a language where you program with unit vectors: orientation
oriented programming"
"what you just typed isn't even well typed"
(The compiler tells me this all the time BTW...)
--
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*
Post a reply to this message
|
 |
|  |
|  |
|
 |
|
 |
|  |
|  |
|
 |
Orchid XP v8 <voi### [at] dev null> wrote:
> "Haskell was developed by Isaac Newton in the 15th Century as a tool to
> help his investigations into the Alchemic arts. It was rediscovered in
> the 1980s by three Cambridge undergraduates who were browsing through
> Newton's laboratory notebooks looking for smutty jokes in the margins,
> and has since developed into an elaborate joke perpetrated by elite
> computer scientists who believe that predictable order of execution is
> contrary to natural law. The current version of Haskell is Haskell 1714,
> which adds syntactic sugar for Zygohistomorphic Premorphisms to the
> original language definition of 1693."
its from the mailing list, isn't it?
Post a reply to this message
|
 |
|  |
|  |
|
 |
|
 |
|  |