Help building a regular expression in python using the re module

Question

im writing a simple propositional logic formula parser in python which uses regular expressions re module and the lex/yacc module for lexing/parsing. Originally my code could pick out implication as ->, but adding logical equivalence (<->) caused issues with the compiled expressions

IMPLICATION = re.compile('[\s]*\-\>[\s]*')
EQUIVALENCE = re.compile('[\s]*\<\-\>[\s]*')
...
elif self.IMPLICATION.search(formula[0].strip()):
...
elif self.EQUIVALENCE.search(formula[0].strip()):
...

I originally tried adding [^<] to the front of -> to make it ignore instances of equivalence but this just made it not accept any instances of implication at all. Any possible help would be warmly welcome :)

Why are you doing this with regexes and not in the yacc grammar? — jrockway
– jrockway, Commented Feb 5, 2009 at 3:55
could you post the smallest self-contained example that exhibits this behavior? It may be instructive for you to create this example as well. — llimllib
– llimllib, Commented Feb 5, 2009 at 3:59

Kenan Banks · Accepted Answer · 2009-02-05 04:59:24Z

4

As far as I can tell, your regular expressions are equivalent to the following:

# This is bad, because IMPLICATION also will match every
# string that EQUIVALENCE matches
IMPLICATION = re.compile("->")
EQUIVALENCE = re.compile("<->")

As you've written it, you're also matching for zero or more whitespace characters before the -> and <-> literal. But you're not capturing the spaces, so it's useless to specify "match whether spaces are present or not". Also, note that - and > do not need to be escaped in these regular expressions.

You have two options as I see it. The first is to make sure that IMPLICATION does not match the same strings as EQUIVALENCE

# This ought to work just fine.
IMPLICATION = re.compile("[^<]->")
EQUIVALENCE = re.compile("<->")

Another option is to use the maximal munch method; i.e., match against all regular expressions, and choose the longest match. This would resolve ambiguity by giving EQUIVALENCE a higher precedence than IMPLICATION.

answered Feb 5, 2009 at 4:59

Kenan Banks

213k36 gold badges161 silver badges176 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

user3850 Over a year ago

+1 for cutting down on the cruft. since the op uses elif, though, simply reversing the order of the two tests should do the same trick (although implicitly, not explicitly)

sykloid · Accepted Answer · 2009-02-05 04:00:42Z

0

I think you can solve this simply by reordering your checking to match equivalences first, and then implications. However, this seems to work :

>>> IMPLICATION = re.compile(r'\s*[^\<]\-\>\s*')
>>> EQUIVALENCE = re.compile(r'\s*\<\-\>\s*')

answered Feb 5, 2009 at 4:00

sykloid

102k12 gold badges67 silver badges71 bronze badges

Collectives™ on Stack Overflow

Help building a regular expression in python using the re module

2 Answers 2

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related