mdw@git.distorted.org.uk Git - sod/blob - doc/parsing.tex

   1 %%% -*-latex-*-
   2 %%%
   3 %%% Description of the parsing machinery
   4 %%%
   5 %%% (c) 2015 Straylight/Edgeware
   6 %%%
   7
   8 %%%----- Licensing notice ---------------------------------------------------
   9 %%%
  10 %%% This file is part of the Sensible Object Design, an object system for C.
  11 %%%
  12 %%% SOD is free software; you can redistribute it and/or modify
  13 %%% it under the terms of the GNU General Public License as published by
  14 %%% the Free Software Foundation; either version 2 of the License, or
  15 %%% (at your option) any later version.
  16 %%%
  17 %%% SOD is distributed in the hope that it will be useful,
  18 %%% but WITHOUT ANY WARRANTY; without even the implied warranty of
  19 %%% MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  20 %%% GNU General Public License for more details.
  21 %%%
  22 %%% You should have received a copy of the GNU General Public License
  23 %%% along with SOD; if not, write to the Free Software Foundation,
  24 %%% Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
  25
  26 \chapter{Parsing} \label{ch:parsing}
  27
  28 %%%--------------------------------------------------------------------------
  29 \section{The parser protocol} \label{sec:parsing.proto}
  30
  31 For the purpose of Sod's parsing library, \emph{parsing} is the process of
  32 reading a sequence of input items, in order, and computing an output value.
  33
  34 A \emph{parser} is an expression which consumes zero or more input items and
  35 returns three values: a \emph{result}, a \emph{success flag}, and a
  36 \emph{consumed flag}.  The two flags are (generalized) booleans.  If the
  37 success flag is non-nil, then the parser is said to have \emph{succeeded},
  38 and the result is the parser's output.  If the success flag is nil then the
  39 parser is said to have \emph{failed}, and the result is a list of
  40 \emph{indicators}.  Finally, the consumed flag is non-nil if the parser
  41 consumed any input items.
  42
  43 \begin{describe}{fun}{combine-parser-failures @<failures> @> @<list>}
  44 \end{describe}
  45
  46 \begin{describe}{fun}{parse-empty \&optional @<value> @> @<function>}
  47 \end{describe}
  48
  49 \begin{describe}{fun}
  50     {parse-fail @<indicator> \&optional @<consumedp> @> @<function>}
  51 \end{describe}
  52
  53 %%%--------------------------------------------------------------------------
  54 \section{Streams} \label{sec:parsing.streams}
  55
  56 \begin{describe*}
  57     {\dhead{cls}{position-aware-stream \&key :file :line :column}
  58      \dhead{gf}{position-aware-stream-file @<stream> @> @<pathname>}
  59      \dhead{gf}{setf (position-aware-stream-file @<stream>) @<pathname>}
  60      \dhead{gf}{position-aware-stream-line @<stream> @> @<fixnum>}
  61      \dhead{gf}{setf (position-aware-stream-line @<stream>) @<fixnum>}
  62      \dhead{gf}{position-aware-stream-column @<stream> @> @<fixnum>}
  63      \dhead{gf}{setf (position-aware-stream-column @<stream>) @<fixnum>}}
  64 \end{describe*}
  65
  66 \begin{describe}{gf}{stream-pathname @<stream> @> @<pathname-or-nil>}
  67   \begin{describe}{meth}{stream}
  68       {stream-pathname (@<stream> stream) @> nil}
  69   \end{describe}
  70   \begin{describe}{meth}{file-stream}
  71       {stream-pathname (@<stream> file-stream) @> @<pathname>}
  72   \end{describe}
  73   \begin{describe}{meth}{position-aware-stream}
  74       {stream-pathname (@<stream> position-aware-stream) @> @<pathname>}
  75   \end{describe}
  76 \end{describe}
  77
  78 \begin{describe}{gf}{stream-line-and-column @<stream> @> @<line> @<column>}
  79   \begin{describe}{meth}{stream}
  80       {stream-line-and-column (@<stream> stream) @> nil nil}
  81   \end{describe}
  82   \begin{describe}{meth}{position-aware-stream}
  83       {stream-line-and-column (@<stream> position-aware-stream)
  84         \nlret @<line> @<column>}
  85   \end{describe}
  86 \end{describe}
  87
  88 %%%--------------------------------------------------------------------------
  89 \section{File locations} \label{sec:parsing.floc}
  90
  91 \begin{describe}{cls}{file-location}
  92 \end{describe}
  93
  94 \begin{describe}{fun}{file-location-p @<object> @> @<generalized-boolean>}
  95 \end{describe}
  96
  97 \begin{describe}{fun}
  98     {make-file-location @<filename> \&optional @<line> @<column>
  99       @> @<file-location>}
 100 \end{describe}
 101
 102 \begin{describe*}
 103     {\dhead{fun}{file-location-filename @<floc> @> @<string-or-nil>}
 104      \dhead{fun}{file-location-line @<floc> @> @<fixnum-or-nil>}
 105      \dhead{fun}{file-location-column @<floc> @> @<fixnum-or-nil>}}
 106 \end{describe*}
 107
 108 \begin{describe}{gf}{file-location @<object> @> @<floc>}
 109   \begin{describe}{meth}{file-location}
 110       {file-location (@<floc> file-location) @> @<floc>}
 111   \end{describe}
 112   \begin{describe}{meth}{stream}
 113       {file-location (@<stream> stream) @> @<floc>}
 114   \end{describe}
 115   \begin{describe}{meth}{t}
 116       {file-location (@<any> t) @> @<floc>}
 117   \end{describe}
 118 \end{describe}
 119
 120 \begin{describe}{cls}{condition-with-location (condition) \&key :location}
 121 \end{describe}
 122
 123 \begin{describe}{meth}{condition-with-location}
 124     {file-location (@<condition> condition-with-location) @> @<floc>}
 125 \end{describe}
 126
 127 \begin{describe*}
 128     {\quad\=\quad\=\kill
 129      \dhead{cls}
 130        {error-with-location (condition-with-location error)     \\ \>
 131          \&key :location}
 132      \dhead{cls}
 133        {warning-with-location (condition-with-location warning) \\ \>
 134          \&key :location}
 135      \dhead{cls}
 136        {information-with-location (condition-with-location information) \\ \>
 137          \&key :location}
 138      \dhead{cls}
 139        {enclosing-error-with-location
 140            (enclosing-error-with-location error)                \\ \>
 141          \&key :condition :location}
 142      \dhead{cls}
 143        {enclosing-warning-with-location
 144            (enclosing-condition-with-location warning)          \\ \>
 145          \&key :condition :location}
 146      \dhead{cls}
 147        {enclosing-information-with-location
 148            (enclosing-condition-with-location information)      \\ \>
 149          \&key :condition :location}
 150      \dhead{cls}
 151        {simple-condition-with-location
 152            (condition-with-location simple-condition)           \\ \>
 153          \&key :format-control :format-arguments :location}
 154      \dhead{cls}
 155        {simple-error-with-location
 156            (error-with-location simple-error)                   \\ \>
 157          \&key :format-control :format-arguments :location}
 158      \dhead{cls}
 159        {simple-warning-with-location
 160            (warning-with-location simple-warning)               \\ \>
 161          \&key :format-control :format-arguments :location}
 162      \dhead{cls}
 163        {simple-information-with-location
 164            (information-with-location simple-information)       \\ \>
 165          \&key :format-control :format-arguments :location}}
 166 \end{describe*}
 167
 168 \begin{describe}{gf}
 169     {enclosing-condition-with-location-type @<condition> @> @<symbol>}
 170 \end{describe}
 171
 172 \begin{describe}{fun}
 173     {make-condition-with-location @<default-type> @<floc>
 174                                   @<datum> \&rest @<arguments>
 175        \nlret @<condition-with-location>}
 176 \end{describe}
 177
 178 \begin{describe*}
 179     {\dhead{fun}{error-with-location @<floc> @<datum> \&rest @<arguments>}
 180      \dhead{fun}{cerror-with-location @<floc> @<continue-string>
 181                                       @<datum> \&rest @<arguments>}
 182      \dhead{fun}{cerror*-with-location @<floc> @<datum> \&rest @<arguments>}
 183      \dhead{fun}{warn-with-location @<floc> @<datum> \&rest @<arguments>}}
 184 \end{describe*}
 185
 186 \begin{describe*}
 187     {\dhead{cls}{parser-error (error) \\ \ind
 188                     \&key :expected :found \-}
 189      \dhead{gf}{parser-error-expected @<condition> @> @<list>}
 190      \dhead{gf}{parser-error-found @<condition> @> @<value>}}
 191 \end{describe*}
 192
 193 \begin{describe}{fun}
 194     {report-parser-error @<error> @<stream> @<show-expected> @<show-found>}
 195 \end{describe}
 196
 197 \begin{describe*}
 198     {\quad\=\kill
 199      \dhead{cls}{base-lexer-error (error-with-location) \&key :location}
 200      \dhead{cls}{simple-lexer-error
 201                       (base-lexer-error simple-error-with-location) \\\>
 202                     \&key :format-control :format-arguments :location}
 203      \dhead{cls}{base-syntax-error (error-with-location) \&key :location}
 204      \dhead{cls}{simple-syntax-error
 205                       (base-syntax-error simple-error-with-location) \\\>
 206                     \&key :format-control :format-arguments :location}}
 207 \end{describe*}
 208
 209 \begin{describe}{mac}
 210     {with-default-error-location (@<floc>) @<declaration>^* @<form>^*
 211       @> @<value>^*}
 212 \end{describe}
 213
 214 \begin{describe}{gf}{classify-condition @<condition> @> @<string>}
 215   \begin{describe*}
 216       {\dhead{meth}{error}
 217          {classify-condition (@<condition> error) @> @<string>}
 218        \dhead{meth}{warning}
 219          {classify-condition (@<condition> warning) @> @<string>}
 220        \dhead{meth}{information}
 221          {classify-condition (@<condition> information)
 222              @> @<string>}
 223        \dhead{meth}{base-lexer-error}
 224          {classify-condition (@<condition> base-lexer-error)
 225              @> @<string>}
 226        \dhead{meth}{base-syntax-error}
 227          {classify-condition (@<condition> base-syntax-error)
 228              @> @<string>}}
 229   \end{describe*}
 230 \end{describe}
 231
 232 \begin{describe}{mac}
 233     {count-and-report-errors () @<declaration>^* @<form>^*
 234       @> @<value> @<n-errors> @<n-warnings>}
 235 \end{describe}
 236
 237 %%%--------------------------------------------------------------------------
 238 \section{Scanners} \label{sec:parsing.scanner}
 239
 240 A \emph{scanner} is an object which keeps track of a parser's progress as it
 241 works through its input.  There's no common base class for scanners: a
 242 scanner is simply any object which implements the scanner protocol described
 243 here.
 244
 245 A scanner maintains a sequence of items to read.  It can step forwards
 246 through the items, one at a time, until it reaches the end (if, indeed, the
 247 sequence is finite, which it needn't be).  Until that point, there is a
 248 current item, though there's no protocol for accessing it at this level
 249 because the nature of the items is left unspecified.
 250
 251 Some scanners support an additional \emph{place-capture} protocol which
 252 allows rewinding the scanner to an earlier point in the input so that it can
 253 be scanned again.
 254
 255
 256 \subsection{Basic scanner protocol} \label{sec:parsing.scanner.basic}
 257
 258 The basic protocol supports stepping the scanner forward through its input
 259 sequence, and detecting the end of the sequence.
 260
 261 \begin{describe}{gf}{scanner-step @<scanner>}
 262   Advance the @<scanner> to the next item, which becomes current.
 263
 264   It is an error to step the scanner if the scanner is at end-of-file.
 265 \end{describe}
 266
 267 \begin{describe}{gf}{scanner-at-eof-p @<scanner> @> @<generalized-boolean>}
 268   Return non-nil if the scanner is at end-of-file, i.e., there are no more
 269   items to read.
 270
 271   If nil is returned, there is a current item, and it is safe to step the
 272   scanner again; otherwise, it is an error to query the current item or to
 273   step the scanner.
 274 \end{describe}
 275
 276
 277 \subsection{Place-capture scanner protocol} \label{sec:parsing.scanner.place}
 278
 279 The place-capture protocol allows rewinding to an earlier point in the
 280 sequence.  Not all scanners support the place-capture protocol.
 281
 282 To rewind a scanner to a particular point, that point must be \emph{captured}
 283 as a \emph{place} when it's current -- so you must know in advance that this
 284 is an interesting place that's worth capturing.  The type of place returned
 285 depends on the type of scanner.  Given a captured place, the scanner can be
 286 rewound to the position held in it.
 287
 288 Depending on how the scanner works, holding onto a captured place might
 289 consume a lot of memory or cause poor performance.  For example, if the
 290 scanner is reading from an input stream, having a captured place means that
 291 data from that point on must be buffered in case the program needs to rewind
 292 the scanner and read that data again.  Therefore it's possible to
 293 \emph{release} a place when it turns out not to be needed any more.
 294
 295 \begin{describe}{gf}{scanner-capture-place @<scanner> @> @<place>}
 296   Capture the @<scanner>'s current position as a place, and return the place.
 297 \end{describe}
 298
 299 \begin{describe}{gf}{scanner-restore-place @<scanner> @<place>}
 300   Rewind the @<scanner> to the state it was in when @<place> was captured.
 301   In particular, the item that was current when the @<place> was captured
 302   becomes current again.
 303
 304   It is an error to restore a @<place> that has been released, or if the
 305   @<place> wasn't captured from the @<scanner>.
 306 \end{describe}
 307
 308 \begin{describe}{gf}{scanner-release-place @<scanner> @<place>}
 309   Release the @<place>, to avoid having to maintaining the ability to restore
 310   it after it's not needed any more..
 311
 312   It is an error if the @<place> wasn't captured from the @<scanner>.
 313 \end{describe}
 314
 315 \begin{describe}{mac}
 316     {with-scanner-place (@<place> @<scanner>) @<declarations>^* @<form>^*
 317       @> @<value>^*}
 318   Capture the @<scanner>'s current position as a place, evaluate the @<form>s
 319   as an implicit progn with the variable @<place> bound to the captured
 320   place.  When control leaves the @<form>s, the place is released.  The
 321   return values are the values of the final @<form>.
 322 \end{describe}
 323
 324
 325 \subsection{Scanner file-location protocol} \label{sec:parsing.scanner.floc}
 326
 327 Some scanners participate in the file-location protocol
 328 (\xref{sec:parsing.floc}).  They implement a method on @|file-location| which
 329 collects the necessary information using scanner-specific functions described
 330 here.
 331
 332 \begin{describe}{fun}{scanner-file-location @<scanner> @> @<file-location>}
 333   Return a @|file-location| object describing the current position of the
 334   @<scanner>.
 335
 336   This calls the @|scanner-filename|, @|scanner-line| and @|scanner-column|
 337   generic functions on the scanner, and uses these to fill in an appropriate
 338   @|file-location|.
 339
 340   Since there are default methods on these generic functions, it is not an
 341   error to call @|scanner-file-location| on any kind of value, but it might
 342   not be very useful.  This function exists to do the work of appropriately
 343   specialized methods on @|file-location|.
 344 \end{describe}
 345
 346 \begin{describe*}
 347     {\dhead{gf}{scanner-filename @<scanner> @> @<string>}
 348      \dhead{gf}{scanner-line @<scanner> @> @<integer>}
 349      \dhead{gf}{scanner-column @<scanner> @> @<integer>}}
 350   Return the filename, line and column components of the @<scanner>'s current
 351   position, for use in assembling a @<file-location>: see the
 352   @|scanner-file-location| function.
 353
 354   There are default methods on all three generic functions which simply
 355   return nil.
 356 \end{describe*}
 357
 358
 359 \subsection{Character scanners} \label{sec:parsing.scanner.char}
 360
 361 Character scanners are scanners which read sequences of characters.
 362
 363 \begin{describe}{cls}{character-scanner () \&key}
 364   Base class for character scanners.  This provides some very basic
 365   functionality.
 366
 367   Not all character scanners are subclasses of @|character-scanner|.
 368 \end{describe}
 369
 370 \begin{describe}{gf}{scanner-current-char @<scanner> @> @<character>}
 371   Returns the current character.
 372 \end{describe}
 373
 374 \begin{describe}{gf}{scanner-unread @<scanner> @<character>}
 375   Rewind the @<scanner> by one step.  The @<chararacter> must be the previous
 376   current character, and becomes the current character again.  It is an error
 377   if: the @<scanner> has reached end-of-file; the @<scanner> has never been
 378   stepped; or @<character> was not the previous current character.
 379 \end{describe}
 380
 381 \begin{describe}{gf}
 382     {scanner-interval @<scanner> @<place-a> \&optional @<place-b>
 383         @> @<string>}
 384   Return the characters in the @<scanner>'s input from @<place-a> up to (but
 385   not including) @<place-b>.
 386
 387   The characters are returned as a string.  If @<place-b> is omitted, return
 388   the characters up to (but not including) the current position.  It is an
 389   error if @<place-b> precedes @<place-a> or they are from different
 390   scanners.
 391
 392   This function is a character-scanner-specific extension to the
 393   place-capture protocol; not all character scanners implement the
 394   place-capture protocol, and some that do may not implement this function.
 395 \end{describe}
 396
 397 \subsubsection{Stream access to character scanners}
 398 Sometimes it can be useful to apply the standard Lisp character input
 399 operations to the sequence of characters held by a character scanner.
 400
 401 \begin{describe}{gf}{make-scanner-stream @<scanner> @> @<stream>}
 402   Returns a fresh input @|stream| object which fetches input characters from
 403   the character scanner object @<scanner>.  Reading characters from the
 404   stream steps the scanner.  The stream will reach end-of-file when the
 405   scanner reports end-of-file.  If the scanner implements the file-location
 406   protocol then reading from the stream will change the file location in an
 407   appropriate manner.
 408
 409   This is mostly useful for applying standard Lisp stream functions, most
 410   particularly the @|read| function, in the middle of a parsing operation.
 411 \end{describe}
 412
 413 \begin{describe}{cls}{character-scanner-stream (stream) \&key :scanner}
 414   A Common Lisp input @|stream| object which works using the character
 415   scanner protocol.  Any @<scanner> which implements the base scanner and
 416   character scanner protocols is suitable.  See @|make-scanner-stream|.
 417 \end{describe}
 418
 419
 420 \subsection{String scanners} \label{sec:parsing.scanner.string}
 421
 422 A \emph{string scanner} is a simple kind of character scanner which reads
 423 input from a string object.  String scanners implement the character scanner
 424 and place-capture protocols.
 425
 426 \begin{describe}{cls}{string-scanner}
 427   The class of string scanners.  The @|string-scanner| class is not a
 428   subclass of @|character-scanner|.
 429 \end{describe}
 430
 431 \begin{describe}{fun}{string-scanner-p @<value> @> @<generalized-boolean>}
 432   Return non-nil if @<value> is a @|string-scanner| object; otherwise return
 433   nil.
 434 \end{describe}
 435
 436 \begin{describe}{fun}
 437     {make-string-scanner @<string> \&key :start :end @> @<string-scanner>}
 438   Construct and return a fresh @|string-scanner| object.  The new scanner
 439   will read characters from @<string>, starting at index @<start> (which
 440   defaults to zero), and continuing until it reaches index @<end> (defaults
 441   to the end of the @<string>).
 442 \end{describe}
 443
 444
 445 \subsection{Character buffer scanners} \label{sec:parsing.scanner.charbuf}
 446
 447 A \emph{character buffer scanner}, or \emph{charbuf scanner} for short, is an
 448 efficient scanner for reading characters from an input stream.  Charbuf
 449 scanners implements the basic scanner, character buffer, place-capture, and
 450 file-location protocols.
 451
 452 \begin{describe}{cls}
 453     {charbuf-scanner (character-scanner)
 454         \&key :stream :filename :line :column}
 455   The class of charbuf scanners.  The scanner will read characters from
 456   @<stream>.  Charbuf scanners implement the file-location protocol: the
 457   initial location is set from the given @<filename>, @<line> and @<column>;
 458   the scanner will update the location as it reads its input.
 459 \end{describe}
 460
 461 \begin{describe}{cls}{charbuf-scanner-place}
 462   The class of place objects captured by a charbuf scanner.
 463 \end{describe}
 464
 465 \begin{describe}{fun}
 466     {charbuf-scanner-place-p @<value> @> @<generalized-boolean>}
 467   Type predicate for charbuf scanner places: returns non-nil if @<value> is a
 468   place captured by a charbuf scanner, and nil otherwise.
 469 \end{describe}
 470
 471 \begin{describe}{gf}
 472     {charbuf-scanner-map @<scanner> @<func> \&optional @<fail>
 473       \nlret @<result> @<success-flag> @<consumed-flag>}
 474   Read characters from the @<scanner>'s buffers.
 475
 476   This is intended to be an efficient and versatile interface for reading
 477   characters from a scanner in bulk.  The function @<func> is invoked
 478   repeatedly, as if by
 479   \begin{prog}
 480     (multiple-value-bind (@<donep> @<used>)                     \\ \ind\ind
 481         (funcall @<func> @<buf> @<start> @<end>)              \-\\
 482       \textrm\ldots)
 483   \end{prog}
 484   The argument @<buf> is a simple string; @<start> and @<end> are two
 485   nonnegative fixnums, indicating that the subsequence of @<buf> between
 486   @<start> (inclusive) and @<end> (exclusive) should be processed.  If
 487   @<func>'s return value @<donep> is nil then @<used> is ignored: the
 488   function has consumed the entire buffer and wishes to read more.  If
 489   @<donep> is non-nil, then @<used> must be a fixnum such that $@<start> \le
 490   @<used> \le @<end>$: the function has consumed the buffer as far as @<used>
 491   (exclusive) and has completed successfully.
 492
 493   If end-of-file is encountered before @<func> completes successfully then it
 494   fails: the @<fail> function is called with no arguments, and is expected to
 495   return two values.  If omitted, @<fail> defaults to
 496   \begin{prog}
 497     (lambda ()                                                  \\ \ind
 498       (values nil nil))
 499   \end{prog}
 500
 501   The @|charbuf-scanner-map| function returns three values.  The first value
 502   is the non-nil @<donep> value returned by @<func> if @|charbuf-scanner-map|
 503   succeeded, or the first value returned by @<fail>; the second value is @|t|
 504   on success, or the second value returned by @<fail>; the third value is
 505   non-nil if @<func> consumed any input, i.e., it returned with @<donep> nil
 506   at least once, or with $@<used> > @<start>$.
 507 \end{describe}
 508
 509
 510 \subsection{Token scanners} \label{sec:parsing.scanner.token}
 511
 512 \begin{describe}{cls}
 513     {token-scanner () \&key :filename (:line 1) (:column 0)}
 514 \end{describe}
 515
 516 \begin{describe}{gf}{token-type @<scanner> @> @<type>}
 517 \end{describe}
 518
 519 \begin{describe}{gf}{token-value @<scanner> @> @<value>}
 520 \end{describe}
 521
 522 \begin{describe}{gf}{scanner-token @<scanner> @> @<type> @<value>}
 523 \end{describe}
 524
 525 \begin{describe}{ty}{token-scanner-place}
 526 \end{describe}
 527
 528 \begin{describe}{fun}
 529     {token-scanner-place-p @<value> @> @<generalized-boolean>}
 530 \end{describe}
 531
 532
 533 \subsection{List scanners}
 534
 535 \begin{describe}{ty}{list-scanner}
 536 \end{describe}
 537
 538 \begin{describe}{fun}{list-scanner-p @<value> @> @<generalized-boolean>}
 539 \end{describe}
 540
 541 \begin{describe}{fun}{make-list-scanner @<list> @> @<list-scanner>}
 542 \end{describe}
 543
 544 %%%--------------------------------------------------------------------------
 545 \section{Parser contexts and parser syntax} \label{sec:parsing.syntax}
 546
 547
 548 \subsection{Parser contexts} \label{sec:parsing.syntax.contexts}
 549
 550 \begin{describe}{mac}
 551     {with-parser-context
 552         (@<context-class> @{ @<init-keyword> @<value> @}^*)     \\ \ind
 553       @<declaration>^*                                          \\
 554       @<form>^*
 555      \-\nlret @<value>^*}
 556 \end{describe}
 557
 558 \begin{describe}{gf}{expand-parser-spec @<context> @<spec> @> @<form>}
 559 \end{describe}
 560
 561 \begin{describe}{gf}
 562     {expand-parser-form @<context> @<head> @<tail> @> @<form>}
 563 \end{describe}
 564
 565 \begin{describe}{gf}{wrap-parser @<context> @<form> @> @<wrapped-form>}
 566 \end{describe}
 567
 568 \begin{describe}{mac}
 569     {defparse @<name> (@[[ :context (@<var> @<context-class>) @]]
 570                        @<destructuring-lambda-list-item>^*)     \\ \ind
 571       @[[ @<declaration>^* @! @<doc-string> @]]                 \\
 572       @<form>^*
 573      \-\nlret @<name>}
 574 \end{describe}
 575
 576 \begin{describe}{lmac}
 577     {parse @<parser> @> @<result> @<success-flag> @<consumed-flag>}
 578 \end{describe}
 579
 580 \begin{describe}{mac}
 581     {parser @<lambda-list>
 582       @[[ @<declaration>^* @! @<doc-string> @]]
 583       @<parser>
 584       @> @<function>}
 585 \end{describe}
 586
 587 \begin{describe}{gf}{parser-at-eof-p @<context> @> @<form>}
 588 \end{describe}
 589
 590 \begin{describe}{gf}{parser-step @<context> @> @<form>}
 591 \end{describe}
 592
 593 \begin{describe}{mac}
 594     {if-parse (@[[ \=:result @<result-var> @!
 595                      :expected @<expected-var> @!             \+\\
 596                      :consumedp @<consumed-var> @]])          \-\\ \ind\ind
 597         @<parser>                                             \-\\
 598       @<consequent>                                             \\
 599       @[@<alternatve>@]
 600      \-\nlret @<value>^*}
 601 \end{describe}
 602
 603 \begin{describe}{mac}
 604     {when-parse (@[@<result-var>@]) @<parser>                   \\ \ind
 605       @<form>^*
 606      \-\nlret @<value>^*}
 607 \end{describe}
 608
 609 \begin{describe}{mac}
 610     {cond-parse (@[[ \=:result @<result-var> @!
 611                        :expected @<expected-var> @!           \+\\
 612                        :consumedp @<consumed-var> @]])        \-\\ \ind
 613       @{ (@<parser> @<form>^*) @}^*
 614      \-\nlret @<value>^*}
 615 \end{describe}
 616
 617
 618 \subsection{Basic parser syntax} \label{sec:parsing.syntax.basic}
 619
 620 \begin{describe}{parse}{:eof}
 621 \end{describe}
 622
 623 \begin{describe}{parseform}{lisp @<form>^*}
 624 \end{describe}
 625
 626 \begin{describe}{parseform}{label @<parser>}
 627 \end{describe}
 628
 629 \begin{describe}{parse}{t}
 630 \end{describe}
 631
 632 \begin{describe}{parseform}{t @<value>}
 633 \end{describe}
 634
 635 \begin{describe}{parse}{nil}
 636 \end{describe}
 637
 638 \begin{describe}{parseform}{nil @<indicator>}
 639 \end{describe}
 640
 641 \begin{describe}{parseform}{when @<cond> @<parser>}
 642 \end{describe}
 643
 644 \begin{describe}{parseform}
 645     {seq (@{ @<atomic-parser-spec> @!
 646              (@[@<var>@] @<parser>) @}^*)                       \\ \ind
 647       @<form>^*}
 648 \end{describe}
 649
 650 \begin{describe}{parseform}{and @<parser>^*}
 651 \end{describe}
 652
 653 \begin{describe}{parseform}{or @<parser>^*}
 654 \end{describe}
 655
 656 \begin{describe}{parseform}{? @<parser> @[@<default>@]}
 657 \end{describe}
 658
 659 \begin{describe}{parseform}
 660     {many (\=@<accumulator-var> @<init-form> @<update-form>   \+\\
 661            @[[ \=:new @<new-var> @! :final @<final-form> @!   \+\\
 662                  :min @<minimum> @! :max @<maximum> @!          \\
 663                  :commitp @<commitp> @]])                   \-\-\\ \ind
 664       @<item-parser> @[@<sep-parser>@]}
 665 \end{describe}
 666
 667 \begin{describe}{parseform}
 668     {list (@[[ :min @<minimum> @! :max @<maximum> @!
 669                :commitp @<commitp> @]])                         \\ \ind
 670       @<item-parser> @[@<sep-parser>@]}
 671 \end{describe}
 672
 673 \begin{describe}{parseform}
 674     {skip-many (@[[ :min @<minimum> @! :max @<maximum> @!
 675                     :commitp @<commitp> @]])                    \\ \ind
 676       @<item-parser> @[@<sep-parser>@]}
 677 \end{describe}
 678
 679 \begin{describe}{fun}{call-pluggable-parser @<symbol> \&rest @<args>}
 680 \end{describe}
 681
 682 \begin{describe}{parseform}{plug @<symbol> @<arg>^*}
 683 \end{describe}
 684
 685 \begin{describe}{fun}
 686     {pluggable-parser-add @<symbol> @<tag> @<parser-function>}
 687 \end{describe}
 688
 689 \begin{describe}{mac}
 690     {define-pluggable-parser @<symbol> @<tag> @<lambda-list>
 691       @[[ @<declaration>^* @! @<doc-string> @]]
 692       @<form>^*}
 693 \end{describe}
 694
 695
 696 \subsection{Place-capture protocol} \label{sec:parsing.syntax.place}
 697
 698 \begin{describe}{gf}{parser-capture-place @<context> @> @<form>}
 699 \end{describe}
 700
 701 \begin{describe}{gf}{parser-restore-place @<context> @<place> @> @<form>}
 702 \end{describe}
 703
 704 \begin{describe}{gf}{parser-release-place @<context> @<place> @> @<form>}
 705 \end{describe}
 706
 707 \begin{describe}{gf}
 708     {parser-places-must-be-released-p @<context> @> @<generalized-boolean>}
 709 \end{describe}
 710
 711 \begin{describe}{mac}
 712     {with-parser-place (@<place-var> @<context>)
 713       @[[ @<declaration>^* @! @<doc-string> @]]
 714       @<form>^*}
 715 \end{describe}
 716
 717 \begin{describe}{parseform}{peek @<parser>}
 718 \end{describe}
 719
 720 \begin{describe}{parseform}{commit}
 721 \end{describe}
 722
 723
 724 \subsection{Character parsers} \label{sec:parsing.syntax.character}
 725
 726 \begin{describe}{cls}{character-parser-context () \&key}
 727 \end{describe}
 728
 729 \begin{describe}{gf}{parser-current-char @<context> @> @<form>}
 730 \end{describe}
 731
 732 \begin{describe}{parseform}
 733     {if-char (@[@<result-var>@]) @<condition> @<consequent> @<alternative>}
 734 \end{describe}
 735
 736 \begin{describe}{parseform}{char @<character>}
 737 \end{describe}
 738
 739 \begin{describe}{parse}[char]{@<character>}
 740 \end{describe}
 741
 742 \begin{describe}{parse}[string]{@<string>}
 743 \end{describe}
 744
 745 \begin{describe}{parse}{:any}
 746 \end{describe}
 747
 748 \begin{describe}{parseform}{satisfies @<predicate>}
 749 \end{describe}
 750
 751 \begin{describe}{parseform}{not @<character>}
 752 \end{describe}
 753
 754 \begin{describe}{parseform}{filter @<predicate>}
 755 \end{describe}
 756
 757 \begin{describe}{parse}{:whitespace}
 758 \end{describe}
 759
 760 \begin{describe}{cls}{token-parser-context () \&key}
 761 \end{describe}
 762
 763 \begin{describe}{gf}{parser-token-type @<context> @> @<form>}
 764 \end{describe}
 765
 766 \begin{describe}{gf}{parser-token-value @<context> @> @<form>}
 767 \end{describe}
 768
 769 \begin{describe}{parseform}{token @<type> @[@<value>@] @[:peekp @<peek>@]}
 770 \end{describe}
 771
 772 \begin{describe}{parse}[atom]{@<atom>}
 773 \end{describe}
 774
 775
 776 \subsection{Scanner contexts} \label{sec:parsing.syntax.scanner}
 777
 778 \begin{describe}{cls}{scanner-context () \&key :scanner}
 779 \end{describe}
 780
 781 \begin{describe}{gf}{parse-scanner @<context> @> @<symbol>}
 782 \end{describe}
 783
 784 \begin{describe}{cls}
 785     {character-scanner-context (scanner-context character-parser-context)
 786       \&key :scanner}
 787 \end{describe}
 788
 789 \begin{describe}{cls}
 790     {token-scanner-context (scanner-context token-parser-context)
 791       \&key :scanner}
 792 \end{describe}
 793
 794
 795 \subsection{Expression parsing} \label{sec:parsing.syntax.expression}
 796
 797 \begin{describe}{gf}{push-operator @<operator> @<state>}
 798 \end{describe}
 799
 800 \begin{describe}{gf}{push-value @<value> @<state>}
 801 \end{describe}
 802
 803 \begin{describe}{gf}{apply-operator @<operator> @<state>}
 804 \end{describe}
 805
 806 \begin{describe}{gf}{operator-push-action @<left> @<right>}
 807 \end{describe}
 808
 809 \begin{describe}{parseform}
 810     {expr \=(@[[ :nestedp @<nestedp-var> @]])                 \+\\
 811             @<operand-parser> @<binop-parser>
 812             @<preop-parser> @<postop-parser>}
 813 \end{describe}
 814
 815 \begin{describe}{gf}{operator-left-precedence @<operator> @> @<prec>}
 816 \end{describe}
 817
 818 \begin{describe}{gf}{operator-right-precedence @<operator> @> @<prec>}
 819 \end{describe}
 820
 821 \begin{describe}{gf}{operator-associativity @<operator> @> @<assoc>}
 822 \end{describe}
 823
 824 \begin{describe}{cls}{prefix-operator () \&key}
 825 \end{describe}
 826
 827 \begin{describe}{cls}{simple-operator () \&key :name :function}
 828 \end{describe}
 829
 830 \begin{describe}{cls}
 831     {simple-unary-operator (simple-operator) \&key :name :function}
 832 \end{describe}
 833
 834 \begin{describe*}
 835     {\quad\=\kill
 836      \dhead{cls}{simple-binary-operator (simple-operator)       \\ \>
 837                   \&key :name :function
 838                         :lprec :rprec :associativity}
 839      \dhead{cls}{simple-postfix-operator (simple-unary-operator) \\ \>
 840                   \&key :name :function :lprec :rprec}
 841      \dhead{cls}{simple-prefix-operator
 842                     (prefix-operator simple-unary-operator)     \\ \>
 843                   \&key :name :function :rprec}}
 844 \end{describe*}
 845
 846 \begin{describe*}
 847     {\dhead{mac}{preop @<name> (@<operand-var> @<lprec>)
 848                   @<declaration>^* @<form>^*
 849                   @> @<prefix-operator>}
 850      \dhead{mac}{postop @<name>
 851                      (@<operand-var> @<lprec> @[[ :rprec @<rprec> @]])
 852                   @<declaration>^* @<form>^*
 853                   \nlret @<postfix-operator>}
 854      \dhead{mac}{binop @<name> (@<operand-var> @<lprec> @<rprec> @<assoc>)
 855                   @<declaration>^*@<form>^*
 856                   @> @<binary-operator>}}
 857 \end{describe*}
 858
 859 \begin{describe*}
 860     {\dhead{cls}{parenthesis () \&key :tag}
 861      \dhead{cls}{open-parenthesis (parenthesis prefix-operator) \&key :tag}
 862      \dhead{cls}{close-parenthesis (parenthesis) \&key :tag}}
 863 \end{describe*}
 864
 865 \begin{describe*}
 866     {\dhead{fun}{lparen @<tag> @> @<open-paren>}
 867      \dhead{fun}{rparen @<tag> @> @<close-paren>}}
 868 \end{describe*}
 869
 870 %%%-------------------------------------------------------------------------
 871 \section{Lexical analyser} \label{sec:parsing.lexical}
 872
 873 \begin{describe}{cls}
 874     {sod-token-scanner (token-scanner)
 875       \&key :filename (:line 1) (:column 0) :char-scanner}
 876 \end{describe}
 877
 878 \begin{describe}{fun}{define-indicator @<indicator> @<description>}
 879 \end{describe}
 880
 881 \begin{describe*}
 882     {\dhead{cls}{lexer-error (parser-error base-lexer-error) \\ \ind
 883                     \&key :expected :found :location \-}
 884      \dhead{cls}{syntax-error (parser-error base-syntax-error) \\ \ind
 885                     \&key :expected :found :location \-}}
 886 \end{describe*}
 887
 888 \begin{describe}{fun}
 889     {syntax-error @<scanner> @<expected> \&key :continuep :location}
 890 \end{describe}
 891
 892 \begin{describe}{fun}
 893     {lexer-error @<char-scanner> @<expected> \&key :location}
 894 \end{describe}
 895
 896 \begin{describe}{parseform}
 897     {skip-until (@[[ :keep-end @<keep-end-flag> @]]) @<token-type>^*}
 898 \end{describe}
 899
 900 \begin{describe}{parseform}
 901     {error (@[[ :ignore-unconsumed @<flag> @!
 902                 :force-process @<flag> @]])                     \\ \ind\ind
 903         @<sub-parser> @<recover-parser>                       \-\\
 904       @<declaration>^*                                          \\
 905       @<form>^*}
 906 \end{describe}
 907
 908 \begin{describe}{parseform}{must @<sub-parser> @[@<default>@]}
 909 \end{describe}
 910
 911 \begin{describe}{fun}
 912     {scan-comment @<char-scanner>
 913       @> @<result> @<success-flag> @<consumed-flag>}
 914 \end{describe}
 915
 916 %%%----- That's all, folks --------------------------------------------------
 917
 918 %%% Local variables:
 919 %%% mode: LaTeX
 920 %%% TeX-master: "sod.tex"
 921 %%% TeX-PDF-mode: t
 922 %%% End: