[Generale] Multithreaded parsing

[Opcode]

Salve a tutti,

dato il crescente numero di core degli attuali processori, l'uso dei threads si stà sempre più diffondendo per via dei vantaggi che non starò qui ad elencare (eccezione per Python che per inciso adoro :P).

Mi chiedevo quindi, durante una normale procedura di parsing, secondo voi, si può fare uso di multithreading per eseguire in modo concorrenziale sia il lexer che il parser vero e proprio?

Mi viene in mente una soluzione di parsing predittivo in cui lo scanner comunica con il parser tramite l'inserzione dei simboli in una tabella anzichè usare la più classica get_next_token() direttamente quando il parser ha bisogno di un nuovo token.

Ho letto sul web qualche articolo in inglese che però parlava di parsing concorrenziale non di eseguire assieme scanner e parser.
Mi vengono però in mente un paio di casi in cui sarebbe necessario usare un semaforo per impedire ai due thread di entrare in conflitto su certi dati, per esempio, il parser finisce di analizzare i token e ne richiede uno nuovo che lo scanner stà inserendo... Insomma, non sarebbe certo facile come un parser normale, ma appunto, potrebbe secondo voi costituire una alternativa per migliorare le prestazioni di parsing?

Ps. ho visto più indietro (parecchio), un topic riguardante un contest di parsing, ma pare morto li!?!

Grazie a tutti,
Lex

[cdimauro]

Potresti usare un approccio del tipo produttore -> consumatore, col thread del lex che produce i token, e quello del parser che li consuma.

Ci sono però due problemi con questo approccio. Il primo è che per sincronizzarli devi usare roba come lock et similia, che riduce le prestazioni del sistema.

Il secondo, più grave, è che quest'approccio funziona soltanto con parser che non sono sensibili al contesto. Quindi se il tuo lexer produce token che non dipendono dal contesto, allora sei a posto, altrimenti non puoi utilizzarlo.

[!fazz]

Originariamente inviato da cdimauro

Potresti usare un approccio del tipo produttore -> consumatore, col thread del lex che produce i token, e quello del parser che li consuma.

Ci sono però due problemi con questo approccio. Il primo è che per sincronizzarli devi usare roba come lock et similia, che riduce le prestazioni del sistema.

Il secondo, più grave, è che quest'approccio funziona soltanto con parser che non sono sensibili al contesto. Quindi se il tuo lexer produce token che non dipendono dal contesto, allora sei a posto, altrimenti non puoi utilizzarlo.

praticamente quasi la mia tesi della triennale anni e anni fà

[Opcode]

Originariamente inviato da cdimauro

Potresti usare un approccio del tipo produttore -> consumatore, col thread del lex che produce i token, e quello del parser che li consuma.

E' esattamente quello che pensavo, ma non avendo trovato molto in questa direzione, prima di provare per incappare nella eventuale impossibilità di realizzazione ho preferito chiedere.

Originariamente inviato da cdimauro

Ci sono però due problemi con questo approccio. Il primo è che per sincronizzarli devi usare roba come lock et similia, che riduce le prestazioni del sistema.

Il secondo, più grave, è che quest'approccio funziona soltanto con parser che non sono sensibili al contesto. Quindi se il tuo lexer produce token che non dipendono dal contesto, allora sei a posto, altrimenti non puoi utilizzarlo.

Si, il parser genera token context-free. E' più che altro a scopo didattico e con la scusa spero di ricavarci un piccolo linguaggio da poter usare per configurazioni varie.

Hai per caso qualche riferimento che descriva più approfonditamente problemi e soluzioni (eventuali) legate a questo tipo di parsing?

Mille grazie per la risposta,
Ciao.

[marco.r]

Originariamente inviato da cdimauro

Ci sono però due problemi con questo approccio. Il primo è che per sincronizzarli devi usare roba come lock et similia, che riduce le prestazioni del sistema.

Trattandosi di un algoritmo non intrinsecamente parallelo dubito che si possa fare altrimenti.
Detto questo non so se ne valga la pena, molto piu' semplice compilare piu' unita' in parallelo...

[Opcode]

Originariamente inviato da marco.r

Trattandosi di un algoritmo non intrinsecamente parallelo dubito che si possa fare altrimenti.
Detto questo non so se ne valga la pena, molto piu' semplice compilare piu' unita' in parallelo...

Non sai se ne vale la pena perchè non credi ce ne sia un beneficio in termini prestazionali, o per altro?

Ciao.

[marco.r]

Originariamente inviato da Opcode

Non sai se ne vale la pena perchè non credi ce ne sia un beneficio in termini prestazionali, o per altro?

Ciao.

Intendo dire che di solito un programma che non sia banale e' diviso in piu' moduli indipendenti, ed e' piu' facile far partire N esecuzioni diverse in parallelo che non parallelizzare il compilatore stesso. Quando programmo in C++ uso il gcc che non e' parallelo ma questo non mi vieta di riuscire ad usare tutti e quattro i core della macchina.

[gugoXX]

Quoto. La compilazione di un file e' cosa breve. Inutile parallelizzare la compilazione singola. Meglio invece istanziare piu' compilatori per compilare piu' file in parallelo, cosa che viene gia' fatta da parecchi tool.

Diverso invece sarebbe pensare di parallelizzare il parsing di un file XML per costruirne l'albero. Ci sono mostri di XML in giro per i quali potrebbe valerne la pena.
Ma tipicamente questi problemi hanno sempre un canale seriale da qualche parte, (es scarico il file XML da rete) e il collo di bottiglia e' quasi sempre li' piuttosto che nel processamento, che e' di per se banale.

[cdimauro]

Originariamente inviato da Opcode

Hai per caso qualche riferimento che descriva più approfonditamente problemi e soluzioni (eventuali) legate a questo tipo di parsing?

Francamente no. E' passato parecchio tempo da quando ho studiato i parser (ti consiglio "The Dragon Book", che è la "bibbia" in materia), e la soluzione che ti ho fornito prima non riguarda nemmeno i parser veri e propri, ma ho semplicemente applicato il classico pattern del produttore / consumatore (nemmeno potevo immaginare che fosse stato oggetto della tesi di "qualcuno" ).

Per il resto, concordo con quanto hanno scritto gli altri.

Originariamente inviato da marco.r

Trattandosi di un algoritmo non intrinsecamente parallelo dubito che si possa fare altrimenti.

Se la grammatica è context-free, come ha già detto, credo che lexer e parser abbiano buone probabilità di essere implementati in thread separati e "paralleli" (anche se rimane il problema della sincronizzazione, appunto).

Detto questo non so se ne valga la pena, molto piu' semplice compilare piu' unita' in parallelo...

Perfettamente d'accordo. E' la soluzione migliore e la più comoda (praticamente a costo zero).

[Opcode]

Originariamente inviato da marco.r

Intendo dire che di solito un programma che non sia banale e' diviso in piu' moduli indipendenti, ed e' piu' facile far partire N esecuzioni diverse in parallelo che non parallelizzare il compilatore stesso. Quando programmo in C++ uso il gcc che non e' parallelo ma questo non mi vieta di riuscire ad usare tutti e quattro i core della macchina.

Chiarissimo.

Originariamente inviato da gugoXX

Diverso invece sarebbe pensare di parallelizzare il parsing di un file XML per costruirne l'albero. Ci sono mostri di XML in giro per i quali potrebbe valerne la pena.
Ma tipicamente questi problemi hanno sempre un canale seriale da qualche parte, (es scarico il file XML da rete) e il collo di bottiglia e' quasi sempre li' piuttosto che nel processamento, che e' di per se banale.

E se il parser fosse il front-end di un interprete anzichè di un compilatore?
Non puoi eseguire più interpreti per eseguire uno stesso programma (singolo processo). Poi è chiaro che anche gli interpreti si possano lanciare in parallelo ma non beneficia di aumento di prestazioni.

Originariamente inviato da cdimauro

Francamente no. E' passato parecchio tempo da quando ho studiato i parser (ti consiglio "The Dragon Book", che è la "bibbia" in materia), e la soluzione che ti ho fornito prima non riguarda nemmeno i parser veri e propri, ma ho semplicemente applicato il classico pattern del produttore / consumatore (nemmeno potevo immaginare che fosse stato oggetto della tesi di "qualcuno" ).

Ti ringrazio, andrò a cercarne una copia cartacea e, in caso di fallimento, cercherò l'ebook.

Originariamente inviato da cdimauro

Per il resto, concordo con quanto hanno scritto gli altri.

Se la grammatica è context-free, come ha già detto, credo che lexer e parser abbiano buone probabilità di essere implementati in thread separati e "paralleli" (anche se rimane il problema della sincronizzazione, appunto).

Ciononostante la cosa devo ammettere che mi intriga, proprio per questa difficoltà di implementazione. Mi piace fare qualcosa di inusuale (ma non inutile), soprattutto per ricerca.

Originariamente inviato da cdimauro

Perfettamente d'accordo. E' la soluzione migliore e la più comoda (praticamente a costo zero).

Mi ripeto, è se fosse il front-end di un interprete?

Grazie a tutti per l'interesse.

[marco.r]

Originariamente inviato da Opcode

E se il parser fosse il front-end di un interprete anzichè di un compilatore?
Non puoi eseguire più interpreti per eseguire uno stesso programma (singolo processo). Poi è chiaro che anche gli interpreti si possano lanciare in parallelo ma non beneficia di aumento di prestazioni.

Qui potresti avere qualche vantaggio (anche se secondo me non troppo elevato).
In questo caso potresti procedere con la strategia suggerita da cdimauro, se procedi in modo intelligente la quantita' di lavoro in piu' non e' improponibile.

[cdimauro]

Originariamente inviato da Opcode

Ti ringrazio, andrò a cercarne una copia cartacea e, in caso di fallimento, cercherò l'ebook.

Se non trovi una copia del Dragon Book ti offro una cena.

Poi io preferisco nettamente il cartaceo, se posso.

Ciononostante la cosa devo ammettere che mi intriga, proprio per questa difficoltà di implementazione. Mi piace fare qualcosa di inusuale (ma non inutile), soprattutto per ricerca.

Considera che di già lexer e parser sono legati da un rapporto "produttore -> consumatore". Poi con parser come ANTLR questo rapporto lo trovi esplicitato.

Non so a quali tecnologie e linguaggio ti stai affidando per realizzare il tutto, ma può darsi che non dovrai sbatterti più di tanto nell'impresa.

[Opcode]

Originariamente inviato da marco.r

Qui potresti avere qualche vantaggio (anche se secondo me non troppo elevato).

Come sospettavo, comunque è a scopo didattico non mi serve per un ambiente di produzione. Semplicemente mi piace fare ricerca e test, non si sà mai quel che viene fuori, senza contare l'interesse della scoperta.

Originariamente inviato da cdimauro

Se non trovi una copia del Dragon Book ti offro una cena.

Beh, se dovessi accidentalmente dimenticarmi come si usa google, dove stanno le librerie e dovessi cercare nella mia libreria in casa...

dove ci incontriamo?

Poi io preferisco nettamente il cartaceo, se posso.

Quoto. Passo già parecchie ore al PC, nonostante stia solo su schermi LCD con la luminosità al minimo la sera, col calar delle tenebre non vedo poi molto al buio. E poi, l'odore di un libro nuovo è sconosciuto agli ebook...

Considera che di già lexer e parser sono legati da un rapporto "produttore -> consumatore". Poi con parser come ANTLR questo rapporto lo trovi esplicitato.

Si ho avuto modo di vedere ANTLR ma ammetto di non averlo mai usato... da quello che vedo sembra una pacchia da usare...

Non so a quali tecnologie e linguaggio ti stai affidando per realizzare il tutto, ma può darsi che non dovrai sbatterti più di tanto nell'impresa.

Libri e reference in primis, non essendo un lavoro ma mera ricerca (da usare casomai in un futuro interprete che dovrò realizzare) ho totale libertà di scelta... Comunque penso di affidarmi ai più classici C/C++, o qualche linguaggio che semplifichi il tutto, magari Python.

[cdimauro]

Originariamente inviato da Opcode

Beh, se dovessi accidentalmente dimenticarmi come si usa google, dove stanno le librerie e dovessi cercare nella mia libreria in casa...

dove ci incontriamo?

A Catania.

Si ho avuto modo di vedere ANTLR ma ammetto di non averlo mai usato... da quello che vedo sembra una pacchia da usare...

Togli pure il sembra.

Libri e reference in primis, non essendo un lavoro ma mera ricerca (da usare casomai in un futuro interprete che dovrò realizzare) ho totale libertà di scelta... Comunque penso di affidarmi ai più classici C/C++, o qualche linguaggio che semplifichi il tutto, magari Python.

Togli il magari.

Ho già realizzato qualcosa con ANTLR & Python, e mi sono trovato benissimo. Poi ANTLR ha un ottime IDE, ANTLRWork, che ti permette di sviluppare grammatiche (e parser annessi) molto comodamente.

[Opcode]

Originariamente inviato da cdimauro

A Catania.

Uhm... viaggio compreso con la cena? (sono 1.400 e rotti km)
Vabbè non vorrei sembrare uno scroccone, il viaggio ce lo metto io. E' un'occasione per fare una vacanza.

Togli pure il sembra.

Togli il magari.

Mi stai intrigando...

Ho già realizzato qualcosa con ANTLR & Python, e mi sono trovato benissimo.

Come darti torto, Python è il mio linguaggio ideale e come tale lo è anche in ambito di ricerca (senza eguali). Poi da quello che dici...

Poi ANTLR ha un ottime IDE, ANTLRWork, che ti permette di sviluppare grammatiche (e parser annessi) molto comodamente.

Ne ho sentito parlare più volte molto positivamente, mi verrebbe da asserire che sia questo il motivo del suo successo rispetto ad altri tool (vedi yacc bison e compagnia bella)... ma non ho usato mai nemmeno quelli, anche se, dalle documentazioni che studiai all'epoca è tutta un'altra storia rispetto ad ANTRL.

[cdimauro]

Originariamente inviato da Opcode

Uhm... viaggio compreso con la cena? (sono 1.400 e rotti km)
Vabbè non vorrei sembrare uno scroccone, il viaggio ce lo metto io. E' un'occasione per fare una vacanza.

La Sicilia merita.

Come darti torto, Python è il mio linguaggio ideale e come tale lo è anche in ambito di ricerca (senza eguali). Poi da quello che dici...

Ne ho sentito parlare più volte molto positivamente, mi verrebbe da asserire che sia questo il motivo del suo successo rispetto ad altri tool (vedi yacc bison e compagnia bella)... ma non ho usato mai nemmeno quelli, anche se, dalle documentazioni che studiai all'epoca è tutta un'altra storia rispetto ad ANTRL.

Mettiamola così: ANTLR è il Python dei generatori di parser. Sintassi semplice ed elegante, genera codice molto facile anche da leggere e debuggare, ed è enormemente produttivo.

Un altro punto di forza è che il lexer e il parser li scrivi nello stesso linguaggio e anche nello stesso file. Un altro è che invece del parser puoi direttamente fargli generare (sempre con lo stesso linguaggio) l'AST delle espressioni parserizzate; così salti pure questa fase, che negli altri parser tipo YACC & co. dev'essere fatta generalmente a manina.

[Opcode]

Originariamente inviato da cdimauro

La Sicilia merita.

Non ne dubito. Se avrò l'occasione di venirci ti avviso, potrei offrirla anche io una cena, il posto lo scegli tu però (con tutte le responsabilità del caso )

Mettiamola così: ANTLR è il Python dei generatori di parser. Sintassi semplice ed elegante, genera codice molto facile anche da leggere e debuggare, ed è enormemente produttivo.

Un altro punto di forza è che il lexer e il parser li scrivi nello stesso linguaggio e anche nello stesso file. Un altro è che invece del parser puoi direttamente fargli generare (sempre con lo stesso linguaggio) l'AST delle espressioni parserizzate; così salti pure questa fase, che negli altri parser tipo YACC & co. dev'essere fatta generalmente a manina.

Ah però. Dell'AST non ne ero a conoscenza... a questo punto anche solo a tempo perso (anche se penso di potergli dedicare un po' di spazio) è da provare. La curiosità e la voglia non mancano... se non sono richiesti requisiti, sono in rotta.

[cdimauro]

Purtroppo su Wikipedia si trova poco sugli AST, per cui ti consiglio di studiare l'argomento sul libro che t'ho consigliato.

Qui trovi un'introduzione ad ANTLR "in 5 minuti". Mentre qui un esempio un po' più complesso, di una calcolatrice, in cui viene mostrato anche come far generare direttamente un AST, e un parser che lo "scorre".

Tra l'altro ho scoperto adesso dal sito che l'ha usato Google nel suo App Engine.

P.S. Allora ti aspetto.

[Opcode]

Originariamente inviato da cdimauro

Purtroppo su Wikipedia si trova poco sugli AST, per cui ti consiglio di studiare l'argomento sul libro che t'ho consigliato.

Già, gli AST li studiai, anche se molto alla veloce, su una dispensa universitaria, per poi passare subito al Three Address Code
Comprerò quanto prima il libro che mi hai consigliato, non vedo l'ora di averlo sotto mano per iniziare a divorarlo.

Qui trovi un'introduzione ad ANTLR "in 5 minuti". Mentre qui un esempio un po' più complesso, di una calcolatrice, in cui viene mostrato anche come far generare direttamente un AST, e un parser che lo "scorre".

Perfetto! il secondo sembra interessante, strano che ieri spulciando non l'abbia trovato... grazie mille per il link.

Tra l'altro ho scoperto adesso dal sito che l'ha usato Google nel suo App Engine.

Allora ti ho battuto io l'ho scoperto tanto tanto tempo fà.... circa.... ieri sera.

P.S. Allora ti aspetto.

ottimo

Guarda un po' cosa ho trovato, magari li hai già visti, ma:
1 - The Language from the Dragon Book in ANTLR
2 - Automate translation of Java to Python

[cdimauro]

No, non li avevo mai visti. Appena ho un po' di tempo mi smazzo il PDF (l'altro l'ho già letto, ed è una bella esperienza ).

Grazie!