[Vari] Automi a stati finiti, linguaggi, calcolabilità. Aspetti teorico-pratici.

[Vincenzo1968]

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.

[misterx]

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

[Vincenzo1968]

No ma questa mia prima domanda è cosa pratica. Devo implementare un programmino che prende in input una grammatica e genera la tabella LL(1).

[misterx]

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]

Grazie per la dritta.

Io un programmino simile lo sto già scrivendo(e funziona anche ).

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.

[misterx]

occhio a come ti esprimi perchè di sgamano subito, è una prof

[email protected]

[Vincenzo1968]

Questa non l'ho capita. Come dovrei esprimermi? E chi dovrebbe sgamarmi? E cosa dovrebbero sgamare?

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:




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?

[misterx]

se fai domande assurde non ti rispondono, più chiaro così ?

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]

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?

[misterx]

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]

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]

Il testo che sto consultando è questo:

http://www.amazon.it/Automi-linguagg.../dp/8871925521

[WarDuck]

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]

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:



Mi confermate che è corretto?

[Vincenzo1968]

Originariamente inviato da WarDuck

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

[Vincenzo1968]

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?

[WarDuck]

Eccolo:

https://skydrive.live.com/redir?resi...NozV-6ZuiRYb1w

Lo puoi aprire con NetBeans o usare il JAR .

La sintassi per la grammatica è simile a questa:

S->aA|c
A->b|e

Dove "S" è lo start symbol e "e" è l'empty string .

[Vincenzo1968]

Originariamente inviato da WarDuck

Eccolo:

https://skydrive.live.com/redir?resi...NozV-6ZuiRYb1w

Lo puoi aprire con NetBeans o usare il JAR .

La sintassi per la grammatica è simile a questa:

S->aA|c
A->b|e

Dove "S" è lo start symbol e "e" è l'empty string .

Grazieeeeeeeeeeee!!!!!!!

[Vincenzo1968]

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]

Mi è stato dato un parere da un amico Ingegnere Informatico.

Aspetto il vostro per avere la certezza assoluta.