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

\end{enumerate}

\end{document}

%%% Local Variables: 

%%% mode: latex

%%% TeX-master: t

%%% End: