\input texinfo.tex
@setfilename nyacc-ug.info
@settitle Not Yet Another Compiler Compiler

@copying
Copyright (C) 2015-2017 -- Matthew R. Wette.

Permission is granted to copy, distribute and/or modify this document
under the terms of the GNU Free Documentation License, Version 1.3 or
any later version published by the Free Software Foundation; with no
Invariant Sections, no Front-Cover Texts, and no Back-Cover Texts.  A
copy of the license is included with the distribution as @file{COPYING.DOC}.
@end copying

@macro nyacc
@sc{NYACC}
@end macro
@c @alias NYACC = @sc{NYACC}

@clear skip

@dircategory The Algorithmic Language Scheme
@direntry
* NYACC User Guide: (nyacc).    The NYACC user's guide.
@end direntry

@titlepage
@title Not Yet Another Compiler-Compiler
@subtitle A LALR(1) Parser Generator Implemented in Guile
@subtitle DRAFT User's manual for NYACC version 0.79.0
@author Matt Wette
@end titlepage

@ifnottex
@node Top, Demonstration, (dir), (dir)
@top NYACC User's Guide
@end ifnottex

@menu
* Demonstration::
* Parsing::
* Translation::
* Coding to the Compiler Tower::
* Administrative::
* TODOs::
* References::
@end menu

@contents

@node Demonstration,, Parsing, Top
@chapter Demonstration

This document is a ROUGH DRAFT.

A LALR(1) parser is a pushdown automata for parsing computer languages.
In this tool the automata, along with its auxiliary parameters
(e.g., actions), is called a @emph{machine}.  The grammar is called 
the @emph{specification}.  The program that processes, driven by the 
machine, input token to generate a final output, or error, is 
the @emph{parser}.

@section A Simple Batch Calculator

A simplest way to introduce working with @nyacc{} is to work through
an example.  Consider the following contents of the file @file{calc1.scm}
in the distributed directory @code{examples/nyacc/lang/calc/}:
@example
(use-modules (nyacc lalr))
(use-modules (nyacc lex))
(use-modules (nyacc parse))

(define spec
  (lalr-spec
   (prec< (left "+" "-") (left "*" "/"))
   (start expr)
   (grammar
    (expr
     (expr "+" expr ($$ (+ $1 $3)))
     (expr "-" expr ($$ (- $1 $3)))
     (expr "*" expr ($$ (* $1 $3)))
     (expr "/" expr ($$ (/ $1 $3)))
     ($fixed ($$ (string->number $1)))
     ($float ($$ (string->number $1)))
     ("(" expr ")" ($$ $2))))))

(define mach (make-lalr-machine spec))
(define raw-parser (make-lalr-parser mach))
(define gen-lexer (make-lexer-generator (lalr-match-table mach)))

(define (calc1-eval str)
  (with-input-from-string str
    (lambda () (raw-parser (gen-lexer)))))

