[BNF] Abbinamento parentesi

[pi00100100]

Non riesco a scrivere una o più regole di produzione in BNF che permettano di ottenere un numero illimitato di parentesi abbinate, come ad esempio:

()
(())
((()))

L'unica cosa che mi viene in mente è:

{ "(" } { ")" }

ma così non è affatto detto che il numero di parentesi sinistre sia uguale al numero delle parentesi destre. Come si può fare? Grazie.

[pi00100100]

Forse è più semplice del previsto:

<expr> ::= "" | ( "(" <expr> ")" )

Però non riesco in alcun modo a disegnarne il diagramma in forma grafica, utilizzando cioè blocchi e linee...

[noname001]

Ciao!

Se non devi produrre la stringa vuota sarebbe più giusto usare (ti scrivo la grammatica):

S -> () | (S)

Per il diagramma di sintassi dovresti prevedere due rami:

[expression]--->( '(' )-->( ')' )------->o

[expression]--->( '(' )--->[expression]--->( ')' )------->o

Per comodità li ho scritti separati ma andrebbero accorpati

[pi00100100]

Purtroppo è proprio l'accorpamento in questione che non mi riesce... Ce la fai per caso a produrre un diagramma grafico utilizzando il tar "code" del forum? Grazie.

[noname001]

Provo:

[expression]---------------------->( '(' )-->( ')' )--------------------->------>o
                    |                                                    |
                    \--------->( '(' )--->[expression]--->( ')' )-------/ 

[pi00100100]

Non ho ancora studiato nel dettaglio queste cose, ma credo che non sia possibile mettere "[expression]" all'interno di un diagramma se non come punto di partenza (e cioè solo una volta).

[noname001]

Da questo diagramma di Wikipedia



c'è ricorsività nella definizione di expression:

expression->term->factor->expression

Se expression è definito indirettamente in termini di se stesso, perchè non potrebbe esserlo direttamente?

[pi00100100]

Ok, credo di aver capito ora. Grazie per l'aiuto!