Beefy Boxes and Bandwidth Generously Provided by pair Networks
Syntactic Confectionery Delight

Re: Re: Perl and Context Free Grammar

by gjb (Vicar)
on Nov 19, 2003 at 13:45 UTC ( #308290=note: print w/replies, xml ) Need Help??

in reply to Re: Perl and Context Free Grammar
in thread Perl and Context Free Grammar

Please make a distinction between regular expressions as known in computer science literature and Perl regular expressions. I know someone like you knows, but many people could get very wrong ideas from a statement such as the above.

Regular expressions in the computer science sense have a subset of the operators Perl regular expressions have, i.e. concatenation, union, kleene star.

Regular expressions describe regular languages, context free grammars describe context free languages and it is known (and fairly easy to prove) that reguular languages are a proper subset of context free languages. Hence you can't parse context free language with a regular expression unless it happens to be a regular language.

Perl regular expressions are more powerful than computer science regular expressions since they've features such as capturing and \1, zero-width assertions and code embedding. It is indeed an open problem what the precise expressive power is.

Sorry for this piece of pedantry, but IMHO it's an important point to make when addressing a very general audience.

Just my 2 cents, -gjb-

Log In?

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://308290]
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others scrutinizing the Monastery: (6)
As of 2021-04-13 18:09 GMT
Find Nodes?
    Voting Booth?

    No recent polls found