tply.tex

Yacc例子代码

\documentstyle[11pt]{article}

\title{TP Lex and Yacc -- The Compiler Writer's Tools for Turbo Pascal\\
       Version 4.1 User Manual}

\author{Albert Gr\"af\\
        Department of Musicinformatics\\
        Johannes Gutenberg-University Mainz\\
        \\
        [e-mail]}

\date{April 1998}

\setlength{\topmargin}{0cm}
\setlength{\oddsidemargin}{0cm}
\setlength{\evensidemargin}{0cm}
\setlength{\textwidth}{16cm}
\setlength{\textheight}{21cm}
%\setlength{\parindent}{0pt}
\parskip=4pt plus 1pt minus 1pt
\itemsep=0pt
\renewcommand{\baselinestretch}{1.1}
\unitlength=1mm
%\tolerance=500
%\parskip=0.1cm
\leftmargini 1.5em
\leftmarginii 1.5em \leftmarginiii 1.5em \leftmarginiv 1.5em \leftmarginv 1.5em
\leftmarginvi 1.5em

\begin{document}

\maketitle

\tableofcontents

\section{Introduction}

This document describes the TP Lex and Yacc compiler generator toolset.
These tools are designed especially to help you prepare compilers and
similar programs like text processing utilities and command language
interpreters with the Turbo Pascal (TM) programming language.

TP Lex and Yacc are Turbo Pascal adaptions of the well-known UNIX (TM)
utilities Lex and Yacc, which were written by M.E. Lesk and S.C. Johnson
at Bell Laboratories, and are used with the C programming language. TP Lex
and Yacc are intended to be approximately ``compatible'' with these programs.
However, they are an independent development of the author, based on the
techniques described in the famous ``dragon book'' of Aho, Sethi and Ullman
(Aho, Sethi, Ullman: {\em Compilers : principles, techniques and tools,\/}
Reading (Mass.), Addison-Wesley, 1986).

Version 4.1 of TP Lex and Yacc works with all recent flavours of Turbo/Borland
Pascal, including Delphi, and with the Free Pascal Compiler, a free Turbo
Pascal-compatible compiler which currently runs on DOS and Linux (other ports
are under development). Recent information about TP Lex/Yacc, and the sources
are available from the TPLY homepage:
\begin{quote}\begin{verbatim}
   http://www.musikwissenschaft.uni-mainz.de/~ag/tply
\end{verbatim}\end{quote}
For information about the Free Pascal Compiler, please refer to:
\begin{quote}\begin{verbatim}
   http://www.freepascal.org
\end{verbatim}\end{quote}

TP Lex and Yacc, like any other tools of this kind, are not intended for
novices or casual programmers; they require extensive programming experience
as well as a thorough understanding of the principles of parser design and
implementation to be put to work successfully. But if you are a seasoned
Turbo Pascal programmer with some background in compiler design and formal
language theory, you will almost certainly find TP Lex and Yacc to be a
powerful extension of your Turbo Pascal toolset.

This manual tells you how to get started with the TP Lex and Yacc programs
and provides a short description of these programs. Some knowledge about
the C versions of Lex and Yacc will be useful, although not strictly
necessary. For further reading, you may also refer to:

\begin{itemize}
   \item
      Aho, Sethi and Ullman: {\em Compilers : principles, techniques and
      tools.\/} Reading (Mass.), Addison-Wesley, 1986.
   \item
      Johnson, S.C.: {\em Yacc -- yet another compiler-compiler.\/} CSTR-32,
      Bell Telephone Laboratories, 1974.
   \item
      Lesk, M.E.: {\em Lex -- a lexical analyser generator.\/} CSTR-39, Bell
      Telephone Laboratories, 1975.
   \item
      Schreiner, Friedman: {\em Introduction to compiler construction with
      UNIX.\/} Prentice-Hall, 1985.
   \item
      The Unix Programmer's Manual, Sections `Lex' and `Yacc'.
\end{itemize}


\subsection*{Credits}

I would like to thank Berend de Boer ([e-mail]), who adapted TP Lex
and Yacc to take advantage of the large memory models in Borland Pascal 7.0
and Delphi, and Michael Van Canneyt ([e-mail]),
the maintainer of the Linux version of the Free Pascal compiler, who is
responsible for the Free Pascal port. And of course thanks are due to the many
TP Lex/Yacc users all over the world for their support and comments which
helped to improve these programs.


\subsection*{Getting Started}

Instructions on how to compile and install TP Lex and Yacc on all supported
platforms can be found in the \verb"README" file contained in the
distribution.

Once you have installed TP Lex and Yacc on your system, you can compile your
first TP Lex and Yacc program \verb"expr". \verb"Expr" is a simple desktop
calculator program contained in the distribution, which consists of a lexical
analyzer in the TP Lex source file \verb"exprlex.l" and the parser and main
program in the TP Yacc source file \verb"expr.y". To compile these programs,
issue the commands
\begin{quote}\begin{verbatim}
   lex exprlex
   yacc expr
\end{verbatim}\end{quote}
That's it! You now have the Turbo Pascal sources (\verb"exprlex.pas" and
\verb"expr.pas") for the \verb"expr" program. Use the Turbo Pascal
compiler to compile these programs as follows:
\begin{quote}\begin{verbatim}
   tpc expr
\end{verbatim}\end{quote}

(Of course, the precise compilation command depends on the type of compiler
you are using. Thus you may have to replace \verb"tpc" with \verb"bpc",
\verb"dcc" or \verb"dcc32", depending on the version of the
Turbo/Borland/Delphi compiler you have, and with \verb"ppc386" for the Free
Pascal compiler. If you are using TP Lex and Yacc with Free Pascal under
Linux, the corresponding commands are:
\begin{quote}\begin{verbatim}
   plex exprlex
   pyacc expr
   ppc386 expr
\end{verbatim}\end{quote}
Note that in the Linux version, the programs are named \verb"plex" and
\verb"pyacc" to avoid name clashes with the corresponding UNIX utilities.)

Having compiled \verb"expr.pas", you can execute the \verb"expr" program and
type some expressions to see it work (terminate the program with an empty
line).  There is a number of other sample TP Lex and Yacc programs (\verb".l"
and \verb".y" files) in the distribution, including a TP Yacc cross reference
utility and a complete parser for Standard Pascal.

The TP Lex and Yacc programs recognize some options which may be specified
anywhere on the command line. E.g.,
\begin{quote}\begin{verbatim}
   lex -o exprlex
\end{verbatim}\end{quote}
runs TP Lex with ``DFA optimization'' and
\begin{quote}\begin{verbatim}
   yacc -v expr
\end{verbatim}\end{quote}
runs TP Yacc in ``verbose'' mode (TP Yacc generates a readable description
of the generated parser).

The TP Lex and Yacc programs use the following default filename extensions:
\begin{itemize}
   \item \verb".l": TP Lex input files
   \item \verb".y": TP Yacc input files
   \item \verb".pas": TP Lex and Yacc output files
\end{itemize}
As usual, you may overwrite default filename extensions by explicitly
specifying suffixes.

If you ever forget how to run TP Lex and Yacc, you can issue the command
\verb"lex" or \verb"yacc" (resp.\ \verb"plex" or \verb"pyacc")
without arguments to get a short summary of the command line syntax.

\section{TP Lex}

This section describes the TP Lex lexical analyzer generator.

\subsection{Usage}

\begin{quote}\begin{verbatim}
lex [options] lex-file[.l] [output-file[.pas]]
\end{verbatim}\end{quote}

\subsection{Options}

\begin{description}
   \item[\verb"-v"]
      ``Verbose:'' Lex generates a readable description of the generated
      lexical analyzer, written to lex-file with new extension \verb".lst".
   \item[\verb"-o"]
      ``Optimize:'' Lex optimizes DFA tables to produce a minimal DFA.
\end{description}

\subsection{Description}

TP Lex is a program generator that is used to generate the Turbo Pascal
source code for a lexical analyzer subroutine from the specification
of an input language by a regular expression grammar.

TP Lex parses the source grammar contained in \verb"lex-file" (with default
suffix \verb".l") and writes the constructed lexical analyzer subroutine
to the specified \verb"output-file" (with default suffix \verb".pas"); if no
output file is specified, output goes to \verb"lex-file" with new suffix
\verb".pas." If any errors are found during compilation, error messages are
written to the list file (\verb"lex-file" with new suffix \verb".lst").

The generated output file contains a lexical analyzer routine, \verb"yylex",
implemented as:
\begin{quote}\begin{verbatim}
   function yylex : Integer;
\end{verbatim}\end{quote}

This routine has to be called by your main program to execute the lexical
analyzer. The return value of the \verb"yylex" routine usually denotes the
number of a token recognized by the lexical analyzer (see the \verb"return"
routine in the \verb"LexLib" unit). At end-of-file the \verb"yylex" routine
normally returns \verb"0".

The code template for the \verb"yylex" routine may be found in the
\verb"yylex.cod" file. This file is needed by TP Lex when it constructs the
output file. It must be present either in the current directory or in the
directory from which TP Lex was executed (TP Lex searches these directories in
the indicated order). (NB: For the Linux/Free Pascal version, the code
template is searched in some directory defined at compile-time instead of the
execution path, usually /usr/lib/fpc/lexyacc.)

The TP Lex library (\verb"LexLib") unit is required by programs using
Lex-generated lexical analyzers; you will therefore have to put an appropriate
\verb"uses" clause into your program or unit that contains the lexical
analyzer routine. The \verb"LexLib" unit also provides various useful utility
routines; see the file \verb"lexlib.pas" for further information.

\subsection{Lex Source}

A TP Lex program consists of three sections separated with the \verb"%%"
delimiter:

\begin{quote}\begin{verbatim}
definitions
%%
rules
%%
auxiliary procedures
\end{verbatim}\end{quote}

All sections may be empty. The TP Lex language is line-oriented; definitions
and rules are separated by line breaks. There is no special notation for
comments, but (Turbo Pascal style) comments may be included as Turbo Pascal
fragments (see below).

The definitions section may contain the following elements:
\begin{itemize}
   \item
      regular definitions in the format:
      \begin{quote}\begin{verbatim}
   name   substitution
      \end{verbatim}\end{quote}
      which serve to abbreviate common subexpressions. The \verb"{name}"
      notation causes the corresponding substitution from the definitions
      section to be inserted into a regular expression. The name must be
      a legal identifier (letter followed by a sequence of letters and digits;
      the underscore counts as a letter; upper- and lowercase are distinct).
      Regular definitions must be non-recursive.
   \item
      start state definitions in the format:
      \begin{quote}\begin{verbatim}
   %start name ...
      \end{verbatim}\end{quote}
      which are used in specifying start conditions on rules (described
      below). The \verb"%start" keyword may also be abbreviated as \verb"%s"
      or \verb"%S".
   \item
      Turbo Pascal declarations enclosed between \verb"%{" and \verb"%}".
      These will be inserted into the output file (at global scope). Also,
      any line that does not look like a Lex definition (e.g., starts with
      blank or tab) will be treated as Turbo Pascal code. (In particular,
      this also allows you to include Turbo Pascal comments in your Lex
      program.)
\end{itemize}

The rules section of a TP Lex program contains the actual specification of
the lexical analyzer routine. It may be thought of as a big \verb"CASE"
statement discriminating over the different patterns to be matched and listing the
corresponding statements (actions) to be executed. Each rule consists of a
regular expression describing the strings to be matched in the input, and a
corresponding action, a Turbo Pascal statement to be executed when the
expression matches. Expression and statement are delimited with whitespace
(blanks and/or tabs). Thus the format of a Lex grammar rule is:

\begin{quote}\begin{verbatim}
   expression      statement;
\end{verbatim}\end{quote}

Note that the action must be a single Turbo Pascal statement terminated
with a semicolon (use \verb"begin ... end" for compound statements). The
statement may span multiple lines if the successor lines are indented with
at least one blank or tab. The action may also be replaced by the \verb"|"
character, indicating that the action for this rule is the same as that for
the next one.

The TP Lex library unit provides various variables and routines which are
useful in the programming of actions. In particular, the \verb"yytext" string
variable holds the text of the matched string, and the \verb"yyleng" Byte
variable its length.

Regular expressions are used to describe the strings to be matched in a
grammar rule. They are built from the usual constructs describing character
classes and sequences, and operators specifying repetitions and alternatives.
The precise format of regular expressions is described in the next section.

The rules section may also start with some Turbo Pascal declarations
(enclosed in \verb"%{ %}") which are treated as local declarations of the
actions routine.