Linguaggi Formali e Compilatori(Formal Languages and Compilers)

prof. S. Crespi Reghizzi, prof. Angelo Morzenti

(prof. Luca Breveglieri)

Prova scritta - 28 febbraio 2013 - Parte I: Teoria

CON SOLUZIONI - A SCOPO DIDATTICO LE SOLUZIONI SONO MOLTO ESTESE E COM-

MENTATE VARIAMENTE - NON SI RICHIEDE CHE IL CANDIDATO SVOLGA IL COMPITO IN MODO AL-

TRETTANTO AMPIO, BENSI CHE RISPONDA IN MODO APPROPRIATO E A SUO GIUDIZIO RAGIONEVOLE

AVVISO - A PARTIRE DALLA SESSIONE ESTIVA (GIUGNO 2013), GLI ESERCIZI DI ANALISI SIN-

TATTICA ANDRANNO AFFRONTATI SECONDO LA TEORIA ELR / ELL - LA TEORIA LR / LL NON SARA PIU

AMMESSA - SI VEDA IL SITO WEB DEL CORSO PER MATERIALE DIDATTICO E INFORMAZIONI

NOME:

MATRICOLA: FIRMA:

ISTRUZIONI - LEGGERE CON ATTENZIONE:

• L’esame si compone di due parti:

– I (80%) Teoria:

1. espressioni regolari e automi finiti

2. grammatiche libere e automi a pila

3. analisi sintattica e parsificatori

4. traduzione sintattica e analisi semantica

– II (20%) Esercitazioni Flex e Bison

• Per superare l’esame l’allievo deve sostenere con successo entrambe le parti (I e II),in un solo appello oppure in appelli diversi, ma entro un anno.

• Per superare la parte I (teoria) occorre dimostrare di possedere conoscenza sufficientedi tutte le quattro sezioni (1-4), rispondendo alle domande obbligatorie.

• E permesso consultare libri e appunti personali.

• Per scrivere si utilizzi lo spazio libero e se occorre anche il tergo del foglio; e vietatoallegare nuovi fogli o sostituirne di esistenti.

• Tempo: Parte I (teoria): 2h.15m - Parte II (esercitazioni): 60m

1 Espressioni regolari e automi finiti 20%

1. Sono dati l’espressione regolare R e l’automa a stati finiti A2 seguenti:

R = b∗ ( a b+ )∗

1 2 3A2 → →

a, b

a a, b

Si risponda alle domande seguenti:

(a) Si consideri l’espressione regolare R data sopra:

i. Si scrivano in ordine alfabetico le stringhe di lunghezza quattro appartenential linguaggio regolare L (R) e si descriva a parole tale linguaggio.

ii. Utilizzando il metodo Berry-Sethi, si ricavi un automa a stati finiti deter-ministico A1 che riconosce il linguaggio regolare L (R); se e necessario, siminimizzi l’automa A1.

iii. (facoltativa) Si dica se il linguaggio regolare L (R) e locale.

(b) Si consideri l’automa a stati finiti A2 dato sopra:

i. Si dica quali delle stringhe date in risposta al punto (a).i sono accettateanche dall’automa A2.

ii. Si costruisca l’automa prodotto A3 = A1 × A2 che accetta il linguaggioL (R) ∩ L (A2), e si dica se l’automa prodotto A3 e deterministico o no.

iii. Si mostrino le tracce delle esecuzioni dell’automa prodotto che accettano lestringhe di cui al punto (b).i.

2

Soluzione

(a) Per la prima domanda:

i. Le stringhe sono cinque: a b a b, a b b b, b a b b, b b a b e b b b b. Il linguaggio hatutte e sole le stringhe dove ogni lettera a e seguita da una lettera b.

ii. Ecco l’automa deterministico A1 tramite il metodo di Berry-Sethi (BS).

R = b∗1(

a2 b+3

)∗

⊣

inizi b1 a2 ⊣

gen. seguiti

b1 b1 a2 ⊣

a2 b3

b3 a2 b3 ⊣

b1 a2 ⊣ b3 a2 b3 ⊣A1 →

↓

→

b b

a

b

a

1 2 3A1 →↓

→

b b

a

b

a

Si vede subito che gli stati 1 e 3 sono indistinguibili: sono finali, con ingressoa vanno nello stato 2, e con ingresso b restano in 1 e 3. Invece lo stato 2e distinguibile sia da 1 sia da 3 poiche non e finale. Pertanto si possonounificare gli stati 1 e 3, cosı:

1 3 2A1 →

↓

b

b

a

Ora l’automa deterministico A1 e minimo.

3

iii. Il linguaggio regolare L (R) e locale. Infatti l’automa A1 minimo che loriconosce, ha due stati e in ciascuno di essi si entra con archi etichettati conla stessa lettera d’ingresso: a per 2 e b per 1 3. E immediato ridisegnarel’automa A1 in forma locale, dove ogni stato e etichettato univocamente conuna lettera d’ingresso, oltre allo stato iniziale. Eccolo:

