Nahát, nahát, eddig három ismerős ebben a topic-ban! :)
A tiltott szavakat szervezzük papíron prefix-fába (trie-ba). A trie-on annyit reszelnék, hogy a node-okba nem az addig leírt szavakat tenném, hanem a betűket (tehát nem az élekre írnám a karaktereket, hanem a node-okba, és egy szó összeolvasásához a gyökérből le kell olvasni az adott levélig.) Ezután a fát járjuk be az alábbi bejárással:
Tetszőleges node-on állva, melynek gyermekei T, U, V, az alábbit generáljuk:
[^TUV]|\>|T()|U()|V()A zárójelekbe pedig belelépünk, és ott a kijelölt részfát bejárva rekurzívan ismételjük az algoritmust. Az algoritmust egy ál-gyökérből indítjuk.
A fát annyival trükközzük még meg, hogy a tiltott szavak végére mindenhova odaírjuk a szóhatárt (
/\>/). Ezek lesznek ugye a fa levelei, ahonnan már nincs hova továbbhaladni. Ilyenkor a fenti alternatívából csak az első ág értelmes (a tagadó osztály), a szóhatárnak a negálását pedig (legalábbis GNU alatt)
/\B/-nek írjuk.
Legyenek például a tiltott szavak: /alma/, /alfa/, /alga/. Ebből az alábbi fa készül:
*
|
a
|
l
/|\
m f g
| | |
a a a
| | |
> > >
A fenti algoritmussal:
[^a]|\>|a(
[^l]|\>|l(
[^mfg]|\>|m(
[^a]|\>|a(
\B
)
)|f(
[^a]|\>|a(
\B
)
)|g(
[^a]|\>|a(
\B
)
)
)
)Az egészet beletesszük egy külső zárójelbe, és az elejére kirakunk egy bal szóhatárt. Összeolvasva:
\<([^a]|\>|a([^l]|\>|l([^mfg]|\>|m([^a]|\>|a(\B))|f([^a]|\>|a(\B))|g([^a]|\>|a(\B)))))Yacc/bison/sed/awk téma: a sed és főleg az awk is erősen programozható, tehát nem biztos, hogy csak emiatt rendes HTML parser-t kell írni bison-ban. A HTML (mivel nem XHTML) amúgy is rosszul formázott lesz. Ha véletlenül XHTML-lel van dolgunk, akkor az xmlstarlet-tel lehet a legjobb nekiugrani. A yacc-ot megtanulni persze amúgy is érdemes.