\section{Introduction}
\begin{frame}
\frametitle{\textsc{SPL}}
- \framesubtitle{Acronym for: \textsc{SPL}: Parser and Lexer}
\begin{block}{Features}
\begin{itemize}
\item Implementation language:
A yard is exactly $36$ inch and an inch is exactly the length
of $3$ barleycorns}.
\item Definitons:
- \begin{lstlisting}
+ \begin{CleanCode}
:: Error = PositionalError Int Int String | Error String
:: Parser a b = Parser ([a] -> (Either Error b, [a]))
- \end{lstlisting}
+ \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
\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
+ \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
-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
+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}
\begin{frame}[fragile]
\frametitle{Two-phase design}
\framesubtitle{Parsing}
+ Read from stdin, write to stdout\\
Added some handy primitives
- \begin{lstlisting}
-parseSColon :: (Parser Token a) -> Parser Token a
+ \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
-parseBBraces :: (Parser Token a) -> Parser Token a
-parseBCBraces :: (Parser Token a) -> Parser Token a
-parseBSqBraces :: (Parser Token a) -> Parser Token a
-trans :: TokenValue (TokenValue -> a) -> Parser Token (Pos, a)
+
trans2 :: TokenValue (TokenValue -> a) -> Parser Token a
trans1 :: TokenValue a -> Parser Token a
+
peekPos :: Parser Token Pos
- \end{lstlisting}
+ \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}
-%- 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?
-% - 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 ;))
+\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}
repositories / cc1516.git / blobdiff