From ae17655efb4ea4ec4801a39690ee91417a399059 Mon Sep 17 00:00:00 2001 From: Anton Johansson Date: Tue, 2 Dec 2008 17:06:04 +0100 Subject: [PATCH] =?utf8?q?SOme=20fixes,=20fr=C3=A5gest=C3=A4llning=20and?= =?utf8?q?=20stuff,=20vi=20snackar=20med=20honom=20imorgon.?= MIME-Version: 1.0 Content-Type: text/plain; charset=utf8 Content-Transfer-Encoding: 8bit --- books.bib | 20 +++++++++++++++++++- rapport.tex | 54 +++++++++++++++++++++++++++++++++--------------------- 2 files changed, 52 insertions(+), 22 deletions(-) diff --git a/books.bib b/books.bib index 29ea818..fa63988 100644 --- a/books.bib +++ b/books.bib @@ -13,7 +13,17 @@ Title = {Artificial intelligence: a modern approach}, Year = {2003}} -@book{witten, +@book{friedl, + author = {Jeffrey E. F. Friedl}, + editor = {Andy Oram}, + title = {Mastering Regular Expressions}, + year = {2002}, + isbn = {0596002890}, + publisher = {O'Reilly \& Associates, Inc.}, + address = {Sebastopol, CA, USA}, + } + + @book{witten, Address = {San Francisco, Calif.}, Author = {Witten, I. H and Frank, Eibe}, Publisher = {Morgan Kaufmann}, @@ -56,3 +66,11 @@ year = {2008}, howpublished = "\texttt{http://www.regular-expressions.info/email.html}" } + +@misc{doctor:website, + author = "Free Software Foundation, Inc.", + title = "Sourcecode of doctor.el", + month = "Oct", + year = {2008}, + howpublished = "\texttt{http://cvs.savannah.gnu.org/viewvc/emacs/emacs/lisp/play/doctor.el?revision=1.27.4.15&view=markup}" +} diff --git a/rapport.tex b/rapport.tex index 7c4478b..90d71ca 100644 --- a/rapport.tex +++ b/rapport.tex @@ -137,11 +137,12 @@ automation (Finite Automation) och reguljära uttryck och påvisade deras likhet. Både reguljära uttryck och Finite Automation är en del av den språktyp som brukar kallas \emph{reguljära språk}, (Regular Language). -I \cite{speech} av Jurafski \emph{et al.} ger man ett exempel på hur -Finite automation och Reguljära uttryck förhåller sig till -varandra. Säg att man ska definiera ett naturligt språk, för enkelhets -skull försöker vi definiera vad som är ''ko-språk''. Vi kan säga att -korrekt ''ko-språk'' definieras av kombinationerna: +I boken ''Speech and language processing\ldots '' \cite{speech} av Jurafski +\emph{et al.} ges ett exempel på hur Finite automation och Reguljära +uttryck förhåller sig till varandra. Säg att ett naturligt språk ska +definieras. För enkelhets skull försöker definieras ''ko-språk''. I +detta exempel är ett korrekt ''ko-språk'' definierat av +kombinationerna: \begin{verbatim} Muu! @@ -166,7 +167,8 @@ Tillstånden \verb!q0-q4! är de giltiga tillstånd som finns, \verb!q1! i figuren markerar möjliga för\-flyttningar mellan till\-stånden. Denna information går även att representera som en -\emph{State-transition-tabell}, som i Tabell~\ref{tab:statetranstable}. +\emph{State-transition-tabell}, som i +Tabell~\ref{tab:statetranstable}. \begin{table}[h] \centering @@ -199,26 +201,32 @@ Det korresponderande \textbf{Reguljära uttrycket} för att beskriva Muu+! \end{verbatim} -Man läser det ungefär som man läser vanlig text. \verb!M! är tillåtet +Detta läses ungefär som vanlig text. \verb!M! är tillåtet starttillstånd, följt av ett \verb!u!, sedan markerar operatorn \verb!u+! att en eller flera \verb!u! är tillåtna. Meningen avslutas med \verb?!?, vilket leder till sluttillståndet i exemplet. % Se sektion TODO för mer info om regexp syntax. + +\section{Litteraturstudie}\label{litteraturstudie} % REGEXP-MANUAL: % Står på sidan 848 i Norvig. +Följande avsnitt baseras på definitionen av reguljära uttryck som ges +i böckerna \cite{norvig, friedl} och Internet-sidan +\cite{regexinfo:website}. + Ett reguljärt uttryck består enkelt nog av text som ska matchas. Om -man vill matcha texten ''hej'' i en textsträng ''hoppsanhejsan'' så -blir det reguljära uttrycket helt enkelt bara ''hej'' och ''hej'':et i +texten ''hej'' ska matchas i en textsträng ''hoppsanhejsan'' så blir +det reguljära uttrycket helt enkelt bara ''hej'' och ''hej'':et i ''hoppsanhejsan'' matchas. Däremot är det mer sällan man använder reguljära uttryck för sådana enkla matchningar. Man vill i stället använda dem till att matcha \textbf{generella mönster}. Ett exempel på ett mönster skulle kunna vara en e-postadress på formen \verb!@.!, där \verb!! -kan innehålla (i detta exempel) alla siffror, alla små och stora -bokstäver (från A till Z), understreck, punkt, procenttecken, -bindestreck och plus. + kan innehålla (i detta exempel) alla siffror, alla små och stora + bokstäver (från A till Z), understreck, punkt, procenttecken, + bindestreck och plus. I stället för att behöva skriva ett textmönster för varje e-postadress som är möjlig att konstruera (i praktiken oräkneligt antal @@ -228,8 +236,9 @@ början\slash slutet av en hel sträng. Man kan också definiera teckenklasser som man vill inkludera i sitt uttryck, till exempel alla stora bokstäver, alla små bokstäver, siffror, eller till och med vilken godtycklig kombination av tecken som helst. I -Tabell~\ref{tab:texthandelser} visas en kort tabell med några -texthändelser och deras motsvarande reguljära uttryck. +Tabell~\ref{tab:texthandelser} (sammanställt från \cite{friedl}), +visas en kort tabell med några texthändelser och deras motsvarande +reguljära uttryck. \begin{table}[h] \centering @@ -276,8 +285,8 @@ samma teckenklass utan att behöva definiera en likadan klass för hela det antalet tecken vi vill matcha. Därför har man definierat något som kallas kvantifierare som gör att man kan bestämma hur många gånger man vill matcha en specifik klass, ett mönster eller bara ett tecken (så -kallade ''tokens''). Tabell \ref{tab:kvantifs} beskriver olika -kvantifierare. +kallade ''tokens''). Tabell \ref{tab:kvantifs} (innehåll sammanställt +från \cite{friedl}), beskriver olika kvantifierare. \begin{table}[h] \centering @@ -384,8 +393,11 @@ och % implementering av algoritmer osv. % TODO - resultat, användningsområden kopplade till AI. -Följande avsnitt berör olika applikationer av reguljära uttryck inom -ämnet Artificiell intelligens. + +Följande avsnitt tar upp några exempel på existerande applikationer av +reguljära uttryck inom ämnet Artificiell intelligens och ett +konstruerat exempel, avsnitt \ref{datah}. Resultatet baseras på +funktionerna som beskrivs i avsnitt~\ref{litteraturstudie}. \subsubsection{ELIZA} Mer avancerade former av Reguljära uttryck kan använda sig av @@ -431,9 +443,9 @@ motpart man kommunicerar med. ELIZA är implementerad för att svara på frågor som rör psykoterapi--så fort man lämnar det bekanta ämnet blir följdfrågorna ologiska ur ett mänskligt perspektiv. -Emacs implementation av ELIZA har en mängd hårdkodade svar. Följande -kodsnutt visar svaren som kan fås av indata som innehåller vissa -nyckelord gällade död: +Emacs implementation av ELIZA har en mängd hårdkodade svar, se källkod +\cite{doctor:website}. Följande kodsnutt visar svaren som kan fås av indata som +innehåller vissa nyckelord gällade död: \begin{footnotesize} \begin{verbatim} -- 2.11.4.GIT