i b aA1 →↓ ↓

In termini di lettere iniziali, finali e digrammi, il linguaggio locale L (R) eevidentemente descrivibile cosı:

Ini = { a, b } Fin = { b } Dig = { a b, b a, b b }

ovvero le stringhe di L (R) non terminano con la lettera a e non contengonoil digramma a a. A queste va aggiunta la stringa vuota ε.

(b) Per la seconda domanda:

i. Le stringhe sono due: a b a b e b b a b. L’automa A2 accetta le stringhe dilunghezza ≥ 2 dove il penultimo carattere e la lettera a.

ii. Ecco l’automa prodotto A3 = A1 × A2:

1 2 3A2 → →

a, b

a a, b

A

B

A1 → →

b

b a

1A 2A 3A

1B 2B 3B

A3 → →

b

ab

b

a a

b

L’automa A3 non e in forma ridotta poiche gli stati 2A e 3B (in tratteggio)sono irraggiungibili dallo stato iniziale, e poiche inoltre lo stato 3B nonraggiunge lo stato finale. L’automa A3 si riduce facilmente cosı:

4

1A 3A

1B 2B

A3 → →

b

aba b

L’automa prodotto A3 non e deterministico e del resto non lo e neppurel’automa fattore A2. Naturalmente lo si potrebbe rendere deterministico.

iii. Ecco le computazioni richieste dell’automa prodotto A3:

→ 1Aa→ 1B

b→ 1A

a→ 2B

b→ 3A →

→ 1Ab→ 1A

b→ 1A

a→ 2B

b→ 3A →

Entrambe accettano la stringa rispettiva, come devono.

5

2 Grammatiche libere e automi a pila 20%

1. Preso l’alfabeto Σ = { 0, 1, ‘(’, ‘)’ }, un numero binario y ∈ { 0, 1 }+ e una stringadi bit. Il linguaggio L1 ⊆ Σ∗ e definito ricorsivamente. Si supponga che le stringhex, x1 e x2 siano frasi arbitrarie di L1. Valgono le tre condizioni ricorsive seguenti:

• ogni binario y appartiene a L1

• la stringa “( x )” appartiene a L1

• il concatenamento “x1 x2” appartiene a L1

Esempi e controesempi:

valida 0 0 1 1 0

valida(

0 ( 1 0 ) ( 1 1 0 ) 1 0 0 ( 1 0 ))

valida ( 1 1 0 0 ) 0(

( 1 0 )) (

1 1 ( 1 1 0 ) 0)

1 0 0

non valida(

0 ( ) ( 1 1 0 ) 1 0 0 ( 1 0 ))

- coppia vuota

