[ 10. January 2000]
- Svato_Straka
Pravidlß pre porovnßvanie v reg. v²razoch - 7. Φas¥ CGI
V minulej Φasti sme si povedali, Φo to regulßrne v²razy s· a ozrejmili sme si niektorΘ zßkladnΘ pravidlß v ich pou₧itφ. Dnes si povieme nieΦo o pravidlßch, ktorΘ sa pou₧φvaj· pri porovnßvanφ vzoru s re¥azcom.
Pre porovnßvanie v Perli sa vyu₧φva tzv. nedeterministick² koneΦn² automat - pamΣtß si, Φo u₧ vysk·Üal a Φo nie, pok²m nieΦo neuspeje, vrßti sa opΣ¥ na zaΦiatok a sk·Üa Φosi inΘ. Z tohto vidno, ₧e pri zle napφsanom vzore pre porovnanie sa m⌠₧e beh programu pomerne dos¥ spomali¥.
Ni₧Üie uvedenΘ pravidlß s· danΘ v poradφ, ak²m automat v Perli postupuje pri porovnßvanφ. Vo vÜeobecnosti sa dß poveda¥, ₧e Perl preferuje zhodu Φo najviac v╛avo pred najdlhÜou zhodou.
Pravidlo Φ. 1
Automat sa sna₧φ nßjs¥ zhodu Φo najviac v╛avo v re¥azci tak, aby sa cel² v²raz zhodoval pod╛a pravidla Φ. 2.
K⌠li tomuto sa porovnßvanie zaΦφna pred prv²m znakom v re¥azci. Porovnßvanie je ·speÜnΘ, ak je nßjdenß zhoda celΘho reg. v²razu pred koncom re¥azca. AK je porovnanie ·speÜnΘ, okam₧ite sa ukonΦφ aby sa prediÜlo ∩alÜφmzbytoΦn²m porovnßvaniam. Toto porovnßvanie nemusφ dosiahnu¥ koniec re¥azca, len koniec reg. v²razu (ak to nie je explicitne urΦenΘ inak). Ak sa na prvom mieste nenßjde zhoda, automat pokraΦuje od ∩alÜej pozφcie (medzi prv²m a druh²m znakom). Porovnßvanie zlyhßva a₧ potom, ak sa nenßjde zhoda reg. v²razu vo vÜetk²ch miestach v re¥azci, vrßtane miesta za posledn²m znakom.
Ke∩₧e miesta, od ktor²ch sa zhoda vyh╛adßva s· medzi znakmi re¥azca, treba by¥ pri pφsanφ reg. v²razov pozorn². Ak by ste toti₧ zadali reg. v²raz ako /o*/ (zhoda so ₧iadnym alebo viacer²mi znakmi o) a re¥azec bude obsahova¥ napr. slovo "ahoj", bude zhoda nßjdenß s nulov²m re¥azcom na zaΦiatku pred "a" namiesto zhody s "o" na tre¥om mieste. V takomto prφpade je lepÜie miesto kvantifikßtoru * pou₧i¥ +, to jest reg. v²raz by bol /o+/.
Pravidlo Φ. 2
V tomto prφpade sa cel² reg. v²raz pova₧uje za mno₧inu alternatφv. Ak exsituje viac alternatφv, s· oddelenΘ znakom | (pipe). Mno₧ina alternatφv sa zhoduje vtedy, ak sa zhoduje ╛ubovolnß z alternatφv pod╛a pravidla Φ. 3. Alternatφvy sa sk·Üaj· v smere z╛ava doprava a porovnßvanie sa zastavφ na prvej nßjdenej zhode. Pok²m nevyhovuje ₧iadna alternatφva, porovnßvanie sa vrßti k pravidlu, ktorΘ vyvolalo pravidlo Φ. 2 ( to m⌠₧u by¥ pravidlß 1, 4 alebo 6). Toto pravidlo potom h╛adß znovu pozφciu, an ktorej by sa dalo pravidlo Φ. 2 pou₧i¥.
Ak existuje len jedna alternatφva, tßto sa zhoduje alebo nie a pravidlo stßle platφ. Nulovß alternatφva tu neexistuje, preto₧e s Φφmko╛vek s nulovou dσ₧kou sa zhoduje nulov² re¥azec.
Pravidlo Φ. 3
╝ubovo╛nß alternatφva sa bude zhodova¥ vtedy, ak sa zhoduje postupne ka₧dß polo₧ka pod╛a pravidiel 4 a 5. Polo₧ka sa skadß z tvrdenia, definovanΘho pravidlom 4 alebo z kvantifikovanΘho at≤mu popφsanΘho v pravidle 5. Polo₧ky, u ktor²ch je uveden²ch viac mo₧nostφ zhody maj· priradenΘ poradie z╛ava doprava. Ak sa polo₧ky nezhoduj·, automat sa vrßti k ∩alÜej alternatφve pod╛a pravidla Φ. 2.
Polo₧ky, ktorΘ sa musia zhodova¥ pod╛a svojho poradia nie s· v reg. v²raze nijako syntakticky oddelenΘ. Ak po₧adujete porovnanie pod╛a /^foo/, po₧adujete porovnanie Ütyroch polo₧iek - nulovΘho tvrdenia a tromch pφsmen, ktorΘ sa musia zhodova¥ samy so sebou presne v tom poradφ, v akom s· uvedenΘ v reg. v²raze.
Pravidlo Φ. 4
Tvrdenie sa musφ zhodova¥ pod╛a nasl. tabu╛ky. Ak tvrdenie v aktußlnej pozφcii nevyhovuje, automat sa vrßti k pravidlu Φ. 3 a sk·Üa inΘ mo₧nosti s polo₧kou s vyÜÜφm poradφm.
| Tvrdenie |
V²znam |
| ^ |
Zhoduje sa so zaΦiatkom re¥azca (riadku, ak je pou₧itΘ /m) |
| $ |
Zhoduje sa s koncom re¥azca (riadku, ak je pou₧itΘ /m) |
| b |
Zhoduje sa s hranicou slova (medzi w a W) |
| B |
Zhoduje sa so vÜetk²m okrem hranice slova |
| A |
Zhoduje sa so zaΦiatkom re¥azca |
| Z |
Zhoduje sa s koncom re¥azca |
| G |
Zhoduje sa tam, kde skonΦilo m//g |
| (?...) |
Zhoduje sa ak by automat naÜiel zhodu s ...∩alej |
| (?!...) |
Zhoduje sa ak by automat nenaÜiel zhodu s ...∩alej |
Tvrdenia $ a Z sa nemusia zhodova¥ len s koncom re¥azca, ale aj o jeden znak sk⌠r, ak je posledn²m re¥azcom znak novΘho riadku.
Tvrdenia (?...) a (?!...) h╛adiace dopredu maj· samy o sebe nulov· dσ₧ku, tvrdia vÜak, ₧e sa v tomto mieste, kde sa pok·Üame o porovnanie, zhoduje (alebo nezhoduje) regulßrny v²raz, ktor² je vo vyÜÜie uvedenej tabu╛ke reprezentovan² ako "naÜiel zhodu s ..." a "nenaÜiel zhodu s ...". Automat sa vrßti spΣ¥ k pravidlu Φ. 2, kde podv²raz otestuje a potom vyma₧e ak²ko╛vek zßznam o tom, ko╛ko re¥azcov bolo pohlten²ch, priΦom ako v²sledok tvrdenia vrßti len ·spech alebo ne·spech tohoto podv²razu.
Pravidlo Φ. 5
Kvantifikovan² at≤m sa zhoduje len vtedy, ak sa zhoduje to╛kokrßt za sebou, ako je danΘ kvantifikßtorom. Tabu╛ku so zoznamom kvantifikßtorov nßjdete v predchßdzaj·cej Φasti.
Kvantifikßtory sa sna₧i av₧dy nßjs¥ najdlhÜiu zhodu.
Pok²m definujete reg. v²raz ako napr. /.*foo/, automat sa pok·si nßjs¥ zhodu s maximßlnym poΦtom ╛ubovo╛n²ch znakov (s· reprezentovanΘ bodkou) a₧ do konca riadku a potom sa sna₧φ nßjs¥ "foo". Toto samozrejme nie je mo₧nΘ, preto₧e "foo" sa nem⌠₧e zhodova¥ s nulov²m re¥azcom na konci riadku. Automat sa teda vracia o znak spΣ¥, pok²m nenßjde "foo". Pok²m je na riadku viac ako jeden v²skyt "foo", vyh╛adßvanie sa zastavφ na poslednom a vÜetky ostatnΘ mo₧nosti ktorΘ boli nßjdenΘ bud· zabudnutΘ.
Pok²m by ste chceli, aby ktor²ko╛vek z kvantifikßtorov h╛adal najkratÜiu zhodu, dosiahnete to umiestnenφm znaku ? za tento kvantifikßtor. Pok²m teda zadßte reg. v²raz /.*?foo/, automat bude h╛ada¥ zhodu nie od konca riadku, ale od nultej pozφcie v riadku, tak₧e vyh╛adßvanie sa zastavφ pri prvom nßjdenom "foo".
Pravidlo Φ. 6
Ka₧d² at≤m sa porovnß na zhodu pod╛a svojho typu pod╛a typov uveden²ch ni₧Üie. Ak sa at≤m nezhoduje alebo neumo₧≥uje zhodu zbytku reg. v²razu, vracia sa automat spΣ¥ k pravidlu 5 a sk·Üa ∩a╛Üiu mo₧nos¥ pod╛a kvantifikovanΘho at≤mu.
Typy at≤mov:
Reg. v²raz v zßtvorkßch, (...), sa zhoduje po╛a toho, Φi sa zhoduje reg. v²raz (tu reprezenovan² ako ...) pod╛a pravidla Φ. 2. Zßtvorky teda sl·₧ia ako operßtor zoskupenia pre kvantifikßtory.
Znak "." (bodka) sa zhoduje s ╛ubovo╛n²m znakom okrem n (nov² riadok).
Zozonam znakov uveden²ch v hranat²ch zßtvorkßch sa zhoduje s ╛ubovo╛n²m jedn²m znakom zo zoznamu. Uvednenφm znaku "^" na zaΦiatok zoznamu sa sp⌠sobφ, ₧e sa bud· zhodova¥ len tie znaky, ktorΘ v zozname nie s· uvedenΘ. Rozsah znakov m⌠₧e by¥ vyznaΦen² pomocou notßcie a-z. M⌠₧e tie₧ by¥ pou₧it² niektor² z k≤dov d, w, s, n, r, t, f alebo nnn (vysvetlenΘ ni₧Üie). Pok²m chcete v zozname porovna¥ pomlΦku alebo prav· hranat· zßtvorku, je nutnΘ pred nimi pou₧i¥ spΣtnΘ lomφtko (""). Pok²m chcete porovna¥ znak "^", nedßvajte ho na prvΘ miesto v zozname.
Pφsmeno, pred ktor²m je uvedenΘ spΣtnΘ lomφtko ("") sa zhoduje so zvlßÜtnym znakom alebo triedou znakov:
| K≤d |
Zodpovedß |
| a |
pφpnutie |
| n |
nov² riadok |
| r |
nßvrat vozφku na zaΦiatok riadku (CR) |
| t |
tabulßtor |
| f |
novß strßnka |
| e |
escape |
| d |
Φφslica (rovnakΘ ako [0-9]) |
| D |
in² znak ako Φφslica |
| w |
znak slova, alfanumerick² (rovnakΘ ako [a-zA-Z_0-9]) |
| W |
in² znak ako znak slova |
| s |
prßzdny znak (ako [tnrf]) |
| S |
in² ako prßzdny znak |
╚φslo o dσ₧ke jednej Φφslice pred ktor²m je znak "" sa zhoduje s t²m, s Φφm sa v skutoΦnosti
zhoduj· zodpovedaj·ce zßtvorky. Tomuto sa hovorφ spΣtnΘ odkazovanie. ╚φslo zlo₧enΘ z viacer²ch Φφslic uvedenΘ znakom "" sa pova₧uje za spΣtn² odkaz, pok²m vzor pred nφm obsahuje aspo≥ to╛ko podre¥azcov a toto Φislo nezaΦφna Φφslicou 0. Dvojice zßtvoriek s· ΦφslovanΘ z╛ava pod╛a poradia ╛avej zßtvorky.
OsmiΦkovΘ Φφslo zlo₧enΘ z dvoch alebo troch Φφslic, ktorΘ je uvedenΘ znakom "" sa zhoduje so znakom Üpecifikovanej hodnoty, pok²m sa nejednß o spΣtn² odkaz.
Pφsmeno x uvedenΘ znakom "" a nasledovanΘ jednou alebo dvoma hexadecimßlnymi Φφslicami sa zhoduje so znakom maj·cim dan· Üestnßstkov· hodnotu.
Pφsmeno c uvedenΘ znakom "" a nasledovanΘ jedn²m pφsmenom sa zhoduje so zodpovedaj·cim kontroln²m (control) znakom.
Ak²ko╛vek in² znak uveden² znkom "" sa zhoduje s t²mto znakom.
Ak²ko╛vek in² tu neuveden² znak sa zhoduje sßm so sebou.
To by bolo k pravidlßm pre reg. v²razy vÜetko, nabud·ce dokonΦφme rozpravu o regulßrnych v²razoch.
|
|
|
Homepage
