[Chomsky] Grammatiche e Linguaggi

[shinji_85]

Mi rendo conto della particolarità del thread... Non so nemmeno se è la sezione più adatta... :boh:
Il mio problema è questo...
Devo testare un programma... Anzi in realtà son due programmi diversi...

Il primo...
Fa inserire una Grammatica (senza restrizioni)... Testa se la Grammatica è (almeno) di Tipo 1 (Context Sensitive)... Se lo è...
Permette all'utente di testare se una parola (Stringa, non vuota) appartiene o meno al Linguaggio generato dalla Grammatica...

Il secondo... A differenza del primo...
Testa se la Grammatica è (almeno) di Tipo 2 (Context Free)... Se lo è...
Permette all'utente di effettuare alcune semplificazioni sulla stessa... Cioè implementa gli algoritmi...
1) "Avoid Left-Recursion"
2) "Avoid Epsilon-Productions"
3) "Avoid Unit Productions"
4) "From Below"
5) "From Above"
Inoltre, utilizzando l'algoritmo di Earley (non so se è il più adatto, ma oramai ho scritto questo), verifica se una parola (anche una Stringa vuota) appartiene o no al Linguaggio generato dalla Grammatica...

Qual è il problema...
Non ho (non trovo) molti esempi (con le soluzioni ne ho solo un paio, direi banali) per testarlo...
Se ci siete già passati e potete darmi una mano ve ne sarei grato...



Immagino già il successo di questa discussione... :sofico: :)

[shinji_85]

Rispondo qui al messaggio privato di rizzi... A proposito, ci conosciamo?!? :D

Come si è capito devo dare l'esame di "Automi, Linguaggi e Traduttori"... ;)



Per i due programmi ho usato Java...
Per l'interfaccia SWT...
Ho perso un sacco di tempo solo per fare (praticamente da zero) una finestra con qualche componente (bottoni, liste etc.)...
Logicamente è tutto organizzato in classi... Quindi ad esempio uso la classe "Grammar", che contiene le produzioni e tutto il resto...
Purtroppo il "tutto il resto" è molto incasinato...
Infatti ho visto Java la prima volta a Giugno... E la teoria delle Grammatiche la sto ancora studiando...
Per gli algoritmi ho letteralmente COPIATO (codificandoli in Java) quelli illustrati nel libro "Quaderni di Informatica - Parte II"...

E chiedevo esempi di test... Beh... E' semplice il motivo...
Testando il programma mi accorgo ogni tanto di errori (a volte madornali) nel codice...
Che puntualmente saltano fuori ad ogni esecuzione con una particolare (a volte nemmeno poi tanto) Grammatica...



Insomma... Dovrei anche iniziare a studiare per altri 2 esami... E' ora di concludere qualcosa... :doh:

[shinji_85]

Nemmeno un esempio di Grammatica di Tipo 1 (che non sia quella che genera il Linguaggio: a^n b^n c^n)?!?


Cioè tutte le Stringhe del tipo abc, aabbcc, aaabbbccc, aaaabbbbcccc... :fagiano: :help: :mc:

[BountyKiller]

pensavo che con il restringimento dei programmi del n.o. queste cose fossero state segate via......
per risponderti dovrei ricordarmi le grammatiche ( parliamo di 8 anni fa)....comunque ricordo che le avevo capite bene e se ci sono riuscito io puoi farcela anche tu....
inutile dire che queste cose come gli automi push down, le macchine di turing sono inutili..logica proposizionale e logica del primo ordine hanno una utilità ( la seconda a patto che sia insegnata da persone capaci di farlo e che che l'abbiano capita prima :D)

coraggio

[shinji_85]

pensavo che con il restringimento dei programmi del n.o. queste cose fossero state segate via......
per risponderti dovrei ricordarmi le grammatiche ( parliamo di 8 anni fa)....comunque ricordo che le avevo capite bene e se ci sono riuscito io puoi farcela anche tu....
inutile dire che queste cose come gli automi push down, le macchine di turing sono inutili..logica proposizionale e logica del primo ordine hanno una utilità ( la seconda a patto che sia insegnata da persone capaci di farlo e che che l'abbiano capita prima :D)

coraggio

Grazie per l'incoraggiamento... In effetti è un esame un po' particolare...
Ma più o meno ci sono con gli algoritmi... E quello che chiedeva di fare il prof... A fatica credo di averlo codificato in Java...
Solo che vorrei testarlo un po' più a fondo... Soprattutto perché di Grammatiche di Tipo 1 conosco solo 1 esempio... Un po' poco... ;)