non valida(

0 ( 1 1 ) ( 1 1 0 ) - sbilanciamento

Si risponda alle domande seguenti:

(a) Si scriva una grammatica G1, non estesa e non ambigua, per il linguaggio L1, ese ne giustifichi la non ambiguita.

(b) In una frase di L1 si consideri una coppia di parentesi corrispondenti. Il numero

binario associato ad esse, e la sequenza di bit contenuti tra dette parentesi,ma non contenuti in parentesi piu interne. Anche i bit eventuali che non sonoracchiusi tra nessuna parentesi, costituiscono un numero binario. Si vedano gliesempi nella tabella successiva.

Si scriva una grammatica G2, non estesa, per il linguaggio L2 ⊂ L1 definito cosı:

x ∈ L2 se e solo se

{

x ∈ L1 and

ogni numero binario in x termina con il bit 0

Esempi, dove i numeri binari cancellati sono quelli che invalidano la stringa:

numeri binari contenuti

valida 0 1 1 0 ( 1 0 ) 0 1 1 0, 1 0

valida 0 ( 1 0 ) 1 0 0(

0 ( 0 ) 0)

0 1 0 0, 1 0, 0 0, 0

non valida ( 0 ( 1 1 ) ( 0 ) ( 1 0 ) 1 ) 0 1, 1 1, 0, 1 0

non valida 1 1 1 1

6

Soluzione

Language L1 looks very similar to the Dyck language. One should remind that theDyck language over the alphabet { ‘ ( ’, ‘ ) ’ } can be defined by means of a simpleEBNF rule: S → S∗ | ‘ ( ’ S ‘ ) ’; or by means of two rules like S → N∗ andN → ‘ ( ’ S ‘ ) ’ with axiom S, so as to single out the role of the correspondingparentheses N . A quick transformation into BNF is: S → N S | ε and N → ( S ).

To apply here these known concepts, one just needs to put in binary numbers, excludevoid parentheses and recode all into BNF . This is done below.

(a) According to the definition in the text, a string of language L1 is a non-emptysequence of nests N and bits B interleaved, like (it may start by B instead):

N+ B+ N+ B+ . . . ∈(

N | B)+

Each nest N is a parenthesis pair that contains a string of the same type. Sofirst here is a straightforward EBNF grammar for language L1 (axiom S):

S →(

N | B)+

- non-empty sequence of nests N and bits B

N → ‘ ( ’ S ‘ ) ’ - parenthesis nest

B → 0 | 1 - bit

This EBNF grammar basically generates the Dyck language, where any twocorresponding parentheses, i.e., a nest, cannot be void and may either containa binary number, i.e., a sequence of one or more bits possibly interleaved withparenthesis nests, or just contain parenthesis nests not interleaved with any bits.

Notice one might explicitly write the axiomatic rule as follows:

S →(

N | B)∗

B N∗ | N+

where the alternative of either having at least one bit or none, is evident.

Then it is mechanically converted into a BNF grammar G1 by transforming theiterations into right recursions (axiom S):

G1

S → N S | B S | N | B - S equivalent to(

N | B)+

N → ( S )

B → 0 | 1

Grammar G1 is basically a well-known Dyck formulation that notoriously hasthe ELR (1) property; so it is deterministic and therefore unambiguous as well.

7

One can compact grammar G1 into only one BNF rule as follows (axiom S):

G′

1 : S → ( S ) S | 0 S | 1 S | ( S ) | 0 | 1

Of course, in such a form the grammar is less readable. It would be fairly morereadable by going back to the extended form (axiom S):

G′′

1 : S →(

‘ ( ’ S ‘ ) ’ | 0 | 1)+

though the extended form is not required by the exercise.

(b) Language L2 constrains the phrases of language L1 by requiring every binarynumber to end by zero. First the EBNF grammar is modified so as to complywith this constraint (axiom S), see also the observation before:

S →(

N | B)∗

0 N∗ | N+ - last bit is zero or no bits at all

N → ‘ ( ’ S ‘ ) ’

B → 0 | 1

This EBNF grammar forces the last bit of every binary number to be zero.Then a BNF grammar G2 for language L2 is mechanically obtained (axiom S):

G2

S → X 0 Y | Z

X → N X | B X | ε - X equivalent to(

N | B)∗

Y → N Y | ε - Y equivalent to N∗

Z → N Z | N - Z equivalent to N+

N → ( S )

B → 0 | 1

Grammar G2 is also unambiguous, basically for the same reasons as before(though this property is not requested).

Of course there may be other solutions, which possibly save a few nonterminalsor rules. For instance one might compact G2: remove Z and the rules that haveit on the left side, and use the axiomatic rule S → X 0 Y | N Y instead; thisreduces the grammar size. One might also replace N by ( S ) wherever it occursin the rules, as well as replace B in the obvious way. Thus one will end up witha highly compacted BNF grammar, still not ambiguous (axiom S):

G′

2

S → X 0 Y | ( S ) Y

X → ( S ) X | 0 X | 1 X | ε

Y → ( S ) Y | ε

It seems hard to go further and obtain a significantly more compact BNF

grammar, unless perhaps ambiguity is admitted. This is not explored here.

8

For completeness, here are two sample syntax trees of grammars G1 (left) and G2

(right) for the short strings 0 1 ( ( 1 0 ) 1 ) and 1 0 ( ( 0 ) ), respectively:

S

B

0

S

B

1

S

N

( S

N

( S

B

1

S

B

0

)

S

B

1

)

S

X

B

1

X

ε

0 Y

N

( S

Z

N

( S

X

ε

0 Y

ε

)

)

Y

ε

0 1 ( ( 1 0 ) 1 ) 1 0 ( ( 0 ) )

So one sees there is quite many a solution to this exercise, more or less compact.

9

2. Si vuole modellare grammaticalmente il costrutto case dello storico linguaggio diprogrammazione Pascal, che realizza il condizionale a piu vie. Ecco un esempio:

case 2 * (x - y) of

(* branch taken if expression 2 * (x - y) equals 1 *)

1 : begin (* branch with two statements *)

a := b + ( c - 1 ) * d;

b := c - 1 (* final semicolon is optional *)

end;

(* branch taken if expression 2 * (x - y) equals 3 or 4 *)

3, 4 : a := 2; (* branch with one statement *)

5 : ; (* a branch with an empty body *)

-8 : begin (* blocks may be nested *)

...

begin (* block with one statement *)

c := -3; (* final semicolon is optional *)

end;

...

end;

(* branch taken in all the other cases *)

otherwise ... (* default branch is optional *)

end

I commenti tra (* e *) non appartengono al linguaggio. Valgono queste specifiche:

• identificatori e costanti sono modellati dai terminali id e num, rispettivamente

• le espressioni sono numeriche, con variabili e costanti, operatori di addizione ‘+’,sottrazione ‘-’ e moltiplicazione ‘*’, e parentesi tonde ‘(’ e ‘)’; le precedenze traoperatori sono le solite: l’operatore ‘*’ ha priorita sugli operatori ‘+’ e ‘-’

• gli assegnamenti ‘:=’ hanno una variabile a sinistra a un’espressione a destra

• il blocco begin-end puo essere vuoto e in esso il punto-e-virgola ‘;’ e facoltativoprima della parola chiave end

• in case ci dev’essere almeno un ramo (branch) diverso dalla clausola otherwise,che e facoltativa e puo comparire solo per ultima

• le etichette di un ramo costituiscono una lista non vuota di costanti numeriche,con separatore virgola ‘,’ e terminatore due-punti ‘:’

• il costrutto case puo essere annidato

Se occorre, si immagini di completare ragionevolmente il costrutto case descrittoprima, motivando eventuali scelte non prescritte dall’esempio o dalle specifiche.

Si scriva una grammatica estesa (EBNF ), non ambigua, che modella il costruttocase di Pascal com’e tratteggiato sopra.

10

Soluzione

L’esempio e chiaro ed esaustivo. Si puo osservare che l’istruzione (statement) e dei tipiseguenti: vuota, assegnamento, blocco begin-end (eventualmente annidato), e case

(ricorsivamente); si veda la regola STATM. Ecco la grammatica (assioma CASE):

〈CASE〉 → case 〈EXPR〉 of 〈BODY〉 end

〈EXPR〉 → 〈TERM〉(

( ‘+ ’ | ‘− ’ ) 〈TERM〉)∗

〈BODY〉 → 〈BRANCH〉(

‘ ; ’ 〈BRANCH〉)∗

[‘ ; ’ 〈OTHER〉

]

〈TERM〉 → 〈FACT〉(

‘ ∗ ’ 〈FACT〉)∗

〈BRANCH〉 → 〈LABELS〉 ‘ : ’ 〈STATM〉

〈OTHER〉 → otherwise 〈STATM〉

〈FACT〉 → id | num | ‘ (’ 〈EXPR〉 ‘ )’

〈LABELS〉 → num(

‘ , ’ num)∗

〈STATM〉 → ε | 〈ASGN〉 | 〈BLOCK〉 | 〈CASE〉

〈ASGN〉 → id ‘ := ’ 〈EXPR〉

〈BLOCK〉 → begin 〈STATM〉(

‘ ; ’ 〈STATM〉)∗

end

Le parentesi quadre indicano opzionalita. Come succede in tanti linguaggi di program-mazione, il blocco begin-end - o un costrutto similare delimitato da altri simboli -contiene una o piu istruzioni; pero esso e facoltativo se ce n’e una sola. Inoltre datoche l’istruzione vuota e ammessa, il blocco puo anche essere vuoto.

La regola BLOCK non inserisce il separatore punto-e-virgola dopo l’ultima istruzione(nonterminale STATM) nel costrutto begin-end; tuttavia poiche l’istruzione vuota eammessa, il separatore risulta facoltativo in quel punto, come si vede nell’esempio.

L’esempio suggerisce che prima della parola chiave end terminante il costrutto case,non ci sia mai separatore punto-e-virgola. Coerentemente la grammatica proposta vi-eta di avere il separatore prima dello end finale di case: infatti la regola CASE non loprevede tra corpo (nonterminale BODY) ed end; e nella regola BODY ci dev’essere al-meno un ramo (nonterminale BRANCH) e ci puo essere la clausola otherwise (nonter-minale OTHER), ma nessuno dei due si puo ridurre alla stringa vuota ε. Il linguaggioPascal e strutturato proprio cosı, tuttavia si tratta di un dettaglio minimo.

La grammatica e in forma estesa (EBNF ), e non e ambigua poiche e costituita dacomponenti notoriamente non ambigui. Sono certamente possibili varianti, puramentesintattiche o magari con piccole differenze interpretative dell’esempio (sebbene i com-menti aiutino a capire), come per esempio se sia lecito avere un’istruzione o un bloccobegin-end vuoti, se sia facoltativo mettere begin-end dove c’e una sola istruzione oinserire un separatore punto-e-virgola prima dello end finale di case, e simili aspetti.

11

3 Analisi sintattica e parsificatori 20%

1. Si consideri la grammatica G seguente (assioma S), rappresentata mediante la suarete di macchine, che qui si riduce a una sola macchina:

G : S → a S b | b S a | ε

1S 2S

0S 5S

3S 4S

→ → →

a

b

S

b

S

a

Si risponda alle domande seguenti, usando la rappresentazione come macchina:

(a) Si mostri che la grammatica G non e ELR (1) costruendo la piu piccola porzionepossibile dell’automa pilota.

(b) Si applichi la procedura di costruzione diretta e semplificata del grafo di controlloPCFG della grammatica G, e si mostri su di esso che la grammatica non eELL (1). Si spieghi in dettaglio il calcolo degli insiemi guida significativi.

(c) Applicando il metodo di Earley alla grammatica G, si analizzi la stringa a b a b.Con riferimento al contenuto del vettore E si mostri che la stringa e accettata,come pure la stringa prefisso a b, mentre la stringa prefisso a b a e rifiutata. Siusi la tabella predisposta di seguito (il numero di righe non e significativo).

(d) (facoltativa) Si dica se il linguaggio L (G) generato dalla grammatica G e deter-ministico, argomentando la risposta.

PER QUANTO SEGUE VEDI ANCHE AVVISO SUL FRONTESPIZIO DEL TESTO

Chi preferisse rispondere con la metodologia classica di analisi LR e LL, usi lagrammatica G, che e gia in forma non estesa, invece della rete di macchine.

12

E (0) a E (1) b E (2) a E (3) b E (4)

13

Soluzione

(a) Ecco il grafo pilota della grammatica G, sviluppato quanto basta per decidere ildeterminismo:

0S ⊣1S ⊣

0S b

3S b

0S a

→

I0

I1 I2

a b

Gia con tre soli m-stati si vede che nello m-stato I1 c’e un conflitto di tipo shift-reduce sulla lettera b. Pertanto la grammatica G non e di tipo ELR (1). Il grafopilota completo e assai piu grande (il lettore lo puo costruire per esercizio).

(b) Ecco il grafo PCFG della grammatica G, costruito direttamente:

1S 2S

0S a b ⊣ 5S a b ⊣

3S 4S

→ → { a, b,⊣ } → { a, b,⊣ }

a

b

S

b

S

a

{ a, b }

{ a, b }

L’insieme di prospezione negli stati finali 0S e 5S e { a, b,⊣ }. Infatti il nontermi-nale S e seguito dai terminali a e b uscendo dagli stati 4S e 2S , rispettivamente;inoltre, essendo S assioma, c’e anche il terminatore ⊣. L’insieme di prospezionecoincide con l’insieme guida sulla freccia di uscita degli stati finali.

Entrambi gli insiemi guida sugli archi di chiamata (call arc) a S uscendo daglistati 1S e 3S , sono { a, b }. Infatti il nonterminale S inizia con i due terminalia e b, e tanto basta per includerli nell’insieme guida. Esso e nullabile, ma enecessariamente seguito da a e b uscendo da 4S e 2S , rispettivamente, e quei dueterminali sono gia nell’insieme guida. Non ci sono altri terminali da aggiungere(e certamente il terminatore ⊣ non va aggiunto).

Si vede subito che nello stato 0S l’insieme di prospezione o equivalentementel’insieme guida sulla freccia di uscita, ha elementi in comune con i due archi dispostamento a e b verso gli stati 1S e 3S , rispettivamente. Dunque in 0S c’econflitto (in termini ELR sarebbe di tipo spostamento-riduzione), pertanto ilgrafo PCFG non e deterministico e la grammatica G non e di tipo ELL (1).

14

(c) Ecco il vettore di Earley completo, con cinque elementi E (i) (0 ≤ i ≤ 4), per lastringa a b a b da analizzare:

E (0) a E (1) b E (2) a E (3) b E (4)

0S 0 1S 0 3S 1 1S 2 3S 3

0S 1 5S 0 5S 1 5S 0

2S 0 0S 2 0S 3 5S 2

4S 1 2S 0 0S 4

2S 2 4S 1

4S 3

b

b S a S

a

a

ε S

b

Poiche nell’elemento E (4) del vettore c’e la candidata finale⟨

5S 0⟩

che si

riferisce all’inizio del vettore, la stringa a b a b e accettata. Similmente, nell’ele-

mento E (2) c’e la candidata finale⟨

5S 0⟩

che si riferisce all’inizio del vettore,

dunque anche la stringa a b e accettata. Invece, nell’elemento E (3) c’e la candi-

data finale⟨

5S 1⟩

che pero non si riferisce all’inizio del vettore, e c’e anche la

candidata finale⟨

0S 3⟩

che pero si riferisce all’elemento stesso (dunque essa

corrisponde a riconoscere in loco la stringa vuota ε); in E (3) non ci sono altrecandidate finali e in particolare non ce n’e nessuna che si riferisca all’inizio delvettore; pertanto la stringa a b a e rifiutata.

Tramite frecce e rappresentata anche la ricostruzione all’indietro dell’albero sin-tattico della stringa a b a b da analizzare: in rosso gli spostamenti terminali;in rosa gli spostamenti nonterminali (con rispettiva riduzione); e in blu la cor-rispondenza tra spostamento nonterminale e la riduzione che lo ha abilitato.Ecco l’albero sintattico ricostruito della stringa a b a b:

S

0Sa→ 1S 1S

S→ 2S

0Sb→ 3S 3S

S→ 4S

0Sε→ 0S

4Sa→ 5S

2Sb→ 5S

S

a S

b S

ε

a

b

15

Per completezza si noti che le varie altre candidate finali con stato 0S cor-

rispondono tutte, tranne la prima, a elementi non iniziali per il vettore; pertantoesse non riconoscono alcun prefisso della stringa a b a b da analizzare. La primariconosce la stringa vuota ε che ovviamente e sempre prefisso, benche banale.

(d) Si puo osservare che il linguaggio L (G) generato dalla grammatica G, somigliamolto al linguaggio delle palindromi senza centro: ogni stringa di L (G) ha laforma u v, dove si ha v = h

(uR

)e la traslitterazione h scambia le lettere a e

b. La traslitterazione h non ha impatto sul determinismo poiche e biunivoca.Ragionevolmente pertanto, trascurando h l’analisi di L (G) deve procedere comeper le palindromi senza centro, ossia stringhe di tipo u uR, che notoriamentecostituiscono un linguaggio nondeterministico poiche un riconoscitore a pila none in grado di individuare deterministicamente il centro della stringa sorgente. Sene conclude che verosimilmente il linguaggio L (G) non e deterministico.

Del resto si noti che se alle stringhe del linguaggio L (G) si da un centro iden-tificabile deterministicamente, come per esempio sostituendo la regola S → ε

con la regola S → c, allora scompare il conflitto di tipo spostamento-riduzioneche figura nello m-stato I1 del grafo pilota, poiche non e piu finale lo stato0S della macchina che rappresenta la grammatica modificata. Cio corrobora -sebbene non dimostri - la conclusione di prima, ossia che il linguaggio originalesia nondeterministico proprio per l’impossibilita di individuare il centrostringa.

16

4 Traduzione e analisi semantica 20%

1. Nel linguaggio sorgente Ls ogni frase ha la struttura ( a+ b+ )+. Pertanto la generica

frase di Ls si presenta come una serie di blocchi, cosı:

am1 bn1 . . .

blocco︷ ︸︸ ︷

ami bni . . . amk bnk con k ≥ 1

Si consideri la traduzione τ tale che ogni blocco e trasformato cosı:

ami bniτ7→

cmi+ni se mi ≥ ni

dni−mi se mi < ni

Esempio:

a2 b2 a2 b3 a3 bτ7→ c4 d c4

Si risponda alle domande seguenti:

(a) Si scriva uno schema puramente sintattico (Gs, Gd) o equivalentemente unagrammatica di traduzione Gτ , per definire la traduzione τ ; si disegnino gli alberisintattici sorgente e destinazione (o unificandoli) per la stringa a2 b2 a2 b3 a3 b.

(b) (facoltativa) Si dica se la traduzione τ e calcolabile mediante un automa tradut-tore a pila deterministico Aτ , argomentando la risposta.

17

Soluzione

(a) The translation grammar Gτ below, defines the requested translation (axiom S):

Gτ

S → C S | D S | C | D

C → ac

C | P

D → D bd

| M bd

P → ac

P bc

| ac

bc

M → aε

M bε

| aε

bε

Here we draw a unified source and destination syntax tree for the sample trans-lation a2 b2 a2 b3 a3 b

τ=⇒ c4 d c4 (one might split it if preferable).

S

C

P

ac

P

ac

bc

bc

S

D

M

aε

M

aε

bε

bε

bd

S

C

ac

C

ac

C

P

ac

bc

The autoinclusive rule P generates equal numbers of source letters a and b

in a block, and translates them into as many destination letters c; while theright-linear rule C generates the possible additional a’s in the block and also

18

translates them into as many c’s; so in this case (which is m ≥ n) the lengthof the block translation amounts to the sum of the numbers of its a’s and b’s.The autoinclusive rule M generates as P does in the source, but it has an emptydestination; while the right-linear rule D generates the additional b’s (at leastone) in the block and translates them into as many destination letters d; so inthis case (which is m < n) the length of the block translation amounts to thedifference of the numbers of its b’s and a’s. The axiomatic rule, which is alsoright-linear, freely generates a sequence of block translations, where each blockis treated according to either case. This is a sufficient justification to prove thecorrectness of the translation grammar Gτ . It is also easy to get convinced thatthe source grammar Gs is not ambiguous. The sample syntax tree above helpsus visualize the grammar operation.

A different solution with fewer nonterminals but more alternatives for the samenonterminal, is the one below (axiom S):

G′

τ

S → P S | M bd

S | P | M bd

P → ac

P | ac

P bc

| ac

bc

M → M bd

| aε

M bε

| aε

bε

Grammar G′

τ is equivalent to Gτ , and is obtained from Gτ by removing nonter-minals C and D by giving their tasks to nonterminals P and M , respectively.

Notice that the source grammar G′

s is ambiguous: for instance, the source stringa a a b b = a 3 b 2 has two syntax trees, see below. The translation is the samehowever: string c 5 in both cases.

S

P

a P

a P

a b

b

S

P

a P

a P

a b

b

Also the source string a a b b b b = a 2 b 4 has two syntax trees and thus isambiguous, but its translation d 2 is the same in both cases. The ambiguitydegree quickly grows as the source string gets longer, but the correspondingdestination string is still unaffected and so grammar G′

τ is correct.

19

A minor optimised variant of grammar G′

τ is below (axiom S):

G′′

τ

S → P S | M S | P | M

P → ac

P | ac

P bc

| ac

bc

M → M bd

| aε

M bε

| aε

bε

bd

Grammar G′′

τ is obtained from G′

τ by differently placing the additional letter b

and its translation into d. Notice the source grammar G′′

s is ambiguous as well.

(b) To answer this question, one may consider a syntax analyser driven by the trans-lation grammar Gτ or directly reason on a generic pushdown transducer Aτ . Thesource grammar Gs that underlies grammar Gτ , is below (axiom S):

Gs

S → C S | D S | C | D

C → a C | P

D → D b | M b

P → a P b | a b

M → a M b | a b

With an easy reasoning, grammar Gs does not have the property ELR (orLR). In fact the languages generated by the nonterminals C and D containthe strings an bn and an bn+1 (n ≥ 1), respectively, and the source languageL (Gs) includes the union of the languages of C and D. As far as the pilot ofthe syntax analyser shifts on the n initial letters a, it will carry on in parallelboth the derivations that start by C and D and go on by P and M , respectively.But when the analyser encounters the first letter b, it will be unable to decidebetween reductions a b P and a b M ; essentially, it exhibits a reduce-reduceconflict. Therefore a syntax transducer driven by Gτ , is not deterministic.

As for the other solutions, grammars G′

τ and G′′

τ have a ambiguous source part,so both are completely useless for obtaining a deterministic syntax transducer.

On the other hand, we argue a generic pushdown transducer Aτ cannot be de-terministic. We know that each letter a encountered, has to be either translatedinto c or ignored, depending on the inequality m ≥ n being true or false for theblock under processing. Two design decisions are possible: either to immediatelyemit the c’s or to push the a’s onto the stack. The former strategy outputs awrong translation in the case false, and so we have to opt for the latter one.

When machine Aτ reads the first b, the stack contains m symbols a. Clearlyemitting the c’s would be too early since the truth status of inequality m ≥ n

is not known yet. Moreover machine Aτ cannot output the translation for theincoming b’s as it does not know whether it should be c or d. Machine Aτ isonly left the possibility of pushing also the b’s onto the stack. But with so doing,machine Aτ is prevented of verifying the inequality because the only way wouldbe to pop one a for each incoming b and test if the stack is empty or not beforereading the last b. We reasonably conclude that a pushdown transducer Aτ ableto compute this translation deterministically, does not exist.

20

2. Si vuole tradurre un’espressione da forma infissa a forma postfissa, servendosi di unagrammatica con attributi invece che di uno schema sintattico di traduzione. Ecco lasintassi dell’espressione da tradurre, aritmetica associativa a destra (assioma S):

S → E

E → T + E

E → T

T → ( E )

T → a

Il modello di espressione e molto semplice e comprende solo l’operatore di addizionee le parentesi. Il terminale a rappresenta genericamente variabili e costanti.

In particolare sono previste due traduzioni diverse ρ e σ, cosı:

• La traduzione ρ calcola l’usuale forma postfissa (associando a destra) e natural-mente elimina le parentesi. Esempio:

la stringa sorgente a +1 a +2 ( a +3 a ) +4 a

si traduce in ρ = a a a a +3 a +4 +2 +1

• La traduzione σ calcola l’usuale forma postfissa (associando a destra), ma solotra un numero dispari di parentesi annidate, mentre altrove (ossia tra un numeropari di parentesi) lascia la forma infissa, e naturalmente conserva le parentesi.Le parti di espressione esterne a parentesi sono considerate a livello pari diannidamento. Esempio:

la stringa sorgente a +1

(a +2 ( a +3 a ) +4 a

)

si traduce in σ = a +1

(a ( a +3 a ) a +4 +2

)

Nei due esempi dati sopra, la numerazione dell’operatore ‘+’ e solo un aiuto visivoper capire come funziona la traduzione, ma non appartiene alla grammatica.

In entrambi i casi l’espressione tradotta va rappresentata tramite un attributo τ ditipo stringa, emesso a livello della radice dell’albero sintattico. Si possono aggiungerealtri attributi, se lo si ritiene necessario od opportuno. Le tabelle da compilare congli attributi e le regole semantiche, sono gia predisposte di seguito.

Si risponda alle domande seguenti:

(a) Si scriva una grammatica con attributi Gρ che calcola la stringa traduzione ρ.

(b) Si scriva una grammatica con attributi Gσ che calcola la stringa traduzione σ, esi precisi se la grammatica Gσ e di tipo one-sweep (a una passata).

(c) (facoltativa) Si decori l’albero sintattico della stringa di esempio per la traduzioneσ, con gli attributi, i loro valori e le dipendenze funzionali tra attributi. L’alberoda decorare e gia dato nel seguito.

21

attributi da usare per le grammatiche - domande (a) e (b)

tipo nome (non)terminali dominio significato

sin τ S, E, T stringa traduzione(secondo ρ o σ)

22

sintassi calcolo attributi per la traduzione ρ - domanda (a)

S0 → E1

E0 → T1 + E2

E0 → T1

T0 → ( E1 )

T0 → a

23

sintassi calcolo attributi per la traduzione σ - domanda (b)

S0 → E1

E0 → T1 + E2

E0 → T1

T0 → ( E1 )

T0 → a

24

albero sintattico di a +(

a + ( a + a ) + a)

da decorare

S

E

T

a

+ E

T

( E

T

a

+ E

T

( E

T

a

+ E

T

a

)

+ E

T

a

)

25

Soluzione

(a) La grammatica con attributi Gρ e molto semplice e puramente sintetizzata: bastal’attributo sinistro τ (gia assegnato nelle specifiche) calcolato secondo la regolapostfissa posponendo l’operatore di addizione. Ecco la grammatica:

sintassi calcolo attributi per la traduzione ρ - domanda (a)

S0 → E1 τ0 = τ1

E0 → T1 + E2 τ0 = τ1 · τ2 · ‘ + ’ - regola postfissa

E0 → T1 τ0 = τ1

T0 → ( E1 ) τ0 = τ1 - elimina parentesi

T0 → a τ0 = ‘ a ’

L’operatore ‘ · ’ concatena le varie istanze dell’attributo stringa τ e le stringhecostanti che derivano dai terminali della grammatica. La funzione semanticaassociata alla regola sintattica di addizione calcola la forma postfissa e quellaassociata alla regola con parentesi, le elimina; il resto e ovvio.

(b) La grammatica con attributi Gσ e piuttosto semplice: la base e fornita dal-la grammatica Gρ costruita prima, cui basta aggiungere un attributo ereditato(destro) booleano λ che commuta tra livello di annidamento pari (false) e dis-pari (true) attraversando le parentesi, e che dirige il calcolo dell’attributo τ

selezionando la regola infissa o postfissa. Ecco gli attributi e la grammatica:

attributi da usare per le grammatiche

tipo nome (non)terminali dominio significato

sin τ S, E, T stringa traduzione(secondo ρ o σ)

des λ S, E, T booleano parita del livello diannidamento tra leparentesi

26

sintassi calcolo attributi per la traduzione σ - domanda (b)

S0 → E1

λ1 = false - inizializzazione

τ0 = τ1

E0 → T1 + E2

λ1 = λ0

λ2 = λ0

if λ0 = true then

τ0 = τ1 · τ2 · ‘ + ’ - regola postfissaelse

τ0 = τ1 · ‘ + ’ · τ2 - regola infissaendif

E0 → T1

λ1 = λ0

τ0 = τ1

T0 → ( E1 )λ1 = not λ0 - commutazione

τ0 = ‘ ( ’ · τ1 · ‘ ) ’ - conserva parentesi

T0 → a τ0 = ‘ a ’

I commenti mettono in evidenza somiglianze e differenze tra la grammatica Gσ

e la piu semplice Gρ. La funzione semantica associata alla regola sintattica diaddizione e formulata come condizionale e calcola la forma postfissa o infissa inalternativa. Le funzioni semantiche associate alla regola sintattica con parentesi,complementano la parita di livello di annidamento tra parentesi e conservano leparentesi stesse. La parita di livello e inizializzata a pari (false) nella regolasintattica assiomatica. Il resto e pure ovvio.

In Gσ e evidente che prima si scende calcolando l’attributo ereditato λ, e poi sisale calcolando l’attributo sintetizzato τ in modo postfisso o infisso secondo ilvalore di λ. Pertanto la grammatica Gσ e di tipo one-sweep (a una passata).

(c) L’albero sintattico e semplice da decorare, una volta progettata la grammaticacon attributi Gσ. Eccolo, con il calcolo degli attributi ereditati e sintetizzati inrosa e blu, rispettivamente:

27

albero sintattico decorato della stringa a +(

a + ( a + a ) + a)

da tradurre

S

E

T

a

+ E

T

( E

T

a

+ E

T

( E

T

a

+ E

T

a

)

+ E

T

a

)

a +(a(a + a)a + +

)= τ λ = false

a +(a(a + a)a + +

)= τ λ = false

a = τ λ = false(a(a + a)a + +

)= τ

λ = false

(a(a + a)a + +

)= τ λ = false

a(a + a)a + + = τλ = true

a = τ λ = true(a + a)a+ = τ

λ = true

(a + a) = τ λ = true a = τ λ = true

a + a = τ λ = false a = τ λ = true

a = τ λ = false a = τ λ = false

a = τ λ = false

Si vede bene il calcolo della traduzione τ , alternativamente postfisso e infissosecondo l’attributo λ. Alcune propagazioni di λ risultano inutili (frecce rosa trat-teggiate) poiche non ci sono piu operatori contenuti, ma naturalmente l’attributoλ e definito in tutti i nodi nonterminali e formalmente va calcolato ovunque.

28