Reguláris kifejezések Hol alkalmazhatunk reguláris kifejezéseket
Vázlat Hol alkalmazhatunk reguláris kifejezéseket
A reguláris kifejezések minimális nyelve
A reguláris kifejezések b®vített nyelve
Automatás feladatok
Gyakorlati tudnivalók
Reguláris kifejezések Hol alkalmazhatunk reguláris kifejezéseket
Mire jók a reguláris kifejezések A reguláris kifejezések a reguláris nyelvek tömör leírását adják. A reguláris kifejezések egy algoritmussal véges automatává alakítható, ami alapján készíthet® olyan program vagy hardvereszköz, amely ellen®rizni tud egy reguláris kifejezést. Ezzel az algoritmussal nem foglalkozunk, (az megtalálható a Bach-könyvben, illetve az átalakítás gyakorlolható a JFLAP programmal). Mi a reguláris kifejezések létrehozásával fogunk foglalkozni. Az ellen®rzést más tárgyakban rábízzuk a programnyelvek kész eszközeire. A programnyelvek és az XML/HTML fájlok környezetfüggetlen nyelvének szintaktikai elemzése kívül esik a reguláris kifejezések hatókörén.
Reguláris kifejezések Hol alkalmazhatunk reguláris kifejezéseket
Reguláris nyelvek, kifejezések és nyelvtanok ill. véges automaták kapcsolata reguláris kifejezés
reguláris nyelv
reguláris nyelvtan
véges automata
Reguláris kifejezések Hol alkalmazhatunk reguláris kifejezéseket
Reguláris nyelvek, kifejezések és nyelvtanok ill. véges automaták kapcsolata reguláris kifejezés
tömör leírás
reguláris nyelv
szavak halmaza
reguláris nyelvtan
véges automata
levezetési szabályok
állapotgráf
Reguláris kifejezések Hol alkalmazhatunk reguláris kifejezéseket
Hol találkozhatunk reguláris kifejezésekkel? Programnyelvek
Van ahol a programnyelv része:
I perl, awk I JavaScript I PostgreSQL
vagy standard könyvtárában benne van:
I C# I Python
Reguláris kifejezések Hol alkalmazhatunk reguláris kifejezéseket
És még hol találkozunk regexp-el? (regular expression = regexp)
Ezekben kereshetünk /-rel: vim man less Firefox
Parancsok, amelyekben használható: grep sed
A django web-keretrendszer a kapott URL-eket reguláris kifejezésekkel hasonlítja össze, így d®l el, mit csinál, milyen paraméterekkel.
Reguláris kifejezések A reguláris kifejezések minimális nyelve
Vázlat Hol alkalmazhatunk reguláris kifejezéseket
A reguláris kifejezések minimális nyelve
A reguláris kifejezések b®vített nyelve
Automatás feladatok
Gyakorlati tudnivalók
Reguláris kifejezések A reguláris kifejezések minimális nyelve
Az alábbiakban r, r1, r2 egy-egy érvényes reguláris kifejezést jelent. A reguláris kifejezések leírhatóak a következ® pár szabály alkalmazásával: r*
r-b®l 0-ra vagy többre illeszkedik
r1|r2
vagy r1-re, vagy r2-re illeszkedik
(r) r1r2
csoportosítás összef¶zés
Példák: kifejezés ab*a (ab)*a
illeszkedik erre
nem illeszkedik erre
aa aba abbba
ab*a
a aba ababa ababababa
ab*a abab
(a|A)lma
Alma alma
colo(|u)r
color colour
Reguláris kifejezések A reguláris kifejezések minimális nyelve
Feladat
Milyen reguláris kifejezés illik az alábbi szavakra?
I ea ema emma emmma . . . emmmmmmmma . . . A feladatokat követ® dián megoldás következik.
Reguláris kifejezések A reguláris kifejezések minimális nyelve
Megoldás
Milyen reguláris kifejezés illik az alábbi szavakra?
I ea ema emma emmma . . . emmmmmmmma . . . I Legkézenfekv®bb megoldás: em*a
Reguláris kifejezések A reguláris kifejezések minimális nyelve
Feladat
Milyen reguláris kifejezés illik az alábbi szavakra?
I ema emma emmma . . . emmmmmmmma . . . , de ea nem A feladatokat követ® dián megoldás következik.
Reguláris kifejezések A reguláris kifejezések minimális nyelve
Megoldás
I ema emma emmma . . . emmmmmmmma . . . , de ea nem
I Legkézenfekv®bb megoldás: emm*a
Reguláris kifejezések A reguláris kifejezések minimális nyelve
Feladat
Milyen reguláris kifejezés illik az alábbi szavakra?
I alma1 alma2 alma3 emma1 emma2 emma3 A feladatokat követ® dián megoldás következik.
Reguláris kifejezések A reguláris kifejezések minimális nyelve
Megoldás
I alma1 alma2 alma3 emma1 emma2 emma3 I Két viszonylag kézenfekv® megoldás is van: (al|em)ma(1|2|3) (alma|emma)(1|2|3)
vagy
Reguláris kifejezések A reguláris kifejezések minimális nyelve
Jelölésmódok
A Bach Iván könyvben a választás jelölése +. Itt a reguláris kifejezések esetén gyakorlatban is használt | jelölést használjuk. A többi jelölés egyezik az itteniekkel. A reguláris kifejezések gyakorlatában a + jel a *-hoz hasonló, de 1 vagy több el®fordulást jelöl.
Reguláris kifejezések A reguláris kifejezések minimális nyelve
Speciális jelentés levédése
A * és vagy
|
|
jeleknek speciális jeletése van, de néha szükséges, hogy *
jelekre illesszünk. Ilyenkor általában a
\
karaktert illesztjük a
speciális jeletés¶ karakter elé, hasonlóan, mint ahogy az újsort jelöljük a karakterláncok esetén (\n). Az egyes alkalmazások reguláris nyelvei eltérnek abban, hogy a levédett vagy a levédetlen alak jelenti a speciális jelentést. Ezek között az egyik véglet a Python nyelv re modulja, ahol általában a speciális jelentést nem kell levédeni, a másik véglet a Vim és a grep, ahol általában a speciális jelentést kell levédeni.
Reguláris kifejezések A reguláris kifejezések minimális nyelve
A speciális jelentések levédése (folyt.) A * és a . (pont) jelöléseket egyik esetben sem kell levédeni a speciális jelentéshez (és más általam ismert programnyelvben sem). (A . tetsz®leges karakterre illeszkedik.) A * és . karakterekre a és
\\
\.
kifejezés illeszkedik. A
\
\*
(visszaper, backslash) karakterre a
reguláris kifejezés illeszkedik.
Az további példákban a Python jelölésmódját mutatom be, a példamegoldáshoz azt kell tudni, és aszerint kell megoldani a feladatokat. A Python nyelvben a csoportosítás zárójelét nem kell levédeni, a és a
\)
\(
illeszkedik a zárójelekre. Szintén nem kell levédeni a
választás függ®leges vonalát, tehát a
\|
a
|
karakterre illeszkedik.
A jelek, amelyeket le kell védeni, mert speciális jelentésük van
*.|\[]{}+?^$
Reguláris kifejezések A reguláris kifejezések minimális nyelve
Feladat
Hogyan illesztenénk olyan kifejezésre, amely 0 vagy több a-bet¶ után egy *, majd egy vagy több b bet¶ követ?
M
Megoldás jön! Lapozás el®tt próbálja megoldani a feladatot!
Reguláris kifejezések A reguláris kifejezések minimális nyelve
Megoldás
Hogyan illesztenénk olyan kifejezésre, amely 0 vagy több a-bet¶ után egy *, majd egy vagy több b bet¶ követ?
a*\*bb*
vagy
a*\*b+
utóbbi esetben eltér® lehet, hogy a + elé kell-e
\.
Reguláris kifejezések A reguláris kifejezések minimális nyelve
Feladat
Hogyan illeszthetünk olyan kifejezést, amelynél két bináris számjegy után . (pont) majd egy bináris számjegy következik? Pl: 01.1 10.0 11.1
M
Megoldás jön! Lapozás el®tt próbálja megoldani a feladatot!
Reguláris kifejezések A reguláris kifejezések minimális nyelve
Megoldás
Hogyan illeszthetünk olyan kifejezést, amelynél két bináris számjegy után . (pont) majd egy bináris számjegy következik?
(0|1)(0|1)\.(0|1)
Reguláris kifejezések A reguláris kifejezések minimális nyelve
Feladat Melyek illeszkednek az els® reguláris kifejezésekre az azt követ® szavak közül?
Reguláris kifejezések A reguláris kifejezések minimális nyelve
Megoldások Az egyes sorokból a következ®ek helyesek csak:
a.*b accb a..b a.*b a**b a...b a\.*b a...b ab a.b a(ab)*b ab aababb aabababb (0|1|2)*(a|b)* 012ab 210ba (|o|O)buda(|i) buda budai Obuda Obudai obuda \((0|1|2),(2|3)\) (1,3) (2,3) (1,2) Zárthelyiben az el®z®höz hasonló kiválasztásos feladatok esetén a helytelenül aláhúzott változatok pontlevonással járnak.
Reguláris kifejezések A reguláris kifejezések b®vített nyelve
Vázlat Hol alkalmazhatunk reguláris kifejezéseket
A reguláris kifejezések minimális nyelve
A reguláris kifejezések b®vített nyelve
Automatás feladatok
Gyakorlati tudnivalók
Reguláris kifejezések A reguláris kifejezések b®vített nyelve
Miért kell b®víteni? A reguláris kifejezések leírásához elegend® a kezdetben említett négy lehet®ség, mégis sok esetben elég körülményes azokkal felírni azt, amit illeszteni szeretnénk. Az egyik nehézség, amikor nagy számú karakter valamelyikére, például tetsz®leges bet¶re, kell illeszkedni, az elég hosszan írható csak le. Ezért bevezetünk egy bet¶- vagy számintervallumok megadására is alkalmas halmazjelölést. Egy másik probléma, hogy az ismétlések számát nem olyan egyszer¶ megadni. Hogyan adhatjuk meg azt, hogy a b bet¶ egymás után legalább 2-szer, de maximum 7-szer szerepelhet? Például így:
(bb|bbb|bbbb|bbbbb|bbbbbb|bbbbbbb) bb(|b|bb|bbb|bbbb|bbbbb) egyik sem
vagy így kellemes.
Reguláris kifejezések A reguláris kifejezések b®vített nyelve
Halmazjelölés A szögletes zárójel halmaz magadására alkalmas. Legegyszer¶bb formájában a felsorolt karakterek halmazát jelenti:
(A már említett . (pont) karaktert itt nem kell levédeni, nincs értelme a speciális jelentésnek.)
Megadhatunk szám és bet¶intervallumokat is, amennyiben a kezd® és végkarakter közé
−
jelet (köt®jel) rakunk.
Például a decimális számjegyeket, a(z ékezet nélküli) nagybet¶ket, illetve a kisbet¶ket a következ®képpen adhatjuk meg:
[0-9]
[A-Z]
[a-z]
Reguláris kifejezések A reguláris kifejezések b®vített nyelve
Feladat
Vajon hogyan adható meg egy nyolcas számrendszerbeli (oktális) számjegy az intervallumjelöléssel?
Reguláris kifejezések A reguláris kifejezések b®vített nyelve
Feladat
Vajon hogyan adható meg egy nyolcas számrendszerbeli (oktális) számjegy az intervallumjelöléssel? [0-7] Hogyan adható meg egy hexadecimális számjegy? (Egyszer¶ség kedvéért a bet¶k nagybet¶vel szerepeljenek: A, B, C, D, E, F!)
Reguláris kifejezések A reguláris kifejezések b®vített nyelve
Feladat
Vajon hogyan adható meg egy nyolcas számrendszerbeli (oktális) számjegy az intervallumjelöléssel? [0-7] Hogyan adható meg egy hexadecimális számjegy? (Egyszer¶ség kedvéért a bet¶k nagybet¶vel szerepeljenek: A, B, C, D, E, F!) ([0-9]|[A-F]) Az intervallumok összevonhatóak egy szögletes zárójelbe szorosan egymás mellé írva: [0-9A-F]
Reguláris kifejezések A reguláris kifejezések b®vített nyelve
Karakterhalmazok megadása
Az el®bbi jelölés tetsz®leges karakterhalmazok megadására is alkalmas. Az [c0-3@] kifejezés a c, 0, 1, 2, 3 és @ mindegyikére illeszkedik. Ha egy halmaznak rakjuk a
[-+03] [+0\-3] [+0-3]
−
−
jelre (köt®jel) is illeszkednie kell, akkor el®re
jelet, vagy védjük le.
−,
+, 0 és 3 karakterekre illeszkedik
ez is +, 0, 1, 2 és 3 karakterekre illeszkedik
Reguláris kifejezések A reguláris kifejezések b®vített nyelve
Feladat
Egy intézetben két épület van, amelyeket K és F bet¶vel jelölnek. A termek sorszámozása mindegyik épületben 0-tól 99-ig történik. A termeket a következ®képp adják meg K.00 K.01 . . . K.99, F.00, F.01, . . . F.99. Írjon reguláris kifejezést, amely mindegyik teremnévre illeszkedik!
M
Megoldás jön! Lapozás el®tt próbálja megoldani a feladatot!
Reguláris kifejezések A reguláris kifejezések b®vített nyelve
Megoldás
[FK]\.[0-9][0-9] Halmazjelölés nélkül:
(F|K)\.(0|1|2|3|4|5|6|7|8|9)(0|1|2|3|4|5|6|7|8|9)
Reguláris kifejezések A reguláris kifejezések b®vített nyelve
Speciális jelölések karakterhalmazokra Néhány speciális halmaz jele látható az alábbi halmazban. Elég az els® hármat tudni. . (pont)
\d \w \W \s \S
tetsz®leges karakterre decimális karakterek [0-9]
[0-9a-zA-Z_] az el®bbi ellentettje
[ \t\n\r\f\v] az el®bbi ellentettje
A \w tehát a változónevekben szerepl® karaktereket tartalmazza \s pedig a szóközt, a tabulátort és az újsort is magában foglaló
a
whitespace karaktereket. Ezek halmazon belül is használhatóak, illetve a halmazjelölés szögletes zárójelén belül a pont elveszti speciális jelentését. Emiatt a
[-.\w]+
illeszkedik az
Django_10.My-Server.hu
kifejezésre.
Reguláris kifejezések A reguláris kifejezések b®vített nyelve
Ismétlések Az alábbi ismétlést jelent® jeleket használhatjuk. természetes számot jelent.
*
0 vagy több ismétl®dés
+
1 vagy több ismétl®dés
?
{n} {n,m} {,m} {n,}
0 vagy 1 ismétl®dés (van vagy nincs) pontosan n ismétl®dés min. n, max. m ismétl®dés max. m ismétl®dés min. n ismétl®dés
n
és
m
mindenhol
Reguláris kifejezések A reguláris kifejezések b®vített nyelve
Feladat Melyek illeszkednek az els® reguláris kifejezésekre az azt követ® szavak közül?
Reguláris kifejezések A reguláris kifejezések b®vített nyelve
Megoldás Csak ezek:
[A-Z]{2}\d{5} CA12345 AA54321 (1?\d{2}|2[0-4]\d|25[0-5]) 255 00 244 133 (da){2,}dog dadadadog dadadog [.\w]+ ... man_page re_howto.pdf index.html b[a-j]+ baba baj https? http https \d+\.\d*[eE]-?\d+ 6.02e23 1.38E-23 1.E-6 \(\d+\+\d+\) (5+6) (123+456) A második kis hibával a 0 és 255 közötti számokat adja. A kis hiba, hogy a 00 01 . . . 09 formájú számok is vannak közöttük. Kis munkával javítható:
([0-9]|[1-9]\d|1\d{2}|2[0-4]\d|25[0-5])
Reguláris kifejezések A reguláris kifejezések b®vített nyelve
Feladat Hogyan illeszthetünk a szokásos magyar rendszámokra? Az alábbiak arra jók, hogy lássuk mire lehet/érdemes reguláris kifejezést írni. Ennyire összetett feladat nem lesz számonkéréskor. Próbáljunk egy közelít® reguláris kifejezést készíteni a következ®kre:
I IP-címek I e-mailek I URL-ek M
Megoldás jön! Lapozás el®tt próbálja megoldani a feladatot!
Reguláris kifejezések A reguláris kifejezések b®vített nyelve
I Korlátozott számú kapcsos zárójelet hogyan ellen®rizhetek? I Korlátlan számú kapcsos zárójelet hogyan ellen®rizhetek? I Korlátozott számú vegyes zárójelet hogyan ellen®rizhetek?
Reguláris kifejezések A reguláris kifejezések b®vített nyelve
I Korlátozott számú kapcsos zárójelpár: Pl. max 2 darab egymásba ágyazott, azaz
({({})?})?
{{}} vagy {}
vagy
ε.
(átláthatóság kedvéért a kapcsos zárójelek levédését elhagytam). Háromnál sorrendek
{}{}{} {{}{}} {{{}}}
I Korlátlan számú kapcsos zárójelpár: A zárójelezések nyelve környezetfüggetlen nyelv, nem fér bele a regulárisba
⇒
nincs
hozzá reguláris kifejezés.
I Korlátozott számú vegyes zárójelpár: Nagyon bonyolult. Ismerni kell a lehetséges sorrendeket.
I Veremautomatával egyszer¶ lesz mindegyik.
Reguláris kifejezések A reguláris kifejezések b®vített nyelve
Az elméleti rész összefoglalója I A reguláris kifejezések tömör leírását adják a reguláris nyelveknek.
Reguláris kifejezések A reguláris kifejezések b®vített nyelve
Az elméleti rész összefoglalója I A reguláris kifejezések tömör leírását adják a reguláris nyelveknek.
I Alkalmasak
Reguláris kifejezések A reguláris kifejezések b®vített nyelve
Az elméleti rész összefoglalója I A reguláris kifejezések tömör leírását adják a reguláris nyelveknek.
I Alkalmasak I
számunkra érdekes adatok megkeresésére (grep), cseréjére (sed, vim),
Reguláris kifejezések A reguláris kifejezések b®vített nyelve
Az elméleti rész összefoglalója I A reguláris kifejezések tömör leírását adják a reguláris nyelveknek.
I Alkalmasak I
számunkra érdekes adatok megkeresésére (grep), cseréjére (sed, vim),
I
hibás alakú adatok kisz¶résére (validálás).
Reguláris kifejezések A reguláris kifejezések b®vített nyelve
Az elméleti rész összefoglalója I A reguláris kifejezések tömör leírását adják a reguláris nyelveknek.
I Alkalmasak I
számunkra érdekes adatok megkeresésére (grep), cseréjére (sed, vim),
I
hibás alakú adatok kisz¶résére (validálás).
I Tömör jelölések karakterhalmazokra és ismétlésre.
Reguláris kifejezések A reguláris kifejezések b®vített nyelve
Az elméleti rész összefoglalója I A reguláris kifejezések tömör leírását adják a reguláris nyelveknek.
I Alkalmasak I
számunkra érdekes adatok megkeresésére (grep), cseréjére (sed, vim),
I
hibás alakú adatok kisz¶résére (validálás).
I Tömör jelölések karakterhalmazokra és ismétlésre. I Reguláris nyelveket adnak meg elemzésre nem alkalmasak.
⇒
programok szintaktikai
Reguláris kifejezések A reguláris kifejezések b®vített nyelve
Az elméleti rész összefoglalója I A reguláris kifejezések tömör leírását adják a reguláris nyelveknek.
I Alkalmasak I
számunkra érdekes adatok megkeresésére (grep), cseréjére (sed, vim),
I
hibás alakú adatok kisz¶résére (validálás).
I Tömör jelölések karakterhalmazokra és ismétlésre. I Reguláris nyelveket adnak meg
⇒
programok szintaktikai
elemzésre nem alkalmasak.
I Zárójelpárosítás ellen®rzésére korlátozottan alkalmas.
Reguláris kifejezések A reguláris kifejezések b®vített nyelve
Mikkel foglalkoztunk eddig? Összetev®k és kapcsolatok El®ször az összetev®k.
kifejezés
Reguláris kifejezések A reguláris kifejezések b®vített nyelve
Mikkel foglalkoztunk eddig? Összetev®k és kapcsolatok El®ször az összetev®k.
reguláris kifejezés
Reguláris kifejezések A reguláris kifejezések b®vített nyelve
Mikkel foglalkoztunk eddig? Összetev®k és kapcsolatok El®ször az összetev®k.
reguláris kifejezés
reguláris nyelv
Reguláris kifejezések A reguláris kifejezések b®vített nyelve
Mikkel foglalkoztunk eddig? Összetev®k és kapcsolatok El®ször az összetev®k.
reguláris kifejezés
reguláris nyelv
reguláris nyelvtan
Reguláris kifejezések A reguláris kifejezések b®vített nyelve
Mikkel foglalkoztunk eddig? Összetev®k és kapcsolatok El®ször az összetev®k.
reguláris kifejezés
reguláris nyelv
reguláris nyelvtan
véges automata
Reguláris kifejezések A reguláris kifejezések b®vített nyelve
Mikkel foglalkoztunk eddig? Összetev®k és kapcsolatok Mindhárom
egyértelm¶en
meghatározza a
nyelvet. Milyen igéket használunk az egyes esetekben? reguláris kifejezés
reguláris nyelv
reguláris nyelvtan
det. véges automata
Reguláris kifejezések A reguláris kifejezések b®vített nyelve
Mikkel foglalkoztunk eddig? Összetev®k és kapcsolatok Mindhárom
egyértelm¶en
meghatározza a
nyelvet. Milyen igéket használunk az egyes esetekben? reguláris kifejezés
reguláris nyelv generálja reguláris nyelvtan
det. véges automata
Reguláris kifejezések A reguláris kifejezések b®vített nyelve
Mikkel foglalkoztunk eddig? Összetev®k és kapcsolatok Mindhárom
egyértelm¶en
meghatározza a
nyelvet. Milyen igéket használunk az egyes esetekben? reguláris kifejezés
reguláris nyelv generálja reguláris nyelvtan
felismeri det. véges automata
Reguláris kifejezések A reguláris kifejezések b®vített nyelve
Mikkel foglalkoztunk eddig? Összetev®k és kapcsolatok
reguláris kifejezés
illeszkedik a szavaira reguláris nyelv generálja reguláris nyelvtan
felismeri det. véges automata
Nézzünk pár feladatot a véges automaták és reguláris kifejezések kapcsolatára.
Reguláris kifejezések Automatás feladatok
Vázlat Hol alkalmazhatunk reguláris kifejezéseket
A reguláris kifejezések minimális nyelve
A reguláris kifejezések b®vített nyelve
Automatás feladatok
Gyakorlati tudnivalók
Reguláris kifejezések Automatás feladatok
Feladat Milyen reguláris kifejezéssel írható le az alábbi véges automata által felismert nyelv? Írjuk le b®vítetlen reguláris kifejezéssel és tömörebben a b®vített reguláris kifejezés használatával! a
b
q0
a
q1
a b
q2 b
Írjuk le a nyelvet halmazjelöléssel is!
M
Megoldás jön! Lapozás el®tt próbálja megoldani a feladatot!
Reguláris kifejezések Automatás feladatok
Megoldás
b*aa*b(a|b)*
vagy
b*a+b[ab]*
Az els® megoldás nem használja a b®vített nyelvet.
L = {b a bw | i ≥ 0, j > 0, w ∈ {a, b}∗ } i
j
Reguláris kifejezések Automatás feladatok
Feladat Milyen reguláris kifejezéssel írható le az alábbi véges automata által felismert nyelv? Használhatja a b®vített reguláris kifejezést! c
b
q0
a
q1
c
q2
b
q3 Írjuk le a nyelvet halmazjelöléssel is! (Létrehozhatja a nyelvtant is, ami ugyanazt a nyelvet generálja, amit az automata felismer.) M
Megoldás jön! Lapozás el®tt próbálja megoldani a feladatot!
Reguláris kifejezések Automatás feladatok
Megoldás
(ab+|ab*c+|)
esetleg
(ab*(b|c+)|)
Az els® változat három függ®leges vonallal elválasztott tagból áll: az els® tag, amikor a B-be érek, a második, amikor a C-be érek, a harmadik amikor S-ben maradok üres szóval. Ugyanebben a sorrendben szerepelnek az alábbi halmazok, amelyeknek az unióját vesszük.
L = {ab | i > 0} ∪ {ab c | i ≥ 0, j > 0} ∪ {ε} i
i
j
Reguláris kifejezések Automatás feladatok
Feladat Rajzolja le olyan véges automaták állapotgráfjait, amely az alábbi reguláris kifejezések által megadott nyelvet ismeri fel!
I ab*c I 0(12*|1+) I a(b*c|a+) ez nehezebb, ilyen nehéz nem lesz.
M
Megoldás jön! Lapozás el®tt próbálja megoldani a feladatot!
Reguláris kifejezések Automatás feladatok
Megoldás ab*c legkézenfekv®bb megoldása: b
q0
a
q1
c
q2
0(12*|1+) egy lehetséges megoldása:
q0
0
q1
1
q2 1
1
q3
2
Reguláris kifejezések Automatás feladatok
Reguláris kifejezésb®l véges automata
A reguláris kifejezések illesztéséhez nem ötletszer¶ megoldások, hanem algoritmusok szükségesek. Az, hogy bármely reguláris kifejezés esetén meg tudjuk alkotni a véges automatát, amellyel meg tudjuk vizsgálni az egyes szavakat. Van erre algoritmus, de mi nem tanuljuk. (A Bach-könyvben vagy máshol megnézheti, aki akarja, és a JFLAP-pel gyakorolhatja, de számunkra nem szükséges.)
Reguláris kifejezések Gyakorlati tudnivalók
Vázlat Hol alkalmazhatunk reguláris kifejezéseket
A reguláris kifejezések minimális nyelve
A reguláris kifejezések b®vített nyelve
Automatás feladatok
Gyakorlati tudnivalók
Reguláris kifejezések Gyakorlati tudnivalók
Mihez szükséges?
A további gyakorlati tudnivalóak nem szükségesek a Formális nyelvek feladatainak a megoldásához, hasznosak viszont a Linux alkalmazása kurzushoz, mivel a grep és a django használatakor (URL-értelmezés, bevitt adatok ellen®rzése=validálása) is szükséges dolgok vannak hátra. Hasznos továbbá, ha valamikor a Pythonban saját programot szeretnénk írni, ami reguláris kifejezéseket használ.
Reguláris kifejezések Gyakorlati tudnivalók
A sor eleje és vége A sor elejére a
^
(kalap) a végére a
$
karakterek illeszkednek.
Ha például a re.search függvénnyel keresünk, akkor az "aba" kifejezés illeszkedni fog az "Alabama" karakterláncra, annak aba részére. A
"^aba"
nem fog illeszkedni rá, de az "abama" és
"abakusz" karakterláncra igen. A
"^aba$"
egyedül az "aba"
karakterláncra fog illeszkedni.
A Formális nyelvek rész feladatai teljes illeszkedést feltételeztek, mintha minden kifejezés elején ott lenne a
^
és a végén a
$.
Ez a
megszokott mód az elméleti tárgyalások során, például a Bach Iván könyvében is, ha például egy nyelvet reguláris kifejezéssel írunk le.
Reguláris kifejezések Gyakorlati tudnivalók
A nyers karakterláncok és a b® írásmód
A Python nyelv re modulja képes reguláris kifejezéseket kezelni.
Ha r bet¶t írunk a karakterlánc elé, a karakterként
⇒
\
nem viselkedik speciális
könnyebben írhatunk reguláris kifejezéseket.
A re.VERBOSE paraméterrel sorokra bonthatjuk, és megjegyzésekkel láthatjuk el a reguláris kifejezéseket.
Reguláris kifejezések Gyakorlati tudnivalók
Példa az r"" és a re.VERBOSE használatára # r nélkül re.search("\\d+\\.\\d*", "123.6") # r-rel re.search(r"\d+\.\d*", "123.6") # r-rel és re.VERBOSE-zel re.search(r""" \d+ # egész rész \. # tizedes pont \d* # törtrész """, "123.6", re.VERBOSE)
Reguláris kifejezések Gyakorlati tudnivalók
Python és Vim összehasonlítása
A speciális jelentést:
I egyikben sem kell levédeni: . (pont), *,
[] ^ $ \
I csak Vimben kell levédeni:
( ) | { ? +
Reguláris kifejezések Gyakorlati tudnivalók
Dokumentációk A reguláris kifejezések az itt leírtaknál nagyobb mélységgel rendelkeznek mind a Python nyelvben, mind a Vim szövegszerkeszt®ben. A reguláris kifejezések Pythonbeli használatáról a Python dokumentációk között a Regular Expression HOWTO (a Python HOWTOs részben) és az re modul dokumentációja (a Library Reference részben) ad jó leírást. A reguláris kifejezések Vimbeli használatáról a :help regexp parancssal lehet többet megtudni. Lásd még: regexp_vim.txt