[sod] / doc / parsing.tex

%%% -*-latex-*-
%%%
%%% Description of the parsing machinery
%%%
%%% (c) 2015 Straylight/Edgeware
%%%

%%%----- Licensing notice ---------------------------------------------------
%%%
%%% This file is part of the Sensble Object Design, an object system for C.
%%%
%%% SOD is free software; you can redistribute it and/or modify
%%% it under the terms of the GNU General Public License as published by
%%% the Free Software Foundation; either version 2 of the License, or
%%% (at your option) any later version.
%%%
%%% SOD is distributed in the hope that it will be useful,
%%% but WITHOUT ANY WARRANTY; without even the implied warranty of
%%% MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
%%% GNU General Public License for more details.
%%%
%%% You should have received a copy of the GNU General Public License
%%% along with SOD; if not, write to the Free Software Foundation,
%%% Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.

\chapter{Parsing} \label{ch:parsing}

%%%--------------------------------------------------------------------------
\section{The parser protocol} \label{sec:parsing.proto}

For the purpose of Sod's parsing library, \emph{parsing} is the process of
reading a sequence of input items, in order, and computing an output value.

A \emph{parser} is an expression which consumes zero or more input items and
returns three values: a \emph{result}, a \emph{success flag}, and a
\emph{consumed flag}.  The two flags are (generalized) booleans.  If the
success flag is non-nil, then the parser is said to have \emph{succeeded},
and the result is the parser's output.  If the success flag is nil then the
parser is said to have \emph{failed}, and the result is a list of
\emph{indicators}.  Finally, the consumed flag is non-nil if the parser
consumed any input items.

\begin{describe}{fun}{combine-parser-failures @<failures> @> @<list>}
\end{describe}

%%%--------------------------------------------------------------------------
\section{File locations} \label{sec:parsing.floc}

\begin{describe}{cls}{file-location}
\end{describe}

\begin{describe}{fun}{file-location-p @<object> @> @<generalized-boolean>}
\end{describe}

\begin{describe}{fun}
    {make-file-location @<filename> \&optional @<line> @<column>
      @> @<file-location>}
\end{describe}

\begin{describe*}
    {\dhead{fun}{file-location-filename @<floc> @> @<string-or-nil>}
     \dhead{fun}{file-location-line @<floc> @> @<fixnum-or-nil>}
     \dhead{fun}{file-location-column @<floc> @> @<fixnum-or-nil>}}
\end{describe*}

\begin{describe}{gf}{file-location @<object> @> @<floc>}
  \begin{describe}{meth}{file-location (@<floc> file-location) @> @<floc>}
  \end{describe}
  \begin{describe}{meth}{file-location (@<stream> stream) @> @<floc>}
  \end{describe}
  \begin{describe}{meth}{file-location (@<any> t) @> @<floc>}
  \end{describe}
\end{describe}

\begin{describe}{cls}{condition-with-location (condition) \&key :location}
\end{describe}

\begin{describe}{meth}
    {file-location (@<condition> condition-with-location) @> @<floc>}
\end{describe}

\begin{describe*}
    {\quad\=\quad\=\kill
     \dhead{cls}
      {error-with-location (condition-with-location error) \\ \>
        \&key :location}
    \dhead{cls}
      {warning-with-location (condition-with-location warning) \\ \>
        \&key :location}
    \dhead{cls}
      {enclosing-error-with-location
          (enclosing-error-with-location error) \\ \>
        \&key :condition :location}
    \dhead{cls}
      {enclosing-warning-with-location
          (enclosing-condition-with-location warning) \\ \>
        \&key :condition :location}
     \dhead{cls}
      {simple-condition-with-location
          (condition-with-location simple-condition) \\ \>
        \&key :format-control :format-arguments :location}
     \dhead{cls}
      {simple-error-with-location
          (error-with-location simple-error) \\ \>
        \&key :format-control :format-arguments :location}
    \dhead{cls}
      {simple-warning-with-location
          (warning-with-location simple-warning) \\ \>
        \&key :format-control :format-arguments :location}}
