elex.texi

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

\input texinfo                  @c -*-texinfo-*-
@c $Id: elex.texi,v 1.5 1997/05/19 02:58:15 matt Exp $

@c %**start of header
@setfilename elex.info
@settitle Elex User's Guide
@c %**end of header

@finalout

@titlepage
@title  Elex
@subtitle User's Guide
@author Matthew Phillips <mpp@@ozemail.com.au>
@end titlepage

@ifinfo
@dircategory Documentation
@direntry
* Elex: (elex).                 Scanner generator package.
@end direntry
@end ifinfo

@c ----------------------------------------------------------------------
@ifinfo
@node    Top, Overview, (dir), (dir)
@top
This is the @var{Elex} user manual.

@menu
* Overview::                    An overview of the Elex package.
* An Example::                  A complete example of using Elex.
* Scanner Scripts::             Definition of scanner scripts.
* The Elex Tool Set::           Description of the tools in this package.
* Code Generation::             How to generate source for a scanner.
* Glossary::                    
* Index::                       

 --- The Detailed Node Listing ---

Overview

* What is Elex?::               What is this thing?
* Why Use Elex?::               Why use this thing?
* The Elex Package::            What you get with this thing.
* Requirements::                What you need to run this thing.
* Future Development::          Where this thing's going.

An Example

* The Calculator::              The calculator example.
* The Scanner Script::          The script for the calculator.
* Testing the Script::          How you test the script.
* Generating the Scanner::      How you make the scanner.
* Using the Scanner::           How to use the scanner.

Scanner Scripts

* Scanner Script Structure::    The parts of a scanner script described.
* Regular Expressions::         Regular expressions in detail
* Productions::                 Productions described.
* Code Fragments::              Code fragment formatting.
* Testing Regular Expressions::  How to quickly test regular expressions.
* Custom Scanner Engines::      Using non-standard scanner engines.
* Multi-language Scanners::     How to handle more than one language.

Scanner Script Structure

* The Symbols Section::         Defines symbol names.
* The Defines Section::         Defines symbolic regular expressions.
* The Productions Section::     Defines how the scanner behaves.

Regular Expressions

* Elex Compared to Perl::       Elex regular expressions against Perl's.
* Operator Precedence::         Operator binding order.
* Regular Expression Grammar::  The BNF grammar for regular expressions.

Productions

* Production Matching Order::   How Elex handles production overlap.

The Elex Tool Set

* The Front End::               The central point of control.
* The Compiler::                The bit that does the work.
* The Debugger::                Use this when something doesn't work.

The Front End

* Generating Code::             Making source code from a script.
* Debugging::                   Using the debugger.
* Compile Only::                Create some useless intermediate files.
* The elex.cfg File::           The Elex configuration file.
* Default Target Language::     The default language for code generation.

Code Generation

* 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.

C++ Code Generator

* 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

$Revision: 1.5 $

@end ifinfo
@c ----------------------------------------------------------------------


@c ----------------------------------------------------------------------
@node    Overview, An Example, Top, Top
@chapter Overview

@menu
* What is Elex?::               What is this thing?
* Why Use Elex?::               Why use this thing?
* The Elex Package::            What you get with this thing.
* Requirements::                What you need to run this thing.
* Future Development::          Where this thing's going.
@end menu

@c ----------------------------------------------------------------------
@node    What is Elex?, Why Use Elex?, Overview, Overview
@section What is Elex?
@cindex introduction to Elex
@cindex scanner, defined
@cindex tokeniser, defined
@cindex lexer, defined
@cindex FSM code generator
@cindex multi-language support

@var{Elex} is a package that generates a scanner (sometimes called
@dfn{lexer} or @dfn{tokeniser}) from a specification oriented around
regular expressions.  A scanner is the part of a program that finds
compound symbols in a stream of characters.  For example, a scanner for
this document would need to recognise words, numbers, whitespace and
punctuation.  Scanners are a very common part of an application, yet
much of the time they are written by hand, a tedious and error-prone
task.  @var{Elex} allows you to simply specify the scanner you want and
then have the scanner generated for you.

@c ----------------------------------------------------------------------
@node    Why Use Elex?, The Elex Package, What is Elex?, Overview
@section Why Use Elex?
@cindex Elex, why to use it
@cindex why use Elex?

While there are many scanner generators around (the best known of which
is the venerable @var{LEX}), almost all of these are specific to a
particular language, generally C or C++.  So if you use a variety of
languages then you'll probably have to use a number of different scanner
generator tools.  But the whole point of using a scanner generator is to
speed the process up, not slow it down by having to learn the in's and
out's of each scanner package.  @var{Elex} solves this problem: it
supports multiple languages and is @emph{easy-to-use} so you can get up
to speed quickly.  Hopefully :)

@c ----------------------------------------------------------------------
@node    The Elex Package, Requirements, Why Use Elex?, Overview
@section The Elex Package
@cindex Elex package
@cindex elexc
@cindex elexd
@cindex elex
@cindex Graphviz, code generator
@cindex code generator, Graphviz
@cindex Graphviz, WWW reference

@emph{Note}: This release of @var{Elex} is missing some features that
are planned for 1.0.  The features that are implemented work, but have
not been exposed to the nasty real world.  The biggest limitation in
this release is that @var{Elex} only supports C++ scanners.

The current release of @var{Elex} has the following components:

@itemize @bullet

