Knowledge Discovery nella Diagnosi di Sistemi Attivi

Analisi Lessicale Ruolo primario = processo di astrazione: [caratteri] [simboli]

Ruolo secondario

Vantaggi nella separazione tra analisi sintattica e analisi lessicale:

1. Semplicità di progetto (la sintassi non si preoccupa di spaziatura, commenti, ...)

2. Efficienza

3. Portabilità

Tecnologie dei Linguaggi Artificiali 2. Analisi lessicale 1

AnalizzatoreLessicale

programma sorgente

simbolo

next()

AnalizzatoreSintattico

SymbolTable

rimozione spaziatura

rimozione commenti

collegamento tra errori e linee sorgente (chiarezza dei messaggi di errore)

(funzione ausiliaria)

pseudo-simboli

Specifica dei Simboli

Stringa lessicale: sequenza significativa di caratteri (lexeme)

Simbolo: astrazione di una classe di stringhe lessicali

Pattern: regola per descrivere le istanze di un simbolo (espressione regolare)

Attributo lessicale: quando il simbolo è astrazione di più stringhe lessicali


alfa = (beta * 3) ⟨id, alfa⟩ ⟨assign, ⟩ ⟨left, ⟩ ⟨id, beta⟩ ⟨times, ⟩ ⟨num, 3⟩ ⟨right, ⟩

Automi Finiti Formalismo per descrivere certi tipi di algoritmi (“macchine”)

In particolare: per controllare l'appartenenza di una stringa a un linguaggio regolare (matching stringa – expreg)

Forte correlazione tra

Processo di riconoscimento di un id definito dalla sequenza delle transizioni coinvolte