\end{describe*}

\begin{describe}{fun}
    {make-condition-with-location @<default-type> @<floc>
                                  @<datum> \&rest @<arguments>
       \nlret @<condition-with-location>}
\end{describe}

\begin{describe*}
    {\dhead{fun}{error-with-location @<floc> @<datum> \&rest @<arguments>}
     \dhead{fun}{cerror-with-location @<floc> @<continue-string>
                                      @<datum> \&rest @<arguments>}
     \dhead{fun}{cerror*-with-location @<floc> @<datum> \&rest @<arguments>}
     \dhead{fun}{warn-with-location @<floc> @<datum> \&rest @<arguments>}}
\end{describe*}

\begin{describe}{mac}
    {with-default-error-location (@<floc>) @<body-form>^* @> @<value>^*}
\end{describe}

\begin{describe}{mac}
    {count-and-report-errors () @<body-form>^*
      @> @<value> @<n-errors> @<n-warnings>}
\end{describe}

%%%--------------------------------------------------------------------------
\section{Scanners} \label{sec:parsing.scanner}

A \emph{scanner} is an object which keeps track of a parser's progress as it
works through its input.  There's no common base class for scanners: a
scanner is simply any object which implements the scanner protocol described
here.

A scanner maintains a sequence of items to read.  It can step forwards
through the items, one at a time, until it reaches the end (if, indeed, the
sequence is finite, which it needn't be).  Until that point, there is a
current item, though there's no protocol for accessing it at this level
because the nature of the items is left unspecified.

Some scanners support an additional \emph{place-capture} protocol which
allows rewinding the scanner to an earlier point in the input so that it can
be scanned again.

\subsection{Basic scanner protocol} \label{sec:parsing.scanner.basic}

The basic protocol supports stepping the scanner forward through its input
sequence, and detecting the end of the sequence.

\begin{describe}{gf}{scanner-step @<scanner>}
  Advance the @<scanner> to the next item, which becomes current.

  It is an error to step the scanner if the scanner is at end-of-file.
\end{describe}

\begin{describe}{gf}{scanner-at-eof-p @<scanner> @> @<generalized-boolean>}
  Return non-nil if the scanner is at end-of-file, i.e., there are no more
  items to read.

  If nil is returned, there is a current item, and it is safe to step the
  scanner again; otherwise, it is an error to query the current item or to
  step the scanner.
\end{describe}

\subsection{Place-capture scanner protocol} \label{sec:parsing.scanner.place}

The place-capture protocol allows rewinding to an earlier point in the
sequence.  Not all scanners support the place-capture protocol.

To rewind a scanner to a particular point, that point must be \emph{captured}
as a \emph{place} when it's current -- so you must know in advance that this
is an interesting place that's worth capturing.  The type of place returned
depends on the type of scanner.  Given a captured place, the scanner can be
rewound to the position held in it.

Depending on how the scanner works, holding onto a captured place might
consume a lot of memory or case poor performance.  For example, if the
scanner is reading from an input stream, having a captured place means that
data from that point on must be buffered in case the program needs to rewind
the scanner and read that data again.  Therefore it's possible to
\emph{release} a place when it turns out not to be needed any more.

\begin{describe}{gf}{scanner-capture-place @<scanner> @> @<place>}
  Capture the @<scanner>'s current position as a place, and return the place.
\end{describe}

\begin{describe}{gf}{scanner-restore-place @<scanner> @<place>}
  Rewind the @<scanner> to the state it was in when @<place> was captured.
  In particular, the item that was current when the @<place> was captured
  becomes current again.

  It is an error to restore a @<place> that has been released, or if the
  @<place> wasn't captured from the @<scanner>.
\end{describe}

\begin{describe}{gf}{scanner-release-place @<scanner> @<place>}
  Release the @<place>, to avoid having to maintaining the ability to restore
  it after it's not needed any more..

  It is an error if the @<place> wasn't captured from the @<scanner>.
\end{describe}

\begin{describe}{mac}
    {with-scanner-place (@<place> @<scanner>) @<body-form>^* @> @<value>^*}
  Capture the @<scanner>'s current position as a place, evaluate the
  @<body-form>s as an implicit progn with the variable @<place> bound to the captured
  place.  When control leaves the @<body-form>s, the place is released.  The return
  values are the values of the final @<body-form>.
\end{describe}

\subsection{Scanner file-location protocol} \label{sec:parsing.scanner.floc}

Some scanners participate in the file-location protocol
(\xref{sec:parsing.floc}).  They implement a method on @|file-location| which
collects the necessary information using scanner-specific functions described
here.

\begin{describe}{fun}{scanner-file-location @<scanner> @> @<file-location>}
  Return a @|file-location| object describing the current position of the
  @<scanner>.

  This calls the @|scanner-filename|, @|scanner-line| and @|scanner-column|
  generic functions on the scanner, and uses these to fill in an appropriate
  @|file-location|.

  Since there are default methods on these generic functions, it is not an
  error to call @|scanner-file-location| on any kind of value, but it might
  not be very useful.  This function exists to do the work of appropriately
  specialized methods on @|file-location|.
\end{describe}

\begin{describe*}
    {\dhead{gf}{scanner-filename @<scanner> @> @<string>}
     \dhead{gf}{scanner-line @<scanner> @> @<integer>}
     \dhead{gf}{scanner-column @<scanner> @> @<integer>}}
  Return the filename, line and column components of the @<scanner>'s current
  position, for use in assembling a @<file-location>: see the
  @|scanner-file-location| function.

  There are default methods on all three generic functions which simply
  return nil.
\end{describe*}

\subsection{Character scanners} \label{sec:parsing.scanner.char}

Character scanners are scanners which read sequences of characters.

\begin{describe}{cls}{character-scanner () \&key}
  Base class for character scanners.  This provides some very basic
  functionality.

  Not all character scanners are subclasses of @|character-scanner|.
\end{describe}

\begin{describe}{gf}{scanner-current-char @<scanner> @> @<character>}
  Returns the current character.
\end{describe}

\begin{describe}{gf}{scanner-unread @<scanner> @<character>}
  Rewind the @<scanner> by one step.  The @<chararacter> must be the previous
  current character, and becomes the current character again.  It is an error
  if: the @<scanner> has reached end-of-file; the @<scanner> is never been
  stepped; or @<character> was not the previous current character.
\end{describe}

\begin{describe}{gf}
    {scanner-interval @<scanner> @<place-a> \&optional @<place-b>
        @> @<string>}
  Return the characters in the @<scanner>'s input from @<place-a> up to (but
  not including) @<place-b>.

  The characters are returned as a string.  If @<place-b> is omitted, return
  the characters up to (but not including) the current position.  It is an
  error if @<place-b> precedes @<place-a> or they are from different
  scanners.

  This function is a character-scanner-specific extension to the
  place-capture protocol; not all character scanners implement the
  place-capture protocol, and some that do may not implement this function.
\end{describe}

\subsubsection{Stream access to character scanners}
Sometimes it can be useful to apply the standard Lisp character input
operations to the sequence of characters held by a character scanner.

\begin{describe}{gf}{make-scanner-stream @<scanner> @> @<stream>}
  Returns a fresh input @|stream| object which fetches input characters from
  the character scanner object @<scanner>.  Reading characters from the
  stream steps the scanner.  The stream will reach end-of-file when the
  scanner reports end-of-file.  If the scanner implements the file-location
  protocol then reading from the stream will change the file location in an
  appropriate manner.

  This is mostly useful for applying standard Lisp stream functions, most
  particularly the @|read| function, in the middle of a parsing operation.
\end{describe}

\begin{describe}{cls}{character-scanner-stream (stream) \&key :scanner}
  A Common Lisp input @|stream| object which works using the character
  scanner protocol.  Any @<scanner> which implements the base scanner and
  character scanner protocols is suitable.  See @|make-scanner-stream|.
\end{describe}

\subsection{String scanners} \label{sec:parsing.scanner.string}

A \emph{string scanner} is a simple kind of character scanner which reads
input from a string object.  String scanners implement the character scanner
and place-capture protocols.

\begin{describe}{cls}{string-scanner}
  The class of string scanners.  The @|string-scanner| class is not a
  subclass of @|character-scanner|.
