[PIPython] problema con stringhe

[Alex Martelli]

On Friday 02 January 2004 06:14 pm, Ernesto wrote:
> Ciao a tutti,
> sono Ernesto. Sto cercando di prendere familiarità con il linguaggio Python
> che spero mi possa aiutare nel mio lavoro (biologia molecolare). Leggendo

Dovrebbe si`, secondo http://www.biopython.org/ .

> qualche manuale ho trovato che è possibile ricercare in una stringa, tutte
> le sottostringhe non sovrapponibili, compilando un'espressione regolare ed
> utilizzando la funzione findall(). Vorrei sapere se c'è un metodo o
> funzione che mi permetta di identificare anche sottostringhe
> sovrapponibili. In concreto, la stringa di partenza è simile alla seguente:
>
> (((A,B),C),D)
>
> Utilizzando una specifica espressione regolare vorrei ottenere una lista
> del tipo: ['(A,B)', '((A,B),C)', '(((A,B),C),D)']
>
> Utilizzando la funzione findall() ottengo solo ['(A,B)'].
> C'è qualcuno in grado di darmi qualche suggerimento?

In generale (un punto fondamentale della teoria dei linguaggi) le espressioni
regolari NON hanno potenza sintattica sufficiente per identificare "parentesi
bilanciate", che cosi` a naso sembra quel che tu vuoi fare.  Non e` un 
problema di Python, nota bene: e` un problema di teoria generale del parsing
(le regular expression hanno esattamente la stessa potenza di parsing di un
automa a stati finiti; per identificare parentesi bilanciate, ti serve invece 
la potenza di un automa con pushdown stack, che e`, dimostrabilmente, in
grado di parsare grammatiche che un automa a stati finiti non puo` parsare).

Questo e` un problema separato da quello che tu indichi, ma suggerisce che
quand'anche si trovasse una soluzione per il problema che tu indichi essa non
farebbe necessariamente al caso tuo.  Se adotti altri approcci di parsing, 
piu` potenti delle RE, potresti "prendere due piccioni con una fava"...


Alex