elex.texi

用于词法分析的词法分析器

@file{FooObject.h} and @file{FooParser.h}) and @var{Perl} (see
@file{FooObject.pm} and @file{FooParser.pm}).

@c ----------------------------------------------------------------------
@node       Default Target Language,  , The elex.cfg File, The Front End
@subsection Default Target Language
@cindex default target language
@cindex -l switch, default behavior

If you don't specify a language to the front end using `-l', it attempts
to guess the language by scanning the script for code fragments with a
language tag.  The first tag found is assumed to be the `primary'
language for the scanner and this is selected as the target.  If no tag
is found then the front end uses the value of the `codegen/default'
section in @file{elex.cfg} (this is set to `cpp' by default).  Finally,
if this section is missing, the front end gives up with an error
message.

@c ----------------------------------------------------------------------
@node       The Compiler, The Debugger, The Front End, The Elex Tool Set
@section    The Compiler
@cindex elexc
@cindex compiler
@cindex .esd files
@cindex .esc files
@cindex FSM, optimisation

The compiler (@file{elexc}) is the central part of the @var{Elex}
package.  It takes a @file{.elx} script file and generates a scanner
definition that is used by a code generator to make a scanner.  As the
compiler parses the script, it generates a consolidated FSM model for
all regular expressions found.  If the parse is successful, the FSM is
then transformed in a number of ways, which includes a global
optimisation to reduce the FSM to the smallest number of states.  The
FSM, along with other information about the scanner is then output to
standard output.  A @file{.ecf} file containing the code fragments from
the script is also generated.

@c ----------------------------------------------------------------------
@node       The Debugger,  , The Compiler, The Elex Tool Set
@section    The Debugger
@cindex elexd
@cindex debugger

The debugger is a sort of `code generator' for @var{Elex} that does not
actually generate any code, but instead matches its standard input
against the regular expressions in a script and reports what matched.
The debugger is built with exactly the same scanner engine as any C++
scanner, so it behaves in the same way as the scanner will in an
application.

The debugger can be invoked by running @file{elex} with the `-d' switch,
or by running @file{elexd} directly with the @file{.esd} file as a
command line argument.

@c ----------------------------------------------------------------------
@node       Code Generation, Glossary, The Elex Tool Set, Top
@chapter    Code Generation

This section discusses aspects of @var{Elex} code generation, including
generating and using C++ scanners, using the Graphviz code generator and
the concept of backtracking scanner engines.

@menu
* C++ Code Generator::          Generates a C++ scanner engine.
* Graphviz Code Generator::     A code generator that creates FSM diagrams.
* Backtracking Scanners::       Scanners that try every possible match.
@end menu

@c ----------------------------------------------------------------------
@node       C++ Code Generator, Graphviz Code Generator, Code Generation, Code Generation
@section    C++ Code Generator
@cindex C++, code generation
@cindex code generation, C++
@cindex ElexScanner

The C++ code generator generates a scanner built on the standard C++
scanner engine.  Specifically, the generated scanner is derived from the
@samp{ElexScanner} class which implements a full backtracking scanner
engine for C++ applications.

The generator works by creating a header file to specify a scanner class
with member functions which correspond to the productions in the script.
@xref{Generating the Scanner} for an example of such a header file.  To
implement the scanner, the generator creates a @file{.cpp} file which is
composed of data structures that describe the FSM to the scanner engine
and the appropriate code fragments from the script inserted as member
functions.

Because the code fragments for handling matches of a particular
production become member functions of the scanner engine, they are able
to manipulate the scanner engine's internals to some extent.  This is
usually exploited to further process matched text (eg. to remove quotes
from strings).  @xref{C++ Scanner Engine} for details on how to interact
with the scanner engine.

@menu
* Using a C++ Scanner::         How to use the scanner in C++ applications.
* C++ Scanner Engine::          Overview of the C++ scanner engine.
* XInputStream::                The scanner's view of an input stream.
@end menu

@c ----------------------------------------------------------------------
@node       Using a C++ Scanner, C++ Scanner Engine, C++ Code Generator, C++ Code Generator
@subsection Using a C++ Scanner
@cindex using a C++ scanner
@cindex C++ scanner, using

Sorry, this section isn't done yet, but @ref{Using the Scanner} should
give enough information on how to use a scanner in a C++ application.
Also see @file{demo/CalcParser.cpp}.

@c ----------------------------------------------------------------------
@node       C++ Scanner Engine, XInputStream, Using a C++ Scanner, C++ Code Generator
@subsection C++ Scanner Engine
@cindex C++ scanner engine
@cindex scanner engine, C++

The C++ scanner engine is an abstract class that all @var{Elex} C++
scanners inherit from.  It implements the logic required to `drive' any
scanner that, when combined with a scanner definition emitted by the
code generator, produces a working scanner.  This section describes the
public interface and relevant protected interfaces of the C++ scanner
engine.

@exdent @b{Public Interfaces}

@table @code

@item ElexScanner (ElexScannerData &data, XInputStream &input, int lookahead = 1)

This creates an instance of the scanner, using @code{data} to represent
the scanner definition generated by @var{Elex}.  @code{data} is a
structure emitted by the code generator: the scanner class passes it to
the @code{ElexScanner} constructor for you, so you only need supply the
@code{input} and @code{lookahead} parameters.

The @code{input} object is used by the scanner as its input.
@xref{XInputStream} for more information.

@code{lookahead} defines the number of symbols the scanner reads ahead
before reporting a match (default is 1).  By reading ahead, the scanner
can backtrack and retract symbol matches when an error occurs in order
to try other possible matches. @xref{Backtracking Scanners} for more
information on backtracking.

@item int getNext ()

Causes the scanner to read the next symbol from its input and return the
symbol value.  This symbol value is also returned by @code{getSymbol
()}.

@item int getSymbol ()

Returns the last symbol value matched by @code{getNext ()}.

@item string &getText ()

Returns the text matched by the last call to @code{getNext ()}.

@item  int getTextLine ()
@itemx int getTextColumn ()

Returns the line and column that the last symbol matched by
@code{getNext ()} began at (both row and column start at 0).

@item  void error (const string &message)
@itemx void warning (const string &message)

Generates error or warning at the current symbol, using @code{message}
as the error/warning message.

@item const ErrorMessageList &getErrors ()

Returns the current list of error/warning messages.

@end table

@exdent @b{Protected Interfaces}

In general, there is not much you should play with in the C++ scanner
engine's innards.  The bits you might need to use are listed below.

@table @code

@item string text

The text matched for the current symbol.  You may modify this as needed
to change the text reported as matched by @code{getText ()}.

@item   int symbolLine
@itemx  int symbolColumn

The current line and column that the last symbol started at.  These are
the values reported by @code{getTextLine ()} and @code{getTextColumn
()}.

@end table

@c ----------------------------------------------------------------------
@node       XInputStream,  , C++ Scanner Engine, C++ Code Generator
@subsection XInputStream
@cindex XInputStream

The @code{XInputStream} class encapsulates an @code{istream}, adding
services required by the C++ scanner engine. This section gives an
overview of @code{XInputStream} class only in case you're interested,
otherwise you can treat @code{XInputStream} as a `black box', using it
in the manner shown in @ref{Using the Scanner}.

@emph{Sorry, the rest of this section is under construction.}

@c ----------------------------------------------------------------------
@node       Graphviz Code Generator, Backtracking Scanners, C++ Code Generator, Code Generation
@section    Graphviz Code Generator
@cindex Graphviz, code generator
@cindex code generator, Graphviz
@cindex .dot files, generating
@cindex .gif files, generating
@cindex GIF files, generating
@cindex graphing the FSM
@cindex visualising the FSM

The Graphviz code generator generates a graph of the FSM constructed by
the @var{Elex} compiler to implement the scanner.  It does this by
generating a Graphviz @file{.dot} file that can be used with the
Graphviz toolset to generate a directed-graph visualisation of the FSM.

To generate a @file{.dot} file for a scanner, run the @var{Elex} front
end like this:

@example
> elex -l dot MyScanner.elx
@end example

This will generate a file called @file{MyScanner.dot}, which is a
standard Graphviz graph specification.  You can then generate a graph in
GIF format using the a command like:

@example
> dot -T gif MyScanner.dot > MyScanner.gif
@end example

You can download the Graphviz 1.0 package from
@url{http://www.research.att.com/sw/tools/graphviz/}.

@c ----------------------------------------------------------------------
@node       Backtracking Scanners,  , Graphviz Code Generator, Code Generation
@section    Backtracking Scanner
@cindex backtracking
@cindex greedy matching
@cindex speculative matching
@cindex lookahead

Scanning for regular expressions is an inherently non-deterministic
process.  Using a FSM representation and performing certain
manipulations can resolve some of this non-determinism, but murky areas
will always remain.  Example: what does a regular expression scanner do
when it has the choice of either accepting a character as part of the
current symbol, or terminating the current symbol and starting a new
one?  Most regular expression scanners are `greedy' in these cases; they
will always try to match the longest possible symbol.  But this can
result in the scanner failing to match legitimate symbols further on.

Assume we have a simplistic regular expression scanner that matches the
expression @code{for|forest|end}.  The scanner is then presented with
the input `forend'.  After the scanner has read `for', it can either
accept `for' as a symbol, or accept the `e' in the hope it will be able
to match `forest'.  The greedy rule specifies that the scanner continue,
and this results in a failure to match either `for' or `forest'.

To solve this problem, most regular expression scanners employ a
backtracking scheme that allows the scanner to mark points where it is
has been greedy (and possibly other points where it had more than one
choice) and return to them if an error occurs.  In the example above,
after finding the error, the scanner would simply backtrack to the point
where it had just read `for', accept `for' as a symbol and then continue
to successfully match `end'.

The @var{Elex} scanner engine employs such a backtracking scheme.  Its
design also allows speculative symbol matching which means that a symbol
match can be retracted by a backtrack operation.  When a certain number
of symbols have been speculatively matched, the oldest symbol is
`frozen' and reported as matched: after which it cannot be retracted.
You can specify the number of symbols that the scanner engine holds as
speculative matches by setting the `lookahead' parameter on the scanner
engine.  Usually the default setting of 1 gives acceptable matching
behavior with good performance.

@c ----------------------------------------------------------------------
@node       Glossary, Index, Code Generation, Top
@unnumbered Glossary

Note: this glossary is pretty sparse right now.  You'll probably be
better off using the index (@pxref{Index}).

@table @dfn
@item code fragment
A piece of source code from a programming language.

@item code generator
A module that plugs into the compiler to generate a scanner for a
particular language.

@item front end
The `elex' program that integrates the compiler, code generators and
debugger.

@item FSM
Finite State Machine: a graph of `states' connected by `edges'.  The
machine is always in one of the states in the graph, and may move to
other states to which the current state is connected by an edge.  In a
scanner, each edge has a character label associated with it, and only
edges whose label matches the current input character are followed.

@item production
A construct that defines a symbol or an event handler in a scanner
script.

@item scanner engine
A module of code that implements a generic @var{Elex} scanner.  A code
generator merges a scanner definition with a scanner engine to produce
the final scanner.

@end table

@c ----------------------------------------------------------------------
@node       Index,  , Glossary, Top
@unnumbered Index

@printindex cp

@contents
@bye