\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: