# Context Free Grammar infinite loop! **URL:** \ **Category:** IT\ **Created:** [October 24, 2012, 2:40pm UTC](https://www.ruby-forum.com/t/context-free-grammar-infinite-loop/223944 "2012-10-24T14:40:50Z")\ **Posts on this page:** 5\ **Page:** 1
**Author:** ![aris](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/a/258eb7/32.png) [@aris](https://www.ruby-forum.com/u/aris)\ **Post date:** [October 24, 2012, 2:40pm UTC](https://www.ruby-forum.com/t/context-free-grammar-infinite-loop/223944/1 "2012-10-24T14:40:50Z")
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](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 [xkcd: Computational Linguists](http://xkcd.com/114/) ---
**Author:** ![apprendistastregone](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/a/7ea924/32.png) [@apprendistastregone](https://www.ruby-forum.com/u/apprendistastregone)\ **Post date:** [October 24, 2012, 8:06pm UTC](https://www.ruby-forum.com/t/context-free-grammar-infinite-loop/223944/2 "2012-10-24T20:06:27Z")
2012/10/24 Davide R. [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid): > 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](http://riffraff.blogsome.com) work: [circleme.com](http://circleme.com) ---
**Author:** ![apprendistastregone](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/a/7ea924/32.png) [@apprendistastregone](https://www.ruby-forum.com/u/apprendistastregone)\ **Post date:** [October 25, 2012, 2:35pm UTC](https://www.ruby-forum.com/t/context-free-grammar-infinite-loop/223944/3 "2012-10-25T14:35:45Z")
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://rubygems.org/gems/llip) > **[GitHub - mcollina/llip: The LL(k) Interpreted Parser (llip) is an automated...](https://github.com/mcollina/llip)** > > The LL(k) Interpreted Parser (llip) is an automated tool to easily create an LL(k) parser and the related scanner without the need of generating anything. Everything is done on the fly through a si... Siccome vi interessa ve la linko 🙂 Il codice tutto open, e se a qualcuno interessa l’approccio alla metaprogrammazione, molto divertente :). Matteo ---
**Author:** ![apprendistastregone](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/a/7ea924/32.png) [@apprendistastregone](https://www.ruby-forum.com/u/apprendistastregone)\ **Post date:** [October 25, 2012, 3:40pm UTC](https://www.ruby-forum.com/t/context-free-grammar-infinite-loop/223944/4 "2012-10-25T15:40:06Z")
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 ---
**Author:** ![apprendistastregone](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/a/7ea924/32.png) [@apprendistastregone](https://www.ruby-forum.com/u/apprendistastregone)\ **Post date:** [October 25, 2012, 5:02pm UTC](https://www.ruby-forum.com/t/context-free-grammar-infinite-loop/223944/5 "2012-10-25T17:02:29Z")
Il giorno 25 ottobre 2012 15:39, Davide R. [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid)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