Dotaz: Rozsirene regularni vyrazy a bezkontextovy jazyk

[Karel Marhoul]

Zdravim, muj dotaz bude souviset s perlovskymi regularnimi vyazy a taky s formalnimi jazyky.

Jazyk a^n b^m (nejdrive libovolny nenulovy pocet znaku 'a' a pak libovolny nenulovy pocet znaku 'b') je regularni a tudiz lze definovat (klasickymi nerozsirenymi) regularnimi vyrazy, viz:

root@bt:~# cat test.txt 
bbbbbaa
aaabb
abbb
aaaabbbb
root@bt:~# grep 'a\+b\+' test.txt 
aaabb
abbb
aaaabbbb

Jazyk a^n b^n (posloupnost znaku 'a' nasledovanyna STEJNYM poctem znaku 'b') je vsak uz jazyk bezkontextovy. Docetl jsem se, ze rozsirene regularni vyrazy (ERE,PCRE) mohou popsat i takovy jazyk. Muze tedy mi prosim tedy nekdo uvest priklad treba z grepem tak jako vyse, ktery mi z toho vstupniho souboru vybere pouze retezec nalezejici do toho jazyka, tedy 'aaaabbbb'?

---

---

Odpovědi

[NN]

$ egrep '[a][b]{4}' test.txt

[chrono]

Na Stackoverflow sa niečo také objavuje pomerne často (napr. Match a^n b^n c^n (e.g. “aaabbbccc”) using regular expressions (PCRE), technicky je to riešenie zložitejšieho problému, ale je tam odkaz aj na ten aaabbb problém).

[wamba]

viz. perldoc perlre

 echo aaaabbbb |perl -nE 'print if /^(a(?1)*b)$/'

[Karel Marhoul]

Dekuji to je presne ono, jen bych to potreboval prevest na grep. Toto nefunguje:

echo aaaabbbb | grep -E '^(a(?1)*b)$'

[chrono]

Je otázne, či sa to dá urobiť s rozšírenými POSIX regexp, ale s pcregrep to funguje.

[Karel Marhoul]

Ja myslel ze PCRE a extended POSIX regexps jsou ekvivalentni...

[chrono]

ERE oproti BRE pridáva viac-menej len operátory ? a + (a mierne mení syntax zápisu napr. a{1,2} z pôvodného a\{1,2\}).

[petr_p]

PCRE znamená Perl Compatible Regular Expression. A perlové výrazy jsou silnější než rozšířené výrazy. Jako rychlý přehled doporučuji manuálovou stránku pcresyntax(3) z balíku pcre. (Že pcre není zcela kompatibilní s Perlem prozatím přejdeme.)

[wamba]

tak tohle by mohlo fungovat

echo aaaabbbb | grep -P '^(a(?1)*b)$'