Linguaggi e grammatiche context free: dubbio

[Gica78R]

Ciao a tutti. Sto bestemmiando un pochino con le grammatiche context free nell'ambito di un progetto per un esame universitario. Tra le altre cose, devo inventarmi (o trovare già pronto) un linguaggio per il quale successivamente costruire un lexer/parser e un traduttore, utilizzando ad esempio JavaCC. Il linguaggio (context free) non deve essere troppo banale, in particolare deve avere degli elementi opzionali (cioè presenti 0 o 1 volta) che possono comparire in un ordine qualsiasi all'interno di una stringa del linguaggio. Vi faccio un esempio banale: supponiamo che il linguaggio in questione contenga solo gli elementi A e B, che questi siano opzionali (cioè possono esserci o meno) e che possano trovarsi in un qualsiasi ordine all'interno della stringa. Esprimendo un tale linguaggio con una grammatica context free l'unica soluzione che mi viene in mente è quella di usare 5 produzioni:

S --> A | B | AB | BA | stringa vuota

Questo perché non mi sembra ci sia altro modo di esprimere un tale linguaggio se non enumerando tutti i possibili casi. Ovviamente al crescere del numero degli elementi opzionali la cosa si fa sempre più complicata.

Secondo voi è corretto quel che dico oppure ci sono modi più efficaci per definire un linguaggio del genere?

A sostegno di quanto dico c'è questa FAQ su JavaCC in cui si fa un esempio simile a quello che ho riportato io e in cui si risponde che la cosa migliore è quella di utilizzare le azioni semantiche.

[Ziosilvio]

Originariamente inviato da Gica78R

Sto bestemmiando un pochino con le grammatiche context free nell'ambito di un progetto per un esame universitario.

Per le domande di informatica teorica c'è una discussione in evidenza nella sottosezione Scienza e tecnica.

Originariamente inviato da Gica78R

supponiamo che il linguaggio in questione contenga solo gli elementi A e B, che questi siano opzionali (cioè possono esserci o meno) e che possano trovarsi in un qualsiasi ordine all'interno della stringa. Esprimendo un tale linguaggio con una grammatica context free l'unica soluzione che mi viene in mente è quella di usare 5 produzioni:

S --> A | B | AB | BA | stringa vuota

Questo perché non mi sembra ci sia altro modo di esprimere un tale linguaggio se non enumerando tutti i possibili casi.

Così però costruisci solo le stringhe formate da A e B, senza ripetizioni.
Se invece vuoi le stringhe in cui A e B compaiono ciascno al più una volta, puoi usare dei simboli ausiliari, che ti rappresentano quelle che nella FAQ chiamano "azioni semantiche".
La maniera più diretta credo sia:

S := TAT | TBT | TATBT | TBTAT | T
T := a{1}T | ... | a{n}T | e

dove a{1}, ..., a{n} sono i caratteri ed e è la stringa vuota.

[Gica78R]

Originariamente inviato da Ziosilvio

Per le domande di informatica teorica c'è una discussione in evidenza nella sottosezione Scienza e tecnica.

Chiedo scusa, non conoscevo quella sezione. Comunque la ricerca dei termini "context free" nel forum non mi aveva dato nessun risultato e allora ho aperto qui...

Così però costruisci solo le stringhe formate da A e B, senza ripetizioni.

Si, il mio era solo un esempio semplice per descrivere il problema.

Se invece vuoi le stringhe in cui A e B compaiono ciascno al più una volta, puoi usare dei simboli ausiliari, che ti rappresentano quelle che nella FAQ chiamano "azioni semantiche".
La maniera più diretta credo sia:

S := TAT | TBT | TATBT | TBTAT | T
T := a{1}T | ... | a{n}T | e

dove a{1}, ..., a{n} sono i caratteri ed e è la stringa vuota.

In questo caso, dato che hai già enumerato tutti i casi possibili per A e B, non c'è bisogno di azioni semantiche; bastano le normali produzioni che hai riportato Con le azioni semantiche evitiamo di scrivere tutte quelle produzioni ma aggiungiamo il codice che, in caso di ripetizione di A o B, genera un'eccezione.


Grazie per la risposta