\end{describe}

\begin{describe}{fun}{string-scanner-p @<value> @> @<generalized-boolean>}
  Return non-nil if @<value> is a @|string-scanner| object; otherwise return
  nil.
\end{describe}

\begin{describe}{fun}
    {make-string-scanner @<string> \&key :start :end @> @<string-scanner>}
  Construct and return a fresh @|string-scanner| object.  The new scanner
  will read characters from @<string>, starting at index @<start> (which
  defaults to zero), and continuing until it reaches index @<end> (defaults
  to the end of the @<string>).
\end{describe}

\subsection{Character buffer scanners} \label{sec:parsing.scanner.charbuf}

A \emph{character buffer scanner}, or \emph{charbuf scanner} for short, is an
efficient scanner for reading characters from an input stream.  Charbuf
scanners implements the basic scanner, character buffer, place-capture, and
file-location protocols.

\begin{describe}{cls}
    {charbuf-scanner (character-scanner)
        \&key :stream :filename :line :column}
  The class of charbuf scanners.  The scanner will read characters from
  @<stream>.  Charbuf scanners implement the file-location protocol: the
  initial location is set from the given @<filename>, @<line> and @<column>;
  the scanner will update the location as it reads its input.
\end{describe}

\begin{describe}{cls}{charbuf-scanner-place}
  The class of place objects captured by a charbuf scanner.
\end{describe}

\begin{describe}{fun}
    {charbuf-scanner-place-p @<value> @> @<generalized-boolean>}
  Type predicate for charbuf scanner places: returns non-nil if @<value> is a
  place captured by a charbuf scanner, and nil otherwise.
\end{describe}

\begin{describe}{gf}
    {charbuf-scanner-map @<scanner> @<func> \&optional @<fail>
      \nlret @<result> @<successp> @<consumedp>}
  Read characters from the @<scanner>'s buffers.

  This is intended to be an efficient and versatile interface for reading
  characters from a scanner in bulk.  The function @<func> is invoked
  repeatedly, as if by
  \begin{prog}
    (multiple-value-bind (@<donep> @<used>) \\ \ind\ind
        (funcall @<func> @<buf> @<start> @<end>) \- \\
      \textrm\ldots)
  \end{prog}
  The argument @<buf> is a simple string; @<start> and @<end> are two
  nonnegative fixnums, indicating that the subsequence of @<buf> between
  @<start> (inclusive) and @<end> (exclusive) should be processed.  If
  @<func>'s return value @<donep> is nil then @<used> is ignored: the
  function has consumed the entire buffer and wishes to read more.  If
  @<donep> is non-nil, then it must be a fixnum such that $@<start> \le
  @<used> \le @<end>$: the function has consumed the buffer as far as @<used>
  (exclusive) and has completed successfully.

  If end-of-file is encountered before @<func> completes successfully then it
  fails: the @<fail> function is called with no arguments, and is expected to
  return two values.  If omitted, @<fail> defaults to
  \begin{prog}
    (lambda () \\ \ind
      (values nil nil))%
  \end{prog}

  The @|charbuf-scanner-map| function returns three values.  The first value
  is the non-nil @<donep> value returned by @<func> if @|charbuf-scanner-map|
  succeeded, or the first value returned by @<fail>; the second value is @|t|
  on success, or the second value returned by @<fail>; the third value is
  non-nil if @<func> consumed any input, i.e., it returned with @<donep> nil
  at least once, or with $@<used> > @<start>$.
\end{describe}

\subsection{Token scanners} \label{sec:parsing.scanner.token}

\begin{describe}{cls}
    {token-scanner () \&key :filename (:line 1) (:column 0)}
\end{describe}

