Forum: Italian Ruby user group Context Free Grammar infinite loop!

Ciao a tutti, non che sia una domanda ruby specifica, ma considerata la 
bravura di molti programmatori in questa lista vorrei sottoporvi questa 
domanda (questa si chiama: captatio benevolentiae).

Sto giocando con il codice di sciGEN 
(http://pdos.csail.mit.edu/scigen/), in quanto, visto che le 
pubblicazioni languono negli ultimi anni di lavoro (sigh), tanto vale 
scrivere un parser che ne genera un TOT a random (magari poi un paio me 
li prendono: la scienza e' cosi!)

mi chiedevo: qual'e' il modo migliore per stoppare le  infinite looping 
substitutions?

Mi spiego:

Se ho la frase

MYLITTLELAB_PAPER EMULATING_THEM with PERVERSE and DIFFERENT kind of 
WARE MYLITTLELAB_PAPER

Dove le parole in maiuscolo sono Token da sostiuire, mi trovo in un 
infinite loop durante la sostituzione.

In sintesi il problema degli infinite loops puo' essere sintetizzato in 
questa "regola":

kw1="%kw1%"

In giro per la rete sembra che il metodo piu' in uso sia quello di dare 
un limite arbitrario al numero di iterazioni del loop.

Esiste un'altra maniera?

Ciao

Davide

P.S: concordo con chi crede che quando uno arriva ai computational 
linguists e' arrivato decisamente alla frutta  http://xkcd.com/114/

2012/10/24 Davide Rambaldi <davide.rambaldi@gmail.com>:

> In giro per la rete sembra che il metodo piu' in uso sia quello di dare un 
limite arbitrario al numero di iterazioni del loop.
>
> Esiste un'altra maniera?


per definizione della regola: no, se gli dici "vai avanti
all'infinito" quello ovviamente va avanti all'infinito.  come se
fosse

def f(x)
 f(x)
end


Non ho idea di come funzioni scigen, ma puoi provare a cambiare la
cosa mettendo un set ristretto dal lato destro tipo

kw1 ="%kw2%"

dove la roba nel secondo  un subset della roba del primo.

Ma sto completamente tirando caso.

--
twitter: @riffraff
blog (en, it): www.riffraff.info riffraff.blogsome.com
work: circleme.com

Complimenti al buon Gabriele per il supporto. Mitico.

Tanti anni fa ho sviluppato un DSL per realizzare context-free lexer e
parser.
https://rubygems.org/gems/llip
https://github.com/mcollina/llip

Siccome vi interessa ve la linko :)
Il codice  tutto open, e se a qualcuno interessa l'approccio alla
metaprogrammazione,  molto divertente :).

Matteo

Grazie ragazzi per le info.

Se vi dico in che linguaggio sto scrivendo questa cosa mi picchiate :-)

Comunque per ora il mio algoritmo stile "pugni e calci" scorre la frase 
di input da sinistra verso destra:

MYLITTLELAB_PAPER EMULATING_THEM with PERVERSE and DIFFERENT kind of 
WARE

Sostituendo i "tokens/rules" (le parole in maiuscolo) con una frase a 
caso tra i terms disponibili :

PERVERSE    perverse
PERVERSE    counterintuitive
PERVERSE    unexpected

Ho messo due controlli:

throw exception se la frase di input contiene due volte lo "start 
token":  MYLITTLELAB_PAPER

Dopo 150 iterazioni, se non ho risolto i tokens, suppongo ci sia una 
circolarita' nel file grammar e tiro una bella eccezzione.

Si, lo sto facendo in C#, non perche' sono sadomaso, ma perche' e' parte 
di un grande progetto per fare una killer app e gudagnare il mio million 
dollar! (ho gia comprato il maglione a girocollo come Steve)

A parte gli scherzi grazie per il link alla gemma ruby. Me la guarda ed 
estraggo l'estraibile.

Gracias

Davide

Il giorno 25 ottobre 2012 15:39, Davide Rambaldi
<davide.rambaldi@gmail.com>ha scritto:
>
> A parte gli scherzi grazie per il link alla gemma ruby. Me la guarda ed
> estraggo l'estraibile.
>

Figurati :).
Se mi mandi una Pull Request accetto volentieri aiuti!

Matteo