View Full Version : [Vari] Automi a stati finiti, linguaggi, calcolabilità. Aspetti teorico-pratici.
Vincenzo1968
19-01-2013, 22:54
Avrei bisogno di un chiarimento su alcuni aspetti teorico-pratici relativi agli automi a stati finiti.
L'argomento m'appassiona assai ma, non avendo fatto l'università, mi trovo un po' in difficoltà.
chi m'illumina?
Avrei parecchie domande ma comincio con una sola, questa:
Per sapere se una grammatica è di tipo LL(1) ci sono i ben noti algoritmi. Ora, avrei bisogno d'implementare l'algoritmo che costruisce la tabella LL(1) per una data grammatica. Cioè, leggo la grammatica da un file di testo(tipo i file .y di Bison), e automaticamente costruisco la tabella LL(1).
Se la tabella, per una data locazione, contiene più di una regola grammaticale, la grammatica non è, come ben sapete, una grammatica LL(1).
In caso contrario posso utilizzare la tabella appena creata per generare un parser di tipo predittivo non ricorsivo.
Ragazzi, lo so che di generatori di parser se ne trovano a dozzine in rete, ma io voglio implementarne uno da me. E poi di generatori di parser LL(1) non ricorsivi non ce ne sono molti. Il più famoso, Antlr(bellissimo, favoloso!), prende in ingresso una grammatica LL(1) ma genera un parser a discesa ricorsiva.
Comunque per il momento m'interessa partire dal file di testo con la grammatica e creare la tabella LL(1). Per la generazione del parser poi si vedrà.
Non voglio il codice già pronto ovviamente, ma suggerimenti, tecniche, metodi, algoritmi.
Chi mi da una mano?
Poi avrei altre domande di ordine più teorico sugli automi a stati finiti, le macchine di Turing e la calcolabilità. Ma intanto cominciamo con questa.
puoi anche seguire un corso universitario che tratti la materia di tuo interesse se lo desideri e senza necessariamente iscriversi e dare esami ;)
Trattazioni così teoriche vengono fatte nel forum Scienza e Tecnica: qui solo cose pratiche :D
Vincenzo1968
20-01-2013, 10:13
No ma questa mia prima domanda è cosa pratica. Devo implementare un programmino che prende in input una grammatica e genera la tabella LL(1).
chiedi ad un tecnico di laboratorio che insegna linguaggi formali ed automi.
Mi era capitato di scrivere per chiedere lumi ad un docente di informatica della sapienza, se non ricordo male, circa un suo algoritmo e mi aveva risposto senza difficoltà: scrivi ad uno di loro.
Io una dritta te l'ho data ;)
Vincenzo1968
20-01-2013, 11:17
Grazie per la dritta. ;)
Io un programmino simile lo sto già scrivendo(e funziona anche :D ).
Volevo confrontarmi con voi per vedere se sto agendo nella maniera corretta o se ci sono algoritmi più adatti, metodi più indicati.
Non ne conosco tecnici di laboratorio che insegnano linguaggi formali.
occhio a come ti esprimi perchè di sgamano subito, è una prof ;)
[email protected]
Vincenzo1968
20-01-2013, 11:36
Questa non l'ho capita. Come dovrei esprimermi? E chi dovrebbe sgamarmi? E cosa dovrebbero sgamare? :confused:
Spiego cosa ho fatto finora:
Ho in ingresso questo file:
expr : term expr1;
expr1 : '+' term expr1;
expr1 : ;
term : factor term1;
term1 : '*' factor term1;
term1 : ;
factor : '(' expr ')';
factor : T_ID;
Il mio programma produce in output il seguente file html:
http://img341.imageshack.us/img341/674/gt01h.jpg
http://img502.imageshack.us/img502/8186/gt02.jpg
Purtroppo il programmino che ho scritto seguendo gli algoritmi nei testi(in particolare sull'Hopcroft) non funziona con grammatiche che contengono regole di produzione mutualmente ricorsive.
Come si può risolvere la cosa?
se fai domande assurde non ti rispondono, più chiaro così ? :D
p.s.
a me non interessa il mondo dei compilatori ma solo quello delle reti neurali per il semplice fatto che di compilatori ve ne sono almeno 2500 mentre le reti neurali sono un campo ancora tutto da esplorare. Se poi penso che implica la conoscenza delle equazioi differenziali che non ho messo in pratica durante i miei studi credo sia la volta buona per cavarci qualcosa. Ad ognuno le proprie passioni.
;)
Vincenzo1968
20-01-2013, 11:43
No, non ho capita nemmeno questa. Che domande assurde?
Ho bisogno di un algoritmo(algoritmo, non il codice già bell'e pronto) per risolvere la faccenda con le grammatiche mutualmente ricorsive. Tutto qui.
EDIT: purtroppo nei testi che ho consultato non c'è niente in proposito. E nemmeno in rete sono riuscito a trovare qualcosa.
Fanno tutti il solito esempietto con piccole grammatiche e buona notte.
Voglio dire, se ho questa grammatica in input:
A : B A a
|
;
B : b B c
| A A
;
Come la risolvo la faccenda?
queste persona fanno corsi e spiegano a modo loro i vari argomenti. Se fai loro una richiesta dimostrando di non conoscere per nulla l'argomento e ti assicuro che lo capiscono al volo, non ti rispondono. Stai quindi sulle genreali, magari qualcosa ti dicono.
fine dei consigli ;)
Vincenzo1968
20-01-2013, 11:50
A me pare di conoscerlo abbastanza bene l'argomento. Ho solo qualche difficoltà su un punto in particolare: le grammatiche con regole di produzione mutuamente ricorsive.
Ne hai algoritmi da suggerire? Se l'argomento non ti appassiona puoi lasciare stare eh!
Ciao :)
Vincenzo1968
20-01-2013, 12:25
Il testo che sto consultando è questo:
http://www.amazon.it/Automi-linguaggi-calcolabilit%C3%A0-John-Hopcroft/dp/8871925521
http://ecx.images-amazon.com/images/I/31n3X2i2GJL._SL500_AA300_.jpg
Stiamo parlando di grammatiche context-free.
Generalmente la prima cosa da fare con una grammatica CF, è semplificarla:
Elimination of Nonterminal symbols that do not generate words
Elimination of symbols unreacheable from the start symbol
Elimination of useless symbols
Elimination of epsilon production
Elimination of Unit Production
Elimination of Left Recursion
Comunque trovi tutto sul Dragon Book, nell'edizione del 2006 in inglese (la seconda), pagine 224 e 225, trovi l'algoritmo per cui data una grammatica in ingresso ottieni in output la tabella di parsing ;).
Chiaramente prima devi vederti alcune definizioni, tipo quelle di FIRST e FOLLOW e compagnia bella.
Niente che non si possa fare da soli.
Avevo fatto un programmino in Java tempo fa per il parsing LR, seguendo proprio quel libro, in caso posto il codice (è tanta roba, c'era anche il Cooke-Younger-Kasami).
Vincenzo1968
20-01-2013, 12:35
No, WarDuch, alle pagine da te indicate c'è l'algoritmo per le grammatiche LR.
Comunque forse ho risolto:
A : B A a
|
;
B : b B c
| A A
;
Il mio programma produce, adesso, il seguente output:
http://img145.imageshack.us/img145/2217/gt03.jpg
http://img856.imageshack.us/img856/7261/gt04.jpg
Mi confermate che è corretto?
Vincenzo1968
20-01-2013, 12:37
Stiamo parlando di grammatiche context-free.
Generalmente la prima cosa da fare con una grammatica CF, è semplificarla:
Elimination of Nonterminal symbols that do not generate words
Elimination of symbols unreacheable from the start symbol
Elimination of useless symbols
Elimination of epsilon production
Elimination of Unit Production
Elimination of Left Recursion
Comunque trovi tutto sul Dragon Book, nell'edizione del 2006 in inglese (la seconda), pagine 224 e 225, trovi l'algoritmo per cui data una grammatica in ingresso ottieni in output la tabella di parsing ;).
Chiaramente prima devi vederti alcune definizioni, tipo quelle di FIRST e FOLLOW e compagnia bella.
Niente che non si possa fare da soli.
Avevo fatto un programmino in Java tempo fa per il parsing LR, seguendo proprio quel libro, in caso posto il codice (è tanta roba, c'era anche il Cooke-Younger-Kasami).
Posta posta, lo sai che sono goloso di algoritmi e tecniche sull'argomento :D
Vincenzo1968
20-01-2013, 12:58
Ragazzi se mi confermate che l'output è corretto posto il mio programma. Potrebbe essere d'ausilio per gli studenti che debbono affrontare l'argomento, no?
Magari faccio stampare(a video o nel file html) come viene generata, passo passo, seguendo l'algoritmo, la tabella LL(1).
È corretto l'output?
Eccolo:
https://skydrive.live.com/redir?resid=83FD660AAB95D700!630&authkey=!ANozV-6ZuiRYb1w
Lo puoi aprire con NetBeans o usare il JAR :D.
La sintassi per la grammatica è simile a questa:
S->aA|c
A->b|e
Dove "S" è lo start symbol e "e" è l'empty string :D.
Vincenzo1968
20-01-2013, 13:03
Eccolo:
https://skydrive.live.com/redir?resid=83FD660AAB95D700!630&authkey=!ANozV-6ZuiRYb1w
Lo puoi aprire con NetBeans o usare il JAR :D.
La sintassi per la grammatica è simile a questa:
S->aA|c
A->b|e
Dove "S" è lo start symbol e "e" è l'empty string :D.
Grazieeeeeeeeeeee!!!!!!!
:yeah: :winner: :yeah:
:D
Vincenzo1968
20-01-2013, 15:37
Sono quasi certo che l'output del mio programma sia corretto; anche nel caso di grammatiche con regole di produzione mutuamente ricorsive.
Ma, appunto, "quasi".
Aspetto conferma prima di postare il codice.
Vincenzo1968
20-01-2013, 20:14
Mi è stato dato un parere da un amico Ingegnere Informatico.
Aspetto il vostro per avere la certezza assoluta.
Vincenzo1968
21-01-2013, 11:05
Porting del programma su Linux:
http://img40.imageshack.us/img40/9753/grammartools00.jpg
http://img705.imageshack.us/img705/1817/grammartools.jpg
:D
Vincenzo1968
21-01-2013, 11:40
http://img707.imageshack.us/img707/8954/grammartoolsinfo.jpg
:D
Vorrei proporre 'sto programmino alla Free Software Foundation. Che debbo fare? Chi debbo contattare? Debbo parlare con Stallman? E dove lo trovo? Mi date il suo numero di telefono?
Vincenzo1968
21-01-2013, 12:36
Gli eseguibili per Linux(a 32 e 64 bit):
http://www.filedropper.com/grammartoolstar
Il programma va lanciato passangogli il file contenente la grammatica da riga di comando.
Per esempio:
./grammartools Files/Grammatica1.txt
Vincenzo1968
21-01-2013, 12:56
E gli eseguibili(32/64 bit) per Windows:
http://www.filedropper.com/grammartools
Per postare i sorgenti voglio aspettare ancora un po'. Sto aggiungendo al programma altre utili opzioni.
Vincenzo1968
22-01-2013, 12:53
No seriamente, cosa bisogna fare per avere il "logo" "Free Software Foundation" per i propri programmi?
Link, contatti?
Vincenzo1968
23-02-2013, 15:32
Scrivo qui per rispondere a tutti quelli(non molti, a dire il vero; pochi ma buoni come si suol dire :D ) che mi scrivono in pvt o via e-mail per avere notizie del programmino.
No, non si tratta di un tool per sbrigarsi a risolvere prima gli esercizi proposti nei corsi di compilatori. Piuttosto può essere visto come un tool che permette di dare una mano per verificare se la soluzione che si è trovata da soli per la creazione della tabella LL(1) corrisponde a quella trovata dal programma o no.
Purtroppo file dropper mantiene i file uploadati solo per pochi giorni. Quindi, se siete interessati, avvisatemi via pvt/e-mail se avete problemi col download che aggiorno il link(o vi mando il programma come allegato all'e-mail).
Comunque, come dicevo prima, sto estendendo il programma in modo che stampi, per esempio, i vari passi necessari per creare la tabella(e gli insiemi nullable, first e follow). Seguendo, appunto passo passo, l'algoritmo che si trova sui testi.
Alla fine renderò disponibili anche i sorgenti, magari su github.
;)
vBulletin® v3.6.4, Copyright ©2000-2025, Jelsoft Enterprises Ltd.