\begin{describe}{gf}{token-type @<scanner> @> @<type>}
\end{describe}

\begin{describe}{gf}{token-value @<scanner> @> @<value>}
\end{describe}

\begin{describe}{gf}{scanner-token @<scanner> @> @<type> @<value>}
\end{describe}

\begin{describe}{ty}{token-scanner-place}
\end{describe}

\begin{describe}{fun}
    {token-scanner-place-p @<value> @> @<generalized-boolean>}
\end{describe}

\subsection{List scanners}

\begin{describe}{ty}{list-scanner}
\end{describe}

\begin{describe}{fun}{list-scanner-p @<value> @> @<generalized-boolean>}
\end{describe}

\begin{describe}{fun}{make-list-scanner @<list> @> @<list-scanner>}
\end{describe}

%%%--------------------------------------------------------------------------
\section{Parsing syntax}

\begin{describe}{gf}{expand-parser-spec @<context> @<spec> @> @<form>}
\end{describe}

\begin{describe}{gf}
    {expand-parser-form @<context> @<head> @<tail> @> @<form>}
\end{describe}

\begin{describe}{gf}{wrap-parser @<context> @<form> @> @<wrapped-form>}
\end{describe}

\begin{describe}{mac}
    {defparse @<name> (@[[ :context (@<var> @<context-class>) @]]
                       @<destructuring-lambda-list-item>^*) \\ \ind
      @<body-form>^* \-
     \nlret @<name>}
\end{describe}

\begin{describe}{mac}
    {with-parser-context
        (@<context-class> @{ @<init-keyword> @<value> @}^*) \\ \ind
      @<body-form>^* \-
     \nlret @<value>^*}
\end{describe}

\begin{describe}{lmac}
    {parse @<parser> @> @<result> @<success-flag> @<consumed-flag>}
\end{describe}

\begin{describe}{gf}{parser-at-eof-p @<context> @> @<form>}
\end{describe}

\begin{describe}{gf}{parser-step @<context> @> @<form>}
\end{describe}

\begin{describe}{sym}{it}
\end{describe}

\begin{describe}{mac}
    {if-parse (@[[ \=:result @<result-var> @!
                     :expected @<expected-var> @! \+ \\
                     :consumedp @<consumed-var> @]]) \- \\ \ind\ind
        @<parser> \- \\
      @<consequent> \\
      @[@<alternatve>@] \-
     \nlret @<value>^*}
\end{describe}

\begin{describe}{mac}
    {when-parse (@[@<result-var>@]) @<parser> \\ \ind
      @<body-form>^* \-
     \nlret @<value>^*}
\end{describe}

\begin{describe}{mac}
    {cond-parse (@[[ \=:result @<result-var> @!
                       :expected @<expected-var> @! \+ \\
                       :consumedp @<consumed-var> @]]) \- \\ \ind
      @{ (@<parser> @<form>^*) @}^* \-
     \nlret @<value>^*}
\end{describe}

\begin{describe}{parse}{:eof}
\end{describe}

\begin{describe}{parseform}{lisp @<form>^*}
\end{describe}

\begin{describe}{parseform}{label @<parser>}
\end{describe}

\begin{describe}{parse}{t}
\end{describe}

\begin{describe}{parseform}{t @<value>}
\end{describe}

\begin{describe}{parse}{nil}
\end{describe}

\begin{describe}{parseform}{nil @<indicator>}
\end{describe}

\begin{describe}{parseform}{when @<cond> @<parser>}
\end{describe}

\begin{describe}{parseform}
    {seq (@{ @<atomic-parser-spec> @! (@[@<var>@] @<parser>) @}^*) \\ \ind
      @<body-form>^*}
\end{describe}

\begin{describe}{parseform}{and @<parser>^*}
\end{describe}

\begin{describe}{parseform}{or @<parser>^*}
\end{describe}

\begin{describe}{parseform}{? @<parser> @[@<default>@]}
\end{describe}

