deliverables/p1/p1.tex

   1 %&p1
   2 \begin{document}
   3 \frame{\titlepage}
   4
   5 \section{Introduction}
   6 \begin{frame}
   7         \frametitle{\textsc{SPL}}
   8         \framesubtitle{Acronym for: \textsc{SPL}: Parser and Lexer}
   9         \begin{block}{Features}
  10                 \begin{itemize}
  11                         \item Implementation language:
  12                                 Clean ({\tiny\url{http://clean.cs.ru.nl}})
  13                                 \pause
  14                                 \begin{itemize}
  15                                         \item Pure language
  16                                         \item Higher order functions
  17                                         \item Monads
  18                                         \item Using parser combinator library \textsc{Yard}
  19                                 \end{itemize}
  20                         \pause
  21                         \item Positional data available for easy locating of errors.
  22                         \pause
  23                         \item Standardized parser errors. This means you can set it as
  24                                 \texttt{buildprg} in \texttt{vim} and you can then use the
  25                                 quickfix window!
  26                 \end{itemize}
  27         \end{block}
  28 \end{frame}
  29
  30 \begin{frame}[fragile]
  31         \frametitle{\textsc{YARD}}
  32         \framesubtitle{A minimal home grown monadic parser combinator library}
  33         \begin{itemize}
  34                 \item Inspired by \textsc{parsec}: $1pc=3.375\cdot10^{16}yd$~\footnote{
  35                                 A yard is exactly $36$ inch and an inch is exactly the length
  36                                 of $3$ barleycorns}.
  37                 \item Definitons:
  38                         \begin{lstlisting}
  39 :: Error = PositionalError Int Int String | Error String
  40 :: Parser a b = Parser ([a] -> (Either Error b, [a]))
  41                         \end{lstlisting}
  42                 \pause
  43                 \item Matches longest left-most parser
  44                 \pause
  45                 \item Stops immediately on error\pause\\
  46                         By design!
  47         \end{itemize}
  48 \end{frame}
  49
  50 \begin{frame}[fragile]
  51         \frametitle{\textsc{YARD} Combinators}
  52         \begin{lstlisting}
  53 instance Functor (Parser a)
  54 instance Applicative (Parser a)
  55 instance Monad (Parser a)
  56 instance Alternative (Parser a)
  57
  58 runParser :: (Parser a b) [a] -> (Either Error b, [a])
  59 (<?>) :: (Parser a b) Error -> Parser a b
  60 fail :: Parser a b
  61 top :: Parser a a
  62 peek :: Parser a a
  63 satisfy :: (a -> Bool) -> Parser a a
  64 check :: (a -> Bool) -> Parser a a
  65 (until) infix 2 :: (Parser a b) (Parser a c) -> Parser a [b]
  66 item :: a -> Parser a a | Eq a
  67 list :: [a] -> Parser a [a] | Eq a
  68 eof :: Parser a Void
  69         \end{lstlisting}
  70 \end{frame}
  71
  72 \section{Design choices}
  73 \begin{frame}
  74         \frametitle{Adapting the grammar}
  75         \begin{itemize}
  76                 \item Remove left recursion
  77                 \item Fixing associativity
  78                 \item Added small features such as escape characters \texttt{
  79                         \textbackslash n\textbackslash b}
  80                 \pause
  81                 \item Show grammar now\ldots
  82         \end{itemize}
  83 \end{frame}
  84
  85 \begin{frame}
  86         \frametitle{Two-phase design}
  87         \framesubtitle{Lexing}
  88         Also done with \textsc{YARD} because
  89         \begin{itemize}
  90                 \item Multiline comments
  91                 \item Alternatives
  92                 \item Positions
  93         \end{itemize}
  94 \end{frame}
  95
  96 \begin{frame}[fragile]
  97         \frametitle{Two-phase design}
  98         \framesubtitle{Parsing}
  99         Added some handy primitives
 100         \begin{lstlisting}
 101 parseSColon :: (Parser Token a) -> Parser Token a
 102 parseBlock :: Parser Token [Stmt]
 103 parseOpR :: (Parser Token Op2) (Parser Token Expr) -> Parser Token Expr
 104 parseOpL :: (Parser Token Op2) (Parser Token Expr) -> Parser Token Expr
 105 parseBBraces :: (Parser Token a) -> Parser Token a
 106 parseBCBraces :: (Parser Token a) -> Parser Token a
 107 parseBSqBraces :: (Parser Token a) -> Parser Token a
 108 trans :: TokenValue (TokenValue -> a) -> Parser Token (Pos, a)
 109 trans2 :: TokenValue (TokenValue -> a) -> Parser Token a
 110 trans1 :: TokenValue a -> Parser Token a
 111 peekPos :: Parser Token Pos
 112         \end{lstlisting}
 113 \end{frame}
 114
 115
 116 \section{Examples}
 117
 118 %- Anything that is specific to your parser
 119 %       - Positions Pim
 120 %       - yard (parser combinators) Pim
 121 %       - Implementation language Pim
 122 %       - Elaborate diffulties and eases (Tussendoor)
 123 %   - LL* Mart
 124 %- Did you split it into two phases lexing and parsing, or just one phase? Pim
 125 %       - Why parser combinator for lexer
 126 %- Did you change the grammar, and if so how? Mart
 127 %       - Standard tricks, remove left assoc, get operator assoc correct.
 128 %       - How did you solve the problems of precedence and associativity?
 129 %       - Stops, this is design, parsing should be correct!!!1!
 130 %- For a couple of example programs, when you do a sequence of    Mart
 131 %    1. parse
 132 %    2. pretty-print
 133 %    3. parse
 134 %    4. pretty-print
 135 %       -- Dit gaan we met een shell scriptje doen
 136 %- Code metrics, loc, etc, met stomme xkcd Mart
 137 %  How many lines of code do you have, how many hours did you work on it?
 138 %       “Measuring programming progress by lines of code is like measuring
 139 %       aircraft building progress by weight.”
 140 %
 141 %       ― Bill Gates
 142 %       Hoeveel uur, ook geen idee. Ook een stomme quote
 143 %- Did you try your parser on weird inputs, like 100 megabyte of nested     Mart
 144 %parenthesis? 1 gigabyte?
 145 %       - Yes, we did, didn't work out. Uses big heap and stack
 146 %- Problems and learned things
 147 %- Demonstrate your parser and pretty-printer on two or three programs that you
 148 %       find interesting        Mart (teminaldingen kun jij goed ;))
 149 \end{document}