\usepackage{../grammar}

\begin{plstx}[margin=1cm]    

:\meta{E} ::= \meta{F} \;|\; \meta{F} \cdot \texttt{*} \cdot \meta{F} \;|\; \meta{F} \cdot \backslash \cdot \meta{F}\\

:\meta{F} ::= \meta{T} \;|\; \meta{T} \cdot \texttt{+} \cdot \meta{T} \;|\; \meta{T} \cdot \texttt{-} \cdot \meta{T}\\

:\meta{T} ::= $num$ \;|\; \texttt{(} \cdot E \cdot \texttt{)}\\

\end{plstx}

where \meta{E}, \meta{F} and \meta{T} are non-terminals, \meta{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)}. Note that

\meta{F} and \meta{T} are ``exchanged'' in this grammar in comparison with

the usual grammar for arithmetic expressions. What does this mean in terms

of precedences of the operators?

\solution{

  For the second part "1+2*3" will be parsed as (1+2)*3, meaning + and - bind

  tighter than * and $\backslash$

}

\solution{

  Already the grammar

  \begin{plstx}[margin=1cm]

    : \meta{E} ::= \meta{E}\cdot +\cdot\meta{E} | num\\

  \end{plstx}

  is ambiguous because a string like "1+2+3" can be parsed

  as (1+2)+3 or 1+(2+3).

  }

  of (1) atomic parsers and of (2) map-parsers (also called semantic actions)?

  \solution{

    Atomic parsers look at a concrete prefix of the input, like num-tokens or identifiers.

    Map-parsers apply a function to the output of a parser. In this way you can transform

    the output from, for example, a string to an integer.

  }

      \solution{ Reason 1 you can filter out whitespaces and comments,

        which makes the grammar rules simpler. If you have to make

        sure that a whitespace comes after a variable say, then your

        parser rule for variables gets more complicated. Same with

        comments which do not contribute anything to the parse tree.

        Reason 2) The lexer can already classify tokens, for example

        as numbers, keywords or identifiers. This again makes the grammar

        rules more deterministic and as a result faster to parse.

        The point is that parser combinators can be used to process

        strings, but in case of compilers where whitespaces and

        comments need to be filtered out, the lexing phase is actually

        quite useful.  }

     Explain why there are three cases in the injection function for sequence

     regular expressions.

     \solution{

       This is because the derivative of sequences can be of the form

       \begin{itemize}

       \item $(der\,c\,r_1)\cdot r_2$

       \item $(der\,c\,r_1)\cdot r_2 \;+\; der\,c\,r_2$  

       \end{itemize}

       In the first case the value needs to be of the form $Seq$, in the second case $\Left$ or $Right$.

       Therefore 3 cases.

       }