Python's Hidden Regular Expression Gems

http://lucumr.pocoo.org/2015/11/18/pythons-hidden-re-gems/

by temp • 11 years ago

276 43 11 years ago

lucumr.pocoo.org

ioquatix• 11 years ago

There is nothing unique about Python's implementation of regular expressions. Ruby has an equally (if not more) powerful `StringScanner`. This is a nice article but it could have done without the "it's one of the best of all dynamic languages I would argue" tone.

the_mitsuhiko2• 11 years ago

Ruby has an equally (if not more) powerful `StringScanner`

The string scanner is just a step by step matching of individual expressions. Because they are not folded together the "skip non matching" part has been done in Ruby which is precisely what the Python scanner avoids.

willvarfar2• 11 years ago

Another very-cool undocumented feature on another regex engine is re2's Set. It compiles a collection of regex to a single regex, and so allows you to very efficiently match a string against an array of patterns.

andreasvc9• 11 years ago

Which re2? I maintain a fork of re2 but it's not in there [1].

If you mention re2 the main cool feature about it is that it is efficient, matching in linear time using DFA. Unfortunately unicode strings need to be encoded to utf8 but if you can design your application to work with utf8 bytestrings you can avoid that cost.

[1] http://github.com/andreasvc/pyre2

willvarfar2• 11 years ago

https://github.com/google/re2/blob/master/re2/set.h <-- c++ API

https://github.com/google/re2/blob/master/re2/prog.h#L339 <-- c

fanf2• 11 years ago

Another package that does this is re2c [1] which is used by spamassassin to compile its rulesets to scan messages faster.

[1] http://re2c.org

fndrplayer13• 11 years ago

Really interesting read. To be honest, I got a little lost around the Scanner implementation portion. Guess its time to take that example and play around with it myself. My one suggestion would be to maybe walk through an example of how the Scanner would work to demonstrate your point.

Thanks for the great post.

the_mitsuhiko2• 11 years ago

I made a larger class in a github repo and an example of what you can do with it here: https://github.com/mitsuhiko/python-regex-scanner/blob/maste...

fulafel• 11 years ago

I did a double take upon seeing "The regex module in Python is really old by now" and had to make sure it's talking about the current re module! re was introduced alongside the older regex module around Python 1.5, the latter was finally removed in Python 2.5.

andreasvc9• 11 years ago

Additionally there's a newer module also named 'regex': https://pypi.python.org/pypi/regex

rspeer• 11 years ago

And this newer 'regex' is actually really good at tricky cases such as matching word boundaries. (An apostrophe or a non-ASCII character is not necessarily a word boundary!)

mkesper• 11 years ago

Lately there had been a comparison of Javascript, Perl and Python regex machinery posted here iirc (can't find right now) and the external regex module was found to be much better regarding unicode support.

berntb• 11 years ago

(How could non-3 Python have good Unicode support? :-) )

The default Python regexp gets into a tailspin on less well formulated regexps, which did work well with both PCRE and Perl 5. (I wrote an application (specialized query language) a few years ago where programmers entered regexps. Sometimes the execution just hanged. This was 2.6 and early 2.7.)

I haven't tried the external regexp module, but hope it is better.

lugus35• 11 years ago

http://doc.perl6.org/language/regexes

Read. Recite. Review.

andreasvc9• 11 years ago

I wonder what the reason is to include code in a release without documenting it. Maybe this article can form the basis for finally documenting this feature?

There's also the reverse with Python: useful code in the documentation not included in the standard library.

HerpDerpLerp• 11 years ago

Maybe this sort of thing will be tackled by the new stackoverflow documentation thing.

This link may do nothing if you are not part of the beta! http://docs-beta.stackexchange.com/documentation

creshal• 11 years ago

I wonder what the reason is to include code in a release without documenting it.

Presumably it's considered an implementation detail and the author didn't realize it was useful for anything else.

dalke• 11 years ago

The author knows that it's useful. See http://effbot.org/zone/xml-scanner.htm where the author uses the scanner:

The 2.0 engine provides another (undocumented) feature that can be used to optimize this even further. The scanner method is used to create a scanner object and attach it to a string.

See http://bugs.python.org/issue5337 where the Python developers wondered if it should be documented.

There's a 10 year old notice at https://mail.python.org/pipermail/patches/2006-November/0210... saying that the code would crash if the scanner was called from multiple threads.

There's no doubt much more information about this - the above was all I cared to find out.

notzorbo2• 11 years ago

This happens pretty often in the Python world. There's a bit of an unwritten rule to leave implementation details public that would be private in other languages. Many libraries simply don't bother with prefixing privates with '_' and just leave things undocumented that you probably shouldn't touch/use.

One notable example is importing libraries in your code automatically exposes them to the caller.

    $ cat lib.py
    import re
    
    def somefunc():
        pass

    $ python
    >>> import lib
    >>> lib.re
    <module 're' from '/usr/lib/python2.7/re.pyc'>

Many packages also do `import *` from files which polutes the package namespace with all kinds of stuff you really don't want in there. For example, the popular Requests package:

    >>> import requests
    >>> requests.logging
    <module 'logging' from '/usr/lib/python2.7/logging/__init__.pyc'>

The logging module is not a public part of requests' API. It's just there because requests uses it internally.

So to answer your question, I'd say it's just common practice. If it's undocumented in Python, you should pretend it doesn't exist.

orf3• 11 years ago

Importing libraries from other libraries like this is very useful:

    $ python
    >>> import lib
    >>> lib.re

