_parser-tools_ 

This documentation assumes familiarity with lex and yacc style lexer
and parser generators.


CHANGE: The lexer generator uses a new back-end based on derivatives
(``Derivatives of Regular Expressions'',
 Janusz A. Brzozowski, JACM, Vol 11, No. 4 (October 1964))
and can now support intersection and negation of arbitrary regular
expressions.  For example, (@ "/*" (~ (@ (&) "*/" (&))) "*/") matches a 
Java comment.

I was expecting the Brzozowski algorithm to generate tables more slowly
than the previous algorithm from the Dragon book (direct re to dfa
translation) and was pleasantly surprised to find it both faster and
more flexible.  Generating the lex table for the Scheme lexer in
collects/syntax-color/scheme-lexer.ss yielded the following comparison
(this particular lexer doesn't use negation or intersection yet) on an
800MHZ Pentium 3:
Dragon book algorithm: 1191 states, 13.86 seconds, .0116 seconds per state
Brzozowski algorithm: 464 states, 5.695 seconds, .0122 seconds per state

For the Java lexer (get-token) in collects/profj/parsers/lexer.ss:
Dragon book algorithm: 268 states, 1.28 seconds, .0048 seconds per state
Brzozowski algorithm: 220 states, 1.34 seconds, .0061 seconds per state

Furthermore, the Brzozowski algorithm is more suited to functional
programming, so the dfa generation code is much more pleasant.


CHANGE: (eof) is no longer treated as a character, but as a 
 special.  This means that (eof) cannot appear except as the
 whole regular expression in a lex rule.

_lex.ss_
A regular expression is one of the following:
 symbol                    expands the lex abbreviation whose name 
                             is symbol
 character                 matches the given character
 string                    matches its sequence of characters
 (epsilon)                 matches the empty string
 (* re)                    matches the sub-expession 0 or more times
 (+ re)                    matches the sub-expression 1 or more times
 (? re)                    matches the sub-expression 0 or 1 times
 (: re ...)                matches one of the sub-expressions
 (& re ...)                matches all of the sub-expressions
 (~ re)                    matches any string that the sub-expression does not match
 (@ re ...)                matches each sub-expression in succession
 (- char char)             matches any character between the two (inclusive)
                             (A single character string can be used here)
 (^ char_or_range ...)     matches any character not listed                               

 (The empty concatenation, `(@), and "" both match the empty string.
  The empty or, `(:), matches nothing.
  The empty carat, `(^), matches any single character.
  The empty and, `(&), matches any string.)

 To denote all strings, use (&) instead of something like (* (^)).  The
 dfa conversion understands the former idiom and will often create smaller
 dfas in the first case.
  
Since negation is not a common operator on regular expressions, here are a 
few examples:

(~ "1") matches all strings except the string "1".
          This includes "11", "111", "0", "01", "" and so on.

(~ (* "1")) matches all strings that are not sequences of "1".
              "0", "00", "11110", "0111", "11001010" and so on.

From Brzozowski's paper: (& (@ (&) "111" (&)) 
                            (~ (: (@ (&) "01") (+ "1"))))
  matches all strings that have 3 consecutive ones, but not those that end in 
  "01" and not those that are ones only.  These include:
  "1110", "0001000111" and "0111" but not "", "11", "11101", "111" and "11111".

(@ "/*" (~ (@ (&) "*/" (&))) "*/") matches Java/C block comments.
 "/**/", "/******/", "/*////*/", "/*asg4*/" and so on.  It does not
 match "/**/*/", "/*  */   */" and so on.
 (@ (&) "*/" (&)) matches any string that has a "*/" in is, so (~ (@ (&)
 "*/" (&))) matches any string without a "*/" in it.

(@ "/*" (* (~ "*/")) "*/") : matches any string that starts with "/*"
 and and ends with "*/", including "/* */ */ */".  (~ "*/") matches any
 string that except "*/".  This includes "*" and "/" separately.  Thus
 (* (~ "*/")) matches "*/" by first matching "*" and then matching "/".
 Any other string is matched directly by (~ "*/").  In other words,
 (* (~ "xx")) = (&).  It is usually not correct to place a * around a ~.


To use the _lexer generator_ you must (require (lib "lex.ss" "parser-tools")).
This gives you the following syntactic forms:

