X-Git-Url: https://git.martlubbers.net/?a=blobdiff_plain;f=deliverables%2Fp1%2Fp1.tex;h=27c30d160b6dad7690a119bf7759744b8e7ed6dd;hb=285d41abeaa5a7c9297009da26b83b0236390c02;hp=3984b6d681182f0e86a2e75ac017a62051c20fea;hpb=81f72dd30fdd6b77e2da54d68d61ce8a41280993;p=cc1516.git diff --git a/deliverables/p1/p1.tex b/deliverables/p1/p1.tex index 3984b6d..27c30d1 100644 --- a/deliverables/p1/p1.tex +++ b/deliverables/p1/p1.tex @@ -2,37 +2,220 @@ \begin{document} \frame{\titlepage} -%- Anything that is specific to your parser -% - Positions Pim -% - yard (parser combinators) Pim -% - Implementation language Pim -% - Elaborate diffulties and eases (Tussendoor) -% - LL* Mart -%- Did you split it into two phases lexing and parsing, or just one phase? Pim -% - Why parser combinator for lexer -%- Did you change the grammar, and if so how? Mart -% - Standard tricks, remove left assoc, get operator assoc correct. -% - How did you solve the problems of precedence and associativity? -%- Does your parser stop after the first encountered error or can it go on? Pim -% (bij Yard erin fietsen) -% - Stops, this is design, parsing should be correct!!!1! -%- For a couple of example programs, when you do a sequence of Mart -% 1. parse -% 2. pretty-print -% 3. parse -% 4. pretty-print -% -- Dit gaan we met een shell scriptje doen -%- Code metrics, loc, etc, met stomme xkcd Mart -% How many lines of code do you have, how many hours did you work on it? -% “Measuring programming progress by lines of code is like measuring -% aircraft building progress by weight.” -% -% ― Bill Gates -% Hoeveel uur, ook geen idee. Ook een stomme quote -%- Did you try your parser on weird inputs, like 100 megabyte of nested Mart -%parenthesis? 1 gigabyte? -% - Yes, we did, didn't work out. Uses big heap and stack -%- Problems and learned things -%- Demonstrate your parser and pretty-printer on two or three programs that you -% find interesting Mart (teminaldingen kun jij goed ;)) +\section{Introduction} +\begin{frame} + \frametitle{\textsc{SPL}} + \begin{block}{Features} + \begin{itemize} + \item Implementation language: + Clean ({\tiny\url{http://clean.cs.ru.nl}}) + \pause + \begin{itemize} + \item Pure language + \item Higher order functions + \item Monads + \item Using parser combinator library \textsc{Yard} + \end{itemize} + \pause + \item Positional data available for easy locating of errors. + \pause + \item Standardized parser errors. This means you can set it as + \texttt{buildprg} in \texttt{vim} and you can then use the + quickfix window! + \end{itemize} + \end{block} +\end{frame} + +\begin{frame}[fragile] + \frametitle{\textsc{YARD}} + \framesubtitle{A minimal home grown monadic parser combinator library} + \begin{itemize} + \item Inspired by \textsc{parsec}: $1pc=3.375\cdot10^{16}yd$~\footnote{ + A yard is exactly $36$ inch and an inch is exactly the length + of $3$ barleycorns}. + \item Definitons: + \begin{CleanCode} +:: Error = PositionalError Int Int String | Error String +:: Parser a b = Parser ([a] -> (Either Error b, [a])) + \end{CleanCode} + \pause + \item Result is either Error or \texttt{b}, not a \texttt{[b]} as + described Hutton \& Meijer \footnote{G. Hutton and E. Meijer. + Monadic parser combinators. 1996.} + \pause + \item Matches longest left-most parser + \pause + \item Stops immediately on error\pause\\ + By design! + \end{itemize} +\end{frame} + +\begin{frame}[fragile] + \frametitle{\textsc{YARD} Combinators} + \framesubtitle{Designed to be minimal, just 14 parsers/combinators} + YARD is designed to be minimal and defines just 14 primitives: + \begin{columns}[t] + \begin{column}{0.5\textwidth} + \begin{CleanCode} +top :: Parser a a +peek :: Parser a a +fail :: Parser a b +eof :: Parser a Void +(until) :: (Parser a b) + (Parser a c) + -> Parser a [b] +satisfy :: (a -> Bool) + -> Parser a a +check :: (a -> Bool) + -> Parser a a +item :: a -> Parser a a +list :: [a] -> Parser a [a] + \end{CleanCode} + \end{column} + \begin{column}{0.5\textwidth} + \begin{CleanCode} +(>>=) :: (Parser a b) + (b -> Parser a c) + -> Parser a c +(<|>) :: (Parser a b) + (Parser a b) + -> Parser a b +some :: (Parser a b) + -> Parser a [b] +many :: (Parser a b) + -> Parser a [b] +optional :: (Parser a b) + -> Parser a (Maybe b) + \end{CleanCode} + \end{column} + \end{columns} +\end{frame} + +\begin{frame}[fragile] + \frametitle{\textsc{YARD} Combinators} + \framesubtitle{Designed to be minimal, just \textbf{7} parsers/combinators} + Actually, scrap that, just \textbf{7} primitives: + \begin{columns}[t] + \begin{column}{0.5\textwidth} + \begin{CleanCode} +top :: Parser a a +peek :: Parser a a +fail :: Parser a b +eof :: Parser a Void + \end{CleanCode} + \end{column} + \begin{column}{0.5\textwidth} + \begin{CleanCode} +(>>=) :: (Parser a b) + (b -> Parser a c) + -> Parser a c +(<|>) :: (Parser a b) + (Parser a b) + -> Parser a b + \end{CleanCode} + \end{column} + \end{columns} + All others can be (and are) derived from these. e.g. + \begin{lstlisting} +satisfy :: (a -> Bool) -> Parser a a +satisfy f = top >>= \c -> if (f c) (return c) fail + \end{lstlisting} +\end{frame} + +\section{Design choices} +\begin{frame} + \frametitle{Adapting the grammar} + \begin{itemize} + \item Remove left recursion + \item Fixing associativity + \item Added small features such as escape characters \texttt{ + \textbackslash n\textbackslash b} + \pause + \item Show grammar now\ldots + \end{itemize} +\end{frame} + +\begin{frame} + \frametitle{Two-phase design} + \framesubtitle{Lexing} + Also done with \textsc{YARD} because + \begin{itemize} + \item Multiline comments + \item Alternatives + \item Positions + \end{itemize} +\end{frame} + +\begin{frame}[fragile] + \frametitle{Two-phase design} + \framesubtitle{Parsing} + Read from stdin, write to stdout\\ + Added some handy primitives + \begin{CleanCode} +parseBlock :: Parser Token [Stmt] + +parseOpR :: (Parser Token Op2) (Parser Token Expr) -> Parser Token Expr +parseOpL :: (Parser Token Op2) (Parser Token Expr) -> Parser Token Expr + +trans2 :: TokenValue (TokenValue -> a) -> Parser Token a +trans1 :: TokenValue a -> Parser Token a + +peekPos :: Parser Token Pos + \end{CleanCode} +\end{frame} + +\begin{frame}[fragile] + \frametitle{Statistics} + \framesubtitle{Lines of code} + \lstinputlisting{|"wc -l ../../*.[di]cl"} + \pause + \begin{block}{} + \emph{``Measuring programming progress by lines of code is like + measuring aircraft building progress by weight.''}\\ + {---} Bill Gates + \end{block} +\end{frame} + +\begin{frame} + \frametitle{Statistics} + \framesubtitle{Hours of work} + We have no clue how much time we have worked on it\ldots + \pause + \begin{block}{} + \emph{``Choose a job you love, and you will never have to work a day in + your life.''}\\ + {---} Confucius + \end{block} +\end{frame} + +\section{Examples} +\begin{frame} + \frametitle{Weird inputs} + \begin{itemize} + \item \pause Heap full + \pause\ldots Increase heap\\ + \texttt{\$ ./spl -h 2000M} + \item \pause Stack full + \pause\ldots Increase stack\\ + \texttt{\$ ./spl -s 200M} + \item \pause Segmentation fault + \pause\ldots Enable memory overcommitting\\ + \texttt{\# echo 1 > /proc/sys/vm/overcommit\_memory} + \item \pause Still segmentation fault + \pause\ldots Buy more \textsc{RAM} + \item \pause Still segmentation fault? + \pause\ldots Divide into modules and parse separatly~\footnote{To be + implemented} + \item \pause Thus, we are only limited by hardware\ldots + \end{itemize} +\end{frame} + +\begin{frame} + \frametitle{Learned lessons} + \begin{itemize} + \item \pause Parser combinators are elegant! + \item \pause Positional errors are a must! + \item \ldots + \end{itemize} +\end{frame} \end{document}