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

>> 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

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