| Autore |
 Discussione  |
|
|
krasta
Utente medio
Città: acquaviva
|
 Inserito il - 09/04/2006 : 14:39:18
|
|
ragazzi quale potrebbe essere una funzione in C per determinare se una grammatica è dipendente da contesto (basta controllare se è monotona e basta?)...grazie
|
emancipate yourself from mental slavery |
|
|
ekkekkazz
Utente innocuo
|
Inserito il - 09/04/2006 : 18:08:17
|
una soluzione potrebbe essere questa:
oltre al controllo della monotonia, fare una iterazione per tutta la lunghezza della parte sinistra e verificare che esista un terminale; se questo esiste, controllare con un'altra iterazione annidata che esista lo stesso terminale anche nella parte destra, e quindi è context-sensitive... poi bisognerebbe fare un controllo per verificare che nella parte sinistra esista almeno un NT... |
 |
|
|
krasta
Utente medio
Città: acquaviva
|
Inserito il - 10/04/2006 : 13:58:22
|
si ma il contesto come lo controllo ?
yAz -> ywz
il contesto y-z come lo controllo ? |
emancipate yourself from mental slavery |
|
|
|
ekkekkazz
Utente innocuo
|
Inserito il - 10/04/2006 : 17:32:45
|
in effetti la soluzione che ho dato io la possiamo buttare... y,z sono in (XuV)*, perciò possono essere anche lambda oppure aF o una qualsiasi forma di frase... il problema è proprio il riconoscimento dei contesti, o più che altro il riconoscimento di A in yAz -> ywz...
prendiamo una produzione BCD->BCe... dobbiamo trovare un modo per determinare la D, e ottenere che tutto il resto della stringa che sta a sinistra è y, e tutto quello a destra è z...
Quindi con un'iterazione per tutti i simboli della parola BCe, cercarsi il corrispondente in BCD... ci rimarranno soltanto la D e la 'e'...
quindi tutto quello a sinistra della D è y, tutto quello a destra è z...
controlliamo che y e z sono uguali a quelli di destra rispetto alla 'e'...
vediamo se riesco a combinare qualcosa col compilatore... poi c'è il problema delle lambda produzione... una cosa alla volta però... |
|
|
|
ekkekkazz
Utente innocuo
|
Inserito il - 12/04/2006 : 01:50:01
|
ok, questa funzione funziona... praticamente estrae i contesti... ora per confrontarli avevo pensato a tipo due puntatori alla parte destra come nella palindrome (Caponetti, brrrr)
int find_context(Production *p, Symbol *y, Symbol *z)
{
int i,j,index[10],k=0;
index[0]=-1;
for (j=0;j<p->left.length;j++)
{ if (!exist_symbol(p->right,p->left.word[j]))
{
index[k++]=j;
}
}
int y_limit=min(index,k);
int z_limit=max(index,k);
if (index[0]==-1)
return 0;
for (j=0;j<y_limit;j++)
*(y++)=p->left.word[j];
*y='\0';
for (j=z_limit+1;j<p->right.length;j++)
*(z++)=p->left.word[j];
*z='\0';
return 1;
}
oh krasta auguri
|
Modificato da - ekkekkazz in data |
|
|
|
peano
Utente medio
Prov.: Bari
|
Inserito il - 12/04/2006 : 09:57:03
|
basta controllare la monotonia e stop.. |
|
|
|
ekkekkazz
Utente innocuo
|
Inserito il - 14/04/2006 : 00:29:30
|
Citazione:
Messaggio inserito da peano
basta controllare la monotonia e stop..
ma non basta...
se io voglio distinguere una produzione lineare da una dipendente?
per esempio A->bC è monotona, però non è CS...
ok, vabene il teorema della gerarchia per cui L3 in L2 in L1, però qui non basta... la monotonia è una condizione necessaria ma non sufficiente. |
|
|
|
Tak3z0
Nuovo Utente
|
Inserito il - 12/06/2006 : 10:17:57
|
scusa ma e' un problema solo mio che non riesco a vedere tutta la codifica quando la si posta [vedi codifiche postate da fran]
credo manchi qualcosa tipo i controlli del while ad esempio ora non se e' un problema solo mio pls potreste uppere il file grazie assai ^^ |
  |
|
|
| |
Discussione |
|
datemi addosso per l'ignoranza