\begin{describe}{parseform}
    {many (\=@<accumulator-var> @<init-form> @<update-form> \+ \\
           @[[ \=:new @<new-var> @! :final @<final-form> @! \+ \\
                 :min @<minimum> @! :max @<maximum> @! \\
                 :commitp @<commitp> @]]) \-\- \\ \ind
      @<item-parser> @[@<sep-parser>@]}
\end{describe}

\begin{describe}{parseform}
    {list (@[[ :min @<minimum> @! :max @<maximum> @!
               :commitp @<commitp> @]])\\ \ind
      @<item-parser> @[@<sep-parser>@]}
\end{describe}

\begin{describe}{parseform}
    {skip-many (@[[ :min @<minimum> @! :max @<maximum> @!
                    :commitp @<commitp> @]])\\ \ind
      @<item-parser> @[@<sep-parser>@]}
\end{describe}

\begin{describe}{fun}{call-pluggable-parser @<symbol> \&rest @<args>}
\end{describe}

\begin{describe}{parseform}{plug @<symbol> @<arg>^*}
\end{describe}

\begin{describe}{fun}
    {pluggable-parser-add @<symbol> @<tag> @<parser-function>}
\end{describe}

\begin{describe}{mac}
    {define-pluggable-parser @<symbol> @<tag> @<lambda-list> @<body-form>^*}
\end{describe}

\begin{describe}{gf}{parser-capture-place @<context> @> @<form>}
\end{describe}

\begin{describe}{gf}{parser-restore-place @<context> @<place> @> @<form>}
\end{describe}

\begin{describe}{gf}{parser-release-place @<context> @<place> @> @<form>}
\end{describe}

\begin{describe}{gf}
    {parser-places-must-be-released-p @<context> @> @<generalized-boolean>>}
\end{describe}

\begin{describe}{mac}
    {with-parser-place (@<place-var> @<context>) @<body-form>^*}
\end{describe}

\begin{describe}{parseform}{peek @<parser>}
\end{describe}

\begin{describe}{cls}{character-parser-context () \&key}
\end{describe}

\begin{describe}{gf}{parser-current-char @<context> @> @<form>}
\end{describe}

\begin{describe}{parseform}
    {if-char (@[@<result-var>@]) @<condition> @<consequent> @<alternative>}
\end{describe}

\begin{describe}{parseform}{char @<character>}
\end{describe}

\begin{describe}[char]{parse}{@<character>}
\end{describe}

\begin{describe}[string]{parse}{@<string>}
\end{describe}

\begin{describe}{parse}{:any}
\end{describe}

\begin{describe}{parseform}{satisfies @<predicate>}
\end{describe}

\begin{describe}{parseform}{not @<character>}
\end{describe}

\begin{describe}{parseform}{filter @<predicate>}
\end{describe}

\begin{describe}{parse}{:whitespace}
\end{describe}

\begin{describe}{cls}{token-parser-context () \&key}
\end{describe}

\begin{describe}{gf}{parser-token-type @<context> @> @<form>}
\end{describe}

\begin{describe}{gf}{parser-token-value @<context> @> @<form>}
\end{describe}

\begin{describe}{parseform}{token @<type> @[@<value>@] @[:peekp @<peek>@]}
\end{describe}

\begin{describe}[atom]{parse}{@<atom>}
\end{describe}

\begin{describe}[string]{parse}{@<string>}
\end{describe}

\begin{describe}{cls}{scanner-context () \&key :scanner}
\end{describe}

\begin{describe}{gf}{parse-scanner @<context> @> @<symbol>}
\end{describe}

\begin{describe}{cls}
    {character-scanner-context (scanner-context character-parser-context)
      \&key :scanner}
\end{describe}

\begin{describe}{cls}
    {token-scanner-context (scanner-context token-parser-context)
      \&key :scanner}
\end{describe}

%% FIXME parser-expr

%%%-------------------------------------------------------------------------
\section{Lexical analyser}

%%%----- That's all, folks --------------------------------------------------

%%% Local variables:
%%% mode: LaTeX
%%% TeX-master: "sod.tex"
%%% TeX-PDF-mode: t
%%% End: