![](/i/fill.gif) |
![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
Invisible wrote:
>>> If there are more than three digits, the above parser fails, and no
>>> other alternatives are tried (i.e., no backtracking).
>>
>> Then you aren't doing what regular expressions can do.
>
> I don't see how that is the case.
You really should learn the essential basics of an entire heirarchy of
formal language theory.
>> In order to *get* the power of regexp, *your* parser has to backtrack.
>> So if you turn backtracking off, there are trivial regular expressions
>> you can't match. If you turn backtracking on, you're using more time and
>> space than a regular expression engine.
>
> 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.
--
Darren New, San Diego CA, USA (PST)
Serving Suggestion:
"Don't serve this any more. It's awful."
Post a reply to this message
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
>> 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?
All I can say to that is: I do not agree.
>> 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.
> If you're using a library to construct regular expressions, of course
> the library is going to be invoked in a way that makes it impossible to
> construct syntactically invalid regular expressions, just like your
> parser is.
>
> You're comparing Haskell against brain-dead worst-possible-stupidity
> regular expression libraries, and saying "See? My way is better!"
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.
Post a reply to this message
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
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
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
>> 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
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
>> 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
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
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
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
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
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
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
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
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
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
"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
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |