\documentclass{article}+
−
\usepackage{../style}+
−
\usepackage{../graphics}+
−
+
−
\begin{document}+
−
+
−
\section*{Homework 6}+
−
+
−
\HEADER+
−
+
−
\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: +
−
Observe 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.+
−
+
−
\item Given the regular expressions+
−
+
−
\begin{center}+
−
\begin{tabular}{ll}    +
−
  1) & $(ab + a)\cdot (\ONE + b)$\\+
−
  2) & $(aa + a)^*$\\+
−
\end{tabular}+
−
\end{center}+
−
+
−
there are several values for how these regular expressions can+
−
recognise the strings (for 1) $ab$ and (for 2) $aaa$. Give in each case+
−
\emph{all} the values and indicate which one is the POSIX value.+
−
+
−
\item Parsing combinators consist of atomic parsers, alternative+
−
  parsers, sequence parsers and semantic actions.  What is the purpose+
−
  of (1) atomic parsers and of (2) semantic actions?+
−
+
−
+
−
+
−
+
−
\item \POSTSCRIPT        +
−
\end{enumerate}+
−
+
−
\end{document}+
−
+
−
%%% Local Variables: +
−
%%% mode: latex+
−
%%% TeX-master: t+
−
%%% End: +
−