Ho visto alcuni commenti che menzionano che le espressioni regolari moderne vanno oltre ciò che può essere rappresentato in un linguaggio normale. Com'è così?I dialetti delle espressioni regolari non sono regolari?
Quali caratteristiche delle moderne espressioni regolari non sono regolari? Gli esempi sarebbero utili.
La prima cosa che viene in mente è backreference:
(\w*)\s\1
(corrisponde a un gruppo di caratteri di parola, seguito da uno spazio e poi lo stesso gruppo trovato in precedenza) ad esempio: hello hello partite, hello world doesn' t.
Questo costrutto non è regolare (ad esempio: non può essere generato da un regular grammar).
Un'altra caratteristica supportata da Perl RegExp compatibile (PCRE), che non è regolare sono modelli ricorsive:
\((a*|(?R))*\)
questo può essere utilizzato per adattarsi a qualsiasi combinazione di parentesi bilanciate e "a" s (da wikipedia)
Alcune sottofrequenze possono essere fatte in una lingua normale. Ad esempio '(.) X \ 1' definisce un linguaggio regolare:" axa "," bxb ", ecc. Credo che sia solo quando combinato con chiusure di Kleene che le backreferenze rendono il linguaggio irregolare. – Gabe
Non è necessario lo spazio in là. '(. *) \ 1' farà. – Nabb
@Nabb: '.' corrisponde a una gamma molto più ampia di caratteri rispetto a' \ w * \ s' – BoltClock
Un automa finito deterministico o non deterministico riconosce solo le lingue regolari, che sono descritte da espressioni regolari. La definizione di un'espressione regolare è semplice. Let S essere un alfabeto. Quindi il set vuoto, la stringa vuota e ogni elemento di S sono espressioni regolari (oltre S). Let u e v essere espressioni regolari. Quindi l'unione (u | v), concatenazione (uv), e la chiusura (u *) di u e v sono espressioni regolari oltre S. Questa definizione è facilmente estendibile alle lingue regolari. Nessuna altra espressione è un'espressione regolare. Come sottolineato, alcuni riferimenti a posteriori sono un esempio. Le pagine di Wikipedia sulle lingue e le espressioni regolari sono buone referenze.
In sostanza, alcune "espressioni regolari" non sono regolari perché non è possibile costruire automi di un tipo particolare per riconoscerli. Ad esempio, la lingua
{a^i b^i: i < = 0}
non è regolare. Questo perché l'automa accettante richiederebbe infiniti stati, ma un automa che accetta lingue regolari deve avere un numero finito di stati.
A giudicare dalla domanda originale, sono abbastanza sicuro che capisca la distinzione tra lingue regolari e non regolari. La sua domanda è, quali caratteristiche delle moderne implementazioni di "espressione regolare" definiscono linguaggi che non sono regolari, e quindi non possono essere espressi in qualche modo usando le operazioni che hai elencato. –
Forse dovrei leggere più da vicino, allora! In ogni caso, non penso di aver causato alcun danno. – danportin
'a^i b^i' è sicuramente non regolare (è un DCFG), ma possiamo effettivamente esprimerlo usando le" espressioni regolari "dei linguaggi di programmazione? – Nabb
Un paio di esempi:
/my (group)/.match("my group")[1] genererà "gruppo". memorizzare qualcosa in un gruppo richiede una memoria esterna, che un automa finito non ha.(?<MYGROUP>.)* potrebbe eseguire più acquisizioni di "." nello stesso gruppo.(?<MYGROUP>test) inserisce uno stack, mentre (?<-MYGROUP>) apre uno stack(?<FIRSTGROUP-LASTGROUP>) che apre LASTGROUP e spinge l'acquisizione dall'indice LASTGROUP sullo stack FIRSTGROUP, che può essere effettivamente utilizzato per corrispondere a costruzioni infinitamente annidate che è sicuramente oltre la potenza di un automato finito n. EsistonoProbabilmente altri buoni esempi :-) Se state ulteriormente interessavano in alcuni dei dettagli di implementazione di pile esterne in combinazione con Regex e di raggruppamento equilibrato e quindi superiore automi ordine di automi a stati finiti, una volta ho scritto due brevi articoli su questo (http://www.codeproject.com/KB/recipes/Nested_RegEx_explained.aspx e http://www.codeproject.com/KB/recipes/RegEx_Balanced_Grouping.aspx).
In ogni caso - finitieness o no - ho blieve che il potere che questa roba in più porta ai linguaggi regolari è grande :-)
Br. Morten
Il raggruppamento e la cattura non sono caratteristiche che rendono la lingua irregolare - tutto ciò che fanno è fornire metadati, non modificare l'espressività della lingua. Ovviamente tutto ciò che coinvolge uno stack (come le retrocopolazioni) lo rende comunque un linguaggio irregolare. – Gabe
Questo probabilmente dovrebbe essere un wiki della comunità –
@webdestroya: Posso capire CW, ma perché non su SO? – BoltClock
@NullUser - Non è una domanda piuttosto soggettiva? –