\input texinfo       @c                    -*- Texinfo -*-
@setfilename flex.info

@ifinfo
@format
START-INFO-DIR-ENTRY

* flex: (flex).	
		Fast lexical analyzer generator.

END-INFO-DIR-ENTRY
@end format
@end ifinfo

@synindex ky cp
@c
@c This file documents ``flex'', the fast lexical analyzer generator.
@c
@c This text is based on the file ``flexdoc.1'' in the UCB flex
@c distribution.  The text may be freely distributed under the terms of
@c the UCB license; see file COPYING.
@c
@c $Id: flex.texinfo,v 1.5 1992/05/29 20:40:09 pesch Exp $

@setchapternewpage odd
@settitle Using @code{flex}
@titlepage
@finalout
@c @smallbook
@c @cropmarks
@title Using @code{flex}
@subtitle A Fast Lexical Analyzer Generator
@sp 1
@subtitle 26 May 1990---Version 2.3
@sp 4
@quotation
This product includes software developed by the University of
California, Berkeley and its contributors.
@end quotation
@author Vern Paxson
@page

@tex
\def\$#1${{#1}} % Kluge: collect RCS revision info without $...$
\xdef\manvers{\$Revision: 1.5 $} % For use in headers, footers too
{\parskip=0pt \hfill {\it Using flex} \par \hfill \manvers\par \hfill
\TeX{}info \texinfoversion\par
\hfill Original text: {\tt vern@@ee.lbl.gov}\par 
\hfill Texinfo conversion:{\tt pesch@@cygnus.com}\par}
@end tex

@vskip 0pt plus 1filll
Copyright (c) 1990 The Regents of the University of California.
All rights reserved.

This code is derived from software contributed to Berkeley by
Vern Paxson.

The United States Government has rights in this work pursuant
to contract no. DE-AC03-76SF00098 between the United States
Department of Energy and the University of California.

Redistribution and use in source and binary forms are permitted
provided that: (1) source distributions retain this entire
copyright notice and comment, and (2) distributions including
binaries display the following acknowledgement:  ``This product
includes software developed by the University of California,
Berkeley and its contributors'' in the documentation or other
materials provided with the distribution and in all advertising
materials mentioning features or use of this software.  Neither the
name of the University nor the names of its contributors may be
used to endorse or promote products derived from this software
without specific prior written permission.


THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR
IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED
WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
PURPOSE.
@end titlepage

@ifinfo
@node Top
@top FLEX---fast lexical analyzer generator

@quotation
This product includes software developed by the University of
California, Berkeley and its contributors.
@end quotation

@menu
* Introduction::        An Overview of @code{flex}, with Examples
* Files::               Input and Output Files
* Invoking::            Command-line Options
* Performance::         Performance Considerations
* Incompatibilities::   Incompatibilities with @code{lex} and @sc{posix}
* Diagnostics::         Diagnostic Messages
* Bugs::                Deficiencies and Bugs
* Acknowledgements::    Contributors to flex
@end menu
@end ifinfo

@node Introduction
@chapter An Overview of @code{flex}, with Examples

@code{flex} is a tool for generating scanners: programs which recognize
lexical patterns in text.  @code{flex} reads the given input files (or
its standard input if no file names are given) for a description of the
scanner to generate.  The description is in the form of pairs of regular
expressions and C code, called @dfn{rules}.  @code{flex} generates as
output a C source file, @file{lex.yy.c}, which defines a routine
@code{yylex}. Compile and link this file with the @samp{-lfl} library to
produce an executable.  When the executable runs, it analyzes its input
for occurrences of the regular expressions.  Whenever it finds one, it
executes the corresponding C code.

Some simple examples follow, to give you the flavor of using
@code{flex}.

@menu
* Text-Substitution::   Trivial Text-Substitution
* Counter::             Count Lines and Characters
* Toy::                 Simplified Pascal-like Language
@end menu

@node Text-Substitution
@section Text-Substitution Scanner

The following @code{flex} input specifies a scanner which,
whenever it encounters the string @samp{username}, will replace it
with the user's login name:

@example
%%
username    printf( "%s", getlogin() );
@end example

By default, any text not matched by a @code{flex} scanner is copied to
the output, so the net effect of this scanner is to copy its input file
to its output with each occurrence of @samp{username} expanded.  In this
input, there is just one rule.  @samp{username} is the pattern and the
@code{printf} is the action.  The @samp{%%} marks the beginning of the
rules.

@node Counter
@section A Scanner to Count Lines and Characters

Here's another simple example:

@example
    int num_lines = 0, num_chars = 0;

%%
\n    ++num_lines; ++num_chars;
.     ++num_chars;

%%
main()
    @{
    yylex();
    printf( "# of lines = %d, # of chars = %d\n",
            num_lines, num_chars );
    @}
@end example

This scanner counts the number of characters and the  number
of  lines in its input (it produces no output other than the
final report on the counts).  The first  line  declares  two
globals,  @code{num_lines}  and @code{num_chars}, which are accessible
both inside @code{yylex} and in the @code{main} routine declared after
the  second  @samp{%%}.  There are two rules, one which matches a
newline (@samp{\n}) and increments both the line  count  and  the
character  count,  and one which matches any character other
than a newline (indicated by the @samp{.} regular expression).

@node Toy
@section Simplified Pascal-like Language Scanner

A somewhat more complicated example:

@smallexample
/* scanner for a toy Pascal-like language */

%@{
/* need this for the call to atof() below */
#include <math.h>
%@}

DIGIT    [0-9]
ID       [a-z][a-z0-9]*

%%

@{DIGIT@}+    @{
            printf( "An integer: %s (%d)\n", yytext,
                    atoi( yytext ) );
            @}

@{DIGIT@}+"."@{DIGIT@}*        @{
            printf( "A float: %s (%g)\n", yytext,
                    atof( yytext ) );
            @}

if|then|begin|end|procedure|function        @{
            printf( "A keyword: %s\n", yytext );
            @}

@{ID@}        printf( "An identifier: %s\n", yytext );

"+"|"-"|"*"|"/"   printf( "An operator: %s\n", yytext );

"@{"[^@}\n]*"@}"     /* eat up one-line comments */

[ \t\n]+          /* eat up whitespace */

.           printf( "Unrecognized character: %s\n", yytext );

%%

main( argc, argv )
int argc;
char **argv;
    @{
    ++argv, --argc;  /* skip over program name */
    if ( argc > 0 )
            yyin = fopen( argv[0], "r" );
    else
            yyin = stdin;

    yylex();
    @}
@end smallexample

This is the beginnings of a simple scanner for a language like Pascal.
It identifies different types of tokens and reports on what it has seen.

The details of this example are explained in the following chapters.

@node Files
@chapter Input and Output Files

@code{flex}'s actions are specified by definitions (which may include
embedded C code) in one or more input files.  The primary
output file is @file{lex.yy.c}.  You can also use some of the
command-line options to get diagnostic output
(@pxref{Invoking,,Command-line options}).
This chapter gives the details of how to structure your input to
define the scanner you need.

@menu
* Input Format::        Format of the Input File
* Scanner::             The Generated Scanner
* Start::               Start Conditions
* Multiple Input::      Multiple Input Buffers
* EOF::                 End-of-File Rules
* Misc::                Miscellaneous Macros
* Parsers::             Interfacing with Parser Generators
* Translation::         Translation Table
@end menu

@node Input Format
@section Format of the Input File

The @code{flex} input file consists of three sections, separated by a
line with just @samp{%%} in it:

@example
@var{definitions}
%%
@var{rules}
%%
@var{user code}
@end example

The @var{definitions} section contains declarations of simple name
definitions to simplify the scanner specification, and declarations of
start conditions, which are explained in a later section.

@noindent
Name definitions have the form:

@example
@var{name} @var{definition}
@end example

The @var{name} is a word beginning with a letter or an underscore
(@samp{_}) followed by zero or more letters, digits, @samp{_}, or
@samp{-} (dash).  The definition is taken to begin at the first
non-whitespace character following the name, and continuing to the end
of the line.  The definition can subsequently be referred to using
@samp{@{@var{name}@}}, which will expand to @samp{(@var{definition})}.
For example,

@example
DIGIT    [0-9]
ID       [a-z][a-z0-9]*
@end example

defines @samp{DIGIT} to be a regular expression which matches a single
digit, and @samp{ID} to be a regular expression which matches a letter
followed by zero or more letters or digits.  A subsequent reference to

@example
@{DIGIT@}+"."@{DIGIT@}*
@end example

@noindent
is identical to

@example
([0-9])+"."([0-9])*
@end example

@noindent
and matches one or more digits followed by a @samp{.} followed by zero
or more digits.

