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
|
401
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
13 |
consisting of whitespaces, identifiers (some letters
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
14 |
followed by digits), numbers, operations \texttt{=},
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
15 |
\texttt{<} and \texttt{>}, and the keywords \texttt{if},
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
16 |
\texttt{then} and \texttt{else}. (ii) Decide whether the
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
17 |
following strings can be lexed in this language?
|
56
|
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 |
|
459
|
60 |
|
721
|
61 |
|
647
|
62 |
\item Parsing combinators consist of atomic parsers, alternative
|
|
63 |
parsers, sequence parsers and semantic actions. What is the purpose
|
|
64 |
of (1) atomic parsers and of (2) semantic actions?
|
|
65 |
|
726
|
66 |
\item Parser combinators can directly be given a string as
|
|
67 |
input, without the need of a lexer. What are the
|
|
68 |
advantages to first lex a string and then feed a
|
|
69 |
sequence of tokens as input to the parser?
|
|
70 |
|
|
71 |
|
|
72 |
|
459
|
73 |
\item \POSTSCRIPT
|
56
|
74 |
\end{enumerate}
|
|
75 |
|
|
76 |
\end{document}
|
|
77 |
|
|
78 |
%%% Local Variables:
|
|
79 |
%%% mode: latex
|
|
80 |
%%% TeX-master: t
|
|
81 |
%%% End:
|