cl-yacc.texi

\input texinfo @c -*-texinfo-*-
@c %**start of header
@setfilename cl-yacc.info
@settitle The CL-Yacc Manual
@afourpaper
@c %**end of header

@dircategory Lisp Programming
@direntry
* CL-Yacc: (cl-yacc).                   Common Lisp LALR(1) parser generator.
@end direntry

@copying
Copyright @copyright{} 2005--2008 by Juliusz Chroboczek.
@end copying

@syncodeindex tp fn

@macro akey {}
@t{&key}
@end macro

@titlepage
@title The CL-Yacc Manual
@author Juliusz Chroboczek
@page
@vskip 0pt plus 1fill
CL-Yacc is a LALR(1) parser generator for Common Lisp, somewhat like
Yacc, GNU Bison, Zebu, lalr.cl or lalr.scm.
@vskip 0pt plus 1fill

@insertcopying

@end titlepage

@contents

@ifnottex
@node Top, Example, (dir), (dir)
@top CL-Yacc

CL-Yacc is a LALR(1) parser generator for Common Lisp, somewhat like
Yacc, GNU Bison, Zebu, lalr.cl or lalr.scm.

@ifhtml
The latest version of CL-Yacc can be found on 
@uref{http://www.irif.fr/~jch/software/cl-yacc/,the CL-Yacc web page}.
@end ifhtml

This manual was written by
@uref{http://www.irif.fr/~jch/,,Juliusz Chroboczek}.

@end ifnottex

@menu
* Example::                     A complete example.
* Reference::                   Reference.
* Index::                       Index.
@end menu

@node Example, Reference, Top, Top
@chapter A complete example

CL-Yacc exports its symbols from the package @code{yacc}:

@lisp
(use-package '#:yacc)
@end lisp

A parser consumes the output of a lexer, that produces a stream of
terminals.  CL-Yacc expects the lexer to be a function of no arguments
(a @dfn{thunk}) that returns two values: the next terminal symbol, and
the value of the symbol, which will be passed to the action associated
with a production.  At the end of the input, the lexer should return
@code{nil}.

A very simple lexer that grabs tokens from a list:

@lisp
(defun list-lexer (list)
  #'(lambda ()
      (let ((value (pop list)))
        (if (null value)
            (values nil nil)
            (let ((terminal
                   (cond ((member value '(+ - * / |(| |)|)) value)
                         ((integerp value) 'int)
                         ((symbolp value) 'id)
                         (t (error "Unexpected value ~S" value)))))
              (values terminal value))))))
@end lisp

We will implement the following grammar:

@display
expression ::= expression @code{+} expression
expression ::= expression @code{-} expression
expression ::= expression @code{*} expression
expression ::= expression @code{/} expression
expression ::= term

term ::= id
term ::= int
term ::= @code{-} term
term ::= @code{(} expression @code{)}
@end display

As this grammar is ambiguous, we need to specify the precedence and
associativity of the operators.  The operators @code{*} and @code{/}
will have the highest precedence, @code{+} and @code{-} will have
a lower one.  All operators will be left-associative.

If no semantic action is specified, CL-Yacc provides default actions
which are either @code{#'list} or @code{#'identity}, depending on how
a production is written.  For building a Lisp-like parse tree with
this grammar, we will need two additional actions:

@lisp
(eval-when (:compile-toplevel :load-toplevel :execute)
  (defun i2p (a b c) 
    "Infix to prefix"
    (list b a c))

  (defun k-2-3 (a b c)
    "Second out of three"
    (declare (ignore a c))
    b)
)
@end lisp

The parser definition itself:
@lisp
(define-parser *expression-parser*
  (:start-symbol expression)
  (:terminals (int id + - * / |(| |)|))
  (:precedence ((:left * /) (:left + -)))

  (expression
   (expression + expression #'i2p)
   (expression - expression #'i2p)
   (expression * expression #'i2p)
   (expression / expression #'i2p)
   term)

  (term
   id
   int
   (- term)
   (|(| expression |)| #'k-2-3)))
@end lisp

After loading this code, the parser is the value of the special
variable @code{*expression-parser*}, which can be passed to
@code{parse-with-lexer}:

@lisp
(parse-with-lexer (list-lexer '(x * - - 2 + 3 * y)) *expression-parser*)
    @result{} (+ (* X (- (- 2))) (* 3 Y))
@end lisp

@node Reference, Index, Example, Top
@chapter Reference

@menu
* Invoking a parser::           How to invoke a parser.
* Macro interface::             High-level macro interface.
* Functional interface::        Low-leve functional interface.
* Conditions::                  Conditions signalled by CL-Yacc.
@end menu

@node Invoking a parser, Macro interface, Reference, Reference
@section Running the parser

The main entry point to the parser is @code{parse-with-lexer}.

@defun parse-with-lexer lexer parser
Parse the input provided by the lexer @var{lexer} using the parser
@var{parser}.

The value of @var{lexer} should be a function of no arguments that
returns two values: the terminal symbol corresponding to the next
token (a non-null symbol), and its value (anything that the associated
actions can take as argument).  It should return @code{(values nil
nil)} when the end of the input is reached.

The value of @var{parser} should be a @code{parser} structure, as
computed by @code{make-parser} and @code{define-parser}.
@end defun

@node Macro interface, Functional interface, Invoking a parser, Reference
@section Macro interface

@defmac define-grammar name option... production...
@format
@var{option} ::= @code{(} @var{keyword} @var{value} @code{)}
@var{production} ::= @code{(} @var{symbol} @var{rhs}... @code{)}
@var{rhs} ::= @var{symbol}
@var{rhs} ::= @code{(} @var{symbol}... [@var{action}] @code{)}
@end format

Generates a grammar and binds it to the special variable @var{name}.
This has the side effect of globally proclaiming @var{name} special.

Every production is a list of a non-terminal symbol and one or more
right hand sides.  Every right hand side is either a symbol, or a list
of symbols optionally followed with an action.

The action should be a non-atomic form that evaluates to a function in
a null lexical environment.  If omitted, it defaults to
@code{#'identity} in the first form of @var{rhs}, and to @code{#'list}
in the second form.

The legal options are:

@table @code
@item :start-symbol
Defines the starting symbol of the grammar.  This is required.

@item :terminals
Defines the list of terminals of the grammar.  This is required.

@item :precedence

The value of this option should be a list of items of the form
@code{(@r{@var{associativity}} . @r{@var{terminals}})}, where
@var{associativity} is one of @code{:left}, @code{:right} or
@code{:nonassoc}, and @var{terminals} is a list of terminal symbols.
@var{Associativity} specifies the associativity of the terminals, and
earlier items will give their elements a precedence higher than that of
later ones.
@end table
@end defmac

@defmac define-parser name option... production...
Generates a parser and binds it to the special variable @var{name}.
This has the side effect of globally proclaiming @var{name} special.

The syntax is the same as that of @code{define-grammar}, except that
the following additional options are allowed:

@table @code
@item :muffle-conflicts

If @code{nil} (the default), a warning is signalled for every
conflict.  If the symbol @code{:some}, then only a summary of the
number of conflicts is signalled.  If @code{T}, then no warnings at
all are signalled for conflicts.  Otherwise, its value should be a
list of two integers (@var{sr} @var{rr}), in which case a summary
warning will be signalled unless exactly @var{sr} shift-reduce and
@var{rr} reduce-reduce conflicts were found.

@item :print-derives-epsilon
If true, print the list of nonterminal symbols that derive the empty
string.

@item :print-first-terminals
If true, print, for every nonterminal symbol, the list of terminals
that it may start with.

@item :print-states
If true, print the computed kernels of LR(0) items.

@item :print-goto-graph
If true, print the computed goto graph.

@item :print-lookaheads
If true, print the computed kernels of LR(0) items together with their
lookaheads.
@end table
@end defmac

@node Functional interface, Conditions, Macro interface, Reference
@section Functional interface

The macros @code{define-parser} and @code{define-grammar} expand into
calls to @code{defparameter}, @code{make-parser}, @code{make-grammar}
and @code{make-production} with suitable @code{make-load-form} magic
to ensure that the time consuming parser generation happens at
compile time rather than at load time.  The underlying functions are
exported in case you want to design a different syntax for grammars,
or generate grammars automatically.

@defun make-production symbol derives @akey{} action action-form
Returns a production for non-terminal @var{symbol} with
right-hand-side @var{derives} (a list of symbols).  @var{Action} is
the associated action, and should be a function; it defaults to
@code{#'list}.  @var{Action-form} should be a form that evaluates to
@var{action} in a null lexical environment; if null (the default), the
production (and hence any grammar or parser that uses it) will not be
fasdumpable.
@end defun

@defun make-grammar @akey{} name start-symbol terminals precedence productions
Returns a grammar.  @var{Name} is the name of the grammar (gratuitious
documentation).  @var{Start-symbol}, @var{terminals} and @var{precedence}
are as in @code{define-grammar}.  @var{Productions} is a list of productions.
@end defun

@defun make-parser grammar @akey{} discard-memos muffle-conflicts print-derives-epsilon print-first-terminals print-states print-goto-graph print-lookaheads
Computes and returns a parser for grammar @var{grammar}.
@var{discard-memos} specifies whether temporary data associated with
the grammar should be discarded.  @var{Muffle-conflicts},
@var{print-derives-epsilon}, @var{print-first-terminals},
@var{print-states}, @var{print-goto-graph} and @var{print-lookaheads}
are as in @code{define-parser}.
@end defun

@node Conditions,  , Functional interface, Reference
@section Conditions

CL-Yacc may signal warnings at compile time when it finds
conflicts.  It may also signal an error at parse time when it finds
that the input is incorrect.

@menu
* Compile-time::                Compile-time conditions.
* Runtime::                     Run-time conditions.
@end menu

@node Compile-time, Runtime, Conditions, Conditions
@subsection Compile-time conditions

If the grammar given to CL-Yacc is ambiguous, a warning of type
@code{conflict-warning} will be signalled for every conflict as it is
found, and a warning of type @code{conflict-summary-warning} will be
signalled at the end of parser generation.

@deftp Condition conflict-warning kind state terminal
Signalled whenever a conflict is found.  @var{Kind} is one of
@code{:shift-reduce} or @code{:reduce-reduce}.  @var{State} (an
integer) and @var{terminal} (a symbol) are the state and terminal for
which the conflict arises.
@end deftp

@deftp Condition conflict-summary-warning shift-reduce reduce-reduce
Signalled at the end of parser generation if there were any conflicts.
@var{Shift-reduce} and @var{reduce-reduce} are integers that indicate
how many conflicts were found.
@end deftp

@deftp Condition yacc-compile-warning
A superclass of @code{conflict-warning} and @code{conflict-summary-warning},
and a convenient place to hook your own condition types.
@end deftp

@node Runtime,  , Compile-time, Conditions
@subsection Runtime conditions

If the output cannot be parsed, the parser will signal a condition of
type @code{yacc-parse-error}.  It should be possible to invoke a
restart from a handler for @code{yacc-parse-error} in order to trigger
error recovery, but this hasn't been implemented yet.

@deftp Condition yacc-parse-error terminal value expected-terminals
Signalled whenever the input cannot be parsed.  The symbol
@var{terminal} is the terminal that couldn't be accepted; @var{value}
is its value.  @var{Expected-terminals} is the list of terminals that
could have been accepted in that state.
@end deftp

@deftp Condition yacc-runtime-error
A superclass of @code{yacc-parse-error}, and a convenient place to
hook your own condition types.
@end deftp

@unnumbered Acknowledgements

I am grateful to Antonio Bucciarelli, Guy Cousineau and Marc Zeitoun
for their help with implementing CL-Yacc.

@unnumbered Copying

@quotation
Copyright @copyright{} 2005--2009 by Juliusz Chroboczek

Permission is hereby granted, free of charge, to any person obtaining a copy
of this software and associated documentation files (the "Software"), to deal
in the Software without restriction, including without limitation the rights
to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
copies of the Software, and to permit persons to whom the Software is
furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in
all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL THE
AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
THE SOFTWARE.
@end quotation

@node Index,  , Reference, Top
@unnumbered Index
@printindex fn

@bye