# HG changeset patch
# User Christian Urban <urbanc@in.tum.de>
# Date 1540247831 -3600
# Node ID d236e75e1d55c6cf5fa66ecc4b7e1315ce74e25e
# Parent  19de761b69e918c10f13c890afe636922c7fb52b
updated

diff -r 19de761b69e9 -r d236e75e1d55 grammar.sty
--- a/grammar.sty	Tue Oct 16 14:40:30 2018 +0100
+++ b/grammar.sty	Mon Oct 22 23:37:11 2018 +0100
@@ -1,4 +1,4 @@
 \usepackage{listproc}
 \usepackage{plstx}
 
-\newcommand*{\meta}[1]{{\ensuremath{\langle}\textit{#1}\/\ensuremath{\rangle}}}
+\newcommand*{\meta}[1]{{\textbf{\textit{#1}}}}
diff -r 19de761b69e9 -r d236e75e1d55 handouts/ho05.pdf
Binary file handouts/ho05.pdf has changed
diff -r 19de761b69e9 -r d236e75e1d55 handouts/ho05.tex
--- a/handouts/ho05.tex	Tue Oct 16 14:40:30 2018 +0100
+++ b/handouts/ho05.tex	Mon Oct 22 23:37:11 2018 +0100
@@ -17,8 +17,8 @@
 example for which there exists no regular expression is the
 language of well-parenthesised expressions. In languages like
 Lisp, which use parentheses rather extensively, it might be of
-interest whether the following two expressions are
-well-parenthesised (the left one is, the right one is not):
+interest to know whether the following two expressions are
+well-parenthesised or not (the left one is, the right one is not):
 
 \begin{center}
 $(((()()))())$  \hspace{10mm} $(((()()))()))$
@@ -29,7 +29,7 @@
 problems, we need more powerful techniques than regular
 expressions. We will in particular look at \emph{context-free
 languages}. They include the regular languages as the picture
-below shows:
+below about language classes shows:
 
 
 \begin{center}
@@ -46,10 +46,30 @@
 \end{tikzpicture}
 \end{center}
 
-\noindent Context-free languages play an important role in
-`day-to-day' text processing and in programming languages.
-Context-free languages are usually specified by grammars. For
-example a grammar for well-parenthesised expressions is
+\noindent Each ``bubble'' stands for sets of languages (remember
+languages are sets of strings). As indicated the set of regular
+languages are fully included inside the context-free languages,
+meaning every regular language is also context-free, but not vice
+versa. Below I will let you think for example what the context-free
+grammar is for the language corresponding to the regular expression
+$(aaa)^*a$.
+
+Because of their convenience, context-free languages play an important
+role in `day-to-day' text processing and in programming
+languages. Context-free in this setting means that ``words'' have one
+meaning only ansd this meaning is independend from in which context
+the ``words'' appear. For example ambiguity issues like
+
+\begin{center}
+\tt Time flies like an arrow; fruit flies like a banana.
+\end{center}  
+
+\noindent
+from natural languages were the meaning of \emph{flies} depend on the
+surounding \emph{context} are avoided as much as possible.
+
+Context-free languages are usually specified by grammars. For example
+a grammar for well-parenthesised expressions can be given as follows:
 
 \begin{plstx}[margin=3cm]
 : \meta{P} ::=  ( \cdot  \meta{P} \cdot ) \cdot \meta{P}
@@ -66,7 +86,8 @@
 
 In general grammars consist of finitely many rules built up
 from \emph{terminal symbols} (usually lower-case letters) and
-\emph{non-terminal symbols} (upper-case letters inside \meta{\mbox{}}). Rules have
+\emph{non-terminal symbols} (upper-case letters written in
+bold like \meta{A}, \meta{N} and so on). Rules have
 the shape
 
 \begin{plstx}[margin=3cm]
diff -r 19de761b69e9 -r d236e75e1d55 slides/slides05.pdf
Binary file slides/slides05.pdf has changed
diff -r 19de761b69e9 -r d236e75e1d55 slides/slides05.tex
--- a/slides/slides05.tex	Tue Oct 16 14:40:30 2018 +0100
+++ b/slides/slides05.tex	Mon Oct 22 23:37:11 2018 +0100
@@ -1,3 +1,4 @@
+
 \documentclass[dvipsnames,14pt,t]{beamer}
 \usepackage{../slides}
 \usepackage{../graphics}
@@ -30,7 +31,7 @@
   \begin{center}
   \begin{tabular}{ll}
   Email:  & christian.urban at kcl.ac.uk\\
-  Office: & N7.07 (North Wing, Bush House)\\
+  Office: & N\liningnums{7.07} (North Wing, Bush House)\\
   Slides: & KEATS (also home work is there)\\
   \end{tabular}
   \end{center}
@@ -371,6 +372,29 @@
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \begin{frame}[c]
+\frametitle{Coursework: PLs (16)}
+
+\begin{itemize}
+\item Java (16)
+\item C++, C, C\# (14)
+\item JavaScript (10)
+\item Scala (9)
+\item Python (9)  
+\item PHP (6)
+\item Haskell (3)
+\item Ruby (4)
+\item Bash, Perl, Powershell (2)
+\item TypeScript (1)
+\item R (1)
+\item Coconut (1)  
+\item Pascal (1)
+\end{itemize}  
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
 \frametitle{Coursework: Nullable}
 
 \begin{center}
@@ -400,18 +424,18 @@
   \bl{$der\, c\, (r^+)$}                   & \bl{$\dn$} & $?$\\
   \bl{$der\, c\, (r^?)$}                   & \bl{$\dn$} & $?$\\
   \bl{$der\, c\, (r^{\{n\}})$}              & \bl{$\dn$} &
-     \bl{$if\;n=0\;then\;\ZERO\;else\;(der\,c\,r)\cdot r^{\{n-1\}}$}\\
+     \bl{$if\;n=0\;then\;\ZERO\;else\;(der\,c\,r)\cdot r^{\{n-\liningnums{1}\}}$}\\
   \bl{$der\, c\, (r^{\{n..\}})$}            & \bl{$\dn$} &
      \bl{$if\;n=0\;then (der\,c\,r)\cdot r^*$}\\
-  & & \bl{$\phantom{if\;n=0\;}else \;(der\,c\,r)\cdot r^{\{n-1..\}}$}\\
+  & & \bl{$\phantom{if\;n=0\;}else \;(der\,c\,r)\cdot r^{\{n-\liningnums{1}..\}}$}\\
   \bl{$der\, c\, (r^{\{..n\}})$}            & \bl{$\dn$} &
-     \bl{$if\;n=0\;then\;\ZERO\;else\;(der\,c\,r)\cdot r^{\{..n-1\}}$}\\
+     \bl{$if\;n=0\;then\;\ZERO\;else\;(der\,c\,r)\cdot r^{\{..n-\liningnums{1}\}}$}\\
   
   \bl{$der\, c\, (r^{\{n..m\}})$}          & \bl{$\dn$} &
      \bl{$if\;n = 0 \wedge m = 0\;then\;\ZERO\; else$}\\
-  \multicolumn{3}{l}{\bl{$if\;n = 0 \wedge m > 0\;then\;(der\,c\,r)\cdot r^{\{..m-1\}}$}}\\
+  \multicolumn{3}{l}{\bl{$if\;n = 0 \wedge m > 0\;then\;(der\,c\,r)\cdot r^{\{..m-\liningnums{1}\}}$}}\\
   \multicolumn{3}{l}{\bl{$\phantom{if\;n = 0 \wedge m > 0\;}else
-          \;(der\,c\,r)\cdot r^{\{n-1..m-1\}}$}}\\
+          \;(der\,c\,r)\cdot r^{\{n-\liningnums{1}..m-\liningnums{1}\}}$}}\\
   \bl{$der\, c\, (\sim{}r)$}              & \bl{$\dn$} & $?$\\
 \end{tabular}
 \end{center}
@@ -436,7 +460,7 @@
 
 \end{frame}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
+ 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \begin{frame}[t]
 \frametitle{Lexer, Parser}
@@ -568,7 +592,7 @@
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\begin{frame}[c]
+\begin{frame}[t]
 \frametitle{Palindromes}
 
 A grammar for palindromes over the alphabet~\bl{$\{a,b\}$}:
@@ -616,7 +640,7 @@
 \item Begin with a string containing only the start symbol, say \bl{\meta{S}}\bigskip
 \item Replace any nonterminal \bl{\meta{X}} in the string by the
 right-hand side of some production \bl{$\meta{X} ::= \textit{rhs}$}\bigskip
-\item Repeat 2 until there are no nonterminals
+\item Repeat 2 until there are no nonterminals left
 \end{enumerate}
 
 \begin{center}
@@ -726,7 +750,7 @@
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \begin{frame}[t]
 \frametitle{Parse Trees}
-\mbox{}\\[-16mm]
+\mbox{}\\[-12mm]
 
 \bl{\begin{plstx}: \meta{E} ::= \meta{F} | \meta{T} \cdot + \cdot \meta{E} |  \meta{T} \cdot - \cdot \meta{E}\\
 : \meta{T} ::= \meta{F} | \meta{F} \cdot * \cdot \meta{T}\\
@@ -805,7 +829,7 @@
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \begin{frame}[c]
-\frametitle{Dangling Else}
+\frametitle{`Dangling' Else}
 
 Another ambiguous grammar:\bigskip
 
@@ -938,19 +962,19 @@
 Addition
 
 \begin{center}
-\bl{$T \sim + \sim E \Rightarrow \underbrace{f((x,y), z) \Rightarrow x + z}_{\text{semantic action}}$}
+\bl{$\meta{T} \sim + \sim \meta{E} \Rightarrow \underbrace{f\,((x,y), z) \Rightarrow x + z}_{\text{semantic action}}$}
 \end{center}\pause
 
 Multiplication
 
 \begin{center}
-\bl{$F \sim * \sim T \Rightarrow f((x,y), z) \Rightarrow x * z$}
+\bl{$\meta{F} \sim * \sim \meta{T} \Rightarrow f\,((x,y), z) \Rightarrow x * z$}
 \end{center}\pause
 
 Parenthesis
 
 \begin{center}
-\bl{$\text{(} \sim E \sim \text{)} \Rightarrow f((x,y), z) \Rightarrow y$}
+\bl{$\text{(} \sim \meta{E} \sim \text{)} \Rightarrow f\,((x,y), z) \Rightarrow y$}
 \end{center}
 
 \end{frame}}
@@ -1062,14 +1086,14 @@
 
 \begin{center}
 \bl{\begin{tabular}{lcl}
-$S$ & $\rightarrow$ &  $1 \cdot S \cdot S$\\
+$\meta{S}$ & $\rightarrow$ &  $1 \cdot \meta{S} \cdot \meta{S}$\\
         & $|$ & $\epsilon$
 \end{tabular}}
 \end{center}\bigskip
 
 \begin{center}
 \bl{\begin{tabular}{lcl}
-$U$ & $\rightarrow$ &  $1 \cdot U$\\
+$\meta{U}$ & $\rightarrow$ &  $1 \cdot \meta{U}$\\
         & $|$ & $\epsilon$
 \end{tabular}}
 \end{center}
@@ -1199,7 +1223,7 @@
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \begin{frame}[c]
-\frametitle{\begin{tabular}{c}Test Program\end{tabular}}
+\frametitle{Test Program}
 
 \mbox{}\\[-18mm]\mbox{}
 
diff -r 19de761b69e9 -r d236e75e1d55 slides/slides06.pdf
Binary file slides/slides06.pdf has changed