That's how __init__.py files work, and is part of what makes Python awesome. Using `import *` is very bad practice in modules (except in very specific cases) because it brings in a bunch of crap you don't want and didn't expect. Modules should define a '__all__' list of 'public things' you want to export, but restricting access is very anti-python as we're all consenting adults.

   If it's undocumented in Python, you should pretend it doesn't exist.

I don't agree. It's fairly common to dive into 3rd party packages code to see what's occurring and to use 'undocumented' things (which is mostly because the documentation is bad rather than being hidden away). Just look at the Django `_meta` API, which people relied on because it was the only place you could get some specific model information in a stable way, despite being undocumented and private. Now it's been formalized into a proper API.

Pythons extensive use of duck typing also makes it a lot easier to work with undocumented stuff, you can make some wide ranging changes to internals (changing types completely, turning properties into functions) but as long as it quacks roughly the same nothing breaks.

mh-• 11 years ago

unwritten rule

I don't know if I'd call this (common) practice an unwritten rule in the Python world.

rather, there's no real notion of visibility.. so the only thing you can do to make something 'look private' is name it obscurely (i.e. the underscore prefix, as you mentioned) and leave it undocumented.

it's perhaps my least favorite part of python module semantics.

rjprins• 11 years ago

Imho, (good) Python code is so easy to read and inspect, that it can be better than documentation. Documentation is less exact. I often find myself reading the libraries that I use, to see what it really does. Once you get into the habit of that, documentation is only useful as a starting point and you can discover a lot more useful functionality. (And also get a good feel of the quality of the library, and learn a lot in terms of patterns)

Of course, this habit comes with the risk that you might have to do more maintenance on your code on library updates.

As documentation takes effort to write and constitutes a sort of contract with your users, it makes sense for library writers to only document the truly essential.

andreasvc9• 11 years ago

I don't think this position of relying on code instead of documentation is tenable for non-trivial code. The amount of effort to understand code is generally much more than that of maintaining documentation of what a function does, meaning of arguments, and any assumptions made. Documentation can (and should) have a much higher signal-to-noise ratio.

Grue3• 11 years ago

Python's re has nothing on CL-PPCRE [1] though. The ability to build up a "regular expression" from S-expressions is just too useful.

[1] http://weitz.de/cl-ppcre/

nanny• 11 years ago

It was also twice as fast as Perl in benchmarks at one point or another.

kbenson2• 11 years ago

That's not exactly hard to do, depending on features. There's a definite trade-off between features and the type of regex engine that can be implemented.

junke2• 11 years ago

For example, here below is a CL version of "Enter The Scanner". Instead of a closure, we could instanciate a class, but this is sufficient:

   (defun create-tokenizer (rules)                                                                                                      
     (loop for (token rule) in rules                                                                                                    
           for regex = (if (stringp rule) `(:regex ,rule) rule)                                                                         
           collect `(:register ,regex) into alternatives                                                                                
           collect token into tokens                                                                                                    
           finally                                                                                                                      
              (let ((scanner (ppcre:create-scanner `(:alternation ,@alternatives)))                                                     
                    (tokens (coerce tokens 'vector)))                                                                                   
                (return                                                                                                                 
                  (lambda (string &key (start 0))                                                                                       
                    ;; generator-like                                                                                                   
                    (lambda ()                                                                                                          
                      (multiple-value-bind (match-start match-end registers)                                                            
                          (ppcre:scan scanner string :start start)                                                                      
                        (cond                                                                                                           
                          (match-start                                                                                                  
                           (setf start match-end)                                                                                       
                           (values                                                                                                      
                            (aref tokens (position-if-not #'null registers))                                                            
                            match-start                                                                                                 
                            match-end))                                                                                                 
                          (t (values))))))))))

The above compiles the regex and returns a closure which accepts a string. That closure returns another closure which generates tokens on-demand for the given string, along with the start and end positions of the token inside the string. Here is a test:

   (loop with tokenizer = (funcall (create-tokenizer '((ws "\\s+")                                                                      
                                                       (plus #\+)                                                                       
                                                       (minus #\-)                                                                      
                                                       (mult #\*)                                                                       
                                                       (div #\/)                                                                        
                                                       (num :digit-class)                                                               
                                                       (par-open #\()                                                                   
                                                       (par-close #\))))                                                                
                                   "(1 + 2) * 3")                                                                                       
         for token = (multiple-value-list (funcall tokenizer))                                                                          
         while token                                                                                                                    
         collect token)                                                                                                                 
                                                                                                                                        
   => ((par-open 0 1) (num 1 2) (ws 2 3) (plus 3 4) (ws 4 5) (num 5 6)                                                                  
 (par-close 6 7) (ws 7 8) (mult 8 9) (ws 9 10) (num 10 11))

junke2• 11 years ago

Note also that the problem exposed in the article about mixing register groups with other register groups in each rule can probably be easily overcome with named registers in CL-PPCRE. See http://weitz.de/cl-ppcre/#*allow-named-registers*.

stefantalpalaru• 11 years ago

it's one of the best of all dynamic languages I would argue

The author should learn about PCRE. I wrote a Python wrapper for it that includes a drop-in 're' substitute: https://github.com/stefantalpalaru/morelia-pcre

larkinrichards• 11 years ago

I believe there is a small bug in the final example, in the tokenize definition it references 'self' where I believe it should reference 'scanner'.

nichochar• 11 years ago

Amazing! This Scanner object seems so beautifully pythonic and intuitive. It's a shame it's not documented honestly: it would be a great way for beginners in python to write language parsers

Python's Hidden Regular Expression Gems

Related Stories