Knowledge Discovery nella Diagnosi di Sistemi Attivi · Relazione fra Alberi Sintattici e...

Analisi Sintattica

Ruolo dell'analizzatore sintattico:

Classificazione degli analizzatori sintattici per grammatiche libere dal contesto:

1. Universali inefficienti

2. Top-down

3. Bottom-up

Tecnologie dei Linguaggi Artificiali 4. Analisi sintattica 1

Analizzatorelessicale

programma sorgente

simbolo

next()

Analizzatoresintattico

SymbolTable

Resto del Front-End

albero sintattico

codice intermediointermedia

Derivazioni

Processo con cui G definisce L operativamente (strumento generativo)

Derivazione: Idea precisa della costruzione top-down dell'albero sintattico Produzione vista come una regola di riscrittura: A : A sostituito da

Derivazione di (id) da E = dimostrazione che (id) è una istanza di E (frase, se derivata dall'assioma)

Generalizzazione: 1 2 n 1 deriva n (in più passi)

Notazione


deriva in un passo

deriva in zero o più passi

deriva in uno o più passi

*

derivazione

albero sintattico

E E E deriva E (forma sentenziale)

E * E (E) * E

E E (E) (id) (frase)

E E + E | E * E | (E) | E | id

+

Derivazioni (ii)

Possibile derivare una frase in diversi modi

Derivazioni canoniche

S forma sentenziale sinistra

S forma sentenziale destra


sinistra

destraad ogni passo, sostituzione del nonterminale più a

sinistra

destra

s

d

*

d

*

s

Relazione fra Alberi Sintattici e Derivazioni

Albero sintattico = rappresentazione grafica di una derivazione indipendentemente dall'ordine scelto nelle sostituzioni (rappresentazione più diretta della derivazione)


E

E

( E )

E + E

id id

E E + E | E * E | (E) | E | id

Variazioni nell'ordine in cui le produzioni sono applicate possono essere eliminate considerando le derivazioni canoniche

Ogni albero sintattico è associato ad una sola derivazione canonica (sinistra e destra)

G ambigua: quando frase associata a più alberi sintattici associata a più derivazioni canoniche

Relazione fra Alberi Sintattici e Derivazioni (ii)

1. E E + E id + E id + E * E id + id * E id + id * id

2. E E * E E E * E id + E * E id + id * E id + id * id


E E + E | E * E | (E) | E | id possibile derivare canonicamente in più modiid + id * id

s s s s s

s s s s s

E

E + E

id E * E

id id

E

E * E

E + E

id id

id

associazione corretta (1) associazione nonriflessa nell'albero (2)

Ambiguità

G ambigua: quando G produce più alberi sintattici per una frase ( quando G produce più derivazioni canoniche per una frase)

Possibile mantenere G ambigua Regole di disambiguamento: scartano alberi sintattici alternativi

Eliminzione della ambiguità in G:


stat if expr then stat | if expr then stat else stat | other

if E1 then S1 else if E2 then S2 else S3

( non ambigua)

stat

if expr then stat else stat

if expr then stat else statE1 S1

E2 S2 S3

Ambiguità (ii)

Regola di disambiguamento: Ogni else bilancia il then sbilanciato più vicino


if E1 then if E2 then S1 else S2

(ambigua)

stat

if expr then stat

if expr then stat else statE1

E2 S1 S2

stat if expr then stat | if expr then stat else stat | other

stat

if expr then stat else stat

if expr then stat E1

E2 S1

S2

(preferita nei LP)

?

Ricorsione Sinistra

G ricorsiva a sinistra: se A (A A) intrattabile con parsing top-down

1. Ricorsione diretta semplice:

2. Ricorsione diretta generale:

3. Ricorsione indiretta:


A A | A A’A’ A’ |

E E + T | TE TE’E’ +TE’ |

A A1 | A2 | ... | An | 1 | 2 | ... | mA 1A’ | 2A’ | ... | mA’A’ 1A’ | 2A’ | ... | nA’ |

E E + T | E T | TE TE’E’ +TE’ | TE’ |

S Aa | bA Ac | Sd |

S Aa Sda

S Aa | bA Ac | Bd | eB Bf | Sg | h

S Aa Bda Sgda

A

A

A

A

A'

A'

A'

+

Ricorsione Sinistra (ii)

Algoritmo per l'eliminazione della ricorsione sinistra:

Hp: G senza


cicli: A AA

+

condizione sufficiente

Ordina i nonterminali: A1, A2, ..., An;

for i=1 to n do

for j=1 to i-1 do

Sostituisci ogni produzione Ai Aj con le produzioni Ai 1 | 2 | ... | k, in cui Aj 1 | 2 | ... | k sono tutte le produzioni correnti di Aj

end-for;

Elimina le eventuali ricorsioni sinistre dirette nelle produzioni di Ai

end-for.

A1

A2

.

.

.

Aj

.

.

.

Ai

.

.

.

An

Relazione tra Grammatiche ed Espressioni Regolari

espressione regolare G equivalente

Algoritmo per generare G partendo dall'NFA = (, S, T, s0, F)


(a | b)*abb a b b1 2 3 4

a

b

A1 aA1 | bA1 | aA2

A2 bA3

A3 bA4

A4

stato i S, crea un nonterminale Ai;

transizione i j T, crea una produzione Ai aAj;

stato finale i F, crea una produzione Ai ;

Assioma di G = nonterminale corrispondente ad s0.

a

2 3

Tabella degli Operatori e Grammatica delle Espressioni

Regole di precedenza / associatività: stabiliscono gli operandi di ogni operatore

G per espressioni: specificabile sulla base della tabella degli operatori


precedenze

Associazione Operatori Nonterminale

sinistra + expr

sinistra * term

livello di precedenza nonterminale

Ulteriore nonterminale factor per le unità di base

expr expr + term | expr – term | term

term term * factor | term / factor | factor

factor digit | (expr)

precedenza crescente factor

associazioni

Tabella degli Operatori e Grammatica delle Espressioni (ii)Data la seguente tabella degli operatori, con precedenza crescente dall'alto verso il basso:

specificare la BNF del corrispondente linguaggio delle espressioni sulla base dei seguenti requisiti:

• gli elementi atomici della espressione sono costanti o identificatori;

• la precedenza / associatività relativa a + e * può essere alterata dalle parentesi;

• la precedenza / associatività relativa a and e or non può essere alterata dalle parentesi.


Operatori Associatività

and, or destra

<, > non associativo+, * sinistra

(a*(b+24)) > x+y and c < z+12 or (d+3)*4 > 10

Operatori Associatività Nonterminale

and, or destra E

<, > non associativo T+, * sinistra S

F

E T and E | T or E | TT S > S | S < S | SS S + F | S * F | FF id | num | ( S )

Knowledge Discovery nella Diagnosi di Sistemi Attivi · Relazione fra Alberi Sintattici e...

Documents

Transcript of Knowledge Discovery nella Diagnosi di Sistemi Attivi · Relazione fra Alberi Sintattici e...