Linguaggio regolare riconosciuto = { cammini nell'automa }


automi finiti

espressioni regolari

id lettera (lettera | cifra) processo di riconoscimento di un id mediante un diagramma

1 lettera 2

lettera

cifra

Stati: cosa è già stato riconosciuto

Transizioni: cambiamento di stato causato dal matching di un carattere

12222a l f a

un cammino che genera la stringa "alfa"

Automi Finiti Deterministici

Def: Un DFA è una quintupla M = (, S, T, s0, F), dove:

= alfabeto

S = insieme degli stati

T: S S = funzione di transizione (deterministica)

s0 = stato iniziale (unico)

F S = insieme degli stati finali (non vuoto)

L riconosciuto da M L(M) = { stringhe generate da un percorso che termina in uno stato finale }


Automi Finiti Deterministici (ii)Note : comparazione della definizione formale di DFA con l'esempio diagrammatico (id)

1. Stati identificabili con qualsiasi etichetta (numeri, lettere, stringhe, ...)

2. Fattorizzazione (astrazione) di n transizioni, una lettera/cifra, mediante la transizione lettera/cifra

3. Def T: S S = funzione T(s, c) deve avere un valore (s, c) transizioni mancanti!

Stato di errore: doppio significato


transizioni mancanti transizioni di errore

1 lettera

lettera

cifra

errore

altroaltro

qualsiasi

lettera (lettera|cifra)

altro c ( - { caratteri coinvolti nelle altre transizioni uscenti dallo stesso stato })

significato sensibile al contesto

non è un identificatore (da stato non-finale)

identificatore seguito da separatore (da stato finale) maximal munch

possibili caratteri di input

2

Esempi di DFA in Forma Diagrammatica

1. L = { x | x include esattamente un b }

2. L = { x | x include al più un b }

3. L = { x | x = costanti numeriche in notazione scientifica }

4. L = { x | x = commento Pascal }

5. L = { x | x = commento C }


b

notbnotb

b

notbnotb

+

cifra

cifra

cifra

. cifra

cifra

E+

cifra

cifra

cifra

{

altro

}

1 2 3 4 5

altro */ /

altro

cifra [0-9]

nat cifra

snat (|) ? nat

num snat (“.”nat) ? (E snat) ?E

**

Aumento della Semantica nei DFA

Rappresentazione non descrive ogni aspetto algoritmico del riconoscimento

Errore backtracking o return(ERROR) ?

Stato finale ?

Matching del carattere ? (accumulazione nel lexeme)

Maximal munch ?

E sempio : identificatore Pascal


start lettera [altro]inside

lettera

cifra

return(id)

transizioni non-lettera

carattere di lookahead (non consumabile)

Inoltre: esprime il maximal munch

end

diagrammaticaformale

Problema dello Stato Iniziale Poiché diversi token in un LP combinazione (fusione) di diversi automi

1. Caso “predittivo”: :=, <=, = (senza ambiguità)

2. Caso ambiguo: <=, <>, < (dovremmo)

In t eoria : combinazione manuale di tutti i token in un grosso DFA complesso!Meglio: estendere DFA a NFA + algoritmo: NFA DFA equivalente (approccio modulare)

Tecnologie dei Linguaggi Artificiali 2. Analisi lessicale

<

<

8

:

<

=

=

=

return(ASSIGN)

return(LE)

return(EQ)

<=

>

return(LE)

return(NE)

return(LT)>

return(LE)

return(NE)

return(LT)

=

[altro]

<

Transizione Vuota

-transizione

Vantaggio: semplice e sistematica combinazione dei riconoscitore dei simboli ("colla" per gli NFA)


formalmente: matching della stringa vuota ()

intuitivamente: effettuata “spontaneamente” (senza consumo del carattere)

:

<

=

=

=

Automi Finiti Nondeterministici

Def: Un NFA è una quintupla M = (, S, T, s0, F), dove:

= alfabeto

S = insieme degli stati

T: S ( {}) 2S = funzione di transizione 2 cause di nondeterminismo

s0 = stato iniziale

F S = insieme degli stati finali

L riconosciuto da M L(M) = { x | x = c1c2...cn, ci ( {}), ed s1 T(s0, c1), s2 T(s1, c2), ... sn T(sn-1, cn), sn F }

Note:

1. x = c1c2...cn, in effetti |x| n

2. Nondeterminismo nella scelta di si T(si-1, ci)

3. Formalmente, NFA non rappresenta un algoritmo, ma può essere simulato da un algoritmo con backtracking ( problema di efficienza)


-transizioni

stesso c per diverse transizioni

Esempi di NFA in Forma Diagrammatica

Riconoscimento di abb

Riconoscimento di L((a | )b) in particolare: , a, b

DFA equivalente:


1

2

3

4

a b

a

1 2 4 2 4 a b b

1 3 4 2 4 2 4a b b

a

bb

b

diversi cammini per la stessa stringa

Esempi di NFA in Forma Diagrammatica (ii)

acab (a | c)b

Tecnologie dei Linguaggi Artificiali 2. Analisi lessicale

c

12

2

3

5

7

1

4

6

8 9 10

a

b

Automi Specificati da Tabelle delle Transizioni

Assunzioni:


Codice generico verdetto

stringa in inputDFA

1lettera

2

lettera

cifra

[altro]3

c

lettera cifra altro F

1 2

2 2 2 [3]

3

1 2 3 4 5

altro *

/ /

altro

c

/ * altro F

1 2

2 3

3 4 3

4 5 4 3

5

Caselle vuote transizioni non specificate

s0 = primo della lista

Estensione informativa stati Fconsumo di c

* *

Automi Specificati da Tabelle delle Transizioni (ii)

Codice generico 3 strutture dati(semplice, eppure universale)

Algoritmo table-driven:


T[stato,c] transizioni interi

Cons[stato,c] Booleani true: avanti (consumo)

F[stato] Booleani true: stato finale

stato := 1; c := next();while not F[stato] and not error(stato) do begin nuovo_stato := T[stato,c]; if Cons[stato, c] then c := next(); stato := nuovo_stato end;if F[stato] then accetta.

ex: stato = -1

Automi Specificati da Tabelle delle Transizioni (iii)

Note sugli algoritmi table-driven:

1. Vantaggi:

2. Svantaggi: spreco di memoria (tabelle sparse compressione)

3. Tecnica estendibile ai NFA

Problema di fondo: Expreg DFA in due passi (automatici nei generatori):


Codice generico

Ridotta dimensione del codice

Facile manutenzione del codice

backtracking inefficiente: meglio trasformare NFA DFA

Codice generico verdetto

stringa in input

DFANFAExpreg1 2

T[stato,c] = { stati }

Expreg NFA (Costruzione di Thompson)

Metodo:

1. Expreg atomica: x =

2. Concatenazione: xy

3. Alternativa: x | y

4. Ripetizione: x*


Costruzione incrementale partendo dagli automi (a, )-transizioni: per incollare insieme sotto-automiAutoma finale = riconoscitore di L(r)

lettera *

|

lettera cifra

a

a

in generale

(automi standardizzati)

x y

x

y

x

5. Parentesi: (x) automa invariato

Expreg NFA (Costruzione di Thompson) (ii) Note :

nuovo stato nuovo nome

Proprietà dell'NFA finale (per costruzione):

1. NFA riconosce L(r)

2. Numero-stati(NFA) 2 * (simboli in r)

3. NFA ha

4. stato NFA: possibile uno fra due casi

Costruzione non unica (semplificazione):

xy:


1 stato iniziale (nessuna transizione entrante)

1 stato finale (nessuna transizione uscente)

1 transizione uscente marcata da c al più 2 transizioni uscenti marcate da

x y x y

Costruzione di Thompson: Esempi


a b

a b

a b

a

ab | aa b

ab

ab | a

|

a

a b

NFA DFA

Rimozione di transizioni

Def di -closure:

1. Stato singolo: s -closure(s) { s’ | s ... s’ in M } { s }

2. Insieme di stati: S -closure(S)


empty (-transizioni) -closure = { stati raggiungibili da -transizioni }multiple (su singolo c) { stati raggiungibili con stesso c }

a

= costruzione di Thompson per a*

1 = { 1, 2, 4 }2 = { 2 }3 = { 2, 3, 4 }4 = { 4 }

U ss S

{1,3} = 1 3 = {1,2,4} {2,3,4} = {1,2,3,4}

1 2 3 4

(cause di nondeterminismo)

Subset Construction

M M’

Computazione di S’, T’, F’:


NFA DFA M = (, S, T, s0, F)

M’ = (, S’, T’, s’0, F’), dove

S’ := { s’0 }; T’ := ∅;

repeat

Scegli un nodo non marcato AS’;

for each c che marca una transizione di M uscente da un nodo in A do

begin

A’c := { z | sA, sz T };

A’c := -closure(A’c);

if A’c S’ then S’ := S’ { A’c };

T’ := T’ { A A’c }

end;

Marca A

until tutti i nodi in S’ sono marcati;

F’ := { A | AS’, A F ∅ }.

c

ccc

AA’c A’c

S’ 2S T’: S’ S’s’0 = s0

F’ S’

c

Esempi NFA DFA

1.

2.


a

1 2 3 4

s’0 = s0 = 1 = {1, 2, 4 }

{1,2,4} a{2,3,4}

a

ab | a

a b

a

s’0 = 1 = {1, 2, 6 }

1

2 3 4 5

6 7

8 {1,2,6} a {3,4,7,8} {5,8}b

a*

Esempi NFA DFA (ii)

3.


lettera (lettera | cifra)*

lettera

cifra

lettera 1 2 3 4

5 6

7 8

9 10

{1}lettera

{2,3,4,5,7,10}

s’0 = { 1 }

lettera

{4,5,6,7,9,10}

{4,5,7,8,9,10}cifra

lettera

cifra lettera

cifra

Knowledge Discovery nella Diagnosi di Sistemi Attivi

Documents

Transcript of Knowledge Discovery nella Diagnosi di Sistemi Attivi