# HG changeset patch # User Christian Urban # Date 1458666564 0 # Node ID c8ce95067c1a3ae1f14c5113d67d5cb2a0420849 # Parent cf3ca219c727948b139723839c312af1217de1e4 updated diff -r cf3ca219c727 -r c8ce95067c1a data.sty --- a/data.sty Mon Feb 22 22:09:31 2016 +0000 +++ b/data.sty Tue Mar 22 17:09:24 2016 +0000 @@ -207,7 +207,6 @@ \end{filecontents} \begin{filecontents}{interpreted.data} -%1 0.00503 200 1.005863 400 7.8296765 500 15.43106 @@ -219,7 +218,7 @@ \end{filecontents} \begin{filecontents}{interpreted2.data} -%1 0.00503 +0 0 200 1.005863 400 7.8296765 600 27.2321885 @@ -230,6 +229,7 @@ \end{filecontents} \begin{filecontents}{compiled2.data} +0 0 200 0.222058 400 0.215204 600 0.202031 diff -r cf3ca219c727 -r c8ce95067c1a handouts/ho01.tex --- a/handouts/ho01.tex Mon Feb 22 22:09:31 2016 +0000 +++ b/handouts/ho01.tex Tue Mar 22 17:09:24 2016 +0000 @@ -5,6 +5,9 @@ \usepackage{../data} %%http://regexcrossword.com/challenges/cities/puzzles/1 +%%https://jex.im/regulex/ +%%https://www.reddit.com/r/ProgrammingLanguages/comments/42dlem/mona_compiler_development_part_2_parsing/ +%%https://www.reddit.com/r/ProgrammingLanguages/comments/43wlkq/formal_grammar_for_csh_tsch_sh_or_bash/ \begin{document} \fnote{\copyright{} Christian Urban, 2014, 2015} diff -r cf3ca219c727 -r c8ce95067c1a handouts/ho02.pdf Binary file handouts/ho02.pdf has changed diff -r cf3ca219c727 -r c8ce95067c1a handouts/notation.pdf Binary file handouts/notation.pdf has changed diff -r cf3ca219c727 -r c8ce95067c1a handouts/notation.tex --- a/handouts/notation.tex Mon Feb 22 22:09:31 2016 +0000 +++ b/handouts/notation.tex Tue Mar 22 17:09:24 2016 +0000 @@ -8,8 +8,8 @@ \section*{A Crash-Course on Notation} -There are innumerable books available about automata and -formal languages. Unfortunately, they often use their own +There are innumerable books available about compiler, automata +and formal languages. Unfortunately, they often use their own notational conventions and their own symbols. This handout is meant to clarify some of the notation I will use. @@ -190,7 +190,7 @@ \noindent but using the big union notation is more concise. An important notion in this module are \defn{languages}, which -are sets of strings. The main goal for us will be how to +are sets of strings. One of the main goals for us will be how to (formally) specify languages and to find out whether a string is in a language or not.\footnote{You might wish to ponder whether this is in general a hard or easy problem, where diff -r cf3ca219c727 -r c8ce95067c1a handouts/scala-ho.pdf Binary file handouts/scala-ho.pdf has changed diff -r cf3ca219c727 -r c8ce95067c1a handouts/scala-ho.tex --- a/handouts/scala-ho.tex Mon Feb 22 22:09:31 2016 +0000 +++ b/handouts/scala-ho.tex Tue Mar 22 17:09:24 2016 +0000 @@ -54,9 +54,8 @@ \begin{lstlisting}[language={},numbers=none,basicstyle=\ttfamily\small] $ scala -Welcome to Scala version 2.11.2 (Java HotSpot(TM) 64-Bit Server VM). -Type in expressions to have them evaluated. -Type :help for more information. +Welcome to Scala version 2.11.8 (Java HotSpot(TM) 64-Bit Server VM). +Type in expressions for evaluation. Or try :help. scala> \end{lstlisting} @@ -133,12 +132,12 @@ \begin{center} \begin{tabular}{r@{\hspace{2mm}}r@{\hspace{2mm}}l@{\hspace{13mm}}l} - $r$ & $::=$ & $\varnothing$ & null\\ - & $\mid$ & $\epsilon$ & empty string\\ - & $\mid$ & $c$ & single character\\ - & $\mid$ & $r_1 \cdot r_2$ & sequence\\ - & $\mid$ & $r_1 + r_2$ & alternative / choice\\ - & $\mid$ & $r^*$ & star (zero or more)\\ + $r$ & $::=$ & $\ZERO$ & null\\ + & $\mid$ & $\ONE$ & empty string\\ + & $\mid$ & $c$ & single character\\ + & $\mid$ & $r_1 \cdot r_2$ & sequence\\ + & $\mid$ & $r_1 + r_2$ & alternative / choice\\ + & $\mid$ & $r^\star$ & star (zero or more)\\ \end{tabular} \end{center} @@ -155,19 +154,19 @@ actually very simple: It first requires an \emph{abstract class}, say, \code{Rexp}. This will act as the type for regular expressions. Second, it requires a case for each -clause in the grammar. The cases for $\varnothing$ and -$\epsilon$ do not have any arguments, while in all the other -cases we do have arguments. For example the character regular -expression needs to take as an argument the character it is -supposed to recognise. In Scala, the cases without arguments -are called \emph{case objects}, whereas the ones with -arguments are \emph{case classes}. The corresponding Scala -code is as follows: +clause in the grammar. The cases for $\ZERO$ and $\ONE$ do not +have any arguments, while in all the other cases we do have +arguments. For example the character regular expression needs +to take as an argument the character it is supposed to +recognise. In Scala, the cases without arguments are called +\emph{case objects}, whereas the ones with arguments are +\emph{case classes}. The corresponding Scala code is as +follows: \begin{lstlisting}[numbers=none] abstract class Rexp -case object NULL extends Rexp -case object EMPTY extends Rexp +case object ZERO extends Rexp +case object ONE extends Rexp case class CHAR (c: Char) extends Rexp case class SEQ (r1: Rexp, r2: Rexp) extends Rexp case class ALT (r1: Rexp, r2: Rexp) extends Rexp @@ -202,20 +201,19 @@ omit such ``tricks'' here. Note that Scala in its response says the variable \code{r} is -of type \lstinline[emph={ALT}]!ALT!, not \code{Rexp}. This -might be a bit unexpected, but can be explained as follows: -Scala always tries to find the most general type that is -needed for a variable or expression, but does not -``over-generalise''. In our definition the type \code{Rexp} is -more general than \lstinline[emph={ALT}]!ALT!, since it is the -abstract class. But in this case there is no need to give -\code{r} the more general type of \code{Rexp}. This is -different if you want to form a list of regular expressions, -for example +of type \code{ALT}, not \code{Rexp}. This might be a bit +unexpected, but can be explained as follows: Scala always +tries to find the most general type that is needed for a +variable or expression, but does not ``over-generalise''. In +our definition the type \code{Rexp} is more general than +\code{Rexp}, since it is the abstract class. But in this case +there is no need to give \code{r} the more general type of +\code{Rexp}. This is different if you want +to form a list of regular expressions, for example \begin{lstlisting}[numbers=none] -scala> val ls = List(ALT(CHAR('a'), CHAR('b')), NULL) -ls: List[Rexp] = List(ALT(CHAR(a),CHAR(b)), NULL) +scala> val ls = List(ALT(CHAR('a'), CHAR('b')), ZERO) +ls: List[Rexp] = List(ALT(CHAR(a),CHAR(b)), ZERO) \end{lstlisting} \noindent In this case, Scala needs to assign a common type to @@ -301,8 +299,8 @@ \begin{center} \begin{tabular}{r@{\hspace{2mm}}c@{\hspace{2mm}}l} -$rev(\varnothing)$ & $\dn$ & $\varnothing$\\ -$rev(\epsilon)$ & $\dn$ & $\epsilon$\\ +$rev(\ZERO)$ & $\dn$ & $\ZERO$\\ +$rev(\ONE)$ & $\dn$ & $\ONE$\\ $rev(c)$ & $\dn$ & $c$\\ $rev(r_1 + r_2)$ & $\dn$ & $rev(r_1) + rev(r_2)$\\ $rev(r_1 \cdot r_2)$ & $\dn$ & $rev(r_2) \cdot rev(r_1)$\\ diff -r cf3ca219c727 -r c8ce95067c1a slides/compiled.data --- a/slides/compiled.data Mon Feb 22 22:09:31 2016 +0000 +++ b/slides/compiled.data Tue Mar 22 17:09:24 2016 +0000 @@ -1,6 +1,6 @@ %% LaTeX2e file `compiled.data' %% generated by the `filecontents' environment -%% from source `slides01' on 2013/12/01. +%% from source `annonce' on 2016/02/23. %% %1 0.234146 %5000 0.227539 diff -r cf3ca219c727 -r c8ce95067c1a slides/compiled2.data --- a/slides/compiled2.data Mon Feb 22 22:09:31 2016 +0000 +++ b/slides/compiled2.data Tue Mar 22 17:09:24 2016 +0000 @@ -1,7 +1,8 @@ %% LaTeX2e file `compiled2.data' %% generated by the `filecontents' environment -%% from source `slides01' on 2013/12/01. +%% from source `annonce' on 2016/02/23. %% +0 0 200 0.222058 400 0.215204 600 0.202031 diff -r cf3ca219c727 -r c8ce95067c1a slides/interpreted.data --- a/slides/interpreted.data Mon Feb 22 22:09:31 2016 +0000 +++ b/slides/interpreted.data Tue Mar 22 17:09:24 2016 +0000 @@ -1,8 +1,7 @@ %% LaTeX2e file `interpreted.data' %% generated by the `filecontents' environment -%% from source `slides01' on 2013/12/01. +%% from source `annonce' on 2016/02/23. %% -%1 0.00503 200 1.005863 400 7.8296765 500 15.43106 diff -r cf3ca219c727 -r c8ce95067c1a slides/interpreted2.data --- a/slides/interpreted2.data Mon Feb 22 22:09:31 2016 +0000 +++ b/slides/interpreted2.data Tue Mar 22 17:09:24 2016 +0000 @@ -1,8 +1,8 @@ %% LaTeX2e file `interpreted2.data' %% generated by the `filecontents' environment -%% from source `slides01' on 2013/12/01. +%% from source `annonce' on 2016/02/23. %% -%1 0.00503 +0 0 200 1.005863 400 7.8296765 600 27.2321885 diff -r cf3ca219c727 -r c8ce95067c1a slides/slides02.tex --- a/slides/slides02.tex Mon Feb 22 22:09:31 2016 +0000 +++ b/slides/slides02.tex Tue Mar 22 17:09:24 2016 +0000 @@ -12,7 +12,7 @@ numbers=none, xleftmargin=0mm} -\pgfplotsset{compat=1.11} +\pgfplotsset{compat=1.12} \newcommand{\bl}[1]{\textcolor{blue}{#1}} diff -r cf3ca219c727 -r c8ce95067c1a slides/slides08.pdf Binary file slides/slides08.pdf has changed diff -r cf3ca219c727 -r c8ce95067c1a style.sty --- a/style.sty Mon Feb 22 22:09:31 2016 +0000 +++ b/style.sty Tue Mar 22 17:09:24 2016 +0000 @@ -9,6 +9,11 @@ \definecolor{darkblue}{rgb}{0,0,0.6} \usepackage[colorlinks=true,urlcolor=darkblue,linkcolor=darkblue]{hyperref} +%%% fo regular expressions +\newcommand{\ZERO}{\mbox{\bf 0}} +\newcommand{\ONE}{\mbox{\bf 1}} + + %%% for trees %% http://anorien.csc.warwick.ac.uk/mirrors/CTAN/graphics/pgf/contrib/forest/forest.pdf