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
(SCIgen - An Automatic CS Paper Generator), 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 xkcd: Computational Linguists

2012/10/24 Davide R. [email protected]:

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

Siccome vi interessa ve la linko :slight_smile:
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 :slight_smile:

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 R.
[email protected]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