> (define-lex-abbrev name re) which associates a regular expression
   with a name to be used in other regular expressions with the
   (symbol) form.  The definition of name has the same scoping
   properties as a normal mzscheme macro definition.  In particular a
   (define-syntax name ...) could interfere.

> (define-lex-abbrevs [name re] ...) defines several lex-abbrevs

> (lexer (re action) ...) expands into a function that takes an
   input-port, matches the re's against the buffer and returns the
   result of executing the corresponding action.  Each action is
   scheme code that has the same scope as its lexer definition, except
   that the variables start-pos, end-pos, lexeme,
   return-without-pos and input-port are also bound in the action
   (hiding any outside binding).
>   start-pos - a position struct for the first character matched
>   end-pos - a position struct for the character after the last
      character in the match
>   lexeme - the matched string
>   input-port - the input-port being processed (this is useful for
      matching input with multiple lexers, see example below)
>   (return-without-pos x) is a function (continuation) that
     immediately returns the value of x from the lexer.  This useful
     in a src-pos lexer to prevent the lexer from adding source
     information.  For example:
     (define get-token
       (lexer-src-pos
       ...
       ((comment) (get-token input-port))
       ...))
     would wrap the source location information for the comment around
     the value of the recursive call.  Using
     ((comment) (return-without-pos (get-token input-port))) 
     will cause the value of the recursive call to be returned without
     wrapping position around it.

   The lexer will raise an exception (exn:read) if none of the regular
   expressions match the input.
   Hint: If ((- #\000 #\377) custom-error-behavior) is the last rule,
   then there will always be a match and custom-error-behavior will be
   executed to handle the error situation as desired, only consuming
   the first character from the input buffer.

   The lexer treats the rules ((eof) action), ((special) action),
   ((special-comment) action) and ((special-error) action) specially.
   In addition to returning characters, input ports can return
   eof-objects and custom input ports can return arbitrary values
   (specials), raise an exception to indicate a non-textual comment
   (special-comments) or raise an exception to indicate a malformed
   special (special-error).  Eofs, specials, special-comments and
   special-errors can never be part of a lexeme with surrounding
   characters.

   The eof rule is matched when the input port returns an eof value.
   Its action works the same as actions for the usual regular
   expressions.

   The special rule is matched when the input port returns a value
   other than a character or eof-object.  The identifier "special" is
   bound to this value in the corresponding action, instead of the
   identifier "lexeme".  If no special rule is present, the lexer
   returns void.

   The special-comment rule is matched when the input port raises a
   special-comment exception instead of returning a value.  If no
   special-comment rule is present, the lexer automatically tries to
   return the next token from the input port.

   The special-error rule is matched when the input port raises an
   exception (other than a special-comment or break exception) while
   trying to read a special value.  This indicates that the special
   value is internally malformed (such as an embedded XML editor with
   malformed syntax).  The identifier "exception" is bound to the
   raised exception in the action.  If no special-error rule is
   present, the exception is raised by the lexer itself.


> (lexer-src-pos (re action) ...) like a lexer, but the return of each
   match is (list action-result start-pos end-pos) instead of simply
   action-result.
   
> (define-tokens group-name (token-name ...)) which binds group-name
   to the group of tokens being defined.  For each token-name, t, a
   function (token-t expr) is created, which constructs a token with
   name t and stores the value of expr in it.  The definition of
   group-name has the same scoping properties as a normal mzscheme
   macro definition.  In particular a (define-syntax group-name ...)
   could interfere.  error cannot be defined as a token since it has
   special use in the parser.

> (define-empty-tokens group-name (token-name ...)) like
   define-tokens, except the resulting token constructors take no
   arguments and store the value #f into the token.

> (token-name token) returns the token's name.
> (token-value token) returns the token's value.
> (token? val) returns #t if val is a token and #f otherwise.

HINT: Token definitions are usually necessary for interoperating with
a generated parser, but may not be the right choice when using the
lexer in other situations.


Several values are also provided for manipulating the position
structures tracked by start-pos and end-pos:

> (position-offset position) - the offset of the character in the stream.
> (position-line position) - the line number of the character.
> (position-col position) - the offset of the character in the current line.
> (position? x) - the question associated with a position struct

and a parameter for tracking the source file:

> (file-path string) - sets the parameter file-path, which the lexer
   will use as the source location if it raises a read error.  This
   allows DrScheme to open the file containing the error.

Each time the scheme code for a lexer is compiled (e.g. when a .ss
file containing a (lex ...) is loaded/required) the lexer generator is
run.  To avoid this overhead place the lexer into a module and compile
the module to a .zo with 'mzc --zo --auto-dir filename'.  This should
create a .zo file in the 'compiled' subdirectory.

Compiling the lex.ss file to an extension can produce a good speedup
in generated lexers since the lex.ss file contains the interpreter for
the generated lex tables.  If mzscheme is able to compile extensions
(a c compiler must be available) run the commands:
cd ${PLTHOME}/collects/parser-tools
mzc --auto-dir lex.ss

NOTE: Since the lexer gets its source information from the port, use
port-count-lines! to enable the tracking of line and column information.
Otherwise the line and column information will return #f.

See the combined lexer/parser example below.


_yacc.ss_

To use the _parser generator_ (require (lib "yacc.ss" "parser-tools")).
This module provides the following syntactic form:

> (parser args ...) where the possible args may come in any order (as
  long as there are no duplicates and all non-optional arguments are
  present) and are:

  > (debug filename) OPTIONAL causes the parser generator to write the
     LALR table to the file named filename (unless the file exists).
     filename must be a string.  Additionally, if a debug file is
     specified, when a running generated parser encounters a parse
     error on some input file, after the user specified error
     expression returns, the complete parse stack is printed to assist
     in debugging the grammar of that particular parser.  The numbers
     in the stack printout correspond to the state numbers in the LALR
     table file.

  > (yacc-output filename) OPTIONAL causes the parser generator to
     write a grammar file in the syntax of YACC/Bison.  The file might
     not be a valid YACC file because the scheme grammar can use
     symbols that are invalid in C.

  > (suppress) OPTIONAL causes the parser generator not to report
     shift/reduce or reduce/reduce conflicts.

  > (src-pos) OPTIONAL causes the generated parser to expect input in
     the form (list token position position) instead of simply token.
     Include this option when using the parser with a lexer generated
     with lexer-src-pos.

  > (error expression) expression should evaluate to a function which
     will be executed for its side-effect whenever the parser
     encounters an error.  If the src-pos option is present, the
     function should accept 5 arguments, 
     (lambda (token-ok token-name token-value start-pos end-pos) ...).     
     Otherwise it should accept 3, 
     (lambda (token-ok token-name token-value) ...).
     The first argument will be #f iff the error is that an invalid
     token was received.  The second and third arguments will be the
     name and the value of the token at which the error was detected.
     The fourth and fifth arguments, if present, provide the source
     positions of that token.

  > (tokens group-name ...) declares that all of the tokens defined in
     the groups can be handled by this parser.

  > (start non-terminal-name ...) declares a list of starting
     non-terminals for the grammar.

  > (end token-name ...) specifies a set of tokens from which some
     member must follow any valid parse.  For example an EOF token
     would be specified for a parser that parses entire files and a
     NEWLINE token for a parser that parses entire lines individually.

  > (precs (assoc token-name ...) ...) OPTIONAL precedence
     declarations to resolve shift/reduce and reduce/reduce conflicts
     as in YACC/BISON.  assoc must be one of left, right or nonassoc.
     States with multiple shift/reduce or reduce/reduce conflicts or
     some combination thereof are not resolved with precedence.

  > (grammar (non-terminal ((grammar-symbol ...) (prec token-name) expression)
                            ...) 
              ...)

     declares the grammar to be parsed.  Each grammar-symbol must be a
     token-name or non-terminal.  The prec declaration is optional.
     expression is a semantic action which will be evaluated when the
     input is found to match its corresponding production.  Each
     action is scheme code that has the same scope as its parser's
     definition, except that the variables $1, ..., $n are bound in
     the expression and may hide outside bindings of $1, ... $n.  $x
     is bound to the result of the action for the $xth grammar symbol
     on the right of the production, if that grammar symbol is a
     non-terminal, or the value stored in the token if the grammar
     symbol is a terminal.  Here n is the number of grammar-symbols on
     the right of the production.  If the src-pos option is present in
     the parser, variables $1-start-pos, ..., $n-start-pos and
     $1-end-pos, ..., $n-end-pos are also available and refer to the
     position structures corresponding to the start and end of the
     corresponding grammar-symbol.  Grammar symbols defined as
     empty-tokens have no $n associated, but do have $n-start-pos and
     $n-end-pos.  All of the productions for a given non-terminal must
     be grouped with it, i.e. No non-terminal may appear twice on the
     left hand side in a parser.

The result of a parser expression with one start non-terminal is a
function, f, that takes one argument.  This argument must be a zero
argument function, t, that produces successive tokens of the input
each time it is called.  If desired, the t may return symbols instead
of tokens.  The parser will treat symbols as tokens of the
corresponding name (with #f as a value, so it is usual to return
symbols only in the case of empty tokens).  f returns the value
associated with the parse tree by the semantic actions.  If the parser
encounters an error, after invoking the supplied error function, it
will try to use error productions to continue parsing.  If it cannot,
it raises a read error.

If multiple start non-terminals are provided, the parser expression
will result in a list of parsing functions (each one will individually
behave as if it were the result of a parser expression with only one
start non-terminal), one for each start non-terminal, in the same order.

Each time the scheme code for a parser is compiled (e.g. when a .ss
file containing a (parser ...) is loaded/required) the parser
generator is run.  To avoid this overhead place the lexer into a
module and compile the module to a .zo with 'mzc --zo --auto-dir
filename'.  This should create a .zo file in the 'compiled'
subdirectory.

Compiling the yacc.ss file to an extension can produce a good speedup
in generated parsers since the yacc.ss file contains the interpreter
for the generated parse tables.  If mzscheme is able to compile
extensions (a c compiler must be available) run the commands:
cd ${PLTHOME}/collects/parser-tools
mzc --auto-dir yacc.ss


Efficiency warning:

The parser macro does not expand directly into a lambda, instead it
looks more like
(parser ...) -> 
(let (code to setup tables and such)
  (lambda (get-token)
    parser-loop))
and the code to setup tables is rather slow, so in situations where the
parser is invoked many times it is by far faster to evaluate the
code to setup tables exactly once, by putting the parser in an
appropriate context, such as the right hand part of a define: 
(define parse (parser ...)).  Doing something like 
(define parse
  (lambda (y)
     (parser ...)))
can be very useful if the parser actions need to refer to a y that
might be different on each execution of the parser, but will lead to
multiple executions of the table setup code.  Consider using a global
parameter for y instead if efficiency is a concern.  The same concerns
hold for a lexer to a lesser extend since the setup code is much
smaller


_yacc-to-scheme.ss_
This library provides one function:
> (trans filename) - reads a C YACC/BISON grammar from filename and
   produces an s-expression that represents a scheme parser for use
   with the yacc.ss module.
This library is intended to assist in the manual conversion of
grammars for use with yacc.ss and not as a fully automatic conversion
tool.  It is not entirely robust.  For example, if the C actions in
the original grammar have nested blocks the tool will fail.




Annotated examples are in the examples subdirectory of the parser-tools
collection directory.


Potential future additions:

If you need any of these features, or if you have a different handy
feature in mind, let me know.

lexer generator:
1) POSIX style regular expressions.  This would take the form of an
   include-like operation to get a file of lex-abbrevs in POSIX syntax
   instead of the s-expression syntax.
2) DFA minimization/compaction.  Should reduce the runtime footprint
   of a lexer.

parser:
1) Increase speed of parser generator.  I doubt much can be done short
   of making mzscheme faster.
2) Fisher-Burke error recovery.  Automatically figure out a "good"
   token to insert when an error is encountered.
3) Possibly change the $1 style to something like SML/NJ YACC uses.
   The SML/NJ YACC refers to the Nth occurrence of grammar symbol name
   in a production RHS as nameN.
4) LALR table compression.  Would reduce the runtime memory
   requirements of parsers.
5) Error checking for useless productions.  Right now productions
   which cannot be used in a parse tree are silently accepted.
6) Allow different end-terminals for different start symbols.

both:
1) Increase runtime speed.  I doubt much can be done short of making
   mzscheme faster.
2) Add more information for check syntax to draw arrows to more things
