1 \documentclass{article}

     2 \usepackage{charter}

     3 \usepackage{hyperref}

     4 \usepackage{amssymb}

     5 \usepackage{amsmath}

     6 \usepackage{tikz}

     7 \usetikzlibrary{automata}

     8 

     9 \newcommand{\dn}{\stackrel{\mbox{\scriptsize def}}{=}}% for definitions

    10 

    11 \begin{document}

    12 

    13 \section*{Homework 6}

    14 

    15 \begin{enumerate}

    16 \item (i) Give the regular expressions for lexing a language

    17 consisting of whitespaces, identifiers (some letters followed by digits), numbers,

    18 operations \texttt{=}, \texttt{<} and \texttt{>}, and the keywords

    19 \texttt{if}, \texttt{then} and \texttt{else}.

    20 (ii) Decide whether the following strings 

    21 can be lexed in this language?

    22 

    23 \begin{enumerate}

    24 \item \texttt{"if y4 = 3 then 1 else 3"}

    25 \item \texttt{"if33 ifif then then23 else else 32"}

    26 \item \texttt{"if x4x < 33 then 1 else 3"}

    27 \end{enumerate}

    28 

    29 In case they can, give the corresponding token sequences. (Hint: 

    30 Observe the maximal munch rule and priorities of your regular

    31 expressions that make the process of lexing unambiguous.)

    32 

    33 \item Suppose the grammar

    34 

    35 \begin{center}

    36 \begin{tabular}{lcl}

    37 $E$ & $\rightarrow$ &  $F \;|\; F \cdot * \cdot F \;|\; F \cdot \backslash \cdot F$\\

    38 $F$ & $\rightarrow$ & $T \;|\; T \cdot \texttt{+} \cdot T \;|\; T \cdot \texttt{-} \cdot T$\\

    39 $T$ & $\rightarrow$ & $num \;|\; \texttt{(} \cdot E \cdot \texttt{)}$\\

    40 \end{tabular}

    41 \end{center}

    42 

    43 where $E$, $F$ and $T$ are non-terminals, $E$ is the starting symbol of the grammar, and $num$ stands for

    44 a number token. Give a parse tree for the string \texttt{(3+3)+(2*3)}.

    45 

    46 \item Define what it means for a grammar to be ambiguous. Give an example of

    47 an ambiguous grammar.

    48 

    49 \item Suppose boolean expressions are built up from

    50 

    51 \begin{center}

    52 \begin{tabular}{ll}

    53 1.) & tokens for \texttt{true} and \texttt{false},\\

    54 2.) & the infix operations \texttt{$\wedge$} and \texttt{$\vee$},\\

    55 3.) & the prefix operation $\neg$, and\\

    56 4.) & can be enclosed in parentheses.

    57 \end{tabular}

    58 \end{center}

    59 

    60 (i) Give a grammar that can recognise such boolean expressions

    61 and (ii) give a sample string involving all rules given in 1.-4.~that 

    62 can be parsed by this grammar.

    63 

    64 

    65 \end{enumerate}

    66 

    67 \end{document}

    68 

    69 %%% Local Variables: 

    70 %%% mode: latex

    71 %%% TeX-master: t

    72 %%% End: