Help building a regular expression in python using the re module

Question

Hi guys, 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 :)

Answer 1

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*')

Answer 2

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.