(define (calc1-demo string)
  (simple-format #t "~A => ~A\n" string (calc1-eval string)))

(calc1-demo "2 + 2")
@end example
Here is an explanation of the above code:
@enumerate
@item
The relevent modules are imported using Guile's @code{use-modules} syntax.
@item
The syntax form @code{lalr-spec} is used to generate a (canonical)
specification from the grammar and options provided in the form.
@item
The @code{prec<} directive indicates that 
the tokens appearing in the sequence of associativity directives
should be interpreted in increasing order of precedence.  The
associativity statements @code{left} indicate that the tokens have left
associativity.  So, in this grammar @code{+}, @code{-}, @code{*}, and
@code{/} are left associative, @code{*} and @code{/} have equal
precedence, @code{+} and @code{-} have equal precedence, but @code{*}
and @code{/} have higher precedence than @code{+} and @code{-}.
@item
The @code{start} directive indicates which left-hand symbol in the
grammar is the starting symbol for the grammar.
@item
The @code{grammar} directive is used to specify the production rules.
@itemize
@item
In the example above one left-hand side is associated with multiple
right hand sides.  But this is not required.
Multiple right-hand sides can be written for a single left-hand side.  
@item
Non-terminals are indicated using symbols (e.g., @code{expr}).
@item
Terminals are indicated using string literals (e.g.,@code{"+"}),
character literals (e.g., @code{#\+}), quoted symbols
(e.g., @code{'+}) or NYACC reserved symbols, which always begin with
@code{$}.  Reserved symbols used in this example are @code{$fixed} and
@code{$float}.   Note that tokens or terminals do not need to be
declared as in Bison or the Guile @code{(system base lalr)} module.
@item
The reserved symbols @code{$fixed} and @code{$float} indicate an
unsigned integer and floating point number, respectively.  The 
@nyacc{} procedures for generating lexical analyzers will emit this token
when the corresponding numbers are detected in the input.
@item
Within the right-hand side of a production rule a @code{$$} form is
used to specify an action associated with the rule.  Ordinarily, the action
appears as the last element of a right-hand side, but mid-rule
actions are possible.  Inside the @code{$$} form, the variables
@code{$1}, @code{$2}, etc.@  refer to the symantic value of the
corresponding item in the right hand side.
@item
The expression returned by @code{lalr-spec} is an association list (a-list);
you can peek at the internals using typical Scheme procedures for a-lists.
@end itemize
@item
The expression comprising the automaton (aka machine) is
generated using the procedure @code{make-lalr-machine}.  This routine
does the bulk of the processing to produce what is needed to generate
a LALR(1) parser.  The result is an association list.
@item
Generating a usable parser procedure requires a few steps.  The first is
to create a raw parser:
@example
(define raw-parser (make-lalr-parser mach)))
@end example
The procedure @code{make-lalr-parser} generates a parser (procedure)
from the machine.  The generated procedure @code{raw-parser} takes one
argument, a lexical analyzer procecdure, and optional keyword arguments.
@item
The next task is to create a generator for lexical analyzers.  This is
performed as follows: 
@example
(define gen-lexer (make-lexer-generator (lalr-match-table mach)))
@end example
We create a generator here because a lexical analyzer may require
internal state (e.g., line number, mode).  The generator is
constructed from the @dfn{match table} provided by the machine.  The
procedure @code{make-lexer-generator} is imported from the module
@code{(nyacc lex)}.  Optional arguments to @code{make-lexer-generator}
allow the user to specify custom readers for identifiers, comments,
numbers, etc.  @xref{lex}
The match table is the handshake between the lexical
analyzer and the parser for encoding tokens.  In this example the
match table is symbol based, but there is an option to hash these
symbols into integers.  @xref{Hashing and Compacting}
@item
We bring the above items together to provide a usable procedure for
evaluating strings:
@example
(define (calc1-eval str)
  (with-input-from-string str
    (lambda () (raw-parser (gen-lexer)))))
@end example
The lexical analyzer reads code from @code{(current-input-port)} so we
set up the environment using @code{with-input-from-string}. 
@xref{Input and Output,,,guile}  The raw parser is provided a lex'er.
@item 
And now we can run it:
@example
(calc1-eval "2 + 2") => 4
@end example
@end enumerate

If we execute the example file above we should get the following:
@example
$ guile calc1.scm
2 + 2 => 4
$
@end example


@section An Interactive Calculator

If one sets up the above code to take input from the terminal it will
not work as expected, requiring keystrokes beyond a RETURN that
completes an expression.  If you replace @code{make-lalr-parser} with
@code{make-lalr-ia-parser} and motify the code a bit, you can get an
interactive parser, as shown below.  This example appears as
@file{calc2.scm} in the same directory as the example above.  (Note:
If you look at the @nyacc{} parse module you will see that the base
parser is quite a bit cleaner than the ia-parser, hence the motivation
to provide both, at least for now.)  Note that this example uses
mid-rule actions and other features not discussed above.

@example
(use-modules (nyacc lalr))
(use-modules (nyacc lex))
(use-modules (nyacc parse))

(define (next) (newline) (display "> ") (force-output))

(define calc2-spec
  (lalr-spec
   (prec< (left "+" "-") (left "*" "/"))
   (start stmt-list)
   (grammar
    (stmt-list
     (stmt)
     (stmt-list stmt))
    (stmt
     (expr ($$ (display $1) (next)) "\n"))
    (expr
     ($empty ($$ ""))
     (expr "+" expr ($$ (+ $1 $3)))
     (expr "-" expr ($$ (- $1 $3)))
     (expr "*" expr ($$ (* $1 $3)))
     (expr "/" expr ($$ (/ $1 $3)))
     ($fixed ($$ (string->number $1)))
     ($float ($$ (string->number $1)))
     ("(" expr ")" ($$ $2))))))

(define calc2-mach (make-lalr-machine calc2-spec))
(define match-table (assq-ref calc2-mach 'mtab))
(define parse (make-lalr-ia-parser calc2-mach))
(define gen-lexer
  (make-lexer-generator match-table #:space-chars " \t"))

(next)
(parse (gen-lexer))
@end example

@section Generating a Language to Run in Guile

One of the many cool features of Guile is that it provides a backend
infrastructure for evaluation of multiple frontend languages.   
The files @file{parser.scm}, @file{compiler.scm} in the
@file{examples/nyacc/lang/calc} directory and @file{spec.scm} in the
@file{examples/language/calc} directory implement our calculator within this
Guile infrastructure.  To demonstrate the calculator try the following
from the @file{examples} directory.
@example
$ guile -L ../module -L .
...
scheme@@(guile-user)> ,L calc
...
Happy hacking with calc!  To switch back, type `,L scheme'.
calc@@(guile-user)> (2 + 2)/(1 + 1)
2
calc@@(guile-user)> 
@end example
The evaluator uses SXML as the intermediate representation between the
parser and compiler, which generates to tree-il.  See also the example
in the directory @file{examples/language/javascript} and
@file{examples/nyacc/lang/javascript} directories.

@section Debugging Output

The parser can provide debugging output with the appropriate keyword
argument.  In @file{calc1.scm} there is a modified version of
@code{calc1-eval} which will print out debugging info:
@example
(define (calc1-eval str)
  (with-input-from-string str
    (lambda () (raw-parser (gen-lexer) #:debug #t))))
@end example
@noindent
To make use of this info you probably want to generate an output file
as describe in Section @ref{Human Readable Output} which provides
context for the debugging output.  The output looks like
@example
state 0, token "2"      => (shift . 3)
state 3, token "+"      => (reduce . 5)
state 0, token expr     => (shift . 4)
state 4, token "+"      => (shift . 5)
state 5, token "2"      => (shift . 3)
state 3, token #<eof>   => (reduce . 5)
state 5, token expr     => (shift . 14)
state 14, token #<eof>  => (reduce . 1)
state 0, token expr     => (shift . 4)
state 4, token #<eof>   => (accept . 0)
2 + 2 => 4
@end example

@c ==================================
@node Parsing
@chapter Parsing

Most of the syntax and procecures for generating skelton parsers
exported from the module @code{(nyacc lalr)}.  Other modules include
@table @code
@item (lalr lex)
This module provides procedures for generating lexical analyzers.
@item (lalr util)
This module provides utilities used by the other modules.
@end table


@section The Specification
@anchor{Specification}

The syntax for generating specifications is @code{lalr-spec}.  As
mentioned in the  previous chapter, the syntax generates an
association list, or @dfn{a-list}. 

@deffn {Syntax} lalr-spec grammar => a-list
This routine reads a grammar in a scheme-like syntax and returns an a-list.
The returned a-list is normally used as an input for
@code{make-lalr-machine}.  The syntax is of the form
@example
(lalr-spec (@var{specifier} @dots{}) @dots{})
@end example
The order of the specifiers does not matter, but typically the
@code{grammar} specifier occurs last.
@end deffn

The specifiers are
@table @code
@item notice
This is used to push a comment string (e.g., copyright) into the
resulting parser tables. 
@item reserve
This is a list of tokens which do not appear in the grammar but should
be added to the match table. 
@item prec<, prec>
These specifiers are used to specify precedence and associativity symbols.
@item expect
This is the expected number of shift-reduce conflicts to occur.
@item start
This specifies the top-level starting non-terminal.
@item alt-start
This specifies alternative start symbols used in @code{restart-spec}.
Its use prevents warning messages.
@item grammar
the grammar see below
@end table

@subheading The Notice

The @code{notice} specifier allows one to provide a comment that will
be carried into generated output files (e.g., parse tables generated
by @code{write-lalr-tables}.  For example, if the spec' looks like
@example
(define spec
  (lalr-spec
   (notice "last edit: Mar 25, 2015")
   @dots{}))
@end example
@noindent
and one generates parse tables from the machine with
@code{write-lalr-tables} then the resulting file will look like
@example
;; calctab.scm

;; last edit: Mar 25, 2015

(define calc-len-v
 #(1 1 @dots{}
 @dots{}
@end example

The notice is available using the expression
@deffn {Procedure} pp-lalr-notice spec [port]
Print the notice to the port, if specified, or @code{(current-output-port)}.
@end deffn

@subheading Reserving Tokens

The @code{notice} specifier allows one to provide a comment that will
be carried into generated output files (e.g., parse tables generated
by @code{write-lalr-tables}.
In the javascript parser we have added reserved keywords:
@example
   (reserve "abstract" "boolean" "byte" "char"
            "class" "const" @dots{})
@end example
@noindent
and this results in a generated match table (for a hashed machine)
that looks like:
@example
    @dots{} ("abstract" . 86) ("boolean" . 87) ("byte" . 88)
    ("char" . 89) ("class" . 90) ("const" . 91) @dots{}
@end example

@subheading Precedence and Associativity

Recall the following specifier from the @code{calc1} example:
@example
   (prec< (left "+" "-") (left "*" "/"))
@end example
@noindent
This declaration indicates presedence among the math operators.
The @code{<} in @code{prec<} indicates that the precedence is in
increasing order.  An equivalent specification would be as follows:
@example
   (prec> (left "*" "/") (left "+" "-"))
@end example

The precedence specification can be used along with @code{$prec} in
the grammer to resolve shift-reduce or reduce-reduce conflicts in a 
grammar.  The classical case is the if-then-else construct in C, where 
a conflict occurs on the input
@example
if (expr1) if (expr2) bar(); else baz();
@end example
@noindent
The above could be interpreted as
@example
if (expr1) @{ if (expr2) bar(); @} else baz();
@end example
@noindent
or as
@example
if (expr1) @{ if (expr2) bar(); else baz(); @}
@end example
@noindent
hence a conflict.  The language specification indicates the latter, so
the parser should shift.  This rule can be specificed in a C parser
as follows:
@example
  (lalr-spec
   @dots{}
   (prec< 'then "else")	       ; "then/else" SR-conflict resolution
   @dots{}
   (grammar
    @dots{}
    (selection-statement
     ("if" "(" expression ")" statement ($prec 'then)
      ($$ `(if ,$3 ,$5)))
     ("if" "(" expression ")" statement "else" statement
      ($$ `(if ,$3 ,$5 ,$7)))
      @dots{}
@end example
@noindent
It is important to note here that we use a quoted symbol @code{'then}
rather than a string @code{"then"} as a dummy token.  If we would have
used @code{"then"} as the dummy then the lex'er would return the associated
token when @code{"then"} appears in the input and the C declaration 
@example
int then(int);
@end example
@noindent
would produce a syntax error.

@subheading Expected Conflicts

There are default rules for handling shift-reduce conflicts.  If you
can live with these it is possible to inhibit the error messages
generated by using the @code{expect} specifier, which takes as
argument the expected number of shift-reduce conflicts:
@example
  (lalr-spec
   (expect 3)
   @dots{}
@end example

@subheading Grammar

The grammer is a list of production rules.  Each production rule take
the form
@example
(@dfn{lhs} (@dfn{rhs1} @dots{}) (@dfn{rhs2} @dots{}) @dots{})
@end example
@noindent
where @dfn{lhs} is the left hand side is a non-termianl represented as
a Scheme identifier.  Each right hand side is a list non-terminals,
terminals, actions or proxies, represented by Scheme
indentifiers, Scheme constants, @code{$$}-expressions or proxy
expressions, respectively.  The terminals can be Scheme strings,
character constants or quoted symbols, but not numbers.  For example,
the following is the production rule for a C99 additive expression:
@example
(add-expr 
 (mul-expr)
 (add-expr "+" mul-expr ($$ `(add ,$1 ,$3)))
 (add-expr "-" mul-expr ($$ `(sub ,$1 ,$3))))
@end example
Here @code{add-expr} and @code{mul-expr}
are non-terminals and @code{"+"}, @code{"-"} are terminals and
@code{($$ `(add ,$1 ,$3))} and @code{($$ `(sub ,$1 ,$3))} are actions.
In the actions @code{$1} refers to the semantic value of the term
@code{add-expr}.

Symbols starting with @code{$} are reserved.  The following symbols
have special meaning:
All symbols starting with @code{$} are reserved.  Unused reserved symbols
will likely not signal an error.  The following reserved symbols are in use:
@table @code
@item $prec
TO BE DOCUMENTED
@item $error
TO BE DOCUMENTED
@item $empty
TO BE DOCUMENTED
@item $ident
This is emitted by the lexical analyzer to indicate an identifier.
@item $fixed
This is emitted by the lexical analyzer to indicate an unsigned integer.
@item $float
This is emitted by the lexical analyzer to indicate an unsigned
floating point number.
@item $string
This is emitted by the lexical analyzer to indicate a string.
@item $code-comm
This is emitted by the lexical analyzer to indicate a comment starting
after code appearing on a line.
@item $lone-comm
This is emitted by the lexical analyzer to indicate a comment starting
on a line without preceeding code.
@item $$, $$-ref, $$/ref
These define an action in the right-hand side of a production.  They
have the forms
@example
($$ @emph{body})
($$-ref 'rule12)
($$/ref 'rule12 @emph{body})
@end example
@noindent
The @code{ref} forms are used to provide references for future use to
support other (non-Scheme) languages, where the parser will be
equipped to execute reduce-actions by reference (e.g. an associative array).
@item $1, $2, ...
These appear as arguments to user-supplied actions and will appear in
the @emph{body} shown above.  The variables reference the symantic
values of right-hand-side symbols of a production rule.  Note that
mid-rule actions count here so
@example
 (lhs (l-expr ($$ (gen-op)) r-expr ($$ (list $2 $1 $3))))
@end example
@noindent
generates a list from the return of @code{(gen-op)} followed by the
semantic value associated with @code{l-expr} and then @code{r-expr}.
@item $?, $*, $+
These are (experimental) macros used for grammar specification.
@example
($? foo bar baz) => ``foo bar baz'' occurs never or once
($* foo bar baz) => ``foo bar baz'' occurs zero or more times
($+ foo bar baz) => ``foo bar baz'' occurs one or more times
@end example
@noindent
However, these have hardcoded actions and are considered to be,
in current form, unattractive for practical use.
@end table

In addition, the following reserved symbols may appear in output files:
@table @code
@item $chlit
??? This is emitted by the lexical analyzer to indicate a character constant.
@item $start
This is used in the machine specification to indicate the production
rule for starting the grammar.
@item $end
This is emitted by the lexical analysis to indicate end of input and
appears in the machine to catch the end of input.
@item $P1, $P2, @dots{}
Symbols of the form @code{$P1}, @code{$P2},... are as symbols for
proxy productions (e.g., for mid-rule actions).  For example, the
production rule
@example
(lhs (ex1 ($$ (gen-x)) ex2 ex3) ($$ (list $1 $2 $3 $4)))
@end example
@noindent
will result in the internal p-rules
@example
(lhs (ex1 $P1 ex2 ex3) ($$ (list $1 $2 $3 $4)))
($P1 ($empty ($$ (gen-x))))
@end example
@item $default
This is used in the generated parser to indicate a default action.
@end table
@c $error

@subheading Recovery from Syntax Errors
@anchor{Recovery from Syntax Errors}

The grammar specification allows the user to handle some syntax
errors.  This allows parsing to continue.  The behavior is similar
to parser generators like @emph{yacc} or @emph{bison}.  The following
production rule-list allows the user to trap an error.
@example
(line
  ("\n")
  (exp "\n")
  ($error "\n"))
@end example
@noindent
If the current input token does not match the grammar, then the parser
will skip input tokens until a @code{"\n"} is read.  The default
behavior is to generate an error message: @emph{"syntax error"}.
To provide a user-defined handler just add an action for the rule:
@example
(line
  ("\n")
  (exp "\n")
  ($error "\n" ($$ (format #t "line error\n"))))
@end example
@noindent
Note that if the action is not at the end of the rule then the default
recovery action (@emph{"syntax error"}) will be executed.

@section Parsing a Sublanguage of a Specification
@anchor{sublanguage}

Say you have a @nyacc{} specification @code{cspec} for the C language
and you want to generate a machine for parsing C expressions.  You can
do this using @code{restart-spec}:
@example
(define cxspec (restart-spec cspec 'expression))
(define cxmach (make-lalr-machine cxspec))
@end example

@section Generating the Machine
@anchor{Parser}

@deffn {Procedure} make-lalr-machine spec => a-list
Given a specification generated by @code{lalr-spec} this procecure
generates an a-list which contains the data required to implement a
parser generated with, for example, @code{make-lalr-parser}.
@end deffn

The generated a-list includes the following keys:
@table @code
@item pat-v
a vector of parse action procecures
@item ref-v
a vector of parse action references (for supporting other languages)
@item len-v
a vector of p-rule lengths
@item rto-v
a vector of lhs symbols (``reduce to'' symbols)
@item lhs-v
a vector of left hand side symbols
@item rhs-v
a vector of vectors of right hand side symbols
@item kis-v
a vector of itemsets
@end table

@subheading Using Hashed Tables

The lexical analyzer will generate tokens.  The parser generates state
transitions based on these tokens.  When we build a lexical analyzer
(via @code{make-lexer}) we provide a list of strings to detect along with
associated tokens to return to the parser.  By default the tokens returned
are symbols or characters.  But these could as well be integers.  Also,
the parser uses symbols to represent non-terminals, which are also used
to trigger state transitions.  We could use integers instead of symbols
and characters by mapping via a hash table.   We will bla bla bla.
There are also standard tokens we need to worry about.  These are
@enumerate
@item the @code{$end} marker
@item identifiers (using the symbolic token @code{$ident}
@item non-negative integers (using the symbolic token @code{$fixed})
@item non-negative floats (using the symbolic token @code{$float})
@item @code{$default} => 0
@end enumerate
And action
@enumerate
@item positive => shift
@item negative => reduce
@item zero => accept
@end enumerate
However, if these are used they should appear in the spec's terminal list.
For the hash table we use positive integers for terminals and negative
integers for non-terminals.  To apply such a hash table we need to:
@enumerate
@item from the spec's list of terminals (aka tokens), generate a list of
terminal to integer pairs (and vice versa)
@item from the spec's list of non-terminals generate a list of symbols
to integers and vice versa.
@item Go through the parser-action table and convert symbols and characters
to integers
@item Go through the XXX list passed to the lexical analyizer and replace
symbols and characters with integers.
@end enumerate
One issue we need to deal with is separating out the identifier-like
terminals (aka keywords) from those that are not identifier-like.  I guess
this should be done as part of @code{make-lexer}, by filtering the token
list through the ident-reader.
NOTE: The parser is hardcoded to assume that the phony token for the
default (reduce) action is @code{'$default} for unhashed machine or
@code{-1} for a hashed machine.

@deffn {Procedure} hashify-machine mach => mach
Convert machine to use integers instead of symbols.  The match table
will change from
@example
("abc" . 'abc)
@end example
@noindent
to
@example
("abc" . 2)
@end example
@noindent
and the pax will change from
@example
("abc" . (reduce . 1))
@end example
@noindent
to
@example
("abc" . 2)
@end example
@end deffn

@deffn {Procedure} machine-hashed? mach => #t|#f
Indicate if the machine has been hashed.
@end deffn

@subheading Compacting Machine Tables

@deffn {Procedure} compact-machine mach [#:keep 3] [#:keepers '()] => mach
A "filter" to compact the parse table.  For each state this will replace
the most populus set of reductions of the same production rule with a
default production.  However, reductions triggered by user-specified keepers
and the default keepers -- @code{'$error}, @code{'$end}, @code{'$lone-comm}
and @code{'$lone-comm} are not counted.  The parser will want to treat
errors and comments separately so that they can be trapped (e.g.,
unaccounted comments are skipped).
@end deffn


@section The Match Table
@anchor{match table}

In some parser generators one declares terminals in the grammar file
and the generator will provide an include file providing the list of
terminals along with the associated ``hash codes''.  In @nyacc{} the
terminals are detected in the grammar as non-identifiers: strings
(e.g., @code{"for"}), symbols (e.g., @code{'$ident}) or characters
(e.g., @code{#\+}).   The machine generation phase of the parser 
generates a match table which is an a-list of these objects along with
the token code.  These codes are what the lexical analyzer should return.
BLA Bla bla.  So in the end we have
@itemize
@item
The user specifies the grammar with terminals in natural form
(e.g., @code{"for"}).
@item
The parser generator internalizes these to symbols or integers, and generates
an a-list, the match table,  of (natural form, internal form).
@item
The programmer provides the match table to the procedure that builds 
a lexical analyzer generator (e.g., @code{make-lexer-generator}).
@item
The lexical analyzer uses this table to associate strings in the input
with entries in the match table.   In the case of keywords the keys will
appear as strings (e.g., @code{for}), whereas in the case of special items,
processed in the lexical analyzer by readers (e.g., @code{read-num}), the
keys will be symbols (e.g., @code{'$float}).
@item
The lexical analyzer returns pairs in the form (internal form, natural form)
to the parser.  Note the reflexive behavior of the lexical analyzer.  It
was built with pairs of the form (natural form, internal form) and returns
pairs of the form (internal form, natural form).
@end itemize

Now one item need to be dealt with and that is the token value for the 
default.  It should be @code{-1} or @code{'$default}. WORK ON THIS.

@section Constructing Lexical Analyzers
@anchor{lex}

The @code{lex} module provides a set of procedures to build lexical
analyzers.  The approach is to first build a set of @dfn{readers} for 
different types of tokens (e.g., numbers, identifiers, character
sequences) and then process input characters (or code points) through
the procedures.  The signature of most readers is the following:
@example
(reader ch) => #f | (@emph{type} . @emph{value})
@end example
@noindent
If the reader fails to read a token then @code{#f} is returned.  If
the reader reads more characters from input and fails, then it will
push back characters.  So, the basic structure of a lexical analyzer
is
@example
(lambda ()
  (let iter ((ch (get-char)))
    (cond
     ((eof-object? ch) '($end . ""))
     ((whitespace-reader ch) (iter (read-char)))
     ((comment-reader ch) (iter (read-char)))
     ((number-reader ch))
     ((keyword-reader ch))
     ((ident-reader ch))
     @dots{}
     (else (error)))))
@end example
@noindent
The types of readers used are
@table @asis
@item ident-reader
reads an identifier
@item num-reader
reads a number
@item string-reader
reads a string literal
@item chlit-reader
reads a character literal
@item comm-reader
reads a comment
@item comm-skipper
same as comm-reader
@item chseq-reader
a reader for a sequence of characters (e.g., @code{+=})
@end table
Note that some of our parsers (e.g., the C99 parser) is crafted to
keep some comments in the output syntax tree.  So comments may be
passed to the parser or skipped, hence the ``skipper''.

The Lex Module does not provide lexical analyzers (lex'ers), but
lexical analyzer generator generators.  The rationale behind this is as
follows.  A lexical analyzer may have state (e.g., beginning of line
state for languages where newline is not whitespace).  In addition,
our generator uses a default set of readers, but allows the caller to
specify other readers.  Or, if the user prefers, lex'ers can be rolled
from provided readers.  Now we introduce our lex'er generator generator:

@deffn {Procedure} make-lexer-generator match-table [options] => generator
Returns a lex'er generator from the match table and options.  The
options are
@table @code
@item #:ident-reader reader
Use the provided reader for reading identifiers.  The default is a C
language ident reader, generated from
@example
(make-ident-reader c:if c:ir)
@end example
@item #:num-reader @var{reader}
Use the provided number reader.
@item #:string-reader @var{reader}
Use the provided reader for string literals.
@item #:chlit-reader @var{reader}
Use the provide charater literal reader.  The default is for C. So,
for example the letter `a' is represented as @code{'a'}.
@item #:comm-reader @var{reader}
Use the provided comment reader to pass comments to the parser.
@item #:comm-skipper @var{reader}
Use the provided comment reader, but throw the token away.  The
default for this is @code{#f}.
@item space-chars @var{string}
not a reader but a string containing the whitespace characters (fix this)
@end table
@example
(define gen-lexer (make-lexer-generator #:ident-reader my-id-rdr))
(with-input-from-file "foo" (parse (gen-lexer)))
@end example
(Minor note: The @var{ident-reader} will be used to read ident-like
keywords from the match table.)
@end deffn

@deffn {Procedure} make-space-skipper chset => proc
This routine will generate a reader to skip whitespace.
@end deffn

@deffn {Procedure} skip-c-space ch => #f|#t
If @code{ch} is C whitespace, skip all spaces, then return @code{#t},
else return @code{#f}.
@end deffn

@deffn {Procedure} make-ident-reader cs-first cs-rest => ch -> #f|string
For identifiers, given the char-set for first character and the char-set
for following characters, return a return a reader for identifiers.
The reader takes a character as input and returns @code{#f} or @code{string}.
This will generate exception on @code{#<eof>}.
@end deffn

@deffn {Procedure} read-c-ident ch => #f|string
If ident pointer at following char, else (if #f) ch still last-read.
@end deffn

@deffn {Procedure} make-ident-like-p ident-reader
Generate a predicate, from a reader, that determines if a string qualifies
as an identifier.
@end deffn

@deffn {Procedure} like-c-ident? ch 
Determine if a string qualifies as a C identifier.
@end deffn

@deffn {Procedure} make-string-reader delim
Generate a reader that uses @code{delim} as delimiter for strings.
TODO: need to handle matlab-type strings.
TODO: need to handle multiple delim's (like python)
@end deffn

@deffn {Procedure} read-oct ch => "0123"|#f
Read octal number.
@end deffn

@deffn {Procedure} read-hex ch => "0x7f"|#f
Read octal number.
@end deffn

@deffn {Procedure} read-c-string ch => ($string . "foo")
Read a C-code string.  Output to code is @code{write} not @code{display}.
Return #f if @var{ch} is not @code{"}. This reader does not yet read
trigraphs.
@end deffn

@deffn {Procedure} make-chlit-reader
Generate a reader for character literals. NOT DONE.
For C, this reads @code{'c'} or @code{'\n'}.
@end deffn

@deffn {Procedure} read-c-chlit ch
@example
... 'c' ... => (read-c-chlit #\') => '($ch-lit . #\c)
@end example
@end deffn

@deffn {Procedure} make-num-reader => (proc ch) => output
Generates a procedure to read C numbers where @var{output} is of the form 
@code{#f}, @code{($fixed . "1")} or @code{($float . "1.0")}
This routine will clean up floats by adding "0" before or after dot.
@end deffn

@deffn {Procedure} cnumstr->scm C99-str => scm-str
Convert C number-string (e.g, @code{0x123LL}) to Scheme numbers-string
(e.g., @code{#x123}).
@end deffn

@deffn {Procedure} read-c-num ch => #f|string
Reader for unsigned numbers as used in C (or close to it).
@end deffn

@deffn {Procedure} make-chseq-reader strtab
Given alist of pairs (string, token) return a function that eats chars
until (token . string) is returned or @code{#f} if no match is found.
@end deffn

@deffn {Procedure} make-comm-reader comm-table [#:eat-newline #t] => \
  ch bol -> ('$code-comm "..")|('$lone-comm "..")|#f
comm-table is list of cons for (start . end) comment.
e.g. ("--" . "\n") ("/*" . "*/")
test with "/* hello **/"
If @code{eat-newline} is specified as true then for read comments 
ending with a newline a newline swallowed with the comment.
Note: assumes backslash is never part of the end
@end deffn

@subsubheading Rolling Your Own Lex'er

The following routines are provided for rolling your own lexical
analyzer generator.  An example is provided in the file
@file{examples/nyacc/lang/matlab}.

@deffn {Procedure} filter-mt p? al => al
Filter match-table based on cars of al.
@end deffn

@deffn {Procedure} remove-mt p? al => al
Remove match-table based on cars of al.
@end deffn

@deffn {Procedure} map-mt f al => al
Map cars of al.
@end deffn

@deffn {Procedure} eval-reader reader string => result
For test and debug, this procedure will evaluate a reader on a string.
A reader is a procedure that accepts a single character argument intended
to match a specific character sequence.  A reader will read more characters
by evaluating @code{read-char} until it matches or fails.  If it fails, it
will pushback all characters read via @code{read-char} and return @code{#f}.
If it succeeds the input pointer will be at the position following the
last matched character.
@end deffn


@section The Parser-Lex'er Interface
@anchor{parser-lexer}

Sometimes LALR(1) parsers must be equipped with methods to parse
non-context free grammars.  With respect to typenames, C is not
context free.  Consider the following example.
@example
typedef int foo_t;
foo_t x;
@end example
@noindent
The lexical analyzer must identify the first occurance of @code{foo_t}
as an identifier and the second occurance of @code{foo_t} as a
typename.  This can be accomplished by keeping a list of typenames in
the parent environment to the parser and lexical analyzer.  In the
parser, when the first statement is parsed, an action could declare
@code{foo_t} to now be a typename.  In the lexical analyzer, as
tokens that look like identifers are parsed they are checked against
the list of typenames and if a match is found, @code{'typename} is
returned, otherwise @code{$ident} is returned.

Another example of this handshaking is used in the JavaScript parser.
The language allows newline as a statement terminator, but it must
be prevented in certain places, for example between @code{++} and
an expression in the post-increment operator.  We handle this using
a mid-rule action to tell the lexer to skip newline if that is the
next token.
@example
  (LeftHandSideExpression ($$ (NSI)) "++" ($$ `(post-inc $1)))
@end example
@noindent
The procedure @code{NSI} in the lex'er is as follows:
@example
(define (NSI) ;; no semicolon insertion
  (fluid-set! *insert-semi* #f))
@end example
@noindent
and the newline reader in the lex'er acts as follows:
@example
  @dots{}
  ((eqv? ch #\newline)
   (if (fluid-ref *insert-semi*)
       (cons semicolon ";")
       (iter (read-char))))
  @dots{}
@end example

@section Parser Tables
@anchor{Parser Tables}


Note that generating a parser requires a machine argument.  It is
possible to export the machine to a pair of files and later regenerate
enough info to create a parser from the tables saved in the machine.

For example, Tables can be generated 
@example
(write-lalr-actions calc1-mach "calc1-act.scm")
(write-lalr-tables calc1-mach "calc1-tab.scm")
@end example
This saves the variable @code{act-v} to the file @file{calc1-act.scm}
and the following variables to the file @file{calc1-tab.scm}:
@table @code
@item len-v
@item pat-v
@item rto-v
@item mtab
@end table
The variable @code{act-v} is a vector of procedures associated with
each of the production rules, to be executed as the associated
production ruled is reduced in parsing.

Then, without reference to the original specification or need to
run @code{make-lalr-machine}, you can ...
@example
(include "calc1-tab.scm")
... code for parser ...
(include "calc1-act.scm")
@end example

Check some of the examples in the @nyacc{} distribution.

@section Hashing and Compacting
@anchor{Hashing and Compacting}

The procedure @code{compact-machine} will compact the parse tables.
That is, if multiple tokens generate the same transition, then these
will be combined into a single @emph{default} transition.
Ordinarily @nyacc{} will expect symbols to be emitted from the lexical
analyzer.  To use integers instead, use the procedure
@code{hashify-machine}.  One can, of course, use both procedures:
@example
(define calc-mach
  (compact-machine
   (hashify-machine
     (make-lalr-machine calc-spec))))
@end example

@deffn {Procedure} machine-compacted? mach => #t|#f
Indicate if the machine has been compacted.
@end deffn

     
@section Exporting Parsers
@nyacc{} provides routines for exporting @nyacc{} grammar
specifications to other LALR parser generators.

The Bison exporter uses the following rules:
@itemize
@item
Terminals expressed as strings which look like C identifiers are
converted to symbols of all capitals.  For example @code{"for"} is
converted to @code{FOR}.
@item
Strings which are not like C identifiers and are of length 1 are
converted to characters.  For example, @code{"+"} is converted to @code{'+'}.
@item
Characters are converted to C characters.
For example, @code{#\!} is converted to @code{'!'}.
@item
Multi-character strings that do not look like identifiers are
converted to symbols of the form @code{ChSeq_@i{i}_@i{j}_@i{k}} where
@i{i}, @i{j} and @i{k} are decimal representations of the character
code.  For example @code{"+="} is converted to @code{ChSeq_43_61}.
@item
Terminals expressed as symbols are converted as-is but @code{$} and @code{-}
are replaced with @code{_}.
@end itemize

TODO: Export to Bison xml format.

The Guile exporter uses the following rules: TBD.

@section Debugging
@anchor {Debugging}

The provided parsers are able to generate debugging information.

@subheading Human Readable Output
@anchor{Human Readable Output}

You can generate text files which provide human-readable forms of
the grammar specification and resulting automaton, akin to what you
might get with bison using the `-r' flag.
@example
(with-output-to-file "calc1.out"
  (lambda ()
    (pp-lalr-grammar calc1-mach)
    (pp-lalr-machine calc1-mach)))
@end example

The above code will generate something that looks like 
@example
0 $start => stmt-list
1 stmt-list =>
2 stmt-list => stmt-list $P1 stmt
3 $P1 =>
4 stmt => "\n"
5 stmt => expr "\n"
6 expr => expr "+" expr
7 expr => expr "-" expr
8 expr => expr "*" expr
9 expr => expr "/" expr
10 expr => "*" '$error
11 expr => '$fixed
12 expr => '$float
13 expr => "(" expr ")"

0:      $start => . stmt-list
        stmt-list => .
        stmt-list => . stmt-list $P1 stmt
                stmt-list => shift 1
                '$end => reduce 1
                "(" => reduce 1
                '$float => reduce 1
                '$fixed => reduce 1
                "*" => reduce 1
                "\n" => reduce 1

1:      stmt-list => stmt-list . $P1 stmt
        $P1 => .
        $start => stmt-list .
                $P1 => shift 2
                "(" => reduce 3
                '$float => reduce 3
                '$fixed => reduce 3
                "*" => reduce 3
                "\n" => reduce 3
                '$end => accept 0

...

21:     expr => expr . "/" expr
        expr => expr . "*" expr
        expr => expr . "-" expr
        expr => expr . "+" expr
        expr => expr "+" expr .
                "+" => reduce 6
                "-" => reduce 6
                "*" => shift 13
                "/" => shift 14
                "\n" => reduce 6
                ")" => reduce 6
                ["+" => shift 11] REMOVED by associativity
                ["-" => shift 12] REMOVED by associativity
                ["*" => reduce 6] REMOVED by precedence
                ["/" => reduce 6] REMOVED by precedence
@end example

@c ==================================
@node Translation
@chapter Translation

In this chapter we present procedures for generating syntax trees in a
uniform form.  This format, based on SXML, may use more cons cells
than other formats but upon use you will see that it is easy to
produce code in the parser, and one can use all the processing tools
that have been written for SXML (e.g., @code{(sxml match)} @code{(sxml
fold)}. 

The syntax of SXML trees is simple:
@example
expr => (tag item @dots{}) | (tag (@@ attr @dots{}) item @dots{})
item => string | expr
attr => (tag . string)
@end example
@noindent
where tag names cannot contain the characters
@quotation
@code{(} @code{)} @code{"} @code{'} @code{`} @code{,} @code{;}
@code{?} @code{>} @code{<} @code{[} @code{]} @code{~} @code{=}
@code{!} @code{#} @code{$} @code{%} @code{&} @code{*} @code{+}
@code{/} @code{\} @code{@@} @code{^} @code{|} @code{@{} @code{@}}
@end quotation
@noindent
and cannot begin with @code{-}, @code{.} or a numeric digit.

For example our Javascript parser given the input
@example
function foo(x, y) @{
  return x + y;
@}
@end example
@noindent
will produce the following syntax tree:
@example
(Program
  (SourceElements
    (FunctionDeclaration
      (Identifier "foo")
      (FormalParameterList
        (Identifier "x")
        (Identifier "y"))
      (SourceElements
        (EmptyStatement)
        (ReturnStatement
          (add (PrimaryExpression (Identifier "x"))
               (PrimaryExpression (Identifier "y"))))
        (EmptyStatement)))
    (EmptyStatement)))
@end example
@noindent
And by the way, put through our tree-il compiler, which uses
@code{foldts*-values} from the module @code{(sxml fold)} we get
@example
(begin
  (define foo
    (lambda ((name . foo))
      (lambda-case
        ((() #f @@args #f () (JS~5575))
         (prompt
           (const return)
           (begin
             (abort (const return)
                    ((apply (@@@@ (nyacc lang javascript jslib) JS:+)
                            (apply (toplevel list-ref)
                                   (lexical @@args JS~5575)
                                   (const 0))
                            (apply (toplevel list-ref)
                                   (lexical @@args JS~5575)
                                   (const 1))))
                    (const ())))
           (lambda-case
             (((tag val) #f #f #f () (JS~5576 JS~5577))
              (lexical val JS~5577)))))))))
@end example

@c attributed grammars

@section Tagged Lists
@anchor{Tagged Lists}

Paring actions in @nyacc{} can use tagged-lists from the module
@code{(nyacc lang util)} to help build SXML trees efficiently.
Building a statement list for a program might go as follows:
@example
  (program
   (stmt-list ($$ `(program ,(tl->list $1)))))
  (stmt-list
   (stmt ($$ (make-tl 'stmt-list $1)))
   (stmt-list stmt ($$ (tl-append $1 $2))))
@end example
@noindent
The sequence of calls to the @code{tl-} routines goes as follows:
@table @code
@item (make-tl 'stmt-list)
Generate a tagged list with tag @code{'stmt-list}.
@item (tl-append $1 $2)
Append item @code{$2} (not a list) to the tagged-list @code{$1}.
@item (tl->list $1)
Convert the tagged-list @code{$1} to a list.  It will be of the form
@example
'(stmt-list (@emph{stmt} @dots{}) (@emph{stmt} @dots{}) @dots{})
@end example
@noindent
The first element of the
list will be the tag @code{'stmt-list}.  If attributes were added, the
list of attributes will be the second element of the list.  
@end table

The following procedures are provided by the module @code{(nyacc lang util)}:

@deffn {Procedure} make-tl tag [item item ...]
Create a tagged-list structure for tag @var{tag}.  Any number of
additional items can be added.
@end deffn

@deffn {Procedure} tl->list tl
Convert a tagged list structure to a list.  This collects added attributes
and puts them right after the (leading) tag, resulting in something like
@example
(<tag> (@@ <attr>) <item> @dots{})
@end example
@end deffn

@deffn {Procedure} tl-insert tl item
Insert item at front of tagged list (but after tag).
@end deffn

@deffn {Procedure} tl-append tl item ...
Append items at end of tagged list.
@end deffn

@deffn {Procedure} tl-extend tl item-l
Extend with a list of items.
@end deffn

@deffn {Procedure} tl-extend! tl item-l
Extend with a list of items.  Uses @code{set-cdr!}.
@end deffn

@deffn {Procedure} tl+attr tl key val)
Add an attribute to a tagged list.  Return the tl.
@example
(tl+attr tl 'type "int")
@end example
@end deffn

@deffn {Procedure} tl-merge tl tl1
Merge guts of phony-tl @code{tl1} into @code{tl}.
@end deffn


@section Working with SXML Based Parse Trees
@anchor{SXML Parse Trees}

To work with the trees described in the last section use
@example
(sx-ref tree 1)
(sx-attr tree)
(sx-attr-ref tree 'item)
(sx-tail tree 2)
@end example

@deffn {Procedure} sx-ref sx ix => item
Reference the @code{ix}-th element of the list, not counting the optional
attributes item.  If the list is shorter than the index, return @code{#f}.
@example
(sx-ref '(abc "def") 1) => "def"
(sx-ref '(abc (@@ (foo "1")) "def") 1) => "def"
@end example
@end deffn

@deffn {Procedure} sx-tag sx => tag
Return the tag for a tree
@end deffn

@deffn {Procedure} sx-cons* tag (attr|#f)? ... => sx
@deffnx {Procedure} sx-list tag (attr|#f)? ... => sx
Generate the tag and the attr list if it exists.  Note that
@end deffn

@deffn {Procedure} sx-tail sx [ix] => (list)
Return the ix-th tail starting after the tag and attribut list, where
@var{ix} must be positive.  For example,
@example
(sx-tail '(tag (@@ (abc . "123")) (foo) (bar)) 1) => ((foo) (bar))
@end example
Without second argument @var{ix} is 1.
@end deffn

@deffn {Procedure} sx-has-attr? sx
A predicate to determine if @var{sx} has attributes.
@end deffn

@deffn {Procedure} sx-attr sx => '(@@ ...)|#f
@example
(sx-attr '(abc (@@ (foo "1")) def) 1) => '(@@ (foo "1"))
@end example
should change this to
@example
(sx-attr sx) => '((a . 1) (b . 2) ...)
@end example
@end deffn

@deffn {Procedure} sx-attr-ref sx key => val
Return an attribute value given the key, or @code{#f}.
@end deffn

@deffn {Procedure} sx-set-attr! sx key val
Set attribute for sx.  If no attributes exist, if key does not exist,
add it, if it does exist, replace it.
@end deffn

@deffn {Procedure} sx-set-attr* sx key val [key val [key ... ]]
Generate sx with added or changed attributes.
@end deffn

@deffn {Procedure} sx+attr* sx key val [key val [@dots{} ]] => sx
Add key-val pairs. @var{key} must be a symbol and @var{val} must be
a string.  Return a new @emph{sx}.
@end deffn

@deffn {Procedure} sx-find tag sx => ((tag ...) (tag ...))
Find the first matching element (in the first level).
@end deffn

This illustrates translation with @code{foldts*-values} and
@code{sxml-match}.

@node Coding to the Compiler Tower
@chapter Coding to the Compiler Tower

@example
(define-module (language javascript spec)
  #:export (javascript)
  #:use-module (nyacc lang javascript separser)
  #:use-module (nyacc lang javascript compile-tree-il)
  #:use-module (nyacc lang javascript pprint)
  #:use-module (system base language))

(define-language javascript
  #:title       "javascript"
  #:reader      js-reader
  #:compilers   `((tree-il . ,compile-tree-il))
  #:printer     pretty-print-js)
@end example

@example
(define-module (nyacc lang javascript compile-tree-il)
  #:export (compile-tree-il)
  #:use-module (nyacc lang javascript jslib)
  #:use-module ((sxml match) #:select (sxml-match))
  #:use-module ((sxml fold) #:select (foldts*-values))
  #:use-module ((srfi srfi-1) #:select (fold))
  #:use-module (language tree-il))

@dots{}

(define (compile-tree-il exp env opts)
  (let* ((xrep (js-sxml->tree-il-ext exp env opts))
         (code (parse-tree-il xrep)))
    (values code env env)))
@end example

@section Pretty Print
@anchor{Pretty Print}

@deffn {Procedure} make-pp-formatter [port] [#:per-line-prefix ""] => fmtr
@example
(fmtr 'push) ;; push indent level
(fmtr 'pop)  ;; pop indent level
(fmtr "fmt" arg1 arg2 ...)
@end example
@end deffn



@node Administrative
@chapter Administrative Notes

@section Installation
Installation instructions are included in the top-level file
@file{INSTALL} of the source distribution.  If you have an installed
Guile then the basic steps are
@example
$ ./configure
$ make install
@end example
@noindent
Help with alternative usage is available with
@example
$ ./configure --help
@end example
@noindent
If Guile is not installed it is possible to install source only:
@example
$ ./configure --site-scm-dir=/path/to/dest --site-scm-go-dir=/dummy
$ make install-srcs
@end example

@section Reporting Bugs
Please report bugs to the support site
@indicateurl{https://savannah.nongnu.org/support/?group=nyacc} or to
the Guile user's mailing list @email{guile-user@@gnu.org}.

@section The Free Documentation License
The Free Documentation License is included in the Guile Reference
Manual.  It is included with the @nyacc{} source as the file 
@file{COPYING.DOC}.

@node TODOs
@chapter TODOs, Notes, Ideas
Todo/Notes/Ideas:
@table @asis
@item 16
add error handling (lalr-spec will now return #f for fatal error)
@item 3
support other target languages:
(write-lalr-parser pgen "foo.py" #:lang 'python)
@item 6
export functions to allow user to control the flow
i.e., something like: (parse-1 state) => state
@item 9
macros - gotta be scheme macros but how to deal with other stuff
@example
(macro ($? val ...) () (val ...))
(macro ($* val ...) () (_ val ...))
(macro ($+ val ...) (val ...) (_ val ...))
@end example
@item 10
support semantic forms: (1) attribute grammars, (2) translational
semantics, (3) operational semantics, (4) denotational semantics
@item 13
add ($abort) and ($accept)
@item 19
add a location stack to the parser/lexer
@item 26
Fix lexical analyzer to return tval, sval pairs using @code{cons-source} 
instead of @code{cons}.  This will then allow support of location info.
@end table


@node References
@chapter References

@table @asis
@item [DB]
Aho, A.V., Sethi, R., and Ullman, J. D., ``Compilers: Principles,
Techniques and Tools,'' Addison-Wesley, 1985 (aka the Dragon Book)
@item [DP]
DeRemer, F., and Pennello, T., ``Efficient Computation of LALR(1)
Look-Ahead Sets.'' ACM Trans. Prog. Lang. and Systems, Vol. 4, No. 4.,
Oct. 1982, pp. 615-649.
@item [RPC]
R. P. Corbett, ``Static Semantics and Compiler Error Recovery,''
Ph.D. Thesis, UC Berkeley, 1985.
@end table


@c Old Stuff, to be removed
@ifset skip
In the DB an item is used to refer to the position in a production and
the position with associated lookaheads that give the possible set of
terminals that can generate a reduction when the item is a candidate for
reduction (i.e., the dot appears at the end of the p-rule). In this
report we use the terms @emph{item} for the position and @emph{la-item}
for the position and associated lookaheads.  An example of an la-item
is as follows:
@example
A => B . C D, e/f/g
@end example
@noindent
where @code{e/f/g} is a tuple of terminals which can appear at
@example
A => B C D ., e/f/g
@end example
@noindent
We denote an item in the code using a cons with the index of the p-rule
in the car and the index of the right-hand side symbol after the dot
in the cdr.  The end of p-rule will be denoted with index @code{-1}.
So if the rule @samp{A=>BCD} appears as index 7, then the above would
be item @code{(7 . 1)} or la-item @code{((7 . 1) e f g)}.
@end ifset

@bye
@c --- last line
