X-Git-Url: https://git.martlubbers.net/?a=blobdiff_plain;ds=sidebyside;f=deliverables%2Fp1%2Fp1.tex;h=67a14b0494814ce514b5a3d2779db8797d0080ac;hb=f622bae746c1b5b970e7171a2df8f0e6e3fcc5b8;hp=3984b6d681182f0e86a2e75ac017a62051c20fea;hpb=9e30ea275d06506244e92f26c121715cbfd9c315;p=cc1516.git diff --git a/deliverables/p1/p1.tex b/deliverables/p1/p1.tex index 3984b6d..67a14b0 100644 --- a/deliverables/p1/p1.tex +++ b/deliverables/p1/p1.tex @@ -2,37 +2,166 @@ \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}} + \framesubtitle{Acronym for: \textsc{SPL}: Parser and Lexer} + \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{lstlisting} +:: Error = PositionalError Int Int String | Error String +:: Parser a b = Parser ([a] -> (Either Error b, [a])) + \end{lstlisting} + \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} + \begin{lstlisting} +instance Functor (Parser a) +instance Applicative (Parser a) +instance Monad (Parser a) +instance Alternative (Parser a) + +runParser :: (Parser a b) [a] -> (Either Error b, [a]) +() :: (Parser a b) Error -> Parser a b +fail :: Parser a b +top :: Parser a a +peek :: Parser a a +satisfy :: (a -> Bool) -> Parser a a +check :: (a -> Bool) -> Parser a a +(until) infix 2 :: (Parser a b) (Parser a c) -> Parser a [b] +item :: a -> Parser a a | Eq a +list :: [a] -> Parser a [a] | Eq a +eof :: Parser a Void + \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} + Added some handy primitives + \begin{lstlisting} +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{lstlisting} +\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{Wierd 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}