[C] Generare parole del linguaggio da una grammatica

[cdere]

Salve!
Ho a dispozione un grammar reader in C, praticamente riesce a prendere in input una grammatica espressa in regole di riscrittura:

(1) S > aBSc
(2) S > abc
(3) Ba > aB
(4) Bb > bb

e me lo mette in una struttura... ora.. qualcuno ha qualche idea su come fare per scrivere su un file le parole generabili da questa grammatica?

Ciao e grazie

[Dark Phoenix]

Noto che tale grammatica genera un linguaggio composto da infinite "parole"...

Per tale motivo ti consiglio di fare un programma che data una profondità genera tutte le parole con quella profondità massima.
Dove la profondità è pari al numero di applicazioni di regole.
Una parola appartiene poi al linguaggio se è composta solo da letterali.

[cdere]

Originariamente inviato da Dark Phoenix

Noto che tale grammatica genera un linguaggio composto da infinite "parole"...

Per tale motivo ti consiglio di fare un programma che data una profondità genera tutte le parole con quella profondità massima.
Dove la profondità è pari al numero di applicazioni di regole.
Una parola appartiene poi al linguaggio se è composta solo da letterali.

Ciao!
si perfetto hai centrato il problema in pieno.. per letterali intendi simboli terminali? (che nella grammatica del primo post indico con lettere minuscole e al contrario, i non-terminali, cioè quelli da sostituire, con lettere maiuscole)

Mi dai qualche idea per "la generazione" ? non ci sono proprio.. sto in alto mare...
Per dire ho pensato:

altezza albero: 1
deve usare per forza la regola (2) e si ferma.

altezza albero: 2
fargli generare tutte le parole possibili usando 2 regole, e prendere solo quelle con i terminali.. ma quello che non capisco è, come fargli generare tutte queste parole?
come decide quale regola utilizzare delle 4 il programma?

Grazie mille per il supporto Dark

[Dark Phoenix]

si scusa mi sono espresso male intendevo terminali (la terminologia è la cosa che prima si dimentica )

Per la generazione la mia idea è piuttosto semplice...
Come puoi immaginare il metodo è ricorsivo...
lo descrivo in modo molto generico e approssimativo, comunque nel tuo stato ricorsivo hai:

1. Forma Generata
2. Profondità

I passi per ogni ricorsione sono i seguenti:

1. Controlli se la forma è composta solo da terminali: se si allora ritorni altrimenti se hai superato la profondità massima ritorni nulla altrimenti....
2. Prendi le regole che puoi applicare
3. Le applichi tutte con profondità + 1

Ricordando che una regola si può applicare in più punti nella tua "forma generata" come l'ho chiamata prima (intendo quella composta da terminali e non terminali), in realtà quando dico le applichi tutte intendo dire che applichi ogni regola ovunque possa essere applicata.

Non sono stato molto chiaro ma conviene procedere per raffinamenti successivi...

P.S.
Di niente per il supporto mi piace questa parte dell'informatica

[cdere]

Il problema è che non so come implementare il controllo su quali regole applicare e come applicarle...

Vediamo un po, io ho una struttura:

 typedef char Symbol;


 typedef struct
 {
     Word left;
     Word right;
 } Production;


 typedef struct
 {
     Production productions[MAX_PRODUCTIONS];
     unsigned numprod;
 } Grammar;


//ipotizzo dichiarare questa struttura:
Grammar g;

In questa struttura 'g' ci sono produzione per produzione (nel mio caso ce ne sono 4) le regole della grammatica...
ogni produzione ha una parte sinistra g.productions.left.word: S > ab
e una parte destra g.productions.right.word: S > abc
Ora, avevo pensato di creare un array di stringhe e memorizzare qui dentro le mie "forme di frase" (stringhe con simboli terminali e non terminali, da scremare in un secondo momento) ma non so proprio come, ne come strutturare il ciclo, ne come effetturare un ipotetico test...

sono nella cacca, ti prego salvami

in ogni modo grazie mille per l'ottima (ed esauriente) risposta (e se sto approfittando impudentemente del tuo tempo fanculizzami tranquillamente )!!

bye

[cdere]

up