\documentclass{article}\usepackage{../style}\usepackage{../graphics}\begin{document}\section*{Homework 6}\HEADER\begin{enumerate}\item (i) Give the regular expressions for lexing a languageconsisting 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 regularexpressions 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 fora 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 ofan 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 expressionsand (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: