I
|
e seguite dal punto e
virgola ;
che funge da
terminatore: S ::=
la mela | il mango | l'arancia ;
la mela
il mango
l'arancia
S
(detto non terminale) permette la generazione dei
simboli la mela
, il mango
oppure l'arancia
(detti terminali).la mela
è pari
ad 1 volta su 3, così come per il mango
e l'arancia
:
perciò in presenza di 3 produzioni si ha 1 probabilità su 3 per
ciascuna di esse; in presenza di 5 produzioni si ha una probabilità su
5, ecc. S ::=
il Animale mangia Frutto ;
Animale ::=
gatto | cane ;
Frutto ::= la
mela | il mango ;
il gatto mangia la mela
il cane mangia il mango
S
come
iniziale, pertanto qualunque grammatica deve presentare almeno
la definizione di esso. S ::= Fido "Fido" ;
Fido ::=
bassotto | pastore |
alano ;
bassotto Fido
pastore Fido
alano Fido
S ::=
"(" (mela |
pera) ")" ;
( mela )
( pera )
::=
,
è possibile specificare una sottoproduzione di qualunque forma tra
parentesi tonde:S ::= la (
pera
| mela | banana
) e' sul (
tavolo
|
davanzale
) ;
la pera e' sul tavolo
la pera e' sul davanzale
la mela e' sul tavolo
la mela e' sul davanzale
la banana e' sul tavolo
la banana e' sul davanzale
S ::= la (pera | mela) e' sul (tavolo | davanzale) [del salotto |
della cucina] ;
la pera e' sul tavolo
la pera e' sul tavolo del salotto
la pera e' sul tavolo della cucina
la pera e' sul davanzale
ecc.(*
e *)
. Tale testo verrà completamente
ignorato dal Polygen. S ::= la
mela | la pera (*
| la banana *) | il mango ;
(* anche questo e' un commento *)
la mela
la pera
il mango
^
può essere
prefisso, suffisso o infisso in qualunque punto di una produzione
per istruire il programma a non inserire un carattere di spazio
nell'output generato: S ::=
"(" ^ (mela |
pera) ^ ")" ;
(mela)
(pera)
S ::= la
bottega del Prodotto ;
Prodotto ::= ^lo sciroppo | ^le
arance | salame ;
la bottega dello sciroppo
la bottega delle arancie
la bottega del salame
_
è la parola chiave che specifica la produzione vuota,
formalmente chiamata epsilon. S ::=
palla | _ ;
palla
_
_
in sè, né in un
carattere di spazio, ma nell'assenza di output. S ::= [palla] ;
palla
_
a
oppure
nulla.+
prefisso ad una qualunque produzione aumenta la probabilità che
questa venga generata rispetto alle altre della stessa serie;
simmetricamente, il simbolo meno -
diminuisce la probabilità. Un numero a piacere di +
e -
può essere specificato: S ::= il
gatto mangia (+ la mela |- la pera |
l'arancia |-- il limone) ;
il gatto mangia la mela
il gatto mangia la pera
il gatto mangia l'arancia
il gatto mangia il limone
S
viene
internamente interpretata come: S ::= il
gatto mangia ( la mela | la mela | la mela | la mela
| la pera | la pera
| l'arancia |
l'arancia | l'arancia
| il limone)
;
la mela
venga generata è maggiore rispetto a quella de l'arancia
,
che è maggiore di quella de la pera
, a sua volta
maggiore de il limone
. S ::=
gatto soriano | cane Razza ;
Razza ::=
pastore | dalmata
|
bastardo ;
PRODUCE gatto soriano
cane pastore
cane dalmata
cane bastardo
gatto soriano
sia generato è pari a
1 su 2; non vale però lo stesso per cane pastore, cane
dalmata
e cane bastardo
, sebbene un utente
possa ritenere ragionevole che siano tutti generabili con la
medesima probabilità.gatto soriano
e cane
Razza
si spartiscono equamente la
produzione di S
, ovvero la
probabilità con cui viene generato gatto soriano
è la
stessa (pari ad 1 su 2) con cui viene generato uno tra cane
pastore, cane dalmata
e cane bastardo
. Nella
fattispecie la distribuzione delle probabilità per ogni
produzione possibile appare come segue:
gatto soriano |
1/2 |
cane pastore |
1/2 * 1/3 = 1/6 |
cane dalmata |
1/2 * 1/3 = 1/6 |
cane bastardo |
1/2 * 1/3 = 1/6 |
S
nel modo seguente: S ::=
gatto soriano | cane pastore | cane dalmata |
cane bastardo ;
S ::=
gatto soriano | cane >Razza ;
Razza ::=
pastore | dalmata
|
bastardo ;
>
,
il programma opera, nella fase di preprocessing a monte della
generazione, la trasformazione di cui sopra, cambiando la distribuzione
delle probabilità nel seguente modo:
gatto soriano |
1/4 |
cane pastore |
1/4 |
cane dalmata |
1/4 |
cane bastardo |
1/4 |
S ::= il (gatto | cane
|
canarino
|
toro
|
lupo
|
gallo)
|
lo storione
|
la
(
capra
|
pecora) ;
lo storione
per un motivo
analogo a quello esposto in sezione 2.0.4.1. Per portare
l'eterogeneità dell'output al (ragionevolmente desiderabile) livello
in cui ciascun animale possa essere prodotto con la medesima
probabilità, sarebbe necessario evitare l'utilizzo delle parentesi
tonde, le quali danno luogo a sole 3 macro-produzioni, e
specificare l'articolo accanto ad ogni nome di animale; in altre
parole, quindi, rinunciare all'architettura originale della grammatica.>
istruisce il programma a delegare al preprocessore l'onere di operare
l'unfolding della sottoproduzione immediatamente seguente, permettendo
all'utente di mantenere inalterata l'architettura della grammatica
sorgente. S ::= il
>
(gatto | cane
|
canarino
|
toro
|
lupo
|
gallo)
|
lo storione
|
la
>
(
capra
|
pecora
)
;
S ::= il
gatto | il cane
|
il canarino
|
il toro
|
il lupo
|
il gallo
|
lo storione
|
la
capra
|
la pecora ;
S ::= M:
>
(
il (gatto | cane
>
(pastore | dalmata) |
canarino
|
toro
|
lupo
|
gallo)
|
lo storione
)
|
F: la
>
(
capra
|
pecora) ;
S ::= M:
il gatto |
M:
il
cane pastore
|
M:
il cane dalmata
|
M:
il canarino
|
M:
il toro
|
M:
il lupo
|
M:
il gallo
|
M:
lo
storione
|
F: la
capra
|
F:
pecora ;
>
è pertanto soggetta prima alla
permutazione, la quale mantiene valida l'azione dell'unfolding
specificata, che viene eseguita successivamente nella nuova posizione
all'interno della sequenza. S ::= >{il >(cane| gatto)} e
{
la
(
pecora
|
capra
)}
;
S ::= il
cane e la
(
pecora
|
capra
)
|
il gatto e la
(
pecora
|
capra
)
|
la
(
pecora
|
capra
)
e il cane
|
la
(
pecora
|
capra
)
e il gatto
;
S ::=
>
>> il
(
cane
|
gatto
)
| la (pecora | capra) << | lo storione ;
S ::= il
cane
|
il
gatto
|
la
pecora
|
la
capra
|
lo
storione
;
S ::= Nome.S mangia Nome.P | (Nome mangiano Nome).P ;
Nome ::= (S: il | P: i) (lup | gatt) ^ (S: o | P: i) ;
il lupo mangia i lupi
il lupo mangia i gatti
il gatto mangia i lupi
il gatto mangia i gatti
i lupi mangiano i lupi
i lupi mangiano i gatti
i gatti mangiano i lupi
i gatti mangiano i gatti
S ::= (Ogg.M | Ogg.F).S | (Ogg.M | Ogg.F).P ;
Ogg ::= M: ((Art Sost).il | (Art Sost).lo)
| F: Art Sost ;
Art ::= M: (il: (S: il | P: i) | lo: (S: lo | P: gli))
| F: (S: la | P: le) ;
Sost ::= M: ( il: (lup ^ Decl.2 | can ^ Decl.3))
| lo: (gnom ^ Decl.2 | zabaion ^ Decl.3))
| F: pecor ^ Decl.1 ;
Decl ::= 1: (S: a | P: e) | 2: (S: o | P: i) | 3: (S: e | P: i) ;
il lupo
il cane
lo gnomo
lo zabaione
la pecora
i lupi
i cani
gli gnomi
gli zabaioni
le pecore
S
, P
,M
ed F
si riferiscono
rispettivamente alle forme singolare, plurale, maschile e
femminile, è stato possibile declinare correttamente sostantivi
appartenenti a classi differenti ed associare l'articolo appropriato.Sost
opportuna.S
si
occupa sostanzialmente di attivare le combinazioni delle
etichette S,P
e M,F
per Ogg
.
Per evitare la frequente scomodità di dover compiere simili
operazioni è possibile specificare a destra del punto tra
parentesi tonde una serie di etichette separate dal pipe,
anziché una singola etichetta. S ::= Ogg.(M|F).(S|P) ;
+
e -
. S ::= Ogg.(+M|--F).(S|-P) ;
S ::= (Ogg.M |
Ogg.M |
Ogg.M |
Ogg.M |
Ogg.F).S
|
(Ogg.M |
Ogg.M |
Ogg.M |
Ogg.M |
Ogg.F).S
|
(Ogg.M |
Ogg.M |
Ogg.M |
Ogg.M |
Ogg.F).P
;
S ::= Cifra | S.nz [^S.] ;
Cifra ::= z: 0 | nz: >(
1| 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9) ;
0
1
23
23081993
112358
20020723
ecc.\
che istruisce il programma a
trasformare in maiuscola (nel caso in cui già non lo sia) la prima
lettera del simbolo terminale immediatamente successivo. S ::= \ pippo (e' | "." \) Eulogia
^
"."
;
Eulogia
::=
proprio un bell'uomo
|
davvero un signore ;
Pippo e' proprio un bell'uomo.
Pippo. Proprio un bell'uomo.
Pippo e' davvero un signore.
Pippo. Davvero un signore.
\
persiste fino al successivo simbolo terminale risultato della
produzione, pertanto ogni altro atomo (epsilon, concatenazione o
l'operatore \
stesso) che si
interpone agirà come di consueto: S ::= a \ ^ \ _ b
PRODUCE
{
e }
sottoproduzioni che vengono
automaticamente sottoposte ad una permutazione. S ::=
se
{
e'
}
{
quindi
}
{
egli
}
;
PRODUCE
S ::=
{
tra 10 minuti
}
^,
{
alle 3 in punto
}^,
{{io} {
partiro'
}
solo
}
;
PRODUCE
S ::=
{
tra 10 minuti
}
^,
{
alle 3 in punto
}^,
({io} {
partiro'
}
solo
)
;
PRODUCE
>>
e <<
:
ciascun atomo, a qualunque livello, per cui ha senso l'unfolding (vedi
sezione 2.0.4) è soggetto ad un
unfolding appunto. Il risultato è l'appiattimento totale di qualunque
sottoproduzione e simbolo non terminale specificati all'interno delle
doppie parentesi acute: S ::=
senti >> M:
(
il
(
cane| gatto
(
soriano
|
persiano)
|
colibri'
)
|
lo
(
storione
| sciacallo
)
)
|
F:
la
(
pecora
|
raganella
|
Animale
)
<< ;
Animale
::=
capra
|
mucca da
(
latte
|
carne
)
;
S
viene tradotto in: S ::=
senti
(
M:
il cane
|
M:
il gatto soriano
|
M:
il gatto persiano
|
M:
il colibri'
|
M:
lo storione
|
M:
lo sciacallo
|
F:
la pecora
|
F:
la raganella
|
F:
la capra
|
F:
la mucca da
(
latte
|
carne
)
)
;
>
per ogni sottoproduzione o
simbolo non terminale di una sottoproduzione, non sempre è possibile
tuttavia operare ricorsivamente l'unfolding di ogni singolo atomo
senza dare luogo ad errori. Il linguaggio supportato dal Polygen
permette a tale proposito di bloccare l'unfolding (di un atomo
per cui tale operazione avrebbe senso) tramite l'operatore prefisso <
. S ::=
senti >> M:
(
il
(
cane | gatto
<(
soriano
|
persiano)
|
colibri'
)
|
lo
(
storione
| sciacallo
)
)
|
F:
la
(
pecora
|
raganella
)
<< ;
S
viene tradotto in: S ::=
senti
(
M:
il cane
|
M:
il gatto
(
soriano
|
persiano)
|
M:
il colibri'
|
M:
lo storione
|
M:
lo sciacallo
|
F:
la pecora
|
F:
la raganella
)
;
::=
introduce
un binding, già ampiamente discusso in questo manuale, cosiddetto debole o chiusura.ESEMPIO
S ::=
Frutto
e
Frutto
;
Frutto
::= la mela | il
mango | l'arancia ;
PRODUCE
la mela e la mela
Frutto
non
subisce una generazione immediata ma viene chiusa insieme all'ambiente
corrente secondo le regole di scoping. Ogni occorrenza del simbolo
Frutto
in
un ambiente discendente (od il medesimo, come nell'esempio) provoca la
generazione della produzione associata
nell'ambiente
chiuso assieme ad essa.:=
introduce
una seconda forma di binding detta forte
o sospensione o assegnazione.ESEMPIO
S ::=
Frutto
e
Frutto
;
Frutto
:= la mela | il
mango | l'arancia ;
PRODUCE
la mela e la mela
Frutto
viene
sospesa e chiusa insieme all'ambiente corrente secondo le regole di
scoping. Durante la generazione, alla prima occorrenza del simbolo
Frutto
in
un ambiente discendente (od il medesimo, come nell'esempio) la
produzione associata viene generata una
sola volta nell'ambiente chiuso assieme ad essa ed il risultato,
immodificabile, della generazione risposto nell'ambiente; ogni
successiva occorrenza dello stesso non terminale produrrà sempre lo
stesso risultato.ESEMPIO
S ::=
A
A
;
A := a | a
^
A
;
PRODUCE
a a
aa aa;
.
Com'è già stato accennato e come è ragionevole aspettarsi, tali binding
vengono introdotti nell'ambiente (vuoto) secondo un rapporto di mutua
ricorsione: ciascuna produzione legata ad un non termianale può infatti
fare riferimento a qualunque simbolo non terminale definito a
top-level, a monte o a valle, incluso quello a cui essa stessa è legata.ESEMPIO
S ::=
S | A
|
B
|
s
;
A ::=
S | A
|
B
|
a
;
B :=
S | A
|
B
|
b ;
;
, la cui ultima occorrenza
separa l'ultimo binding dal corpo.ESEMPIO
S ::=
sono (X
:= Agg
;
Molto
::=
molto [
Molto
]
;
X ^ "," anzi
Molto
X
| decisamente
Molto
Agg
)
e
Agg
;
Agg
::=
bello
|
simpatico
;
PRODUCE
sono bello, anzi molto bello e simpaticoX
e Molto
sono
locali alla sottoproduzione che li definisce, mentre Agg
è utlizzato sia dal corpo di tale
sottoproduzione che dal corpo di S
. X
è un simbolo
introdotto localmente il cui unisco scopo è in qualche modo fissare la generazione di Agg
, che nell'ambiente a top-level è
definita tramite un binding debole (vedi sezione 2.0.10.1): in generale l'utilizzo degli
scope assieme alle varie forme di binding aggiunge molta potenza al
linguaggio ed aumenta le possibilità di ingegnerizzazione di una
grammatica.ESEMPIO
S ::=
sono (X
:= Agg
;
(
Molto
::=
molto [
Molto
]
;
X ^ "," anzi
Molto
X
| decisamente
Molto
Agg
)
)
e
Agg
;
Agg
::=
bello
|
simpatico
;
ESEMPIO
S ::=
(
X
::=
a
|
b
;
A)
;
A ::=
X
X
;
X
:=
x
|
y
;
PRODUCE
X
nella sottoproduzione di S
non
ha alcun effetto sulla generazione di A
,
che è stata chiusa assieme
all'ambiente in cui è stata definita (vedi sezione 2.0.10.1), ovvero quello a
top-level, in cui la
X
è legata alla produzione x
|
y
.ESEMPIO
S ::=
(
X
::=
a
|
b
;
(
X
::=
x
|
y
;
X))
;
PRODUCE
x
All'interno della secondo sottoproduzione innestata non
c'è visibilità della definizione esterna di X
.
Le medesime regole di applicano ovviamente anche all'ambiente top-level.ESEMPIO
S ::=
(
X
::=
a
|
b
;
(
X
::=
x
[
X
]
;
X))
;
PRODUCE
X
nel secondo binding innestato viene
dunque vista come un ricorsione, non come un riferimento alla
X
dell'ambiente padre.ESEMPIO
S ::=
(
X
::=
x
[
A
]
;
A
::= a
[X]
; (
X
::=
y
[
A
]
;
A
::=
b [X]; X))
;
PRODUCE
S ::= (sei
(
M:
un |
F:
una)
(
M:
bel
|
F:
bella
)
ragazz ^
(
M:
o
|
F:
a)).(M|F)
;
,
separa gli atomi che
rappresentano le possibili scelte: S ::= sei
un
,
una
bel
,
bella
ragazz ^
o
,
a
;
,
viene tradotta in una sottoproduzione che consiste in tante produzioni
separate da |
quanti sono gli
atomi nel gruppo e dove ognuna di tali produzioni presenta l'i-esimo atomo di ogni gruppo, per
ogni i. L'esempio di cui sopra
viene tradotto in: S ::= sei
un bel ragazz
^
o | sei una bella ragazz
^
a
;
S ::=
non
potro'
,
(ho potuto) mai
,
_ venire da te ;
S ::=
una ragazza m^ (o^)+
lto
carina ;
S ::= (a | b)+
;
S ::= (X
:=
a | b; (X)+)
;
S ::= Cifra [^ S] ;
Cifra ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 ;
0
23
853211
000000
00011122335
ecc. S1 ::=
gatto | cane |
cammello ;
S2 ::= gatto | (cane | cammello) ;
gatto
cane
cammello
S1
la
distribuzione delle probabilità è:gatto | 1/3 |
cane | 1/3 |
cammello | 1/3 |
S2
invece:gatto | 1/2 |
cane | 1/2 * 1/2 = 1/4 |
cammello | 1/2 * 1/2 = 1/4 |
+
o
al -
per le sottoproduzioni
tra parentesi quadrate. S ::= la (+ _ | bella) casa ;
la casa
la bella casa
+
o la -
a piacere.bella
. S ::= A | B ;
A ::= a ;
Questa grammatica dà luogo ad un errore, in quanto B
non è definito. S ::= S | A ;
A ::= B ;
B ::= S | A;
S ::= a | A ;
A ::= B ;
B ::= A ;
a
, è altresì possibile che venga imboccato
un percorso che non terminerà mai: è perciò importante che anche simili
casi siano segnalati da un messaggio di errore.>
di unfolding (vedi la sezione 2.0.4.1) ad un
simbolo non terminale che produrrebbe una ricorsione ciclica. S ::= >A ;
A ::= >B ;
B ::= >S ;
S ::= A ;
A ::=
A
^ | _ ;
_
A ::=
mela | pera |
capra ;
A ::= mandarino | anguria ;
S
::=
(A ::= mela | pera | capra ; A ::= mandarino | anguria
;
il
A
)
;
I
I
non
permette l'utilizzo dell'opzione -info
del programma. S ::= [a] ;
a
_
S ::= a A.z ;
A
::= x: x | y: y ;
S ::= a {b} c ;
S ::= >(b c) ;
S ::= >
A
A
A
;
A := a | b ;
S
è il simbolo non terminale iniziale. S ::= DECLS
DECL ::= Nonterm "::=" PRODS
| Nonterm ":=" PRODS
DECLS ::= (DECL ";")+
PRODS ::= PROD ("|" PROD)+
PROD ::= ("+" | "-")* SEQ
LABELS ::= LABEL ("|" LABEL)*
LABEL ::=
("+" | "-")*
Label
SEQ ::= [Label ":"]
(ATOMS)+
ATOMS ::=
ATOM ("," ATOM)*
ATOM ::= Term
| "^"
| "_"
| "\"
| UNFOLDABLE
| ">" UNFOLDABLE
| "<" UNFOLDABLE
| ATOM "."
| ATOM DotLabel
| ATOM ".(" LABELS ")"
UNFOLDABLE ::= Nonterm
| "("
SUB ")" ["+"]
| "[" SUB "]"
| "{" SUB "}"
| ">>" SUB
"<<"
SUB ::=
[DECLS
] PRODS
S ::= DECLS
DECL ::= Nonterm "::=" PRODS
| Nonterm ":=" PRODS
DECLS ::= (DECL ";")+
PRODS ::= SEQ
("|" SEQ)*
SEQ ::= [Label ":"] (ATOM)+
ATOM ::= Nonterm
| Term
| "^"
| "_"
| "(" SUB ")"
| ATOM "."
| ATOM DotLabel
SUB ::= [DECLS] PRODS
Term ::= [a-z 0-9 '][a-z A-Z 0-9 ']*
| " [A-Z a-z 0-9 ( ) _ - ? .
, ! : \ & # + * / % $ � [ ] { } ~ @ ; : | < > =
^ ' \ "]* "
Nonterm ::= [A-Z][A-Z a-z 0-9]*
Label ::= [A-Z a-z 0-9]+
DotLabel ::= . Label
Term
di cui in sezione 4.1.3 riconosce tra virgolette
il backslash \
, che funge da carattere escape. E'
possibile che un simbolo terminale tra virgolette contenga sequenze
escape tra le seguenti:\\ | backslash |
\" | virgolette |
\n | new line |
\r | carriage return |
\b | backspace |
\t | tab |
\xyz
|
codice ASCII decimale xyz
|
sintassi concreta |
sintassi astratta |
L: A11,... , An1 ...
A1n , ... , Anm |
L: ( A11...A1m | ... |
An1...Amn ) |
A.( + (a1)-(b1)
l1|...| +(an)-(bn)
ln) |
(X ::= A; X.l1 |(1)
... |(w1) X.l1 | ... | X.ln |(1)
... |(wn) X.ln) dove wi = ai - bi
- min {a1-b1
... an-bn } |
+(a1)-(b1)
P1 | ... | +(an)-(bn)
Pn |
P1 | (1)
... | (w1)
P1 |
... |
Pn | (1)
... | (wn)
Pn
dove wi = ai - bi
- min {a1-b1
... an-bn } |
[ D;
P
] |
(_ | (
D; P
)) |
(
D; P
)+ |
( X ::=
( D; P
)
(_ | X ) ; X ) |
>>
D; P
<<
|
(D; P'
) dove P' = f(A ) per ogni atomo A in P con f( A ) = A
se A non appartiene all'insieme degli atormi unfoldablef( <U ) = U
se U appartiene all'insieme degli atomi unfoldablef( U ) = > f(U ) se U appartiene all'insieme degli atomi unfoldable
|
P1 | ... | A1 { D1 ; Q1}.
... An { Dn
; Q n }. | ... | Pn |
P1 | ... | ( A1 ( D1 ; Q11 ) .
... An ( D1 ; Q1 n ) . ln
|
... | Dn
;
Dn
;
)
| ... | Pn dove Qji è
l' i-esimo elemento della j-esima Q1..
Q n(con
i = 1..n, j = 1..n!) |
P1 | ... | L: A >( D; Q1 | ... | Qm).l B | ... | Pn |
( D; P1 | ... | L: A (Q1).l B | ... | L: A (Qm).l B | ... | Pn )
|
P1 | ... | L: A >X.l B | ... | Pn D; Q1 | ... | Qm |
( D; P1 | ... | L: A (Q1).l B | ... | L: A (Qm).l B | ... | Pn )
|
P , Q |
produzioni o serie di produzioni |
A , B |
atomi o (sotto)sequenze di atomi |
D |
dichirazione o serie di
dichiarazioni |
L , l |
etichette |
X , Y |
simboli non terminali |
+(n)-(m) |
giustapposizione di n operatori + e m operatori - |
P | (1)
... | (n)
P |
ripetizione di n produzioni P |