Metalinguaggi

a.a. 2016-2017 - Laurea Magistrale in Teoria dei Linguaggi e della Comunicazione Audiovisiva

di Espressioni regolari, Automi a Stati Finiti e Linguaggi di Markup

di Espressioni regolari, Automi a Stati Finiti e Linguaggi di Markup

Espressioni Regolari

Pattern Matching

Pattern Matching

in un testo T vengono ricercate le stringhe che corrispondono a un pattern p (schema)

Pattern Matching

Pattern Matching

Pattern Matching

Ricerche più raffinate

◉cercare tutte le parole che terminano in -ato

◉le parole con al massimo 3 lettere

◉le frasi che iniziano con un articolo

◉le sequenze di numeri che formano una data

◉le frasi fatte da esattamente 6 parole

◉ecc...

strumento ideale per:

◉ ricercare pattern testuali elaborati

◉sostituire testo

Espressioni Regolari (RE)

Pattern

RE PATTERN

carattere /a/ “il cane”

stringa intera /cane/ “il cane mangia la pappa”

multiword /mark up/“il linguaggio di mark up” “il linguaggio di markup”

case sensitive /Cane/“Cane che non sei altro!” “il cane mangia la pappa”

Classi di caratteri

RE PATTERN

la lettera i oppure b /[ib]/ “l"aiuola” “l"ebano”

i numeri 1,2 o 3 /[123]/“1 kg di farina” “33 trentini”

Unisa o unisa /[Uu]nisa/“Unisa” “unisa”

? /[Ll]inguistic[aoi]/ ?

Alternativa tra RE

RE PATTERN

la stringa cane o la stringa gatto

/cane|gatto/ “cane” “gatto”

due re [Uu]nisa|[Ll]inguistic[ao] ?

Intervalli

RE PATTERN

qualsiasi lettera minuscola

/[a-z]/ “l"aiuola” “ebano”

qualsiasi lettera minuscola o maiuscola

/[A-Za-z]/"Linguistica" "linguistico"

qualsiasi numero /[0-9]/“1 kg di farina” “33 trentini”

Diverso da

RE PATTERN

non la lettera a /^a/ “bonobo”

“78”

non una lettera minuscola

/[^a-z]/“Linguistica” “92 leopardi”

non un numero da 2 a 5 /[^2-5]/“1 kg di farina”

“cavolfiore”

Abbreviazioni

\t tabulazione \n a capo

\w /[a-zA-Z]/ \W /[^a-zA-Z]/

\d /[0-9]/ \D /[^0-9]/

\s /\t\s/ \S /[^\t\s]/

Problemacome trovare i belati in corpus di dialoghi tra pecore?

bebeeee

beeeeeeeeee

bee

Moltiplicatori

/ba+/ 1<a<n “b”, “ba”, “baa”, “baaaaaaaa”

/ba*/ 0<a<n “b”, “ba”, “baaaaa”

/baa*/ 0<a<n “b”, “ba”, “baa”, “baaaaaaaa”

/tokens?/ 0<s<1 “token”, “tokens”

Wildcard

/./ qualsiasi carattere "a", "9", " ", "?", "-", "j", "£"...

/a.s/ qualsiasi stringa di 3 caratteri che inizia per a e finisce per s

"abs", "a#s", "a s", "a,s", "a_s"

/t.*s/qualsiasi stringa che inizia per

t e finisce per sts", "tas", "tacos", "tts", "tanti

auguri a carlos"

/.*/ qualsiasi stringa, anche vuota

intera linea fino al ritorno a capo

Esercizi1. tutte le vocali minuscole o maiuscole 2. le parole che iniziano per consonante

3. le parole che terminano con un segno di punteggiatura (es. "cane," "finito;" ecc.)

4. le parole che iniziano per "pre" o per "per"

5. le parole di 5 lettere che iniziano con "s" e finiscono con "o"

6. Il passato prossimo del verbo mangiare 7. le date in cui giorno, mese e anno sono tutti espressi da numeri

8. la sequenza alfanumerica dei codici fiscali

9. le url dei siti web

Bibliografia

◉http://regexr.com/ pagina web dove è possibile testare le espressioni regolari

◉http://www.regular-expressions.info/tools.html pagina di riferimento sulle re ed elenco di tools online e offline esistenti

◉http://stp.lingfil.uu.se/~santinim/ml/2014/JurafskyMartinSpeechAndLanguageProcessing2ed_draft%202007.pdf capitolo 2 sezione 2.1

Automi a Stati Finiti

RE e Automi a Stati Finiti

◉ Le RE sono un metalinguaggio per la ricerca di testi.

◉ Una RE è un modo per descrivere un Automa a Stati Finiti (ASF)

◉ Ogni RE può essere descritta come un ASF e viceversa.

◉ Una RE è un modo per descrivere un linguaggio regolare

◉ Un altro modo per descrivere un linguaggio regolare è quello di usare grammatiche regolari

Un ASF è definito da una quintupla di elementi:

◉ Q un insieme finito di N stati q0, q1,…qn

◉ ∑ un alfabeto finito di simboli di input

◉ q0 lo stato iniziale

◉ F l’insieme degli stati finali, tali che F⊆Q

◉ δ(q,σ) la funzione di transizione tra stati, tale che dato uno stato qi∈Q (stato di partenza) e un simbolo σ ∈Σ, δ(qi,σ)=qj

(stato di arrivo)

Automi a Stati Finiti

Automi a Stati FinitiUn ASF è il modello astratto di una macchina in grado di riconoscere se una stringa appartiene o meno a un certo linguaggio

Automi a Stati FinitiUn ASF riconosce una stringa x se e solo se la testina ha letto tutti i simboli che compongono x e l’ASF si trova in uno stato finale

ASF deterministici e non deterministici

Morfologia e ASF

Trasduttori a stati finitiMacchine astratte che leggono in input un insieme di stringhe X e generano in output un insieme di stringhe Y

Trasduttori a stati finiti

Bibliografia

◉http://madebyevan.com/fsm/ tool per creare ASF da browser

◉http://www.nooj-association.org/index.php software basato sugli ASF per creare grammatiche

◉http://stp.lingfil.uu.se/~santinim/ml/2014/JurafskyMartinSpeechAndLanguageProcessing2ed_draft%202007.pdf capitolo 2 sezione 2.2 (da 2.2.1 a 2.2.5)

Extensible Markup Language (XML)

Codificare un testo digitale

Metadati strutturali

Annotazione linguistica

Markup per codificare informazioni strutturali

Markup per codificare informazioni linguistiche

Bibliografia & Co.

◉ descrizione storica e tecnica dei linguaggi di markup, in particolare di XML (slides): http://www.di.unipi.it/~cappelli/seminari/galdi.pdf

◉esempio di corpus annotato http://www.corpusitaliano.it/

◉pagina che comprende un elenco di corpora annotati a diversi livelli http://www.ilc.cnr.it/it/content/risorse