# HG changeset patch
# User Christian Urban <urbanc@in.tum.de>
# Date 1351800047 0
# Node ID f28824933a663e3f4044c654151880795200b2db
# Parent  cceed8d66b2840fe6c272423a371e3203312d3f7
added

diff -r cceed8d66b28 -r f28824933a66 hw06.pdf
Binary file hw06.pdf has changed
diff -r cceed8d66b28 -r f28824933a66 hw06.tex
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/hw06.tex	Thu Nov 01 20:00:47 2012 +0000
@@ -0,0 +1,72 @@
+\documentclass{article}
+\usepackage{charter}
+\usepackage{hyperref}
+\usepackage{amssymb}
+\usepackage{amsmath}
+\usepackage{tikz}
+\usetikzlibrary{automata}
+
+\newcommand{\dn}{\stackrel{\mbox{\scriptsize def}}{=}}% for definitions
+
+\begin{document}
+
+\section*{Homework 6}
+
+\begin{enumerate}
+\item (i) Give the regular expressions for lexing a language
+consisting of whitespaces, identifiers (some letters followed by digits), numbers,
+operations \texttt{=}, \texttt{<} and \texttt{>}, and the keywords
+\texttt{if}, \texttt{then} and \texttt{else}.
+(ii) Decide whether the following strings 
+can be lexed in this language?
+
+\begin{enumerate}
+\item \texttt{"if y4 = 3 then 1 else 3"}
+\item \texttt{"if33 ifif then then23 else else 32"}
+\item \texttt{"if x4x < 33 then 1 else 3"}
+\end{enumerate}
+
+In case they can, give the corresponding token sequences. (Hint: 
+Observer the maximal munch rule and priorities of your regular
+expressions that make the process of lexing unambiguous.)
+
+\item Suppose the grammar
+
+\begin{center}
+\begin{tabular}{lcl}
+$E$ & $\rightarrow$ &  $F \;|\; F \cdot * \cdot F \;|\; F \cdot \backslash \cdot F$\\
+$F$ & $\rightarrow$ & $T \;|\; T \cdot \texttt{+} \cdot T \;|\; T \cdot \texttt{-} \cdot T$\\
+$T$ & $\rightarrow$ & $num \;|\; \texttt{(} \cdot E \cdot \texttt{)}$\\
+\end{tabular}
+\end{center}
+
+where $E$, $F$ and $T$ are non-terminals, $E$ is the starting symbol of the grammar, and $num$ stands for
+a number token. Give a parse tree for the string \texttt{(3+3)+(2*3)}.
+
+\item Define what it means for a grammar to be ambiguous. Give an example of
+an ambiguous grammar.
+
+\item Suppose boolean expressions are built up from
+
+\begin{center}
+\begin{tabular}{ll}
+1.) & tokens for \texttt{true} and \texttt{false},\\
+2.) & the infix operations \texttt{$\wedge$} and \texttt{$\vee$},\\
+3.) & the prefix operation $\neg$, and\\
+4.) & can be enclosed in parentheses.
+\end{tabular}
+\end{center}
+
+(i) Give a grammar that can recognise such boolean expressions
+and (ii) give a sample string involving all rules given in 1.-4.~that 
+can be parsed by this grammar.
+
+
+\end{enumerate}
+
+\end{document}
+
+%%% Local Variables: 
+%%% mode: latex
+%%% TeX-master: t
+%%% End: 
diff -r cceed8d66b28 -r f28824933a66 slides06.pdf
Binary file slides06.pdf has changed
diff -r cceed8d66b28 -r f28824933a66 slides06.tex
--- a/slides06.tex	Thu Nov 01 10:04:30 2012 +0000
+++ b/slides06.tex	Thu Nov 01 20:00:47 2012 +0000
@@ -548,7 +548,7 @@
 $P$ & $\rightarrow$ &  $V\cdot N$ \\
 $N$ & $\rightarrow$ &  $N\cdot N$ \\
 $N$ & $\rightarrow$ &  $\texttt{students} \;|\; \texttt{Jeff} \;|\; \texttt{geometry} \;|\; \texttt{trains} $ \\
-$E$ & $\rightarrow$ &  $\texttt{trains}$ 
+$V$ & $\rightarrow$ &  $\texttt{trains}$ 
 \end{tabular}}
 \end{center}