56
|
1 |
\documentclass{article}
|
292
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
2 |
\usepackage{../style}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
3 |
\usepackage{../graphics}
|
56
|
4 |
|
|
5 |
\begin{document}
|
|
6 |
|
|
7 |
\section*{Homework 6}
|
|
8 |
|
359
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
9 |
\HEADER
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
10 |
|
56
|
11 |
\begin{enumerate}
|
|
12 |
\item (i) Give the regular expressions for lexing a language
|
|
13 |
consisting of whitespaces, identifiers (some letters followed by digits), numbers,
|
|
14 |
operations \texttt{=}, \texttt{<} and \texttt{>}, and the keywords
|
|
15 |
\texttt{if}, \texttt{then} and \texttt{else}.
|
|
16 |
(ii) Decide whether the following strings
|
|
17 |
can be lexed in this language?
|
|
18 |
|
|
19 |
\begin{enumerate}
|
|
20 |
\item \texttt{"if y4 = 3 then 1 else 3"}
|
|
21 |
\item \texttt{"if33 ifif then then23 else else 32"}
|
|
22 |
\item \texttt{"if x4x < 33 then 1 else 3"}
|
|
23 |
\end{enumerate}
|
|
24 |
|
|
25 |
In case they can, give the corresponding token sequences. (Hint:
|
89
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
26 |
Observe the maximal munch rule and priorities of your regular
|
56
|
27 |
expressions that make the process of lexing unambiguous.)
|
|
28 |
|
|
29 |
\item Suppose the grammar
|
|
30 |
|
|
31 |
\begin{center}
|
|
32 |
\begin{tabular}{lcl}
|
|
33 |
$E$ & $\rightarrow$ & $F \;|\; F \cdot * \cdot F \;|\; F \cdot \backslash \cdot F$\\
|
|
34 |
$F$ & $\rightarrow$ & $T \;|\; T \cdot \texttt{+} \cdot T \;|\; T \cdot \texttt{-} \cdot T$\\
|
|
35 |
$T$ & $\rightarrow$ & $num \;|\; \texttt{(} \cdot E \cdot \texttt{)}$\\
|
|
36 |
\end{tabular}
|
|
37 |
\end{center}
|
|
38 |
|
|
39 |
where $E$, $F$ and $T$ are non-terminals, $E$ is the starting symbol of the grammar, and $num$ stands for
|
|
40 |
a number token. Give a parse tree for the string \texttt{(3+3)+(2*3)}.
|
|
41 |
|
|
42 |
\item Define what it means for a grammar to be ambiguous. Give an example of
|
|
43 |
an ambiguous grammar.
|
|
44 |
|
|
45 |
\item Suppose boolean expressions are built up from
|
|
46 |
|
|
47 |
\begin{center}
|
|
48 |
\begin{tabular}{ll}
|
|
49 |
1.) & tokens for \texttt{true} and \texttt{false},\\
|
|
50 |
2.) & the infix operations \texttt{$\wedge$} and \texttt{$\vee$},\\
|
|
51 |
3.) & the prefix operation $\neg$, and\\
|
|
52 |
4.) & can be enclosed in parentheses.
|
|
53 |
\end{tabular}
|
|
54 |
\end{center}
|
|
55 |
|
|
56 |
(i) Give a grammar that can recognise such boolean expressions
|
|
57 |
and (ii) give a sample string involving all rules given in 1.-4.~that
|
|
58 |
can be parsed by this grammar.
|
|
59 |
|
|
60 |
|
|
61 |
\end{enumerate}
|
|
62 |
|
|
63 |
\end{document}
|
|
64 |
|
|
65 |
%%% Local Variables:
|
|
66 |
%%% mode: latex
|
|
67 |
%%% TeX-master: t
|
|
68 |
%%% End:
|