\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 expression+ −
+ −
\[(ab + a)\cdot (\ONE + b)\]+ −
+ −
there are two values for how this regular expression can recognise+ −
the string $ab$. Give both values and indicate which one is the+ −
POSIX value.+ −
+ −
\item \POSTSCRIPT + −
\end{enumerate}+ −
+ −
\end{document}+ −
+ −
%%% Local Variables: + −
%%% mode: latex+ −
%%% TeX-master: t+ −
%%% End: + −