View Full Version : [java] riconoscitore linguaggio di programmazione
Buongiorno a tutti. Per un progetto devo realizzare un riconoscitore di linguaggi di programmazione (C, Java, Python almeno). Come input ho il codice sorgente...
come posso fare? o meglio, io preso il codice sorgente, analizzo il lessico, ma come faccio a trovare delle peculiarità fra questi 3 linguaggi in modo efficiente così da riconoscerli in maniera abbastanza stabile?
banryu79
15-10-2010, 13:41
Problema interessante, non ci avevo mai pensato.
In pratica hai un problema di pattern-matching: dato un testo, riconoscere se quel testo rispsetta la sinatssi e la grammatica di uno dei linguaggi formali (Python, Java, C).
Se si potesse, basterebbe passare il testo alle N implementazioni di parser per i rispettivi N linguaggi e analizzare il risultato (n. errori di sintassi incontrati, porzione di testo valido prima del primo errore: questo nel caso il parsing fallisse in tutti e tre i casi; l'aspettativa è che almeno uno riesca).
Purtroppo io non so aiutarti, ma qui nel forum ci sono degli esperti che potrebbero fornirti delle buone idee.
Ciao :)
wingman87
15-10-2010, 13:58
Se si potesse, basterebbe passare il testo alle N implementazioni di parser per i rispettivi N linguaggi e analizzare il risultato (n. errori di sintassi incontrati, porzione di testo valido prima del primo errore: questo nel caso il parsing fallisse in tutti e tre i casi; l'aspettativa è che almeno uno riesca).
Stessa cosa che è venuta in mente a me.
Se scarichi JavaCC c'è inclusa tra gli esempi la grammatica java da cui generare il parser, per gli altri 2 linguaggi credo si possa trovare.
Umh... chissà cosa succede poi se gli dai in pasto uno di questi... http://en.wikipedia.org/wiki/Polyglot_(computing)
banryu79
15-10-2010, 14:06
Umh... chissà cosa succede poi se gli dai in pasto uno di questi... http://en.wikipedia.org/wiki/Polyglot_(computing)
OMG :eekk:
Se si potesse, basterebbe passare il testo alle N implementazioni di parser per i rispettivi N linguaggi e analizzare il risultato (n. errori di sintassi incontrati, porzione di testo valido prima del primo errore: questo nel caso il parsing fallisse in tutti e tre i casi; l'aspettativa è che almeno uno riesca).
vabbè, a sto punto prendo il nome del file sorgente, cerco il punto, ed esamino l'estensione... ^^
vabbè... io pensavo invece di fare 3 mappe, una per ciascun linguaggio di programmazione, contenente tutte le parole dei 3 linguaggi. esamino le prime 100 parole del file sorgente (togliendo commenti, "", () e tutte quelle robe là), e faccio una stima della percentuale corretta...
quello con percentuale maggiore è il più probabile... il problema è che sarebbe parecchio pesante, e poco stabile!
banryu79
15-10-2010, 14:13
...
quello con percentuale maggiore è il più probabile... il problema è che sarebbe parecchio pesante, e poco stabile!
Parecchio pesante penso di no, perchè dici?
Se con "stabile" intendi che produce risultati poco accurati/affidabili, sono d'accordo.
Stessa cosa che è venuta in mente a me.
Se scarichi JavaCC c'è inclusa tra gli esempi la grammatica java da cui generare il parser, per gli altri 2 linguaggi credo si possa trovare.
Potrebbe essere un buon approccio? Magari verrebbe fuori qualcosa di carino.
vabbè, a sto punto prendo il nome del file sorgente, cerco il punto, ed esamino l'estensione... ^^
Potrebbe anche essere un'idea :P ma se in input invece di un file hai uno stream di caratteri? Ti attacchi :D
Parecchio pesante penso di no, perchè dici?
Se con "stabile" intendi che produce risultati poco accurati/affidabili, sono d'accordo.
Potrebbe essere un buon approccio? Magari verrebbe fuori qualcosa di carino.
bè, più pesante che non un parser! e comunque meno affidabile...
il punto è che non penso di poter scrivere il codice del parser...
banryu79
15-10-2010, 14:24
bè, più pesante che non un parser! e comunque meno affidabile...
il punto è che non penso di poter scrivere il codice del parser...
Il parser non lo devi mica per forza implementare a mano.
Ti appoggi a un generatore di parser.
Un generatore di parser fa quello che il suo nome suggerisce: gli dai una grammatica in pasto, e lui ti sputa il parser ad hoc.
Il tuo problema diverrebbe quindi quello di specificare le tre grammatiche dei tre linguaggi nel formato accettato come input dallo specifico generatore di parser a cui ti appoggi.
Fai un giro sul web e prova a leggerti qualcosa su JavaCC e Yacc.
Poi torna qua, magari qualche esperto si fa vivo (so che qualcuno qui ha avuto esperienze con questi tools) ;)
c'e una libreria java ( jmimemagic (http://sourceforge.net/projects/jmimemagic/) ) che individua il mime type dei file che potrebbe fare al caso tuo, nn so però se sa riconoscere il sorgente oppure il compilato
Auguri :D
ho avuto un'idea: sto facendo una selezione delle varie keywords dei tre linguaggi:
http://www.lattecafe.net/java/articoli/javakeyword.htm
http://it.wikipedia.org/wiki/C_(linguaggio)#Parole_chiave
http://docs.python.org/release/2.3.5/ref/keywords.html
di modo da eliminare quelle che ci sono in tutti e 3 i linguaggi di programmazione. Sucessivamente pensavo di fare una ricerca nel file sorgente di alcune di queste, procedendo ad eliminare le alternative, determinando quale potrebbe essere il linguaggio di programmazione con il quale è stato scritto il codice sorgente.
Questo ovviamente con l'ipotesi che sia stato messo in input almeno uno dei tre linguaggi.
Poi devo varare alcune strategie per gestire frammenti di codice tipo:
"{}";
" ";
etc...
è meno pesante che compilarli tutti e 3, un po' impreciso, ma dovrebbe funzionare, che dite?? altre proposte?
banryu79
15-10-2010, 16:46
è meno pesante che compilarli tutti e 3, un po' impreciso, ma dovrebbe funzionare, che dite?? altre proposte?
Guarda che fare il parsing di un sorgente non significa compilarlo.
Guarda che fare il parsing di un sorgente non significa compilarlo.
sì, bè... intendevo quello per compilare ^^...
dici che potrebbe funzionare come metodo comunque?
Vincenzo1968
15-10-2010, 17:40
edit
banryu79
15-10-2010, 17:58
dici che potrebbe funzionare come metodo comunque?
Immagino dipenda cosa tu intendi per "funzionare".
Procediamo con ordine: lo scopo è implementare un "riconoscitore di linguaggio".
Io un "riconoscitore di linguaggio" lo intendo così:
Input: uno stream di caratteri (del testo) arbitrario.
Output: una stringa che contenga il testo "sconosciuto" se l'input non appartiene a uno degli N linguaggi supportati dal riconoscitore, oppure una stringa che contenga il nome del linguaggio riconosciuto.
Già questo implica che bisogna definire i termini secondo i quali un dato testo T viene considerato come codice sorgente valido per il dato linguaggio L(T) e i termini secondo i quali non è considerato come un codice sorgente valido.
Ad esempio: il riconoscitore riconoscerà solo sorgenti sintatticamente validi? Oppure riconoscerà anche sorgenti contenenti errori di sintassi?
Come valuti se un testo arbitrario T è un codice sorgente valido, scritto in un dato linguaggio L? La risposta ovvia (dato che i linguaggi di programmazione sono linguaggi formali) sarebbe verificare se T è ben formato rispetto la grammatica di L.
Però nulla ti vieta di usare un qualsiasi approccio ti permetta di risolvere il tuo problema; solo che risolvere il problema significa soddisfare i requisiti del problema dunque (secondo me) dovresti prima interrogarti su quali siano i requisiti da soddisfare (che o ti sono stati dati, o puoi scegliere tu).
Altrimenti è difficile dirti qualcosa di concreto, almeno per me.
Secondo me servono i 3 parser dei 3 linguaggi di programmazione, in particolare una soluzione forse "banale" sarebbe quella di richiamare ed appoggiarti direttamente ai 3 compilatori e farti ritornare il risultato della compilazione.
Comunque pensandoci un po' credo che ognuno di quei 3 linguaggi ha caratteristiche peculiari che possono aiutarti.
Ad esempio un file Java ha sicuramente la keyword class e già da questo puoi fare delle ipotesi.
Un file C potrebbe avere delle direttive #include e comunque sicuramente ci sono delle parentesi graffe a delimitare i blocchi di codice (cosa che python non ha).
In ogni caso il codice C deve essere all'interno di una funzione, non può essere scritto a se stante, specialmente se è costituito da un solo file ci deve essere un main da qualche parte.
Questi tuttavia sono metodi "euristici" che possono servire più per andare ad esclusione. Se il tuo obiettivo è dire se un dato testo è un programma Java funzionante, allora non vedo altro modo che darlo in pasto al suo compilatore.
Se invece ti concentri solo sulle keyword puoi solamente dire che il file di testo contiene determinate keyword, ma non è detto che poi il contenuto del file di testo sia un programma funzionante.
Se invece ti concentri solo sulle keyword puoi solamente dire che il file di testo contiene determinate keyword, ma non è detto che poi il contenuto del file di testo sia un programma funzionante.
sì, ma non ho direttive in merito... Quindi penso sia lecito supporre che l'input dato sia funzionante in uno dei tre linguaggi. Per avere comunque maggiore solidità dovrei aggiungere un controllo sintattico, ma a questo punto davvero do in pasto a tutti e tre i compilatori. Dunque creo farò così:
1. controllo di estensione del file sorgente. (se mi viene dato un file .java, so che è scritto in java, anche se non compila)
2. riduco il codice così da ottenere una lista di parole "chiave";
3. inserisco le parole chiave "uniche" (quelle che si usano solo in uno dei 3 linguaggi) in 3 liste (rispettivamente java, c, python);
4. effettuo la ricerca delle parole delle 3 liste nell'elenco ottenuto dall'input;
5. Il programma da comunque una stima di quale sia il linguaggio che con maggior probabilità è stato utilizzato, per aggior completezza bisognerebbe creare anche un analizzatore sintattico.
punti deboli:
a. non è molto sicuro, ma da un'idea generale;
b. se viene messo in input un linguaggio sconosciuto, potrebbe uscire in output uno dei tre linguaggi;
c. classifica frammenti di codice non compilabili;
Non è tanto diverso dal capire in che lingua è scritto un documento di testo. Usa NGramJ http://ngramj.sourceforge.net/. Cancelli i profili per le lingue e ci metti i tuoi per linguaggi di programmazione ed hai finito. Per capire come creare profili ed aggiungerli alla lista leggi questo: http://blog.afterthedeadline.com/2010/02/08/n-gram-language-guessing-with-ngramj/
Ho fatto una prova veloce con solo java e php:
java -jar cngram.jar -lang2 shared.make_timestamp.php
speed: php:0.857 java:0.000 --:0.143 .. java:0.000 |0.0E0 |0.0E0 dt=1676
java -jar cngram.jar -lang2 CharTrie.java
speed: java:0.970 php:0.000 --:0.030 .. php:0.000 |0.0E0 |0.0E0 dt=3055
Con profili creati da corpus da circa 100k è già molto preciso a dire quale linguaggio è.
banryu79
16-10-2010, 12:54
Non è tanto diverso dal capire in che lingua è scritto
un documento di testo. Usa NGramJ http://ngramj.sourceforge.net/...
Fico. Questo è un approccio "smart" :D
l'idea sarebbe comunque che io trovi un metodo efficiente per risolvere un problema, senza "commissionarlo troppo" a pacchetti o software esterni...
Beh i parser dei linguaggi di programmazione in genere vanno in ordine O(n), quindi se commissioni ai compilatori la questione impieghi al più O(3n), che è sempre O(n).
Comunque chiederei a chi t'ha commissionato questa cosa se basta una stima probabilistica sulla base delle keyword oppure ha bisogno di saperlo con esattezza e questo implicherebbe controllare che il codice nel documento sia ben formato (ovvero rispetti i canoni semantici e sintattici di quel linguaggio).
Ora dato che mi sembra assurdo mettersi a rifare i parser LR1 per le grammatiche di quei 3 linguaggi, è evidente che nel secondo caso si passa direttamente a dare in pasto il file ai vari compilatori.
Anche se questa soluzione mi sembra troppo banale (ma di fatto è un modo, per altro neanche così pessimo, per risolvere il problema).
Onestamente se il progetto chiede solamente di creare un programma che riesca differenziare file sorgenti di java, c e python io eviterei di spaccarmi la testa a fare qualcosa di veramente generale (che richiederebbe uno sforzo e spropositato) e mi fermerei solamente alle differenze tra questi linguaggi. Ad esempio in python le parentesi graffe {} sono piuttosto rare (dizionari sicuramente, così al volo non mi ricordo altri usi ma forse ce ne sono) e quindi possono essere usate come ottimo discriminante per sorgenti python e sorgenti di linguaggi c-like. Inoltre, se non sbaglio (ho studiato java pochissimo, scusate se scrivo castronerie), qualunque definizione di metodi e variabili deve essere fatta all'interno di classi o interfacce e quindi da qualche parte in un file sorgente di java ci dovrà essere la keyword class e/o interface che in c non sono keyword. Basta solamente stare attenti e scrivere un parser che si renda conto del contesto in cui quelle keyword sono utilizzate e il tutto dovrebbe funzionare. Ovviamente bisogna probabilmente raffinare un po' le cose: in c potrei fare un #define class something oppure potrei aver definito class e interface in un header incluso ecc ecc.
Tutta questa tirata solo per dare il mio consiglio (:p ): concentrati sulle differenze tra i linguaggi che ti sono stati richiesti, non esagerare con la generalità (premature generalization is the root of all evil, per parafrasare knuth)
vBulletin® v3.6.4, Copyright ©2000-2025, Jelsoft Enterprises Ltd.