Kde se asi stala chyba, Python

Kde se asi stala chyba: Regulární výrazy

Napsat komentář

Regulární výrazy jsou populární mezi mnoha programátory. V dnešním díle seriálu o chybách se podíváme na to, co je špatně na regulární výrazu  [+-0123456789] .

Regulární výrazy samy o sobě jsou relativně silný formalizmus pro vyhledávání a nahrazování v textu. Přestože je někdy také rád použiji, řadím je mezi write-only programovací jazyky spolu s dalšími jako je Perl, Brainfuck nebo Whitespace. Častěji používám řetězcové operace a metody, obzvláště v Pythonu, kde někdy mohou býti výrazně přehlednější než regulární výrazy. A dost často se pomocí nich nechá vyvarovat takovým chybám, které vám dnes ukážu.

Úkol zní jasně…

Pomocí regulárního výrazu zpracovat řetězec, který má obsahovat číslo typu int nebo float, kladné popř. záporné. Pracovat budeme opět v Pythonu a omezíme se na to, že chceme pouze matchovat regulární výraz na vstupní řetězec.

Kód vypadá jednoduše a dokonce funguje:

import re

RE = r'[+-0123456789]+(\.[0123456789]+)?'

for i in ['+1.0', '-1.0', '1.0', 'abcd', 'a.b']:
    matches = re.match(RE, i)
    print i, bool(matches)

Výstup přesně podle očekávání:

+1.0 True
-1.0 True
1.0 True
abcd False
a.b False

Později ve vývojovém cyklu…

Nyní vezmeme náš funkční kód a řekneme si, že chceme zvlášť zpracovat celou část a zvlášť desetinnou část. Zpracováním budiž vypsání informace o tom, že číslo desetinnou část má nebo nemá. Využijeme k tomu jedinou skupinu (uzavřenou v závorkách) v regulárním výrazu RE. Jen připomenu, že m.group(1) je None, pokud se skupina v řetězci nevyskytuje, převedeno na logickou hodnotu pak False:

for i in ['+1.0', '-1.0', '1.0', '10']:
    m = re.match(RE, i)
    desetiny = m.group(1)
    print i, bool(desetiny)

Výstup je ale překvapivě nesprávný:

+1.0 False
-1.0 False
1.0 False
10 False

Kde se asi stala chyba?

Výše uvedený příklad je jednoduchý a můžeme s ním dobře experimentovat. Praktický problém, kde jsem na chybu narazil, byl k experimentování výrazně nepříznivější. První z ladících experimentů bylo odstranění skupiny v regulárním výrazu:

RE = r'[+-0123456789]+'

for i in ['+1.0', '-1.0', '1.0', 'abcd', 'a.b']:
    matches = re.match(RE, i)
    print i, bool(matches)

Výsledek již sám o sobě byl zajímavý:

+1.0 True
-1.0 True
1.0 True
abcd False
a.b False

Dvakrát jsem tenkrát kontroloval, zda se spouští skutečně upravený kód. Když jsem se ujistil, že ano, nestačil jsem se dále divit:

for i in ['1,0', '1/0']:
    matches = re.match(RE, i)
    print i, bool(matches)

A výsledek svědčící o umělé inteligenci regulárních výrazů:

1,0 True
1/0 True

Ke konci pracovní doby a po mnoha pokusech člověk začíná věřit na chyby v implementaci regulárních výrazů v Pythonu. Po několikátém čtení zdrojového kódu se mi příčina vynořila před očima jako patník ze tmy: Znak mínus v regulárním výrazu není mínus, ale určuje rozsah znaků. Regulární výraz přijímá znaky 1 až 9 a pak libovolný znak v ASCII tabulce mezi + a 0, takže navíc právě znaky čárka, mínus, tečka a lomeno.

Teď už je vše jasné: skupina se nikdy nematchovala, protože regulární výrazy jsou hladové (greedy) a protože již první část výrazu odpovídala tečce a dalším číslům, na skupinu již nevyzbylo. Proto její odstranění chování žádným způsobem nepozměnilo. Protože rozsah znaků obsahoval i ono chtěné mínus, vše z první ukázky fungovalo zdánlivě dobře. A stejně tak regulární výraz odpovídal řetězcům 1,0 a 1/0.

Opravu jistě bystrý čtenář snadno nahlédne… Pro ty méně bystré — do regulárního výrazu stačí před znak mínus doplnit zpětné lomítko. Více krypticky ve stylu write-only pak stačí pouze přehodit pořadí  plusu a mínusu:

RE = r'[-+0123456789]+(\.[0123456789]+)?'

for i in ['+1.0', '-1.0', '1.0', '10']:
    m = re.match(RE, i)
    desetiny = m.group(1)
    print i, bool(desetiny)

A výstup dle očekávání:

+1.0 True
-1.0 True
1.0 True
10 False

Závěrem

Řešení spočívající v prohození dvou znaků je z mého pohledu velice kryptické, nedokáži si pomoci, ale pomocí kombinace metod split(), isdigit() a dalších by se daného chování dalo dosáhnout elegantněji. Tím nechci říci, že regulární výrazy v moderním programování nemají své místo — zpravidla mají, s vysokým nájmem a drahými příspěvky do fondu oprav.

Poznámka pod čarou

Přestože z teorie formálních jazyků víme, že regulární gramatika je přijímána konečným automatem, je důležité si uvědomit, že regulární výrazy neodpovídají regulárním gramatikám! Většina současných implementací používá pro matchování backtracking. Tyto implementace pak mohou používat vychytávky jako backreference to a named group (?P=name), lookahead assertion (?=…), positive lookbehind assertion (?<=…) a další (viz dokumentace modulu re).

Pro ilustraci si zkuste příklad:

re.search("(a+)+b", "aaaaaaaaaaaaaaaaaaaaaaaaaa")

Kolik času zabere tento jediný match? Setinu sekundy? Sekundu? Sto sekund? Jak komu…

Napsat komentář