Newsgroup: it.scienza.informatica
Titolo: Grammatiche non contestuali: problema

Salve a tutti. Svolgendo qualche semplice esercizio inerente la
sintesi di grammatiche context-free ho incontrato più volte la
seguente difficoltà: mettiamo il caso che io voglia costruire una
grammatica le cui frasi siano formule atomiche della logica dei
predicati. La definizione di tali formule è la seguente: se P è un
simbolo predicativo di arietà m e t1,...,tm sono termini, allora
P(t1,...,tm) è una formula atomica. Come posso rappresentare in BNF
(Backus-Naur form) o in EBNF (extended Backus-Naur form) l'arietà di P
in modo generale (m nella definizione)? Avevo pensato per esempio a
definire una produzione che avesse come membro destro P({<termine>}^n)
che dovrebbe significare (in EBNF) che il termine può apparire per un
massimo di n volte ma... Anche nessuna! Oppure n-1 o n-23 volte!
Grazie infinite a chi vorrà aiutarmi.
					Giova

xxx@xxx.x (Giova) writes:

Allora, l'arieta` di P e` una cosa che non si puo` esprimere con
grammatiche contex-free. Se 'm' e` fissato allora puoi fare una serie
di regole che funzionino con quel determinato 'm'.
ad esempio per m=4
T -> P(T,T,T,T)
va bene.
in (E)BNF sarebbe
<termine> ::= P(<termine> {,<termine>}^(m-1)) | P()
scritto cosi vuol dire che ,<termine> appare esattamente m-1 volte.
(m, naturalmente, e` deciso a priori)
Se vuoi esprimere anche una sorta di dichiarazione dell'arieta` di P
ci vogliono grammatiche contestuali. Ma non hanno quasi nessuna utilita`
pratica per la complicazione che creano.
Nei compilatori veri vengono implementate di solito regole di questo tipo
<termine> ::= <nome-funzione>(<lista-parametri>)
<lista-parametri> ::= nil
<lista-parametri> ::= <lista-parametri-1>
<lista-parametri-1> ::= <termine>
<lista-parametri-1> ::= <termine>,<lista-parametri-1>
il conteggio effettivo del numero di parametri usati viene fatto dopo
con altri sistemi.
-- 
# Giorgio Vecchiocattivi.
# Dip. Informatica, Universita` di Pisa. 

Ciao,
non sono sicuro di aver capito la tua domanda, ma se ti interessa
rappresentare l'arietą con una CFG non puoi. Nel senso che non
hai strumenti per "contare" quanti argomenti ci sono. Puoi riconoscere:
p() p(t) p(t-t-t) p(t-t-t-t-t-t-t-t-t-t-t)
con la grammatica:
P -> p ( T )
T -> empty | L
L -> t | t-L
dove {P,T,L} non terminali e { empty, (, ), t,-} tokens.
Ma non puoi contare quante "t" ci sono. E questo non dipende dal
formalismo che usi per rappresentare la grammatica.
Spero di esserti stato d'aiuto in qualche modo.
Ciao.
Davide.

in modo generale (m nella definizione)?
Se ho capito bene, dovresti scrivere qualcosa tipo
TermList ::= Term {, TermList}
Dove Term e` la categoria dei termini e cio` che e` tra le graffe e` opzionale.
Qundi una formula sarebbe qualcosa del tipo
Formula ::= Ide({TermList})
Spero di aver scritto bene...
Saluti,
Paolo
----------------------------------------------------------
  Paolo Marotta
  Computer Science, University of Pisa
  home:   
http://www.cli.di.unipi.it/~marotta
  e-mail: 
mar...@cli.di.unipi.it
 
----------------------------------------------------------

 					Giova
Allora, l'arieta` di P e` una cosa che non si puo` esprimere con
grammatiche contex-free. Se 'm' e` fissato allora puoi fare una serie
di regole che funzionino con quel determinato 'm'.
ad esempio per m=4
T -> P(T,T,T,T)
va bene.
in (E)BNF sarebbe
<termine> ::= P(<termine> (,<termine>)^(m-1)) | P()
                          ^          ^ 
                          +----------+-queste sono parentesi, non simboli terminali
(non mi ricordo come si scrivono in BNF


grammatiche contex-free. ..
Grazie mille! Č proprio ciň che mi serviva sapere.