Mundarija (23)
- 1. Kirish va motivatsiya
- 2. Nazariya — chuqur tushuntirish
- 2.1. Lookaround — "qarash", lekin olmaslik
- 2.2. Lookbehind cheklovi
- 2.3. Bir nechta lookahead — "hammasi bajarilsin"
- 2.4. Chegara tuzoqlari
- 2.5. Katastrofik backtracking
- 2.6. Atomik guruh va possessiv miqdorlar (3.11+)
- 2.7. Shartli guruh va bytes
- 2.8. Tokenizator
- 2.9. Regexni qachon ishlatmaslik
- 3. Tez ma'lumotnoma
- 4. Batafsil misollar
- Misol 1 — Lookahead va lookbehind
- Misol 2 — Amaliy naqshlar va chegara tuzoqlari
- Misol 3 — Katastrofik backtracking
- Misol 4 — Amaliy: kichik hisoblash tili
- 5. To'g'ri va noto'g'ri tushunishlar
- 6. Keng tarqalgan xatolar va yechimlari
- 7. Integratsiya — bu bilim qayerda kerak bo'ladi
- 8. Eng yaxshi amaliyotlar
- 9. Amaliy topshiriq
- Xulosa
15.3-dars: re: amaliy naqshlar
15-QISM — STANDART KUTUBXONA · 3-dars
1. Kirish va motivatsiya
Oldingi ikki darsda muntazam ifodalar tilini va guruhlar bilan ishlashni o'rgandik. Endi uchta amaliy savol qoldi:
- Kontekstga qarab qidirish. "
so'mdan oldingi sonlar", "$belgisidan keyingi raqamlar", "parolda kamida bitta katta harf, raqam va belgi bo'lsin" — kontekstning o'zini natijaga qo'shmasdan. - Real naqshlar. Email, URL, IP manzil, telefon — internetdagi "tayyor" naqshlarning ko'pchiligi yo ortiqcha narsani o'tkazadi, yo to'g'risini rad etadi.
- Xavfsizlik va tezlik. Qaysi naqsh bitta satrda soniyalab ishlab, serverni to'xtatib qo'yadi?
Real vaziyat. 2019-yil 2-iyulda Cloudflare'ning global tarmog'i taxminan 27 daqiqaga ishdan chiqdi. Sabab — WAF qoidalariga qo'shilgan bitta muntazam ifoda: uning ichida .*(?:.*=.*) qismi bor edi. Bunday naqsh ba'zi satrlarda katastrofik backtracking ga tushadi — protsessorlar 100% band bo'lib qoldi. Bu hodisa ReDoS (Regular expression Denial of Service) deb ataladi va uni bir necha qator Python kodi bilan qayta hosil qilish mumkin.
Bu darsda kontekstli qidiruvni, amaliy naqshlarning tuzoqlarini, backtracking dan himoyalanishni va regexning eng kuchli qo'llanishi — tokenizator yozishni o'rganamiz.
Bu darsda:
- Lookahead va lookbehind:
(?=...),(?!...),(?<=...),(?<!...) - Bir nechta lookahead bilan qoidalar (parol siyosati)
- Amaliy naqshlar: IP, URL, telefon, email — va chegara tuzoqlari
- Katastrofik backtracking va ReDoS
- Atomik guruh
(?>...)va possessiv miqdorlar*+,++(3.11+) - Shartli guruh
(?(1)...),bytesnaqshlar - Tokenizator:
finditer+lastgroup - Amaliy: kichik hisoblash tilining tokenizatori va hisoblovchisi
2. Nazariya — chuqur tushuntirish
2.1. Lookaround — "qarash", lekin olmaslik
Lookaround pozitsiyani tekshiradi va hech qanday belgini iste'mol qilmaydi — natijaga kirmaydi.
| Yozuv | Nomi | Ma'nosi |
|---|---|---|
X(?=Y) |
Ijobiy lookahead | X, undan keyin Y kelsa |
X(?!Y) |
Salbiy lookahead | X, undan keyin Y kelmasa |
(?<=Y)X |
Ijobiy lookbehind | X, undan oldin Y bo'lsa |
(?<!Y)X |
Salbiy lookbehind | X, undan oldin Y bo'lmasa |
re.findall(r"\d+(?= so'm)", "12 so'm, 5 dona, 300 so'm") # ['12', '300']
re.findall(r"(?<=\$)\d+", "$40 va 50$") # ['40']Klassik qo'llanish — minglik ajratgich. Pozitsiya: oldida raqam bor va keyin 3 ga karrali raqamlar bilan tugaydi:
re.sub(r"(?<=\d)(?=(?:\d{3})+(?!\d))", " ", "1234567") # '1 234 567'2.2. Lookbehind cheklovi
Python re da lookbehind qat'iy uzunlikda bo'lishi kerak:
| Naqsh | Holat |
|---|---|
(?<=\$) |
1 belgi |
(?<=USD ) |
4 belgi |
(?<=\d+) |
look-behind requires fixed-width pattern |
| `(?<=ab | xyz)` |
| `(?:(?<=ab) | (?<=xyz))` |
2.3. Bir nechta lookahead — "hammasi bajarilsin"
Lookahead pozitsiyani siljitmagani uchun ularni ketma-ket qo'yish — mantiqiy "VA":
PAROL = re.compile(
r"(?=.*[a-z])" # kichik harf bor
r"(?=.*[A-Z])" # katta harf bor
r"(?=.*[0-9])" # raqam bor
r"(?=.*[^\w\s])" # belgi bor
r".{8,}" # uzunlik
)
PAROL.fullmatch("Salom123!") # ✅Amaliyotda har qoidani alohida tekshirib, foydalanuvchiga aniq xabar berish yaxshiroq: "katta harf yetishmayapti" — "parol noto'g'ri" dan ancha foydali.
2.4. Chegara tuzoqlari
Naqsh "o'zi to'g'ri", lekin kattaroq satr ichidan qism topib oladi:
| Naqsh (chegarasiz) | Matn | Topilgani |
|---|---|---|
| IPv4 | 256.1.1.1 |
56.1.1.1 |
| Telefon | +998-91-123-45-678 |
+998911234567 |
| URL | http://x.io. |
http://x.io. — oxiridagi nuqta bilan |
| Yechim | Qachon |
|---|---|
\b |
So'z va so'z bo'lmagan belgi orasida — lekin 2 va 5 orasida emas |
(?<![0-9])...(?![0-9]) |
Raqamli naqshlar uchun |
fullmatch |
Butun qiymat tekshirilayotganda |
| Oxiridagi tinish belgisini kesish | URL, email matn ichida |
2.5. Katastrofik backtracking
re — backtracking dvigatel: mos kelmasa, orqaga qaytib boshqa variantni sinaydi. Ba'zi naqshlarda variantlar soni eksponensial o'sadi.
re.fullmatch(r"(a+)+", "a" * 25 + "!") # soniyalar, keyin daqiqalarn ta a ni (a+)+ ichida bo'laklarga ajratish usullari — 2^(n-1). Oxiridagi ! tufayli hammasi sinab chiqiladi.
Xavfli shakllar:
| Naqsh | Muammo |
|---|---|
(a+)+, (a*)*, (\d+)* |
Ichma-ich miqdorlar |
| `(a | a)+, (a |
(\w+\s?)+$ |
Ixtiyoriy ajratgichli takror |
.*.*=.* |
Ketma-ket ochko'z .* lar |
Belgisi: mos keladigan satrlarda tez, deyarli mos keladigan satrlarda juda sekin. Test ma'lumotlari odatda "yaxshi" bo'lgani uchun muammo ishlab chiqarishda ochiladi.
2.6. Atomik guruh va possessiv miqdorlar (3.11+)
Ular orqaga qaytishni taqiqlaydi: bir marta olingan belgilar qaytarib berilmaydi.
| Yozuv | Ma'nosi |
|---|---|
(?>...) |
Atomik guruh |
a*+, a++, a?+, a{2,5}+ |
Possessiv miqdorlar |
re.fullmatch(r"a*a", "aaa") # ✅ — a* bitta 'a' ni qaytarib beradi
re.fullmatch(r"a*+a", "aaa") # None — a*+ hammasini oldi va qaytarmaydi
re.fullmatch(r"(?>a+)+", "a" * 25 + "!") # ⭐ darhol NoneReDoS dan himoya:
- Ichma-ich miqdorlardan qoching:
(a+)+→a+ - Muqobillar bir-birini qoplamasin
- Kerak joyda — atomik guruh / possessiv miqdor
- Kirish uzunligini cheklang — eng oddiy va ishonchli himoya
- Foydalanuvchi naqsh kiritadigan tizimda —
reemas, chiziqli vaqt kafolatli dvigatel (google-re2)
re da muddat (timeout) parametri yo'q.
2.7. Shartli guruh va bytes
re.fullmatch(r"(<)?\w+(?(1)>)", "<ab>") # ✅ — '<' bo'lsa '>' ham kerak
re.fullmatch(r"(<)?\w+(?(1)>)", "<ab") # Nonebytes bilan ishlash uchun naqsh ham bytes bo'ladi: re.findall(rb"\d+", b"..."). str naqsh bytes matnga qo'llanmaydi.
2.8. Tokenizator
Regex leksik tahlil (tokenlarga ajratish) uchun ideal (15.1-dars, Vazifa 7). Naqsh: har token turi — nomli guruh, hammasi | bilan, oxirida "istalgan boshqa belgi" — xato:
TOKEN = re.compile(r"""
(?P<SON>\d+(?:\.\d+)?)
| (?P<NOM>[A-Za-z_]\w*)
| (?P<OP>[-+*/=()])
| (?P<BOSHLIQ>\s+)
| (?P<XATO>.)
""", re.VERBOSE)
for m in TOKEN.finditer(kod):
tur, qiymat = m.lastgroup, m[0]| Qoida | Sabab |
|---|---|
| Uzunroq/aniqroq token oldinda | ` |
Oxirida XATO guruhi |
Noma'lum belgi jim tashlab ketilmaydi |
m.lastgroup |
Qaysi tur mos kelgani |
m.start() |
Xato joyini ko'rsatish |
2.9. Regexni qachon ishlatmaslik
| Vazifa | Yaxshiroq vosita |
|---|---|
| Satr boshlanishi/tugashi | startswith / endswith |
| Oddiy qism bormi | in |
| Bitta ajratgich bo'yicha bo'lish | str.split |
| Sanani tekshirish | datetime.strptime (15.4-dars) |
| Email haqiqiyligi | Tasdiqlash xati |
| HTML, JSON, CSV | Parser (16-qism) |
| URL qismlari | urllib.parse |
| IP manzil | ipaddress moduli |
3. Tez ma'lumotnoma
r"\d+(?= so'm)" # keyin ' so'm' bo'lsa
r"(?<![0-9])[0-9]{9}(?![0-9])" # aniq 9 raqam, atrofida raqam yo'q
r"(?=.*[A-Z])(?=.*[0-9]).{8,}" # bir nechta shart
r"(?<=\d)(?=(?:\d{3})+(?!\d))" # minglik ajratgich joyi
r"(?>a+)b", r"a++b" # orqaga qaytmaslik
m.lastgroup # tokenizatorda token turiQoidalar
lookaround pozitsiyani tekshiradi, belgini olmaydi
lookbehind — qat'iy uzunlik
raqamli naqsh atrofida (?<![0-9]) ... (?![0-9])
ichma-ich miqdor (a+)+ — xavfli
kirish uzunligini cheklang
tokenizator oxirida XATO guruhi4. Batafsil misollar
Misol 1 — Lookahead va lookbehind
r"""Ijobiy va salbiy lookahead/lookbehind; minglik ajratgich; lookbehind cheklovi; parol siyosati — naqsh va aniq xabarlar."""
import re
def main() -> None:
print("=== 1. To'rt xil qarash ===")
matn = "12 so'm, 5 dona, 300 so'm, $40, 50$"
print(f" \\d+(?= so'm) → {re.findall(r"\d+(?= so'm)", matn)}")
print(f" \\b\\d+\\b(?! so'm) → {re.findall(r"\b\d+\b(?! so'm)", matn)}")
print(f" (?<=\\$)\\d+ → {re.findall(r'(?<=\$)\d+', matn)}")
print(f" (?<![$\\d])\\d+(?!\\d)(?=\\$) → {re.findall(r'(?<![$\d])\d+(?!\d)(?=\$)', matn)}")
print(" ⭐ kontekst tekshirildi, lekin natijaga kirmadi")
print("\n=== 2. Minglik ajratgich ===")
for son in ("1234567", "1000", "999", "12345678.905"):
butun, _, qoldiq = son.partition(".")
ajratilgan = re.sub(r"(?<=\d)(?=(?:\d{3})+$)", " ", butun)
print(f" {son:>13} → {ajratilgan}{'.' + qoldiq if qoldiq else ''}")
print("\n=== 3. ⚠️ Lookbehind cheklovi ===")
for naqsh in (r"(?<=\d+)x", r"(?<=ab|xyz)c"):
try:
re.compile(naqsh)
except re.error as xato:
print(f" {naqsh:14} → {type(xato).__name__}: {xato}")
print(f" (?:(?<=ab)|(?<=xyz))c → {re.findall(r'(?:(?<=ab)|(?<=xyz))c', 'abc xyzc qc')}")
print("\n=== 4. Parol siyosati: bitta naqsh ===")
PAROL = re.compile(r"(?=.*[a-z])(?=.*[A-Z])(?=.*[0-9])(?=.*[^\w\s]).{8,}")
parollar = ["Salom123!", "salom123!", "Sal1!", "SalomDunyo1", "SALOM 123 !a"]
for parol in parollar:
print(f" {parol!r:15} → {'✅' if PAROL.fullmatch(parol) else '❌'}")
print("\n=== 5. Parol siyosati: aniq xabarlar ===")
QOIDALAR = [
(re.compile(r"[a-z]"), "kichik harf"),
(re.compile(r"[A-Z]"), "katta harf"),
(re.compile(r"[0-9]"), "raqam"),
(re.compile(r"[^\w\s]"), "maxsus belgi"),
]
for parol in parollar:
yetishmaydi = [nom for naqsh, nom in QOIDALAR if not naqsh.search(parol)]
if len(parol) < 8:
yetishmaydi.append("kamida 8 belgi")
print(f" {parol!r:15} → {', '.join(yetishmaydi) or 'hammasi joyida'}")
print(" ⭐ foydalanuvchiga nima yetishmayotganini aytish — bitta naqshdan foydaliroq")
if __name__ == "__main__":
main()Natijaning muhim qismi:
=== 1. To'rt xil qarash ===
\d+(?= so'm) → ['12', '300']
\b\d+\b(?! so'm) → ['5', '40', '50']
(?<=\$)\d+ → ['40']
(?<![$\d])\d+(?!\d)(?=\$) → ['50']
⭐ kontekst tekshirildi, lekin natijaga kirmadi
=== 2. Minglik ajratgich ===
1234567 → 1 234 567
1000 → 1 000
999 → 999
12345678.905 → 12 345 678.905
=== 3. ⚠️ Lookbehind cheklovi ===
(?<=\d+)x → PatternError: look-behind requires fixed-width pattern
(?<=ab|xyz)c → PatternError: look-behind requires fixed-width pattern
(?:(?<=ab)|(?<=xyz))c → ['c', 'c']
=== 4. Parol siyosati: bitta naqsh ===
'Salom123!' → ✅
'salom123!' → ❌
'Sal1!' → ❌
'SalomDunyo1' → ❌
'SALOM 123 !a' → ✅
=== 5. Parol siyosati: aniq xabarlar ===
'Salom123!' → hammasi joyida
'salom123!' → katta harf
'Sal1!' → kamida 8 belgi
'SalomDunyo1' → maxsus belgi
'SALOM 123 !a' → hammasi joyida
⭐ foydalanuvchiga nima yetishmayotganini aytish — bitta naqshdan foydaliroqNima ko'rsatdi: 2.1, 2.2, 2.3-bo'limlar.
Misol 2 — Amaliy naqshlar va chegara tuzoqlari
r"""IPv4, URL, telefon va email naqshlari: sodda va tuzatilgan variantlar; chegara tuzoqlari; sinov jadvali; ipaddress va urllib bilan solishtirish."""
import ipaddress
import re
from urllib.parse import urlsplit
OKTET = r"(?:25[0-5]|2[0-4][0-9]|1[0-9]{2}|[1-9]?[0-9])"
IP_SODDA = re.compile(r"(?:\d{1,3}\.){3}\d{1,3}")
IP_OKTET = re.compile(rf"{OKTET}(?:\.{OKTET}){{3}}")
IP_TOGRI = re.compile(rf"(?<![0-9.]){OKTET}(?:\.{OKTET}){{3}}(?![0-9]|\.[0-9])")
TELEFON = re.compile(
r"""
(?<![0-9])
(?:\+?998[\s-]?)?
\(?(?P<kod>[0-9]{2})\)?[\s-]?
(?P<a>[0-9]{3})[\s-]?
(?P<b>[0-9]{2})[\s-]?
(?P<c>[0-9]{2})
(?![0-9])
""",
re.VERBOSE,
)
URL = re.compile(r"https?://[^\s<>\"']+")
EMAIL = re.compile(r"(?<![\w.+-])[\w.+-]+@[\w-]+(?:\.[\w-]+)*\.[A-Za-z]{2,}(?![\w-])")
def main() -> None:
print("=== 1. IPv4: uch bosqich ===")
matn = "10.0.0.1 999.1.1.1 256.1.1.1 192.168.1.255 1.2.3.4.5"
print(f" sodda: {IP_SODDA.findall(matn)}")
print(f" oktet bilan: {IP_OKTET.findall(matn)} ← 256 dan '56' olindi")
print(f" chegara bilan: {IP_TOGRI.findall(matn)}")
tekshiruv = [s for s in matn.split() if s.count(".") == 3]
ipaddress_natija = []
for s in tekshiruv:
try:
ipaddress.IPv4Address(s)
ipaddress_natija.append(s)
except ValueError:
pass
print(f" ipaddress bilan mos: {ipaddress_natija == [s for s in tekshiruv if IP_TOGRI.fullmatch(s)]}")
print("\n=== 2. Telefon: me'yorlash ===")
for kirish in ("+998 90 123 45 67", "998901234567", "(90) 123-45-67", "90 123 45 67",
"+998-91-123-45-678", "karta 8600123456789012"):
m = TELEFON.search(kirish)
natija = f"+998{m['kod']}{m['a']}{m['b']}{m['c']}" if m else "—"
print(f" {kirish!r:24} → {natija}")
print("\n=== 3. URL: oxiridagi tinish belgilari ===")
matn = "Sayt: https://wisar.uz/kurs?id=5), yana http://x.io. va (https://a.uz/b)."
xom = URL.findall(matn)
tozalangan = [u.rstrip(".,;:!?)") for u in xom]
print(f" xom: {xom}")
print(f" tozalangan: {tozalangan}")
qismlar = urlsplit(tozalangan[0])
print(f" urlsplit: scheme={qismlar.scheme!r}, netloc={qismlar.netloc!r}, path={qismlar.path!r}, query={qismlar.query!r}")
print(" ⭐ URL qismlari uchun regex emas, urllib.parse")
print("\n=== 4. Email: amaliy naqsh ===")
sinovlar = {
"aziz@wisar.uz": True,
"Aziz.K+kurs@mail.co.uz": True,
"a@b": False,
"aziz@@wisar.uz": False,
"aziz@wisar.uz.": True,
"@wisar.uz": False,
}
for kirish, kutilgan in sinovlar.items():
topildi = EMAIL.search(kirish)
natija = topildi[0] if topildi else None
belgi = "✅" if (natija is not None) == kutilgan else "❌"
print(f" {belgi} {kirish!r:26} → {natija!r}")
print(" ⚠️ naqsh shaklni tekshiradi; manzil mavjudligini faqat tasdiqlash xati isbotlaydi")
if __name__ == "__main__":
main()Natijaning muhim qismi:
=== 1. IPv4: uch bosqich ===
sodda: ['10.0.0.1', '999.1.1.1', '256.1.1.1', '192.168.1.255', '1.2.3.4']
oktet bilan: ['10.0.0.1', '99.1.1.1', '56.1.1.1', '192.168.1.255', '1.2.3.4'] ← 256 dan '56' olindi
chegara bilan: ['10.0.0.1', '192.168.1.255']
ipaddress bilan mos: True
=== 2. Telefon: me'yorlash ===
'+998 90 123 45 67' → +998901234567
'998901234567' → +998901234567
'(90) 123-45-67' → +998901234567
'90 123 45 67' → +998901234567
'+998-91-123-45-678' → —
'karta 8600123456789012' → —
=== 3. URL: oxiridagi tinish belgilari ===
xom: ['https://wisar.uz/kurs?id=5),', 'http://x.io.', 'https://a.uz/b).']
tozalangan: ['https://wisar.uz/kurs?id=5', 'http://x.io', 'https://a.uz/b']
urlsplit: scheme='https', netloc='wisar.uz', path='/kurs', query='id=5'
⭐ URL qismlari uchun regex emas, urllib.parse
=== 4. Email: amaliy naqsh ===
✅ 'aziz@wisar.uz' → 'aziz@wisar.uz'
✅ 'Aziz.K+kurs@mail.co.uz' → 'Aziz.K+kurs@mail.co.uz'
✅ 'a@b' → None
✅ 'aziz@@wisar.uz' → None
✅ 'aziz@wisar.uz.' → 'aziz@wisar.uz'
✅ '@wisar.uz' → None
⚠️ naqsh shaklni tekshiradi; manzil mavjudligini faqat tasdiqlash xati isbotlaydiNima ko'rsatdi: 2.4, 2.9-bo'limlar.
Misol 3 — Katastrofik backtracking
r"""Eksponensial o'sishni o'lchash; atomik guruh va possessiv miqdor bilan tuzatish; naqshni qayta yozish; kirish uzunligini cheklash."""
import re
import time
def olchov(naqsh: re.Pattern[str], matn: str) -> tuple[float, bool]:
bosh = time.perf_counter()
natija = naqsh.fullmatch(matn)
return time.perf_counter() - bosh, natija is not None
def main() -> None:
XAVFLI = re.compile(r"(a+)+")
ATOMIK = re.compile(r"(?>a+)+")
POSSESSIV = re.compile(r"(?:a++)+")
SODDA = re.compile(r"a+")
print("=== 1. ⚠️ (a+)+ — deyarli mos keladigan satr ===")
vaqtlar = {}
for n in (16, 18, 20, 22):
vaqt, mos = olchov(XAVFLI, "a" * n + "!")
vaqtlar[n] = vaqt
print(f" n={n}: mos={mos}")
print(f" n 16 → 22 (+6 belgi), vaqt kamida 20 barobar oshdi: {vaqtlar[22] / vaqtlar[16] >= 20}")
print(f" mos keladigan satrda esa tez: {olchov(XAVFLI, 'a' * 22)[0] < 0.01}")
print(" ⭐ yaxshi test ma'lumoti muammoni yashiradi")
print("\n=== 2. Tuzatishlar ===")
matn = "a" * 22 + "!"
for nom, naqsh in (("atomik (?>a+)+", ATOMIK), ("possessiv (?:a++)+", POSSESSIV), ("sodda a+", SODDA)):
vaqt, mos = olchov(naqsh, matn)
print(f" {nom:20} mos={mos}, 10 ms dan tez: {vaqt < 0.01}")
print(f" natijalar bir xil (mos kelmaydi): {not XAVFLI.fullmatch('a' * 10 + '!') and not SODDA.fullmatch('a' * 10 + '!')}")
print("\n=== 3. ⚠️ Possessiv miqdor ma'noni o'zgartirishi mumkin ===")
print(f" a*a 'aaa' da: {re.fullmatch(r'a*a', 'aaa') is not None}")
print(f" a*+a 'aaa' da: {re.fullmatch(r'a*+a', 'aaa') is not None} ← a*+ oxirgi 'a' ni qaytarmadi")
print("\n=== 4. Real shakl: so'zlar ro'yxati ===")
XAVFLI_SOZLAR = re.compile(r"(?:\w+\s?)+:")
XAVFSIZ_SOZLAR = re.compile(r"\w+(?:\s\w+)*:")
matn = "salom dunyo " + "x" * 14 + "!" # ⚠️ har qo'shimcha belgi vaqtni ~2 barobar oshiradi
t1, _ = olchov(XAVFLI_SOZLAR, matn)
t2, _ = olchov(XAVFSIZ_SOZLAR, matn)
print(f" (?:\\w+\\s?)+: sekin: {t1 > 0.05}")
print(f" \\w+(?:\\s\\w+)*: 10 ms dan tez: {t2 < 0.01}")
print(f" ikkalasi mos keladigan satrda bir xil: "
f"{bool(XAVFLI_SOZLAR.fullmatch('salom dunyo:')) == bool(XAVFSIZ_SOZLAR.fullmatch('salom dunyo:'))}")
print(" ⭐ ixtiyoriy ajratgich (\\s?) o'rniga aniq tuzilma: so'z (bo'shliq so'z)*")
print("\n=== 5. Kirish uzunligini cheklash ===")
MAKS = 200
def xavfsiz_tekshir(naqsh: re.Pattern[str], matn: str) -> str:
if len(matn) > MAKS:
return f"rad etildi: {len(matn)} > {MAKS} belgi"
return "mos" if naqsh.fullmatch(matn) else "mos emas"
print(f" {xavfsiz_tekshir(XAVFSIZ_SOZLAR, 'salom dunyo:')}")
print(f" {xavfsiz_tekshir(XAVFSIZ_SOZLAR, 'a ' * 500)}")
print(" ⭐ re da timeout yo'q — uzunlik chegarasi eng ishonchli himoya")
if __name__ == "__main__":
main()Natijaning muhim qismi:
=== 1. ⚠️ (a+)+ — deyarli mos keladigan satr ===
n=16: mos=False
n=18: mos=False
n=20: mos=False
n=22: mos=False
n 16 → 22 (+6 belgi), vaqt kamida 20 barobar oshdi: True
mos keladigan satrda esa tez: True
⭐ yaxshi test ma'lumoti muammoni yashiradi
=== 2. Tuzatishlar ===
atomik (?>a+)+ mos=False, 10 ms dan tez: True
possessiv (?:a++)+ mos=False, 10 ms dan tez: True
sodda a+ mos=False, 10 ms dan tez: True
natijalar bir xil (mos kelmaydi): True
=== 3. ⚠️ Possessiv miqdor ma'noni o'zgartirishi mumkin ===
a*a 'aaa' da: True
a*+a 'aaa' da: False ← a*+ oxirgi 'a' ni qaytarmadi
=== 4. Real shakl: so'zlar ro'yxati ===
(?:\w+\s?)+: sekin: True
\w+(?:\s\w+)*: 10 ms dan tez: True
ikkalasi mos keladigan satrda bir xil: True
⭐ ixtiyoriy ajratgich (\s?) o'rniga aniq tuzilma: so'z (bo'shliq so'z)*
=== 5. Kirish uzunligini cheklash ===
mos
rad etildi: 1000 > 200 belgi
⭐ re da timeout yo'q — uzunlik chegarasi eng ishonchli himoyaNima ko'rsatdi: 2.5, 2.6-bo'limlar.
Misol 4 — Amaliy: kichik hisoblash tili
Regexning eng kuchli qo'llanishi — tokenizator. Kichik til yozamiz: o'zgaruvchilar, + - * /, qavslar va ^ (daraja). Regex matnni tokenlarga ajratadi (qator va ustun raqami bilan), qolganini — ustuvorlik va qavslarni — oddiy rekursiv tahlilchi bajaradi. Bu 15.1-darsdagi "regex — leksika, parser — sintaksis" tamoyilining amaldagi ko'rinishi.
"""Nomli guruhli tokenizator; qator/ustun kuzatuvi; xatolarni joyi bilan ko'rsatish; rekursiv tahlilchi va hisoblovchi."""
import re
from dataclasses import dataclass
TOKEN = re.compile(
r"""
(?P<SON>\d+(?:\.\d+)?)
| (?P<NOM>[A-Za-z_]\w*)
| (?P<OP>\*\*|[-+*/^()=])
| (?P<QATOR>\n)
| (?P<BOSHLIQ>[ \t]+)
| (?P<IZOH>\#[^\n]*)
| (?P<XATO>.)
""",
re.VERBOSE,
)
@dataclass(frozen=True, slots=True)
class Token:
tur: str
qiymat: str
qator: int
ustun: int
class TilXatosi(Exception):
pass
def korinish(t: Token) -> str:
return {"OXIR": "matn oxiri", "QATOR": "qator oxiri"}.get(t.tur, repr(t.qiymat))
def tokenlarga_ajrat(kod: str) -> list[Token]:
tokenlar, qator, qator_boshi = [], 1, 0
for m in TOKEN.finditer(kod):
tur, ustun = m.lastgroup, m.start() - qator_boshi + 1
assert tur is not None
if tur == "QATOR":
tokenlar.append(Token("QATOR", "", qator, ustun))
qator, qator_boshi = qator + 1, m.end()
elif tur == "XATO":
raise TilXatosi(f"{qator}:{ustun}: noma'lum belgi {m[0]!r}")
elif tur not in ("BOSHLIQ", "IZOH"):
qiymat = "^" if m[0] == "**" else m[0]
tokenlar.append(Token(tur, qiymat, qator, ustun))
tokenlar.append(Token("OXIR", "", qator, len(kod) - qator_boshi + 1))
return tokenlar
class Hisoblovchi:
def __init__(self) -> None:
self.xotira: dict[str, float] = {}
def bajar(self, kod: str) -> list[float]:
self.tokenlar, self.i, natijalar = tokenlarga_ajrat(kod), 0, []
while self.joriy.tur != "OXIR":
if self.joriy.tur == "QATOR":
self.i += 1
continue
natijalar.append(self.ifoda_qatori())
return natijalar
@property
def joriy(self) -> Token:
return self.tokenlar[self.i]
def ol(self, tur: str, qiymat: str | None = None) -> Token:
t = self.joriy
if t.tur != tur or (qiymat is not None and t.qiymat != qiymat):
kutilgan = qiymat or tur
raise TilXatosi(f"{t.qator}:{t.ustun}: {kutilgan!r} kutilgan, {korinish(t)} keldi")
self.i += 1
return t
def ifoda_qatori(self) -> float:
if self.joriy.tur == "NOM" and self.tokenlar[self.i + 1].qiymat == "=":
nom = self.ol("NOM").qiymat
self.ol("OP", "=")
self.xotira[nom] = self.qoshish()
return self.xotira[nom]
return self.qoshish()
def qoshish(self) -> float:
natija = self.kopaytirish()
while self.joriy.qiymat in ("+", "-"):
op = self.ol("OP").qiymat
natija = natija + self.kopaytirish() if op == "+" else natija - self.kopaytirish()
return natija
def kopaytirish(self) -> float:
natija = self.daraja()
while self.joriy.qiymat in ("*", "/"):
t = self.ol("OP")
ong = self.daraja()
if t.qiymat == "/" and ong == 0:
raise TilXatosi(f"{t.qator}:{t.ustun}: nolga bo'lish")
natija = natija * ong if t.qiymat == "*" else natija / ong
return natija
def daraja(self) -> float:
asos = self.birlik()
if self.joriy.qiymat == "^":
self.ol("OP")
return asos ** self.daraja() # o'ngdan chapga: 2^3^2 = 2^9
return asos
def birlik(self) -> float:
t = self.joriy
if t.qiymat == "-":
self.ol("OP")
return -self.birlik()
if t.tur == "SON":
return float(self.ol("SON").qiymat)
if t.tur == "NOM":
nom = self.ol("NOM").qiymat
if nom not in self.xotira:
raise TilXatosi(f"{t.qator}:{t.ustun}: {nom!r} aniqlanmagan")
return self.xotira[nom]
if t.qiymat == "(":
self.ol("OP", "(")
natija = self.qoshish()
self.ol("OP", ")")
return natija
raise TilXatosi(f"{t.qator}:{t.ustun}: kutilmagan {korinish(t)}")
def main() -> None:
print("=== 1. Tokenlar ===")
for t in tokenlarga_ajrat("narx = 12.5 * (soni + 2) # izoh")[:8]:
print(f" {t.qator}:{t.ustun:<3} {t.tur:5} {t.qiymat!r}")
print("\n=== 2. Dastur ===")
dastur = """\
narx = 45000
soni = 3
chegirma = 0.1
jami = narx * soni * (1 - chegirma)
2 ^ 3 ^ 2
-(2 + 3) * 4 ** 2
"""
hisob = Hisoblovchi()
for qator, natija in zip(dastur.splitlines(), hisob.bajar(dastur)):
print(f" {qator:38} → {natija:g}")
print(f" xotira: {hisob.xotira}")
print("\n=== 3. Xatolar joyi bilan ===")
for kod in ("x = 5 $ 2", "y = (1 + 2", "3 / (2 - 2)", "a + 1", "narx = * 3"):
try:
Hisoblovchi().bajar(kod)
except TilXatosi as xato:
print(f" {kod!r:14} → {xato}")
print("\n=== 4. Ko'p qatorli xato ===")
try:
Hisoblovchi().bajar("a = 1\nb = a +\nc = 3")
except TilXatosi as xato:
print(f" {xato}")
print(" ⭐ regex — tokenlar va joylar; tuzilma — tahlilchi")
if __name__ == "__main__":
main()Natijaning muhim qismi:
=== 1. Tokenlar ===
1:1 NOM 'narx'
1:6 OP '='
1:8 SON '12.5'
1:13 OP '*'
1:15 OP '('
1:16 NOM 'soni'
1:21 OP '+'
1:23 SON '2'
=== 2. Dastur ===
narx = 45000 → 45000
soni = 3 → 3
chegirma = 0.1 → 0.1
jami = narx * soni * (1 - chegirma) → 121500
2 ^ 3 ^ 2 → 512
-(2 + 3) * 4 ** 2 → -80
xotira: {'narx': 45000.0, 'soni': 3.0, 'chegirma': 0.1, 'jami': 121500.0}
=== 3. Xatolar joyi bilan ===
'x = 5 $ 2' → 1:7: noma'lum belgi '$'
'y = (1 + 2' → 1:11: ')' kutilgan, matn oxiri keldi
'3 / (2 - 2)' → 1:3: nolga bo'lish
'a + 1' → 1:1: 'a' aniqlanmagan
'narx = * 3' → 1:8: kutilmagan '*'
=== 4. Ko'p qatorli xato ===
2:8: kutilmagan qator oxiri
⭐ regex — tokenlar va joylar; tuzilma — tahlilchiNima ko'rsatdi: 2.8-bo'lim.
5. To'g'ri va noto'g'ri tushunishlar
| Noto'g'ri fikr | To'g'risi |
|---|---|
| "Lookahead topilgan narsani natijaga qo'shadi" | Faqat pozitsiyani tekshiradi |
| "Lookbehind istalgan naqsh bo'lishi mumkin" | re da faqat qat'iy uzunlik |
"\b raqamli naqshni to'liq chegaralaydi" |
Raqamlar orasida chegara yo'q |
| "Internetdan olingan email regex to'g'ri" | Ko'pi ortiqcha yoki kam o'tkazadi |
| "Sekin regex — biroz sekin" | Eksponensial — soniyalar va daqiqalar |
| "Testlar o'tsa, naqsh xavfsiz" | Muammo "deyarli mos" satrlarda chiqadi |
| "Possessiv miqdor faqat tezlashtiradi" | Ma'noni ham o'zgartirishi mumkin |
| "Regex bilan istalgan tilni tahlil qilish mumkin" | Tokenlar — ha; tuzilma — parser |
6. Keng tarqalgan xatolar va yechimlari
1. Raqamli naqsh atrofida chegara yo'q
re.findall(r"[0-9]{9}", "8600123456789012") # ❌ karta ichidan "telefon"
re.findall(r"(?<![0-9])[0-9]{9}(?![0-9])", s) # ✅2. Ichma-ich miqdorlar
re.compile(r"(\w+\s?)+$") # ❌ ReDoS
re.compile(r"\w+(?:\s\w+)*$") # ✅3. Uzunlik chegarasisiz foydalanuvchi kiritishi
NAQSH.fullmatch(request.body) # ❌
if len(s) <= 1000 and NAQSH.fullmatch(s): ... # ✅4. O'zgaruvchan uzunlikdagi lookbehind
r"(?<=USD|EUR |so'm )\d+" # ❌ PatternError
r"(?:(?<=USD)|(?<=EUR )|(?<=so'm ))\d+" # ✅5. URL oxiridagi tinish belgisi
URL.findall("sayt: https://wisar.uz.") # ['https://wisar.uz.']
[u.rstrip(".,;:!?)") for u in URL.findall(s)] # ✅6. Tokenizatorda XATO guruhi yo'q
re.findall(r"\d+|[a-z]+|[-+*/]", "2 $ 3") # ❌ '$' jim tashlandi
# ✅ oxirida (?P<XATO>.) va xato ko'tarish7. Foydalanuvchi naqshini re bilan bajarish
re.search(foydalanuvchi_naqshi, matn) # ❌ ReDoS
# ✅ re.escape (oddiy qidiruv) yoki google-re28. Regex bilan IP/URL/sanani to'liq tekshirish
IP.fullmatch(s) # ⚠️ faqat shakl
ipaddress.ip_address(s) # ✅ IPv4 va IPv67. Integratsiya — bu bilim qayerda kerak bo'ladi
- 15.1–15.2-darslar (o'tilgan): naqsh tili, guruhlar
- 15.4-dars:
datetime.strptime— sanalarni regexsiz tekshirish - 16-qism: fayl formatlari uchun parserlar
- 17.10-dars:
hypothesisbilan naqshlarni tasodifiy ma'lumotda sinash - 20.5-dars: Pydantic modellari — kiritishni tekshirish va uzunlik chegaralari
- 20.4-dars: route va parametrlar
- 27.5-dars: xulq-atvor naqshlari — Interpreter naqshi va tokenizator
8. Eng yaxshi amaliyotlar
Raqamli naqshlarni
(?<![0-9])va(?![0-9])bilan chegaralang.Har naqsh uchun "o'tishi" va "o'tmasligi" kerak bo'lgan sinovlar yozing — chegaradagi holatlar bilan.
Ichma-ich miqdorlardan va bir-birini qoplaydigan muqobillardan qoching.
Foydalanuvchi kiritishining uzunligini cheklang.
Maxsus modullar bor joyda — ularni ishlating:
ipaddress,urllib.parse,datetime,email.utils.Murakkab qoidalarni bitta naqshga tiqmang — alohida tekshiruv va aniq xabarlar.
Tokenizatorda nomli guruhlar,
lastgroupvaXATOguruhi.Xato xabarida joyni ko'rsating — qator va ustun.
9. Amaliy topshiriq
Vazifa 1: Natijani bashorat qiling
import re
1. print(re.findall(r"\w+(?=!)", "salom! dunyo"))
2. print(re.findall(r"\b\w+\b(?!!)", "salom! dunyo"))
3. print(re.findall(r"(?<=#)\w+", "#python va #rust"))
4. print(re.findall(r"(?<!#)\b\w+", "#python va #rust"))
5. print(re.sub(r"(?<=\d)(?=(?:\d{3})+$)", ",", "1000000"))
6. print(bool(re.fullmatch(r"(?=.*\d).{4,}", "abcd")))
7. print(re.fullmatch(r"a*+a", "aa"))
8. print(bool(re.fullmatch(r"(?>a*)b", "aab")))
9. print(re.findall(r"[0-9]{3}", "12345"))
10. print(re.findall(r"(?<![0-9])[0-9]{3}(?![0-9])", "123 12345"))
11. print(bool(re.fullmatch(r"(\()?\d+(?(1)\))", "(42")))
12. print(re.findall(rb"[a-z]+", b"abc 12 de"))Javoblar
['salom']['dunyo']—salomdan keyin!bor['python', 'rust']['va']1,000,000False— raqam yo'qNone—a*+hammasini oldiTrue—buchun qaytish kerak emas['123']['123']False—(bor,)yo'q[b'abc', b'de']
Vazifa 2: Xatolarni tuzating
1. KARTA = re.compile(r"[0-9]{16}") # 20 xonali son ichidan ham topadi
2. NARX = re.compile(r"(?<=so'm |USD )\d+")
3. SOZLAR = re.compile(r"^(\w+\s*)+$") # uzun matnda osilib qoladi
4. def email_bormi(s):
return re.search(r"\S+@\S+", s) is not None # "a@b" va "x@@y" ham o'tadi
5. TOKEN = re.compile(r"\d+|[a-z]+|[-+*/]")
def tokenlar(kod):
return TOKEN.findall(kod) # noma'lum belgilar yo'qolib ketadiJavoblar
1. KARTA = re.compile(r"(?<![0-9])[0-9]{16}(?![0-9])")
2. NARX = re.compile(r"(?:(?<=so'm )|(?<=USD ))\d+")
3. SOZLAR = re.compile(r"\w+(?:\s+\w+)*\s*") # fullmatch bilan; va uzunlik chegarasi
4. EMAIL = re.compile(r"[\w.+-]+@[\w-]+(?:\.[\w-]+)*\.[A-Za-z]{2,}")
def email_bormi(s):
return len(s) <= 254 and EMAIL.fullmatch(s) is not None
5. TOKEN = re.compile(r"(?P<SON>\d+)|(?P<NOM>[a-z]+)|(?P<OP>[-+*/])|(?P<BOSH>\s+)|(?P<XATO>.)")
def tokenlar(kod):
natija = []
for m in TOKEN.finditer(kod):
if m.lastgroup == "XATO":
raise ValueError(f"{m.start()}: noma'lum belgi {m[0]!r}")
if m.lastgroup != "BOSH":
natija.append((m.lastgroup, m[0]))
return natijaVazifa 3: ReDoS ovchisi
- Kamida 8 ta naqsh to'plang (internet, loyihalar, o'zingiz yozgan)
- Har biri uchun "deyarli mos keladigan" satrlar generatori yozing (
n= 10, 15, 20, 25) - Vaqt o'sishini o'lchang: chiziqli, polinomial yoki eksponensial
- Xavfli naqshlarni atomik guruh yoki qayta yozish bilan tuzating
- Tuzatilgan naqsh eski naqsh bilan bir xil satrlarni qabul qilishini 1000 ta tasodifiy satrda tekshiring
Vazifa 4: O'zbek matni uchun naqshlar to'plami
Modul yozing (uzb_naqshlar.py):
- Telefon (barcha keng tarqalgan shakllar) →
+998XXXXXXXXX - Avtomobil davlat raqami (
01 A 123 AA,01 123 AAA) - Pasport seriyasi va raqami (
AA 1234567) - STIR (INN, 9 raqam) — atrofida raqam bo'lmasin
- Har naqsh uchun 10 ta ijobiy va 10 ta salbiy sinov, bitta
pytestfayli (17-qism)
Vazifa 5: Tokenizatorni kengaytiring
Misol 4 dagi tilga qo'shing:
- Satrlar:
"salom"(ichida\"ekranlash bilan) - Funksiyalar:
sqrt(x),max(a, b)— vergul tokeni - Taqqoslash:
==,!=,<=,>=,<,>— uzunroq operatorlar oldinda - Izoh ichidagi
#va satr ichidagi#farqlansin - Har yangi token uchun joyi to'g'ri ko'rsatilgan xato misoli
Vazifa 6: Matndan ma'lumot ajratuvchi
E'lonlar matnidan (kamida 30 ta real e'lon) ajrating:
- Narx:
12 000 000 so'm,$450,450 dollar,1,2 mln→ so'mdagi son - Telefon raqamlari
- Xonalar soni:
3 xonali,3-xonali,uch xonali - Maydon:
75 m²,75 kv.m - Natijani jadvalda ko'rsating va xato ajratilgan holatlarni tahlil qiling
Vazifa 7: O'ylash
Python'ning re moduli, Perl, Java va JavaScript regex dvigatellari backtracking asosida ishlaydi. Google'ning RE2, Rust'ning regex kutubxonasi va Go'ning regexp paketi esa chiziqli vaqtni kafolatlaydi, lekin backreference va lookaround ni qo'llab-quvvatlamaydi. Nega bunday kelishuv bor va qaysi holatda qaysi dvigatelni tanlash kerak?
Javob
Qisqa javob: Chiziqli vaqt faqat muntazam tillar nazariyasi doirasida kafolatlanadi — naqsh cheklangan avtomatga (DFA/NFA simulyatsiyasi) aylantiriladi. Backreference va lookaround bu doiradan chiqadi: ular "avval nima topilgan" yoki "oldinda nima bor" degan qo'shimcha xotirani talab qiladi va backtracking ga olib keladi. Shuning uchun kelishuv: kuchli til yoki vaqt kafolati.
1. Ikki xil dvigatel
Backtracking (re, PCRE, Java, JS) |
Avtomat (RE2, Rust regex, Go) |
|
|---|---|---|
| Algoritm | Chuqurlikka qidiruv, orqaga qaytish | Thompson NFA / DFA simulyatsiyasi |
| Eng yomon vaqt | Eksponensial | O(n · m) — chiziqli |
Backreference \1 |
||
| Lookaround | (ba'zilari cheklangan) | |
| Atomik guruh, possessiv | Kerak emas | |
| Xotira | Kam | DFA holatlari ko'p bo'lishi mumkin |
2. Nega backreference chiziqli bo'la olmaydi
(\w+) \1 — "bir xil so'z ikki marta" — muntazam til emas (15.1-dars, Vazifa 7). Uni tanish uchun topilgan so'zni eslab qolish kerak, cheklangan avtomatda esa bunday xotira yo'q. Umumiy holda backreference bilan moslik muammosi NP-to'liq.
3. Thompson algoritmi
- Naqsh NFA ga aylantiriladi
- Matn bir marta chapdan o'ngga o'qiladi
- Har qadamda barcha mumkin bo'lgan holatlar to'plami bir vaqtda kuzatiladi — orqaga qaytish yo'q
- Holatlar soni naqsh uzunligi bilan chegaralangan → har belgi
O(m)→ jamiO(n·m)
4. Qaysi holatda nimani tanlash
| Vaziyat | Tanlov |
|---|---|
| Naqshni dasturchi yozadi, kirish cheklangan | re — qulay va kuchli |
| Foydalanuvchi naqsh kiritadi (qidiruv, filtr, qoida) | RE2 (google-re2) |
| Katta hajmdagi jurnallar/oqimlar | RE2 / Rust regex — bashorat qilinadigan tezlik |
| WAF, xavfsizlik qoidalari | Chiziqli dvigatel (Cloudflare hodisasidan keyin shunday qilingan) |
| Backreference yoki lookaround shart | re + uzunlik chegarasi + sinovlar |
5. Amaliy himoya re bilan qolganda
- Kirish uzunligini cheklash
- Ichma-ich miqdorlardan qochish, atomik guruhlar
- Naqshlarni "deyarli mos" satrlar bilan vaqt bo'yicha sinash (Vazifa 3)
- Og'ir tekshiruvni alohida jarayonda muddat bilan bajarish (14.5-dars)
6. Xulosa
- Kelishuv nazariyadan kelib chiqadi: muntazam tillar — chiziqli, qo'shimcha xotira — backtracking
requlay, lekin eng yomon holatda eksponensial- Foydalanuvchi naqshlari va xavfsizlik qoidalari — chiziqli dvigatel
- O'zingiz yozgan naqshlar —
re, lekin cheklov va sinovlar bilan
Nimani mustahkamlaydi: 2.1–2.9-bo'limlar.
Xulosa
Bu darsda muntazam ifodalarni real vazifalarda ishlatishni va ularning xavfli tomonlarini o'rgandik.
Eng muhim uch fikr:
Lookaround va chegaralar — aniqlik kaliti.
(?=...),(?!...),(?<=...),(?<!...)kontekstni tekshiradi, lekin natijaga qo'shmaydi; bir nechta lookahead ketma-ket — mantiqiy "VA".reda lookbehind faqat qat'iy uzunlikda. Raqamli naqshlar(?<![0-9])...(?![0-9])bilan chegaralanmasa,256.1.1.1ichidan56.1.1.1, karta raqami ichidan "telefon" topiladi. IP, URL va sanalar uchun esaipaddress,urllib.parsevadatetimeishonchliroq.Backtracking eksponensial bo'lishi mumkin.
(a+)+kabi ichma-ich miqdorlar va bir-birini qoplaydigan muqobillar "deyarli mos keladigan" satrlarda har bir qo'shimcha belgi bilan vaqtni ko'paytiradi — misolda 6 ta belgi vaqtni o'nlab barobar oshirdi. Himoya: naqshni qayta yozish, atomik guruh(?>...)yoki possessiv miqdor (3.11+), kirish uzunligini cheklash; foydalanuvchi naqshlari uchun — chiziqli vaqtli dvigatel.Regexning eng kuchli joyi — tokenizator. Nomli guruhlar,
finditer,lastgroupva oxiridagiXATOguruhi bilan matn joyi ko'rsatilgan tokenlarga ajratiladi; tuzilmani (ustuvorlik, qavslar) esa oddiy rekursiv tahlilchi bajaradi. Bu — kompilyatorlar, shablon dvigatellari va konfiguratsiya tillarining asosi.
Keyingi darsda standart kutubxonaning boshqa muhim moduliga o'tamiz: datetime — sanalar, vaqtlar, oraliqlar va ular bilan ishlashdagi tuzoqlar.
Izohlar (0)
Izoh yozish uchun kiring.
- Hozircha izoh yo'q. Birinchi bo'ling!