how to express the following regular expression?
Joona I Palaste
palaste at cc.helsinki.fi
Wed Nov 21 23:03:20 CET 2001
Carl Howells <chowells at cs.uoregon.edu> scribbled the following
on comp.lang.java.programmer:
> "Stephen" <fungho at sinaman.com> wrote...
>> I want to search the following formats:
>>
>> ([1234567890]*)R
>> or
>> P([1234567890]*)
>>
>> this means there must be a 'P' before the number or a 'R' after the
>> number. However, I think I can't use this:
>> P?([1234567890]*)R?
>> because the number without P and R is also matched!
>>
>> How can I express it?
> Exactly you you'd expect... One or the other:
> (P\d*)|(\d*R)
> You could also use [0-9] in place of \d, if you were really set on using the
> [] notation. But there's no reason to use [1234567890].
This is indeed the only way. Regular expressions don't remember
things. When the regular expression "gets" to the R part, it
forgets what it did when it "was" in the P part.
This is the main reason why a criterion such as:
(((1234))) where the number of left parantheses is equal to the
number of right parantheses
cannot be expressed as a regular expression.
Noam Chomsky has written a definition of languages which addresses
this problem.
Context-free grammars are more powerful than regular expressions.
For example my criterion above can be expressed as the following
grammar (BNF notation):
TARGET ::= STRING
STRING ::= '(' STRING ')'
| DIGITS
DIGITS ::=
| ('0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9')
DIGITS
The OP's criterion can be expressed as follows:
TARGET ::= STRING
STRING ::= 'P' DIGITS
| DIGITS 'R'
DIGITS ::=
| ('0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9')
DIGITS
--
/-- Joona Palaste (palaste at cc.helsinki.fi) ---------------------------\
| Kingpriest of "The Flying Lemon Tree" G++ FR FW+ M- #108 D+ ADA N+++|
| http://www.helsinki.fi/~palaste W++ B OP+ |
\----------------------------------------- Finland rules! ------------/
"All that flower power is no match for my glower power!"
- Montgomery Burns
More information about the Python-list
mailing list