@item
elex: This is the front end for the @var{Elex} tool set, similar in
purpose to @var{gcc}. It integrates the compiler, debugger and any
number of code generators.

@item
elexc: The @var{Elex} compiler.

@item
elexd: A debugger that allows the regular expressions in @var{Elex}
scripts to be tested before being used in a scanner.

@item
C++ code generator: generates a C++ scanner.

@item
Graphviz code generator: this generates `.dot' files that can be used
with Graphviz (@url{http://www.research.att.com/sw/tools/graphviz/}) to
visualise the FSM that @var{Elex} generates for a scanner.
@end itemize

@c ----------------------------------------------------------------------
@node    Requirements, Future Development, The Elex Package, Overview
@section Requirements
@cindex requirements of Elex
@cindex Elex, requirements

These `requirements' are just what have been used to develop @var{Elex}:
it @i{should} compile under g++ (or even other C++ compilers) on any
vaguely POSIX-compliant platform (it ran on a Solaris system not too
long ago).

@itemize @bullet

@item
Linux 1.x, 2.x or other Unix'ish platform.

@item
g++ version 2.7.2.

@item
GNU make 3.74.  The supplied Makefiles use a few features specific to
GNU make.  If enough people want them, there'll be some non-GNU
Makefiles in the future.

@item
Perl 5.000.  The installation script and front end are both written in
@var{Perl}.  If by some miracle you don't already have it, download it
from @url{http://www.perl.org/CPAN}.

@end itemize

@c ----------------------------------------------------------------------
@node    Future Development,  , Requirements, Overview
@section Future Development
@cindex future development of Elex
@cindex limitations of Elex
@cindex regular expressions, limitations in elex
@cindex Ada 95 code generation
@cindex Java code generation

This section lists a number of features which aren't in this release,
but which are planned for version 1.0.

@itemize @bullet

@item
@b{Enhanced regular expressions}: @var{Elex} aims to support @var{Perl}
`standard' regular expressions (with a few extensions), but currently
lacks a number of standard operators, most notably `^', and `$'.  The
vanilla regular expressions in @var{Elex} allow repetition with `*',
`+', and `?', alternation with `|', sets using `[...]', wildcards with
`.'  and precedence using `(...)'.  Subexpressions are not yet
supported.  Don't get all depressed though, these vanilla regular
expressions have been sufficient for a number of fairly advanced
scanners.  Regular expressions will be the first part of @var{Elex} to
be enhanced: version 1.0 of @var{Elex} will support most---if not
all---of @var{Perl}'s regular expression syntax.  @xref{Elex Compared to
Perl} for a detailed list of differences between @var{Elex} and
@var{Perl} regular expressions.

@item
@b{More languages}: code generators for Java and Ada 95 (in that order)
are next highest on the list of enhancements.  Java will be first
because (a) everyone thinks it's pretty sexy right now and (b) it's
close enough to C++ that it should be straightforward to translate the
C++ scanner driver.

@end itemize

@c ----------------------------------------------------------------------
@node       An Example, Scanner Scripts, Overview, Top
@chapter    An Example
@cindex example of a scanner
@cindex writing a scanner, an example
@cindex C++ scanner, an example

@menu
* The Calculator::              The calculator example.
* The Scanner Script::          The script for the calculator.
* Testing the Script::          How you test the script.
* Generating the Scanner::      How you make the scanner.
* Using the Scanner::           How to use the scanner.
@end menu

This section goes through an example which demonstrates the creation,
testing, compilation and use of an @var{Elex} C++ scanner.  With any
luck this will be the only part of this document that you need to read
from start to finish: the rest of the documentation should act as a
reference.

Note: the source code developed in this section, plus a Makefile can be
found in the @file{demo} subdirectory of the @var{Elex} installation.

@c ----------------------------------------------------------------------
@node       The Calculator, The Scanner Script, An Example, An Example
@section    The Calculator
@cindex calculator example
@cindex calculator grammar
@cindex BNF grammar for calculator example
@cindex bc calculator

Let's suppose you're sitting in your office one day, playing Tetris, and
suddenly your boss comes in and says `Jim, I need a calculator program.
It's got to handle double-precision arithmetic and have all the standard
mathematical operators, plus built-in @var{pi} and @var{e}.  And I need
it by lunchtime.'

Lunch is still a good hour away, so you finish the game and then start
thinking about whether your boss has flipped out and forgotten that
there about a billion calculator programs that already do what he wants.
In fact, you could just give your boss a copy of @var{bc}.  But then you
remember you have this sexy new package called @var{Elex} that you can
use here, so you decide to write some code.

First, being a good disciplined programmer, you write a grammar for the
expressions that the calculator will accept:

@example
@group
  <expr> ::= <term>   (  `+'  <term> )*
  <expr> ::= <term>   (  `-'  <term> )*
  <term> ::= <factor> (  `/'  <factor> )*
  <term> ::= <factor> (  `*'  <factor> )*
  <term> ::= <factor> ( `mod' <factor> )*
<factor> ::= number
<factor> ::= `(' <expr> `)'
<factor> ::= variable
number   ::= @var{0-9+(\.0-9+)?([eE][\+\-]?0-9+)?}
variable ::= @var{[a-zA-Z][a-zA-Z_]*}
@end group
@end example

For those who don't know, or care, what a @dfn{BNF grammar} is, this bit
isn't important.  What is important is that to implement a parser for