The rules section of the @code{flex} input contains a series of rules of
the form:

@example
@var{pattern}   @var{action}
@end example

@noindent
where the @var{pattern} must be unindented and the @var{action} must
begin on the same line.

See below for a further description of patterns and actions.

Finally, the user code section is simply copied to @file{lex.yy.c}
verbatim.  It is used for companion routines which call or are called by
the scanner.  The presence of this section is optional; if it is
missing, the second @samp{%%} in the input file may be skipped, too.

In the definitions and rules sections, any indented text or text
enclosed in @samp{%@{} and @samp{%@}} is copied verbatim to the output
(with the @samp{%@{@}} removed).  The @samp{%@{@}} must appear
unindented on lines by themselves.

In the rules section, any indented or @samp{%@{@}} text appearing before
the first rule may be used to declare variables which are local to the
scanning routine and (after the declarations) code which is to be
executed whenever the scanning routine is entered.  Other indented or
@samp{%@{@}} text in the rule section is still copied to the output, but
its meaning is not well defined and it may well cause compile-time
errors (this feature is present for @sc{posix} compliance; see below for
other such features).

In the definitions section, an unindented comment (i.e., a line
beginning with @samp{/*}) is also copied verbatim to the output up to
the next @samp{*/}.  Also, any line in the definitions section beginning
with @samp{#} is ignored, though this style of comment is deprecated and
may go away in the future.

@menu
* Patterns::    Patterns in the input
* Matching::    How the input is matched
* Actions::     Actions
@end menu

@node Patterns
@subsection Patterns in the Input

The patterns in the input are written using an extended set of regular
expressions.  These are:

@table @code
@item @var{x}
match the character @samp{@var{x}}

@item .
any character except newline

@item [xyz]
a ``character class''; in this case, the pattern matches either an
@samp{x}, a @samp{y}, or a @samp{z}

@item [abj-oZ]
a ``character class'' with a range in it; matches an @samp{a}, a
@samp{b}, any letter from @samp{j} through @samp{o}, or a @samp{Z}

@item [^A-Z]
a ``negated character class'', i.e., any character but those in the
class.  In this case, any character @emph{except} an uppercase letter.

@item [^A-Z\n]
any character @emph{except} an uppercase letter or a newline

@item @var{r}*
zero or more @var{r}'s, where @var{r} is any regular expression

@item @var{r}+
one or more @var{r}'s

@item @var{r}?         zero or one @var{r}'s (that is, ``an optional @var{r}'')

@item @var{r}@{2,5@}
anywhere from two to five @var{r}'s

@item @var{r}@{2,@}
two or more @var{r}'s

@item @var{r}@{4@}
exactly 4 @var{r}'s

@item @{@var{name}@}
the expansion of the @var{name} definition (see above)

@item "[xyz]\"foo"
the literal string: @samp{[xyz]"foo}

@item \@var{X}
if @var{X} is an @samp{a}, @samp{b}, @samp{f}, @samp{n}, @samp{r}, @samp{t},
or @samp{v}, then the @sc{ansi} C interpretation of @samp{\@var{X}}.
Otherwise, a literal @samp{@var{X}} (used to escape operators such as
@samp{*})

@item \123
the character with octal value @code{123}

@item \x2a
the character with hexadecimal value @code{2a}

@item (@var{r})
match an @var{r}; parentheses are used to override precedence (see
below)

@item @var{r}@var{s}
the regular expression @var{r} followed by the regular expression
@var{s}; called ``concatenation''

@item @var{r}|@var{s}
either an @var{r} or an @var{s}

@item @var{r}/@var{s}
an @var{r} but only if it is followed by an @var{s}.  The @var{s} is not
part of the matched text.  This type of pattern is called @dfn{trailing
context}.

@item ^@var{r}
an @var{r}, but only at the beginning of a line

@item @var{r}$
an @var{r}, but only at the end of a line.  Equivalent to @samp{r/\n}.

@item <@var{s}>@var{r}
an @var{r}, but only in start condition @var{s} (see below for
discussion of start conditions)

@item <@var{s1},@var{s2},@var{s3}>@var{r}
same, but in any of start conditions @var{s1}, @var{s2}, or @var{s3}

@item <<EOF>>
an end-of-file

@item <@var{s1},@var{s2}><<EOF>>
an end-of-file when in start condition @var{s1} or @var{s2}
@end table

The regular expressions listed above are grouped according to
precedence, from highest precedence at the top to lowest at the bottom.
Those grouped together have equal precedence.  For example,

@example
foo|bar*
@end example

@noindent
is the same as

@example
(foo)|(ba(r*))
@end example

@noindent
since the @samp{*} operator has higher precedence than concatenation,
and concatenation higher than alternation (@samp{|}).  This pattern
therefore matches either the string @samp{foo} or the string @samp{ba}
followed by zero or more instances of @samp{r}.  To match @samp{foo} or
zero or more instances of @samp{bar}, use:

@example
foo|(bar)*
@end example

@noindent
and to match zero or more instances of either @samp{foo} or @samp{bar}:

@example
(foo|bar)*
@end example

@noindent
Some notes on patterns:

@itemize @bullet
@item
A negated character class such as the example @samp{[^A-Z]} above will
match a newline unless @samp{\n} (or an equivalent escape sequence) is
one of the characters explicitly present in the negated character class
(e.g., @samp{[^A-Z\n]}).  This is unlike how many other regular
expression tools treat negated character classes, but unfortunately the
inconsistency is historically entrenched.  Matching newlines means that
a pattern like @samp{[^"]*} can match an entire input (overflowing the
scanner's input buffer) unless there's another quote in the input.

@item
A rule can have at most one instance of trailing context (the @samp{/}
operator or the @samp{$} operator).  The start condition, @samp{^}, and
@samp{<<EOF>>} patterns can only occur at the beginning of a pattern,
and, as well as with @samp{/} and @samp{$}, cannot be grouped inside
parentheses.  A @samp{^} which does not occur at the beginning of a rule
or a @samp{$} which does not occur at the end of a rule loses its
special properties and is treated as a normal character.
@end itemize

@noindent
The following are illegal:

@example
foo/bar$
<sc1>foo<sc2>bar
@end example

@noindent
You can write the first of these instead as @samp{foo/bar\n}.

In the following examples, @samp{$} and @samp{^} are treated as
normal characters:

@example
foo|(bar$)
foo|^bar
@end example

If what you want to specify is ``either @samp{foo}, or @samp{bar}
followed by a newline'' you can use the following (the special @samp{|}
action is explained below):

@example
foo      |
bar$     /* action goes here */
@end example

A similar trick will work for matching ``either @samp{foo}, or @samp{bar}
at the beginning of a line.''

@node Matching
@subsection How the Input is Matched

When the generated scanner runs, it analyzes its input looking for
strings which match any of its patterns.  If it finds more than one
match, it takes the one matching the most text (for trailing context
rules, this includes the length of the trailing part, even though it
will then be returned to the input).  If it finds two or more matches of
the same length, the rule listed first in the @code{flex} input file is
chosen.

Once the match is determined, the text corresponding to the match
(called the @dfn{token}) is made available in the global character
pointer @code{yytext}, and its length in the global integer
@code{yyleng}. The action corresponding to the matched pattern is then
executed (a more detailed description of actions follows), and then the
remaining input is scanned for another match.

If no match is found, then the default rule is executed: the next
character in the input is considered matched and copied to the standard
output.  Thus, the simplest legal @code{flex} input is:

@example
%%
@end example

@noindent
which generates a scanner that simply copies its input (one character at
a time) to its output.

@node Actions
@subsection Actions
Each pattern in a rule has a corresponding action, which can be any
arbitrary C statement.  The pattern ends at the first non-escaped
whitespace character; the remainder of the line is its action.  If the
action is empty, then when the pattern is matched the input token is
simply discarded.  For example, here is the specification for a program
which deletes all occurrences of @samp{zap me} from its input:

@example
%%
"zap me"
@end example

@noindent
(It will copy all other characters in the input to the output since they
will be matched by the default rule.)

Here is a program which compresses multiple blanks and tabs down to a
single blank, and throws away whitespace found at the end of a line:

@example
%%
[ \t]+        putchar( ' ' );
[ \t]+$       /* ignore this token */
@end example

If the action contains a @samp{@{}, then the action spans till the
balancing @samp{@}} is found, and the action may cross multiple lines.
@code{flex} knows about C strings and comments and won't be fooled by
braces found within them, but also allows actions to begin with
@samp{%@{} and will consider the action to be all the text up to the
next @samp{%@}} (regardless of ordinary braces inside the action).

An action consisting solely of a vertical bar (@samp{|}) means ``same as
the action for the next rule.''  See below for an illustration.

Actions can include arbitrary C code, including return statements to
return a value to whatever routine called @code{yylex}. Each time
@code{yylex} is called it continues processing tokens from where it last
left off until it either reaches the end of the file or executes a
return.  Once it reaches an end-of-file, however, then any subsequent
call to @code{yylex} will simply immediately return, unless
@code{yyrestart} is first called (see below).

@noindent
Actions are not allowed to modify @samp{yytext} or @samp{yyleng}.

There are a number of special directives which can be included within an
action:

@table @code
@item ECHO 
copies @code{yytext} to the scanner's output.

@item BEGIN
followed by the name of a start condition places the scanner in the
corresponding start condition (see below).

@item REJECT
directs the scanner to proceed on to the ``second best'' rule which
matched the input (or a prefix of the input).  The rule is chosen as
described above in @ref{Matching,,How the Input is Matched}, and
@code{yytext} and @code{yyleng} set up appropriately.  It may either be
one which matched as much text as the originally chosen rule but came
later in the @code{flex} input file, or one which matched less text.
For example, the following will both count the words in the input and
call the routine @code{special} whenever @samp{frob} is seen:

@example
        int word_count = 0;
%%

frob        special(); REJECT;
[^ \t\n]+   ++word_count;
@end example

Without the @code{REJECT}, any @samp{frob} in the input would not be
counted as a word, since the scanner normally executes only one action
per token.  Multiple @code{REJECT} actions are allowed, each one finding
the next best choice to the currently active rule.  For example, when
the following scanner scans the token @samp{abcd}, it will write
@samp{abcdabcaba} to the output:

@example
%%
a        |
ab       |
abc      |
abcd     ECHO; REJECT;
.|\n     /* eat up any unmatched character */
@end example

(The first three rules share the fourth's action, since they use the
special @samp{|} action.) @code{REJECT} is a particularly expensive
feature in terms of scanner performance; if it is used in any of the
scanner's actions, it will slow down all of the scanner's matching.
Furthermore, @code{REJECT} cannot be used with the @samp{-f} or
@samp{-F} options (see below).

Note also that unlike the other special actions, @code{REJECT} is a
branch; code immediately following it in the action will not be
executed.

@item yymore()
tells the scanner that the next time it matches a rule, the
corresponding token should be appended onto the current value of
@code{yytext} rather than replacing it.  For example, given the input
@samp{mega-kludge} the following will write @samp{mega-mega-kludge} to
the output:

@example
%%
mega-    ECHO; yymore();
kludge   ECHO;
@end example

First @samp{mega-} is matched and echoed to the output.  Then
@samp{kludge} is matched, but the previous @samp{mega-} is still hanging
around at the beginning of yytext so the ECHO for the @samp{kludge} rule
will actually write @samp{mega-kludge}.  The presence of @code{yymore}
in the scanner's action entails a minor performance penalty in the
scanner's matching speed.

@item yyless(@var{n})
returns all but the first @var{n} characters of the current token back
to the input stream, where they will be rescanned when the scanner looks
for the next match.  @code{yytext} and @code{yyleng} are adjusted
appropriately (e.g., @code{yyleng} will now be equal to @var{n}).  For
example, on the input @samp{foobar} the following will write out
@samp{foobarbar}:

@example
@group
%%
foobar    ECHO; yyless(3);
[a-z]+    ECHO;
@end group
@end example

@samp{yyless(0)} will cause the entire current input string to be
scanned again.  Unless you've changed how the scanner will subsequently
process its input (using @code{BEGIN}, for example), this will result in
an endless loop.


@item unput(@var{c})
puts the character @var{c} back onto the input stream.  It will be the
next character scanned.  The following action will take the current
token and cause it to be rescanned enclosed in parentheses.

@example
@{
int i;
unput( ')' );
for ( i = yyleng - 1; i >= 0; --i )
    unput( yytext[i] );
unput( '(' );
@}
@end example

Note that since each @code{unput} puts the  given  character
back at the beginning of the input stream, pushing back
strings must be done back-to-front.

@item input()
reads the next character from the input stream.  For example, the
following is one way to eat up C comments:

@smallexample
%%
"/*"        @{
            register int c;

            for ( ; ; )
                @{
                while ( (c = input()) != '*' &&
                        c != EOF )
                    ; /* eat up text of comment */

                if ( c == '*' )
                    @{
                    while ( (c = input()) == '*' )
                        ;
                    if ( c == '/' )
                        break; /* found the end */
                    @}

                if ( c == EOF )
                    @{
                    error( "EOF in comment" );
                    break;
                    @}
                @}
            @}
@end smallexample

(Note that if the scanner is compiled using C++, then @code{input} is
instead referred to as @code{yyinput}, in order to avoid a name clash
with the C++ stream named @code{input}.)

@item yyterminate()
can be used in lieu of a @code{return} statement in an action.  It terminates
the scanner and returns a 0 to the scanner's caller, indicating
@samp{all done}.  Subsequent calls to the scanner will immediately
return unless preceded by a call to @code{yyrestart} (see below).  By
default, @code{yyterminate} is also called when an end-of-file is
encountered.  It is a macro and may be redefined.
@end table

@node Scanner
@section The Generated Scanner

The output of @code{flex} is the file @file{lex.yy.c}, which contains
the scanning routine @code{yylex}, a number of tables used by it for
matching tokens, and a number of auxiliary routines and macros.  By
default, @code{yylex} is declared as follows:

@example
int yylex()
    @{
    @r{@dots{}} various definitions and the actions in here @r{@dots{}}
    @}
@end example

@noindent
(If your environment supports function prototypes, then it will be
@samp{int yylex( void )}.)  This definition may be changed by redefining
the @code{YY_DECL} macro.  For example, you could use:

@example
#undef YY_DECL
#define YY_DECL float lexscan( a, b ) float a, b;
@end example

@noindent
to give the scanning routine the name @code{lexscan}, returning a
@code{float}, and taking two @code{float} values as arguments.  Note
that if you give arguments to the scanning routine using a
K&R-style/non-prototyped function declaration, you must terminate the
definition with a semicolon (@samp{;}).

Whenever @code{yylex} is called, it scans tokens from the global input
file @file{yyin} (which defaults to @file{stdin}).  It continues until
it either reaches an end-of-file (at which point it returns the value 0)
or one of its actions executes a return statement.  In the former case,
when called again the scanner will immediately return unless
@code{yyrestart} is called to point @file{yyin} at the new input file.
(@code{yyrestart} takes one argument, a @samp{FILE *} pointer.) In the
latter case (i.e., when an action executes a return), the scanner may
then be called again and it will resume scanning where it left off.

By default (and for efficiency), the scanner uses block-reads rather
than simple @code{getc} calls to read characters from @file{yyin}.  You
can control how it gets input by redefining the @code{YY_INPUT} macro.
@code{YY_INPUT}'s calling sequence is
@samp{YY_INPUT(@var{buf},@var{result},@var{max_size})}.  Its action is
to place up to @var{max_size} characters in the character array
@var{buf} and return in the integer variable result either the number of
characters read or the constant @code{YY_NULL} (0 on Unix systems) to
indicate EOF.  The default @code{YY_INPUT} reads from the global
file-pointer @file{yyin}.

A sample redefinition of @code{YY_INPUT} (in the definitions section
of the input file):

@example
%@{
#undef YY_INPUT
#define YY_INPUT(buf,result,max_size) \
    @{ \
    int c = getchar(); \
    result = (c == EOF) ? YY_NULL : (buf[0] = c, 1); \
    @}
%@}
@end example

This definition will change the input processing to occur one character
at a time.

You also can add in things like keeping track of the input line number
this way; but don't expect your scanner to go very fast.

When the scanner receives an end-of-file indication from
@code{YY_INPUT}, it then checks the @code{yywrap} function.  If
@code{yywrap} returns false (zero), then it is assumed that the function
has gone ahead and set up @file{yyin} to point to another input file,
and scanning continues.  If it returns true (non-zero), then the
scanner terminates, returning 0 to its caller.

The default @code{yywrap} always returns 1.  At present, to redefine it
you must first @samp{#undef yywrap}, as it is currently implemented as a
macro.  As indicated by the hedging in the previous sentence, it may be
changed to a true function in the near future.

The scanner writes its  @code{ECHO}  output  to  the  @file{yyout}  global
(default, @file{stdout}), which may be redefined by the user simply
by assigning it to some other @code{FILE} pointer.

@node Start
@section Start Conditions

@code{flex} provides a mechanism for conditionally activating rules.
Any rule whose pattern is prefixed with @samp{<@var{sc}>} will only be
active when the scanner is in the start condition named @var{sc}.  For
example,

@example
<STRING>[^"]*        @{ /* eat up the string body ... */
            @r{@dots{}}
            @}
@end example

@noindent
will be active only when the  scanner  is  in  the  @samp{STRING}
start condition, and

@smallexample
<INITIAL,STRING,QUOTE>\.        @{ /* handle an escape ... */
            @r{@dots{}}
            @}
@end smallexample

@noindent
will be active only when the current start condition is either
@samp{INITIAL}, @samp{STRING}, or @samp{QUOTE}.

Start conditions are declared in the definitions (first) section of the
input using unindented lines beginning with either @samp{%s} or
@samp{%x} followed by a list of names.  The former declares
@emph{inclusive} start conditions, the latter @emph{exclusive} start
conditions.  A start condition is activated using the @code{BEGIN}
action.  Until the next @code{BEGIN} action is executed, rules with the
given start condition will be active and rules with other start
conditions will be inactive.  If the start condition is inclusive, then
rules with no start conditions at all will also be active.  If it is
exclusive, then only rules qualified with the start condition will be
active.  A set of rules contingent on the same exclusive start condition
describe a scanner which is independent of any of the other rules in the
@code{flex} input.  Because of this, exclusive start conditions make it
easy to specify ``miniscanners'' which scan portions of the input that
are syntactically different from the rest (e.g., comments).

If the distinction between inclusive and exclusive start conditions is
still a little vague, here's a simple example illustrating the
connection between the two.  The set of rules:

@example
%s example
%%
<example>foo           /* do something */
@end example

@noindent
is equivalent to

@example
%x example
%%
<INITIAL,example>foo   /* do something */
@end example

The default rule (to ECHO any unmatched character) remains active in
start conditions.

@samp{BEGIN(0)} returns to the original state where only the rules with
no start conditions are active.  This state can also be referred to as
the start-condition @samp{INITIAL}, so @samp{BEGIN(INITIAL)} is
equivalent to @samp{BEGIN(0)}. (The parentheses around the start
condition name are not required but are considered good style.)

@code{BEGIN} actions can also be given as indented code at the beginning
of the rules section.  For example, the following will cause the scanner
to enter the @samp{SPECIAL} start condition whenever @code{yylex} is
called and the global variable enter_special is true:

@example
        int enter_special;

%x SPECIAL
%%
        if ( enter_special )
            BEGIN(SPECIAL);

<SPECIAL>blahblahblah
@r{@dots{} more rules follow @dots{}}
@end example

To illustrate the uses of start conditions, here is a scanner which
provides two different interpretations of a string like @samp{123.456}.
By default this scanner will treat the string as three tokens: the
integer @samp{123}, a dot @samp{.}, and the integer @samp{456}.  But if
the string is preceded earlier in the line by the string
@samp{expect-floats} it will treat it as a single token, the
floating-point number @code{123.456}:

@example
%@{
#include <math.h>
%@}
%s expect

%%
expect-floats        BEGIN(expect);

<expect>[0-9]+"."[0-9]+      @{
            printf( "found a float, = %f\n",
                    atof( yytext ) );
            @}
<expect>\n           @{
            /* that's the end of the line, so
             * we need another "expect-number"
             * before we'll recognize any more
             * numbers
             */
            BEGIN(INITIAL);
            @}

[0-9]+      @{
            printf( "found an integer, = %d\n",
                    atoi( yytext ) );
            @}

"."         printf( "found a dot\n" );
@end example

Here is a scanner which recognizes (and discards) C comments while
maintaining a count of the current input line.

@smallexample
%x comment
%%
        int line_num = 1;

"/*"         BEGIN(comment);

<comment>[^*\n]*        /* eat anything that's not a '*' */
<comment>"*"+[^*/\n]*   /* eat up '*'s not followed by '/'s */
<comment>\n             ++line_num;
<comment>"*"+"/"        BEGIN(INITIAL);
@end smallexample

Note that start-conditions names are really integer values and can be
stored as such.  Thus, the above could be extended in the following
fashion:

@smallexample
%x comment foo
%%
        int line_num = 1;
        int comment_caller;

"/*"         @{
             comment_caller = INITIAL;
             BEGIN(comment);
             @}

@r{@dots{}}

<foo>"/*"    @{
             comment_caller = foo;
             BEGIN(comment);
             @}

<comment>[^*\n]*        /* eat anything that's not a '*' */
<comment>"*"+[^*/\n]*   /* eat up '*'s not followed by '/'s */
<comment>\n             ++line_num;
<comment>"*"+"/"        BEGIN(comment_caller);
@end smallexample

One can then implement a ``stack'' of start conditions using an array of
integers.  (It is likely that such stacks will become a full-fledged
@code{flex} feature in the future.)  Note, though, that start conditions
do not have their own namespace; @samp{%s} and @samp{%x} declare names
in the same fashion as @code{#define}.

@node Multiple Input
@section Multiple Input Buffers

Some scanners (such as those which support ``include'' files) require
reading from several input streams.  As @code{flex} scanners do a large
amount of buffering, one cannot control where the next input will be
read from by simply writing a @code{YY_INPUT} which is sensitive to the
scanning context.  @code{YY_INPUT} is only called when the scanner
reaches the end of its buffer, which may be a long time after scanning a
statement such as an ``include'' which requires switching the input
source.

To negotiate these sorts of problems, @code{flex} provides a mechanism
for creating and switching between multiple input buffers.  An input
buffer is created by using:

@example
YY_BUFFER_STATE yy_create_buffer( FILE *@var{file}, int @var{size} )
@end example

@noindent
which takes a @code{FILE} pointer and a size and creates a buffer
associated with the given file and large enough to hold @var{size}
characters (when in doubt, use @code{YY_BUF_SIZE} for the size).  It
returns a @code{YY_BUFFER_STATE} handle, which may then be passed to
other routines:

@example
void yy_switch_to_buffer( YY_BUFFER_STATE @var{new_buffer} )
@end example

@noindent
switches the scanner's input buffer so subsequent tokens will come from
@var{new_buffer}. Note that @code{yy_switch_to_buffer} may be used by
@code{yywrap} to sets things up for continued scanning, instead of
opening a new file and pointing @file{yyin} at it.

@example
void yy_delete_buffer( YY_BUFFER_STATE @var{buffer} )
@end example

@noindent
is used to reclaim the storage associated with a buffer.

@code{yy_new_buffer} is an alias for @code{yy_create_buffer}, provided
for compatibility with the C++ use of @code{new} and @code{delete} for
creating and destroying dynamic objects.

Finally, the @code{YY_CURRENT_BUFFER} macro returns a
@code{YY_BUFFER_STATE} handle to the current buffer.

Here is an example of using these features for writing a scanner which
expands include files (the @samp{<<EOF>>} feature is discussed below):

@smallexample
/* the "incl" state is used for picking up the name
 * of an include file
 */
%x incl

%@{
#define MAX_INCLUDE_DEPTH 10
YY_BUFFER_STATE include_stack[MAX_INCLUDE_DEPTH];
int include_stack_ptr = 0;
%@}

%%
include             BEGIN(incl);

[a-z]+              ECHO;
[^a-z\n]*\n?        ECHO;

<incl>[ \t]*      /* eat the whitespace */
<incl>[^ \t\n]+   @{ /* got the include file name */
        if ( include_stack_ptr >= MAX_INCLUDE_DEPTH )
            @{
            fprintf( stderr, "Includes nested too deeply" );
            exit( 1 );
            @}

        include_stack[include_stack_ptr++] =
            YY_CURRENT_BUFFER;

        yyin = fopen( yytext, "r" );

        if ( ! yyin )
            error( @r{@dots{}} );

        yy_switch_to_buffer(
            yy_create_buffer( yyin, YY_BUF_SIZE ) );

        BEGIN(INITIAL);
        @}

<<EOF>> @{
        if ( --include_stack_ptr < 0 )
            @{
            yyterminate();
            @}

        else
            yy_switch_to_buffer(
                 include_stack[include_stack_ptr] );
        @}
@end smallexample

@node EOF
@section End-of-File Rules

The special rule @samp{<<EOF>>} indicates actions which are to be taken
when an end-of-file is encountered and @code{yywrap} returns non-zero
(i.e., indicates no further files to process).  The action must finish
by doing one of four things:

@itemize @bullet
@item
the special @code{YY_NEW_FILE} action, if @file{yyin} has been pointed
at a new file to process;

@item
a return statement;

@item
the special @code{yyterminate} action;

@item
or switching to a new buffer using @code{yy_switch_to_buffer} as shown
in the example above.
@end itemize

@samp{<<EOF>>} rules may not be used with other patterns; they may only
be qualified with a list of start conditions.  If an unqualified
@samp{<<EOF>>} rule is given, it applies to all start conditions which
do not already have @samp{<<EOF>>} actions.  To specify an
@samp{<<EOF>>} rule for only the initial start condition, use

@example
<INITIAL><<EOF>>
@end example

These rules are useful for catching things like unclosed comments.  An
example:

@example
%x quote
%%

@r{@dots{} other rules for dealing with quotes @dots{}}

<quote><<EOF>>   @{
         error( "unterminated quote" );
         yyterminate();
         @}
<<EOF>>  @{
         if ( *++filelist )
             @{
             yyin = fopen( *filelist, "r" );
             YY_NEW_FILE;
             @}
         else
            yyterminate();
         @}
@end example

@node Misc
@section Miscellaneous Macros

The macro @code{YY_USER_ACTION} can be redefined to provide an action
which is always executed prior to the matched rule's action.  For
example, it could be @code{#define}d to call a routine to convert
@code{yytext} to lower-case.

The macro @code{YY_USER_INIT} may be redefined to provide an action
which is always executed before the first scan (and before the scanner's
internal initializations are done).  For example, it could be used to
call a routine to read in a data table or open a logging file.

In the generated scanner, the actions are all gathered in one large
switch statement and separated using @code{YY_BREAK}, which may be
redefined.  By default, it is simply a @code{break}, to separate each
rule's action from the following rule's.  Redefining @code{YY_BREAK}
allows, for example, C++ users to @samp{#define YY_BREAK} to do nothing
(while being very careful that every rule ends with a @code{break} or a
@code{return}!) to avoid suffering from unreachable statement warnings
where because a rule's action ends with @code{return}, the
@code{YY_BREAK} is inaccessible.

@node Parsers
@section Interfacing with Parser Generators
One of the main uses of @code{flex} is as a companion to parser
generators like @code{yacc}.  @code{yacc} parsers expect to call a
routine named @code{yylex} to find the next input token.  The routine is
supposed to return the type of the next token as well as putting any
associated value in the global @code{yylval}.  To use @code{flex} with
@code{yacc}, specify the @samp{-d} option to @code{yacc} to instruct it
to generate the file @code{y.tab.h} containing definitions of all the
@code{%token}s appearing in the @code{yacc} input.  Then include this
file in the @code{flex} scanner.  For example, if one of the tokens is
@samp{TOK_NUMBER}, part of the scanner might look like:

@example
%@{
#include "y.tab.h"
%@}

%%

[0-9]+        yylval = atoi( yytext ); return TOK_NUMBER;
@end example

@node Translation
@section Translation Table

In the name of @sc{posix} compliance, @code{flex} supports a translation
table  for  mapping input characters into groups.  The table
is specified in the first  section,  and  its  format  looks
like:

@example
%t
1        abcd
2        ABCDEFGHIJKLMNOPQRSTUVWXYZ
52       0123456789
6        \t\ \n
%t
@end example

This example specifies that the characters @samp{a}, @samp{b}, @samp{c},
and @samp{d} are to all be lumped into group #1, upper-case letters in
group #2, digits in group #52, tabs, blanks, and newlines into group #6,
and no other characters will appear in the patterns.  The group numbers
are actually disregarded by @code{flex}; @code{%t} serves, though, to
lump characters together.  Given the above table, for example, the
pattern @samp{a(AA)*5} is equivalent to @samp{d(ZQ)*0}.  They both say,
``match any character in group #1, followed by zero or more pairs of
characters from group #2, followed by a character from group #52.''
Thus @samp{%t} provides a crude way for introducing equivalence classes
into the scanner specification.

Note that  the  @samp{-i}  option  (see  below)  coupled  with  the
equivalence  classes which @code{flex} automatically generates take
care of virtually all the instances when one might  consider
using @samp{%t}. But what the hell, it's there if you want it.

@node Invoking
@chapter Command-line Options

You can call @code{flex} with the following command-line options:

@table @code
@item -b
Generate backtracking information to @file{lex.backtrack}.  This is a
list of scanner states which require backtracking and the input
characters on which they do so.  By adding rules one can remove
backtracking states.  If all backtracking states are eliminated and
@samp{-f} or @samp{-F} is used, the generated scanner will run faster
(see the @samp{-p} flag).  Only users who wish to squeeze every last
cycle out of their scanners need worry about this option.
(@xref{Performance,,Performance Considerations}.)

@item -c
is a do-nothing, deprecated option included for @sc{posix} compliance.

@emph{Note:} in previous releases of @code{flex}, you could use
@file{-c} to specify table-compression options.  This functionality is
now given by the @samp{-C} flag.  To ease the the impact of this change,
when @code{flex} encounters @samp{-c}, it currently issues a warning
message and assumes that @samp{-C} was desired instead.  In the future
this ``promotion'' of @samp{-c} to @samp{-C} will go away in the name of
full @sc{posix} compliance (unless the @sc{posix} meaning is removed first).

@item -d
makes the generated scanner run in debug mode.  Whenever a pattern is
recognized and the global @code{yy_flex_debug} is non-zero (which is the
default), the scanner will write to @file{stderr} a line of the form:

@example
--accepting rule at line 53 ("the matched text")
@end example

The line number refers to the location of the rule in the file defining
the scanner (i.e., the file that was fed to @code{flex}).  Messages are
also generated when the scanner backtracks, accepts the default rule,
reaches the end of its input buffer (or encounters a @code{NUL}; at this
point, the two look the same as far as the scanner's concerned), or
reaches an end-of-file.

@item -f
specifies (take your pick) full table or fast scanner.  No table
compression is done.  The result is large but fast.  This option is
equivalent to @samp{-Cf} (see below).

@item -i
instructs @code{flex} to generate a case-insensitive scanner.  The case
of letters given in the @code{flex} input patterns will be ignored, and
tokens in the input will be matched regardless of case.  The matched
text given in @code{yytext} will have the preserved case (i.e., it will
not be folded).

@item -n
is another do-nothing, deprecated option included only for @sc{posix}
compliance.

@item -p
generates a performance report to @file{stderr}.  The report consists of
comments regarding features of the @code{flex} input file which will
cause a loss of performance in the resulting scanner.  Note that the use
of @code{REJECT} and variable trailing context
(@pxref{Bugs,,Deficiencies and Bugs}) entails a substantial performance
penalty; use of @code{yymore}, the @samp{^} operator, and the @samp{-I}
flag entail minor performance penalties.

@item -s
causes the default rule (that unmatched scanner input is echoed to
@file{stdout}) to be suppressed.  If the scanner encounters input that
does not match any of its rules, it aborts with an error.  This option
is useful for finding holes in a scanner's rule set.

@item -t
instructs @code{flex} to write the scanner it generates to standard
output instead of @file{lex.yy.c}.

@item -v
specifies that @code{flex} should write to @file{stderr} a summary of
statistics regarding the scanner it generates.  Most of the statistics
are meaningless to the casual @code{flex} user, but the first line
identifies the version of @code{flex}, which is useful for figuring out
where you stand with respect to patches and new releases, and the next
two lines give the date when the scanner was created and a summary of
the flags which were in effect.

@item -F
specifies that the fast scanner table representation should be used.
This representation is about as fast as the full table representation
(@samp{-f}), and for some sets of patterns will be considerably smaller
(and for others, larger).  In general, if the pattern set contains both
``keywords'' and a catch-all, ``identifier'' rule, such as in the set:

@example
"case"    return TOK_CASE;
"switch"  return TOK_SWITCH;
@r{@dots{}}
"default" return TOK_DEFAULT;
[a-z]+    return TOK_ID;
@end example

@noindent
then you're better off using the full table representation.  If only the
``identifier'' rule is present and you then use a hash table or some
such to detect the keywords, you're better off using @samp{-F}.

This option is equivalent to @samp{-CF} (see below).

@item -I
instructs @code{flex} to generate an interactive scanner.  Normally,
scanners generated by @code{flex} always look ahead one character before
deciding that a rule has been matched.  At the cost of some scanning
overhead, @code{flex} will generate a scanner which only looks ahead
when needed.  Such scanners are called interactive because if you want
to write a scanner for an interactive system such as a command shell,
you will probably want the user's input to be terminated with a newline,
and without @samp{-I} the user will have to type a character in addition
to the newline in order to have the newline recognized.  This leads to
dreadful interactive performance.

If all this seems  too  confusing,  here's  the  general
rule:  if  a  human  will  be  typing  in input to your
scanner, use @samp{-I}, otherwise don't;  if  you  don't  care
about   squeezing  the  utmost  performance  from  your
scanner and you don't  want  to  make  any  assumptions
about the input to your scanner, use @samp{-I}.

@emph{Note:} @samp{-I} cannot be used in  conjunction  with  full  or
fast tables, i.e., the @samp{-f}, @samp{-F}, @samp{-Cf}, or @samp{-CF} flags.

@item -L
instructs @code{flex} not to generate @code{#line} directives.  Without
this option, @code{flex} peppers the generated scanner with @code{#line}
directives so error messages in the actions will be correctly located
with respect to the original @code{flex} input file, and not to the
fairly meaningless line numbers of @file{lex.yy.c}.  (Unfortunately
@code{flex} does not presently generate the necessary directives to
``retarget'' the line numbers for those parts of @file{lex.yy.c} which
it generated.  So if there is an error in the generated code, a
meaningless line number is reported.)

@item -T
makes @code{flex} run in trace mode.  It will generate a lot of messages
to @file{stdout} concerning the form of the input and the resultant
non-deterministic and deterministic finite automata.  This option is
mostly for use in maintaining @code{flex}.

@item -8
instructs @code{flex} to generate an 8-bit scanner, i.e., one which can
recognize 8-bit characters.  On some sites, @code{flex} is installed
with this option as the default.  On others, the default is 7-bit
characters.  To see which is the case, check the verbose (@samp{-v})
output for @samp{equivalence classes created}.  If the denominator of
the number shown is 128, then by default @code{flex} is generating 7-bit
characters.  If it is 256, then the default is 8-bit characters and the
@samp{-8} flag is not required (but may be a good idea to keep the
scanner specification portable).  Feeding a 7-bit scanner 8-bit
characters will result in infinite loops, bus errors, or other such
fireworks, so when in doubt, use the flag.  Note that if equivalence
classes are used, 8-bit scanners take only slightly more table space
than 7-bit scanners (128 bytes, to be exact); if equivalence classes are
not used, however, then the tables may grow up to twice their 7-bit
size.

@item -C@r{[}efmF@r{]}
controls the degree of table compression.

@samp{-Ce} directs @code{flex} to construct equivalence classes, i.e.,
sets of characters which have identical lexical properties (for example,
if the only appearance of digits in the @code{flex} input is in the
character class @samp{[0-9]} then the digits @samp{0}, @samp{1},
@dots{}, @samp{9} will all be put in the same equivalence class).
Equivalence classes usually give dramatic reductions in the final
table/object file sizes (typically a factor of 2--5) and are pretty
cheap performance-wise (one array look-up per character scanned).

@samp{-Cf} specifies that the full scanner tables should be
generated; @code{flex} will not compress the tables by taking
advantages of similar transition functions for different states.

@samp{-CF} specifies that the alternate fast scanner representation
(described above under the @samp{-F} flag) should be used.

@samp{-Cm} directs @code{flex} to construct meta-equivalence classes,
which are sets of equivalence classes (or characters, if equivalence
classes are not being used) that are commonly used together.
Meta-equivalence classes are often a big win when using compressed
tables, but they have a moderate performance impact (one or two
@code{if} tests and one array look-up per character scanned).

A lone @samp{-C} specifies that the scanner tables should be compressed,
but @code{flex} is not to use either equivalence classes nor
meta-equivalence classes.

The options @samp{-Cf} or @samp{-CF} and @samp{-Cm} do not make sense
together.  There is no opportunity for meta-equivalence classes if the
table is not compressed.  Otherwise the options may be freely mixed.

The default setting is @samp{-Cem}, which specifies that @code{flex}
should generate equivalence classes and meta-equivalence classes.  This
setting provides the highest degree of table compression.  You can trade
off faster-executing scanners at the cost of larger tables with the
following generally being true:

@example
@group
    @r{slowest and smallest}
          -Cem
          -Cm
          -Ce
          -C
          -C@{f,F@}e
          -C@{f,F@}
    @r{fastest and largest}
@end group
@end example

Note that scanners with the smallest tables are usually generated and
compiled the quickest, so during development you will usually want to
use the default, maximal compression.

@samp{-Cfe} is often a good compromise between speed and size for
production scanners.

@samp{-C} options are not cumulative;  whenever  the  flag  is
encountered, the previous @samp{-C} settings are forgotten.

@item -S@var{skeleton_file}
overrides the default skeleton  file  from  which  @code{flex}
constructs its scanners.  You'll never need this option
unless you are doing @code{flex} maintenance or development.
@end table

@node Performance
@chapter Performance Considerations

The main design goal of @code{flex} is that it generate high
performance scanners.  It has been optimized for dealing well with large
sets of rules.  Aside from the effects of table compression on scanner
speed outlined above, there are a number of options/actions which
degrade performance.  These are, from most expensive to least:

@display
@code{REJECT}

pattern sets that require backtracking
arbitrary trailing context

@samp{^} beginning-of-line operator
@code{yymore}
@end display

@noindent
with the first three all being quite expensive and the last two being
quite cheap.

@code{REJECT} should be avoided at all costs  when  performance  is
important.  It is a particularly expensive option.

Getting rid of backtracking is messy and often may be an enormous amount
of work for a complicated scanner.  In principle, one begins by using
the @samp{-b} flag to generate a @file{lex.backtrack} file.  For
example, on the input

@example
%%
foo        return TOK_KEYWORD;
foobar     return TOK_KEYWORD;
@end example

@noindent
the file looks like:

@example
State #6 is non-accepting -
 associated rule line numbers:
       2       3
 out-transitions: [ o ]
 jam-transitions: EOF [ \001-n  p-\177 ]

State #8 is non-accepting -
 associated rule line numbers:
       3
 out-transitions: [ a ]
 jam-transitions: EOF [ \001-`  b-\177 ]

State #9 is non-accepting -
 associated rule line numbers:
       3
 out-transitions: [ r ]
 jam-transitions: EOF [ \001-q  s-\177 ]

Compressed tables always backtrack.
@end example

The first few lines tell us that there's a scanner state in which it can
make a transition on an @samp{o} but not on any other character, and
that in that state the currently scanned text does not match any rule.
The state occurs when trying to match the rules found at lines 2 and 3
in the input file.  If the scanner is in that state and then reads
something other than an @samp{o}, it will have to backtrack to find a
rule which is matched.  With a bit of headscratching one can see that
this must be the state it's in when it has seen @samp{fo}.  When this
has happened, if anything other than another @samp{o} is seen, the
scanner will have to back up to simply match the @samp{f} (by the
default rule).

The comment regarding State #8 indicates there's a problem when
@samp{foob} has been scanned.  Indeed, on any character other than a
@samp{b}, the scanner will have to back up to accept @samp{foo}.
Similarly, the comment for State #9 concerns when @samp{fooba} has been
scanned.

The final comment reminds us that there's no point going to all the
trouble of removing backtracking from the rules unless we're using
@w{@samp{-f}} or @samp{-F}, since there's no performance gain doing so with
compressed scanners.

The way to remove the backtracking is to add ``error'' rules:

@example
%%
foo         return TOK_KEYWORD;
foobar      return TOK_KEYWORD;

fooba       |
foob        |
fo          @{
            /* false alarm, not really a keyword */
            return TOK_ID;
            @}
@end example

Eliminating backtracking among a list of keywords can also be done using
a ``catch-all'' rule:

@example
%%
foo         return TOK_KEYWORD;
foobar      return TOK_KEYWORD;

[a-z]+      return TOK_ID;
@end example

This is usually the best solution when appropriate.

Backtracking messages tend to cascade.  With a complicated set of rules
it's not uncommon to get hundreds of messages.  If one can decipher
them, though, it often only takes a dozen or so rules to eliminate the
backtracking (though it's easy to make a mistake and have an error rule
accidentally match a valid token.  A possible future @code{flex} feature
will be to automatically add rules to eliminate backtracking).

Variable trailing context (where both the leading and trailing parts do
not have a fixed length) entails almost the same performance loss as
@code{REJECT} (i.e., substantial).  So when possible a rule like:

@example
%%
mouse|rat/(cat|dog)   run();
@end example

@noindent
is better written:

@example
%%
mouse/cat|dog         run();
rat/cat|dog           run();
@end example

@noindent
or as

@example
%%
mouse|rat/cat         run();
mouse|rat/dog         run();
@end example

Note that here the special @samp{|} action does not provide any savings,
and can even make things worse (@pxref{Bugs,,Deficiencies and Bugs}).

Another area where the user can increase a scanner's performance (and
one that's easier to implement) arises from the fact that the longer the
tokens matched, the faster the scanner will run.  This is because with
long tokens the processing of most input characters takes place in the
(short) inner scanning loop, and does not often have to go through the
additional work of setting up the scanning environment (e.g.,
@code{yytext}) for the action.  Recall the scanner for C comments:

@example
%x comment
%%
        int line_num = 1;

"/*"         BEGIN(comment);

<comment>[^*\n]*
<comment>"*"+[^*/\n]*
<comment>\n             ++line_num;
<comment>"*"+"/"        BEGIN(INITIAL);
@end example

@noindent
This could be sped up by writing it as:

@example
%x comment
%%
        int line_num = 1;

"/*"         BEGIN(comment);

<comment>[^*\n]*
<comment>[^*\n]*\n      ++line_num;
<comment>"*"+[^*/\n]*
<comment>"*"+[^*/\n]*\n ++line_num;
<comment>"*"+"/"        BEGIN(INITIAL);
@end example

Now instead of each newline requiring the processing of another action,
recognizing the newlines is ``distributed'' over the other rules to keep
the matched text as long as possible.  Note that adding rules does not
slow down the scanner!  The speed of the scanner is independent of the
number of rules or (modulo the considerations given at the beginning of
this section) how complicated the rules are with regard to operators
such as @samp{*} and @samp{|}.

A final example in speeding up a scanner: suppose you want to scan
through a file containing identifiers and keywords, one per line and
with no other extraneous characters, and recognize all the keywords.  A
natural first approach is:

@example
%%
asm      |
auto     |
break    |
@r{@dots{} etc @dots{}}
volatile |
while    /* it's a keyword */

.|\n     /* it's not a keyword */
@end example

@noindent
To eliminate the back-tracking, introduce a catch-all rule:

@example
%%
asm      |
auto     |
break    |
@r{@dots{} etc @dots{}}
volatile |
while    /* it's a keyword */

[a-z]+   |
.|\n     /* it's not a keyword */
@end example

Now, if it's guaranteed that there's exactly one word per line, then we
can reduce the total number of matches by a half by merging in the
recognition of newlines with that of the other tokens:

@example
%%
asm\n    |
auto\n   |
break\n  |
@r{@dots{} etc @dots{}}
volatile\n |
while\n  /* it's a keyword */

[a-z]+\n |
.|\n     /* it's not a keyword */
@end example

One has to be careful here, as we have now reintroduced backtracking
into the scanner.  In particular, while we know that there will never be
any characters in the input stream other than letters or newlines,
@code{flex} can't figure this out, and it will plan for possibly needing
backtracking when it has scanned a token like @samp{auto} and then the
next character is something other than a newline or a letter.
Previously it would then just match the @samp{auto} rule and be done,
but now it has no @samp{auto} rule, only a @samp{auto\n} rule.  To
eliminate the possibility of backtracking, we could either duplicate all
rules but without final newlines, or, since we never expect to encounter
such an input and therefore don't how it's classified, we can introduce
one more catch-all rule, this one which doesn't include a newline:

@example
%%
asm\n    |
auto\n   |
break\n  |
@r{@dots{} etc @dots{}}
volatile\n |
while\n  /* it's a keyword */
[a-z]+\n |
[a-z]+   |
.|\n     /* it's not a keyword */
@end example

Compiled with @samp{-Cf}, this is about as fast as one  can  get  a
@code{flex} scanner to go for this particular problem.

A final note: @code{flex} is slow when matching @code{NUL}'s, particularly
when  a  token  contains multiple @code{NUL}'s.  It's best to write
rules which match short amounts of text if it's  anticipated
that the text will often include @code{NUL}'s.

@node Incompatibilities
@chapter Incompatibilities with @code{lex} and @sc{posix}

@code{flex} is a rewrite of the Unix tool @code{lex} (the two
implementations do not share any code, though), with some extensions
and incompatibilities, both of which are of concern to those who wish to
write scanners acceptable to either implementation.  At present, the
@sc{posix} @code{lex} draft is very close to the original @code{lex}
implementation, so some of these incompatibilities are also in
conflict with the @sc{posix} draft.  But the intent is that except as noted
below, @code{flex} as it presently stands will ultimately be @sc{posix}
conformant (i.e., that those areas of conflict with the @sc{posix} draft will
be resolved in @code{flex}'s favor).  Please bear in mind that all the
comments which follow are with regard to the @sc{posix} draft standard of
Summer 1989, and not the final document (or subsequent drafts); they are
included so @code{flex} users can be aware of the standardization issues
and those areas where @code{flex} may in the near future undergo changes
incompatible with its current definition.

@code{flex} is fully compatible with @code{lex} with the following exceptions:

@itemize @bullet
@item
The undocumented @code{lex} scanner internal variable @code{yylineno} is
not supported.  It is difficult to support this option efficiently,
since it requires examining every character scanned and reexamining the
characters when the scanner backs up.  Things get more complicated when
the end of buffer or file is reached or a @code{NUL} is scanned (since
the scan must then be restarted with the proper line number count), or
the user uses the @code{yyless}, @code{unput}, or @code{REJECT} actions,
or the multiple input buffer functions.

The fix is to add rules which, upon seeing a newline, increment
@code{yylineno}.  This is usually an easy process, though it can be a
drag if some of the patterns can match multiple newlines along with
other characters.

@code{yylineno} is not part of the @sc{posix} draft.

@item
The @code{input} routine is not redefinable, though it may be called to
read characters following whatever has been matched by a rule.  If
@code{input} encounters an end-of-file the normal @code{yywrap}
processing is done.  A ``real'' end-of-file is returned by @code{input}
as @code{EOF}.

Input is instead controlled by redefining the @code{YY_INPUT} macro.

The @code{flex} restriction that @code{input} cannot be redefined is in
accordance with the @sc{posix} draft, but @code{YY_INPUT} has not yet been
accepted into the draft (and probably won't; it looks like the draft
will simply not specify any way of controlling the scanner's input other
than by making an initial assignment to @file{yyin}).

@item
@code{flex} scanners do not use @code{stdio} for input.  Because of
this, when writing an interactive scanner one must explicitly call
@code{fflush} on the stream associated with the terminal after writing
out a prompt.  With @code{lex} such writes are automatically flushed
since @code{lex} scanners use @code{getchar} for their input.  Also,
when writing interactive scanners with @code{flex}, the @samp{-I} flag
must be used.

@item
@code{flex} scanners are not as reentrant as @code{lex} scanners.  In
particular,  if  you have an interactive scanner and an
interrupt handler which long-jumps out of the  scanner,
and  the  scanner is subsequently called again, you may
get the following message:

@smallexample
fatal flex scanner internal error--end of buffer missed
@end smallexample

@noindent
To reenter the scanner, first use

@example
yyrestart( yyin );
@end example

@item
@code{output} is not supported.  Output from the @code{ECHO} macro is
done to the file-pointer @code{yyout} (default @code{stdout}).

The @sc{posix} draft mentions that an @code{output} routine exists but
currently gives no details as to what it does.

@item
@code{lex} does not support exclusive start  conditions  (@samp{%x}),
though they are in the current @sc{posix} draft.

@item
When definitions are expanded, @code{flex}  encloses  them  in
parentheses.  With @code{lex}, the following:

@example
NAME    [A-Z][A-Z0-9]*
%%
foo@{NAME@}?      printf( "Found it\n" );
%%
@end example

will not match the string @samp{foo} because, when the macro is
expanded, the rule is equivalent to @samp{foo[A-Z][A-Z0-9]*?} and the
precedence is such that the @samp{?} is associated with
@samp{[A-Z0-9]*}.  With @code{flex}, the rule will be expanded to
@samp{foo([A-Z][A-Z0-9]*)?} and so the string @samp{foo} will match.
Note that because of this, the @samp{^}, @samp{$}, @samp{<@var{s}>},
@samp{/}, and @samp{<<EOF>>} operators cannot be used in a @code{flex}
definition.

The @sc{posix} draft interpretation is the same as in @code{flex}.

@item
To specify a character class which matches anything but a left bracket
(@samp{]}), in @code{lex} one can use @samp{[^]]} but with @code{flex}
one must use @samp{[^\]]}.  The latter works with @code{lex}, too.

@item
The lex @samp{%r} (generate a Ratfor scanner)  option  is  not
supported.  It is not part of the @sc{posix} draft.

@item
If you are providing your own @code{yywrap} routine, you must include a
@samp{#undef yywrap} in the definitions section (section 1).  Note that
the @samp{#undef} will have to be enclosed in @samp{%@{@}}.

The @sc{posix} draft specifies that @code{yywrap} is a function, and this is
very unlikely to change; so @code{flex} users are warned that
@code{yywrap} is likely to be changed to a function in the near future.

@item
After a call to @code{unput}, @code{yytext} and @code{yyleng} are
undefined until the next token is matched.  This is not the case with
@code{lex} or the present @sc{posix} draft.

@item
The precedence of the @samp{@{@}} (numeric range) operator is different.
@code{lex} interprets @samp{abc@{1,3@}} as ``match one, two, or three
occurrences of @samp{abc},'' whereas @code{flex} interprets it as
``match @samp{ab} followed by one, two, or three occurrences of
@samp{c}.''  The latter is in agreement with the current @sc{posix} draft.

@item
The precedence of the @samp{^}  operator  is  different.   @code{lex}
interprets  @samp{^foo|bar}  as  ``match  either @samp{foo} at the
beginning of a line, or @samp{bar} anywhere'',  whereas  @code{flex}
interprets  it  as ``match either @samp{foo} or @samp{bar} if they
come at the beginning of a line''.   The  latter  is  in
agreement with the current @sc{posix} draft.

@item
To refer to @code{yytext} outside of the scanner source file, the
correct definition with @code{flex} is @samp{extern char *yytext} rather
than @samp{extern char yytext[]}.  This is contrary to the current @sc{posix}
draft but a point on which @code{flex} will not be changing, as the
array representation entails a serious performance penalty.  It is
hoped that the @sc{posix} draft will be amended to support the @code{flex}
variety of declaration (as this is a fairly painless change to require
of @code{lex} users).

@item
@file{yyin} is initialized by @code{lex} to be @code{stdin};
@code{flex}, on the other hand, initializes @file{yyin} to @code{NULL}
and then assigns it to stdin the first time the scanner is called,
providing @file{yyin} has not already been assigned to a non-@code{NULL}
value.  The difference is subtle, but the net effect is that with
@code{flex} scanners, @file{yyin} does not have a valid value until the
scanner has been called.

@item
The special table-size declarations such as @samp{%a} supported by
@code{lex} are not required by @code{flex} scanners; @code{flex} ignores
them.

@item
The name @code{FLEX_SCANNER} is @code{#define}'d so scanners  may  be
written for use with either @code{flex} or @code{lex}.
@end itemize

The following @code{flex} features are not included in lex  or  the
@sc{posix} draft standard:

@display
@code{yyterminate()}
@code{<<EOF>>}
@code{YY_DECL}
@code{#line} directives
@samp{%@{@}} around actions
@code{yyrestart()}
comments beginning with @samp{#} (deprecated)
multiple actions on a line
@end display

This last feature refers to the fact that with @code{flex} you can put
multiple actions on the same line, separated with semicolons, while with
@code{lex}, the following

@example
foo    handle_foo(); ++num_foos_seen;
@end example

@noindent
is (rather surprisingly) truncated to

@example
foo    handle_foo();
@end example

@code{flex} does not truncate the action.  Actions that are not enclosed
in braces are simply terminated at the end of the line.

@node Diagnostics
@chapter Diagnostic Messages

@table @code
@item reject_used_but_not_detected undefined
@itemx yymore_used_but_not_detected undefined
These errors can occur at compile time.  They indicate that the scanner
uses @code{REJECT} or @code{yymore} but that @code{flex} failed to
notice the fact, meaning that @code{flex} scanned the first two sections
looking for occurrences of these actions and failed to find any, but
somehow you snuck some in (via a @code{#include} file, for example).
Make an explicit reference to the action in your @code{flex} input file.
(Note that previously @code{flex} supported a
@code{%used}/@code{%unused} mechanism for dealing with this problem;
this feature is still supported but now deprecated, and will go away
soon unless the author hears from people who can argue compellingly that
they need it.)

@item flex scanner jammed
A scanner compiled with @samp{-s} has encountered an input string which
wasn't matched by any of its rules.

@item flex input buffer overflowed
A scanner rule matched a string long enough to overflow the scanner's
internal input buffer (16K bytes by default---controlled by
@code{YY_BUF_SIZE} in @file{flex.skel}.  Note that to redefine this
macro, you must first @code{#undefine} it).

@item scanner requires -8 flag
Your scanner specification includes recognizing 8-bit characters and you
did not specify the @samp{-8} flag (and your site has not installed
@code{flex} with @samp{-8} as the default).

@item fatal flex scanner internal error--end of buffer missed
This can occur in an scanner which is reentered after a long-jump has
jumped out (or over) the scanner's activation frame.  Before reentering
the scanner, use:

@example
yyrestart( yyin );
@end example

@item too many %t classes!
You managed to put every single character into its own @code{%t} class.
@code{flex} requires that at least one of the classes share characters.
@end table

@node Bugs
@chapter Deficiencies and Bugs

Some trailing context patterns cannot be properly matched and generate
warning messages (@samp{Dangerous trailing context}).  These are
patterns where the ending of the first part of the rule matches the
beginning of the second part, such as @samp{zx*/xy*}, where the
@samp{x*} matches the @samp{x} at the beginning of the trailing context.
(Note that the @sc{posix} draft states that the text matched by such patterns
is undefined.)

For some trailing context rules, parts which are actually fixed-length
are not recognized as such, leading to the abovementioned performance
loss.  In particular, parts using @samp{|} or @{n@} (such as
@samp{foo@{3@}}) are always considered variable-length.

Combining trailing context with the special @samp{|} action can result
in fixed trailing context being turned into the more expensive variable
trailing context.  For example, this happens in the following example:

@example
%%
abc      |
xyz/def
@end example

Use of @code{unput} invalidates @code{yytext} and @code{yyleng}.

Use of @code{unput} to push back more text than was  matched  can
result  in the pushed-back text matching a beginning-of-line
(@samp{^}) rule even though it didn't come at  the  beginning  of
the line (though this is rare!).

Pattern-matching of @code{NUL}'s is substantially slower than matching
other characters.

@code{flex} does not generate correct @code{#line} directives for code
internal to the scanner; thus, bugs in @file{flex.skel} yield bogus line
numbers.

Due to both buffering of input and read-ahead, you cannot intermix calls
to @file{stdio.h} routines, such as, for example, @code{getchar}, with
@code{flex} rules and expect it to work.  Call @code{input} instead.

The total table entries listed by the @samp{-v} flag excludes the number
of table entries needed to determine what rule has been matched.  The
number of entries is equal to the number of DFA states if the scanner
does not use @code{REJECT}, and somewhat greater than the number of
states if it does.
@c FIXME what is "DFA"?

@code{REJECT} cannot be used with the @samp{-f} or @samp{-F} options.

Some of the macros, such as @code{yywrap}, may in the future become
functions which live in the @code{-lfl} library.  This will doubtless
break a lot of code, but may be required for @sc{posix} compliance.

The @code{flex} internal algorithms need documentation.

@node Acknowledgements
@chapter Contributors to @code{flex}

The author of @code{flex} is Vern Paxson, with the help of many ideas
and much inspiration from Van Jacobson.  Original version by Jef
Poskanzer.  The fast table representation is a partial implementation of
a design done by Van Jacobson.  The implementation was done by Kevin
Gong and Vern Paxson.

Thanks to the many @code{flex} beta-testers, feedbackers, and
contributors, especially Casey Leedom, @code{benson@@odi.com}, Keith Bostic,
Frederic Brehm, Nick Christopher, Jason Coughlin, Scott David Daniels,
Leo Eskin, Chris Faylor, Eric Goldman, Eric Hughes, Jeffrey R. Jones,
Kevin B. Kenny, Ronald Lamprecht, Greg Lee, Craig Leres, Mohamed el
Lozy, Jim Meyering, Marc Nozell, Esmond Pitt, Jef Poskanzer, Jim
Roskind, Dave Tallman, Frank Whaley, Ken Yap, and those whose names have
slipped my marginal mail-archiving skills but whose contributions are
appreciated all the same.

Thanks to Keith Bostic, John Gilmore, Craig Leres, Bob Mulcahy, Rich
Salz, and Richard Stallman for help with various distribution headaches.

Thanks to Esmond Pitt and Earle Horton for 8-bit character support; to
Benson Margulies and Fred Burke for C++ support; to Ove Ewerlid for the
basics of support for @code{NUL}'s; and to Eric Hughes for the basics of
support for multiple buffers.

Work is being done on extending @code{flex} to generate scanners in
which the state machine is directly represented in C code rather than
tables.  These scanners may well be substantially faster than those
generated using @samp{-f} or @samp{-F}.  If you are working in this area
and are interested in comparing notes and seeing whether redundant work
can be avoided, contact Ove Ewerlid
(@code{ewerlid@@mizar.DoCS.UU.SE}).

This work was primarily done when I was at the Real Time Systems Group
at the Lawrence Berkeley Laboratory in Berkeley, CA.  Many thanks to all
there for the support I received.

Send comments to:

@display
Vern Paxson
Computer Systems Engineering
Bldg. 46A, Room 1123
Lawrence Berkeley Laboratory
Berkeley, CA 94720

vern@@ee.lbl.gov
@end display

@contents

@bye
