%
-% Copyright 2001-2007 Adrian Thurston <thurston@cs.queensu.ca>
+% Copyright 2001-2009 Adrian Thurston <thurston@complang.org>
%
% This file is part of Ragel.
\usepackage{graphicx}
\usepackage{comment}
\usepackage{multicol}
+\usepackage[
+ colorlinks=true,
+ linkcolor=black,
+ citecolor=green,
+ filecolor=black,
+ urlcolor=black]{hyperref}
\topmargin -0.20in
\oddsidemargin 0in
current file is searched for a machine of the given name. If both are present,
the given input file is searched for a machine of the given name.
+Ragel searches for included files from the location of the current file.
+Additional directories can be added to the search path using the \verb|-I|
+option.
+
\subsection{Importing Definitions}
\label{import}
the following forms. Ragel treats these forms as state machine definitions.
\begin{itemize}
- \setlength{\itemsep}{-2mm}
+ \setlength{\itemsep}{-2mm}
\item \verb|name '=' number|
\item \verb|name '=' lit_string|
\item \verb|'define' name number|
specifications are ignored. See Section \ref{export} for a description of
exporting machine definitions.
+Ragel searches for imported files from the location of the current file.
+Additional directories can be added to the search path using the \verb|-I|
+option.
\section{Lexical Analysis of a Ragel Block}
\label{lexing}
\ref{controlling-nondeterminism} for more on this problem and how to solve it.
The Graphviz tool is an immense help when debugging improperly compiled
-machines or otherwise learning how to use Ragel. In many cases, practical
-parsing programs will be too large to completely visualize with Graphviz. The
-proper approach is to reduce the language to the smallest subset possible that
-still exhibits the characteristics that one wishes to learn about or to fix.
-This can be done without modifying the source code using the \verb|-M| and
-\verb|-S| options. If a machine cannot be easily reduced,
-embeddings of unique actions can be very useful for tracing a
-particular component of a larger machine specification, since action names are
-written out on transition labels.
+machines or otherwise learning how to use Ragel. Graphviz Dot files can be
+generated from Ragel programs using the \verb|-V| option. See Section
+\ref{visualization} for more information.
+
\subsection{Union}
$n$ is the number of states.
\section{Visualization}
+\label{visualization}
+
+%In many cases, practical
+%parsing programs will be too large to completely visualize with Graphviz. The
+%proper approach is to reduce the language to the smallest subset possible that
+%still exhibits the characteristics that one wishes to learn about or to fix.
+%This can be done without modifying the source code using the \verb|-M| and
+%\verb|-S| options. If a machine cannot be easily reduced,
+%embeddings of unique actions can be very useful for tracing a
+%particular component of a larger machine specification, since action names are
+%written out on transition labels.
Ragel is able to emit compiled state machines in Graphviz's Dot file format.
+This is done using the \verb|-V| option.
Graphviz support allows users to perform
incremental visualization of their parsers. User actions are displayed on
-transition labels of the graph. If the final graph is too large to be
+transition labels of the graph.
+
+If the final graph is too large to be
meaningful, or even drawn, the user is able to inspect portions of the parser
by naming particular regular expression definitions with the \verb|-S| and
\verb|-M| options to the \verb|ragel| program. Use of Graphviz greatly
experimentation and also to track down bugs caused by unintended
nondeterminism.
+Ragel has another option to help debugging. The \verb|-x| option causes Ragel
+to emit the compiled machine in an XML format.
+
\chapter{User Actions}
Ragel permits the user to embed actions into the transitions of a regular
\sasp\verb|>!action >err(name) >err{...} | -- the start state\\
\sasp\verb|<!action <err(name) <err{...} | -- any state except the start state\\
-\sasp\verb|$!action $eof(name) $err{...} | -- all states\\
+\sasp\verb|$!action $err(name) $err{...} | -- all states\\
\sasp\verb|%!action %err(name) %err{...} | -- final states\\
\sasp\verb|@!action @err(name) @err{...} | -- any state except final states\\
\sasp\verb|<>!action <>err(name) <>err{...}| -- any except start and final (middle)
% GENERATE: erract
% %%{
-% machine erract;
-% ws = ' ';
-% address = 'foo@bar.com';
-% date = 'Monday May 12';
+% machine erract;
+% ws = ' ';
+% address = 'foo@bar.com';
+% date = 'Monday May 12';
\begin{inline_code}
\begin{verbatim}
action cmd_err {
% %% write data;
% void f()
% {
-% %% write init;
-% %% write exec;
+% %% write init;
+% %% write exec;
% }
% END GENERATE
{\em finishing}, and {\em leaving} embeddings in the order in which they
appear.
-Ragel does not permit a single action to appear multiple times in an action
+By default Ragel does not permit a single action to appear multiple times in an action
list. When the final machine has been created, actions that appear more than
once in a single transition, to-state, from-state or EOF action list have their
duplicates removed.
identical program text. It simply checks for duplicates using each action
block's unique location in the program.
+The removal of duplicates can be turned off using the \verb|-d| option.
+
\section{Values and Statements Available in Code Blocks}
\label{vals}
last \verb|fcall| was made. Use of \verb|fret| requires the declaration of a
call stack. Control is immediately transferred to the destination state.
-\item \verb|fbreak;| -- Save the current state and immediately break out of the
-execute loop. This statement is useful in conjunction with the \verb|noend|
-write option. Rather than process input until the end marker of the input
-buffer is arrived at, the fbreak statement can be used to stop processing input
-upon seeing some end-of-string marker. It can also be used for handling
-exceptional circumstances. The fbreak statement does not change the pointer to
-the current character. After an \verb|fbreak| call the \verb|p| variable will point to
-the character that was being traversed over when the action was
-executed. The current state will be the target of the current transition.
+\item \verb|fbreak;| -- Advance \verb|p|, save the target state to \verb|cs|
+and immediately break out of the execute loop. This statement is useful
+in conjunction with the \verb|noend| write option. Rather than process input
+until \verb|pe| is arrived at, the fbreak statement
+can be used to stop processing from an action. After an \verb|fbreak|
+statement the \verb|p| variable will point to the next character in the input. The
+current state will be the target of the current transition. Note that \verb|fbreak|
+causes the target state's to-state actions to be skipped.
\end{itemize}
\end{center}
\graphspace
-Finish-guarded concatenation is equivalent to the following:
+Finish-guarded concatenation is equivalent to the following, with one
+exception. If the right machine's start state is final, the higher priority is
+also embedded into it as a leaving priority. This prevents the left machine
+from persisting via the zero-length string.
\verbspace
\begin{verbatim}
EOF actions are used then the \verb|eof| variable is required. If
stack-based state machine control flow statements are used then the
\verb|stack| and \verb|top| variables are required. If a scanner is declared
-then the \verb|act|, \verb|tokstart| and \verb|tokend| variables must be
+then the \verb|act|, \verb|ts| and \verb|te| variables must be
declared.
\begin{itemize}
\item \verb|act| - This must be an integer value. It is a variable sometimes
used by scanner code to keep track of the most recent successful pattern match.
-\item \verb|tokstart| - This must be a pointer to character data. In Java and
+\item \verb|ts| - This must be a pointer to character data. In Java and
Ruby code this must be an integer. See Section \ref{generating-scanners} for
more information.
-\item \verb|tokend| - Also a pointer to character data.
+\item \verb|te| - Also a pointer to character data.
\end{itemize}
The access statement specifies how the generated code should
access the machine data that is persistent across processing buffer blocks.
This applies to all variables except \verb|p|, \verb|pe| and \verb|eof|. This includes
-\verb|cs|, \verb|top|, \verb|stack|, \verb|tokstart|, \verb|tokend| and \verb|act|.
+\verb|cs|, \verb|top|, \verb|stack|, \verb|ts|, \verb|te| and \verb|act|.
The access statement is useful if a machine is to be encapsulated inside a
structure in C code. It can be used to give the name of
a pointer to the structure.
The variable statement specifies how to access a specific
variable. All of the variables that are declared by the user and
used by Ragel can be changed. This includes \verb|p|, \verb|pe|, \verb|eof|, \verb|cs|,
-\verb|top|, \verb|stack|, \verb|tokstart|, \verb|tokend| and \verb|act|.
+\verb|top|, \verb|stack|, \verb|ts|, \verb|te| and \verb|act|.
In Ruby and Java code generation the \verb|data| variable can also be changed.
\section{Pre-Push Statement}
\end{verbatim}
\verbspace
-
The write statement is used to generate parts of the machine.
-There are four
-components that can be generated by a write statement. These components are the
-state machine's data, initialization code, execution code, and exports.
+There are seven
+components that can be generated by a write statement. These components make up the
+state machine's data, initialization code, execution code, and export definitions.
A write statement may appear before a machine is fully defined.
This allows one to write out the data first then later define the machine where
it is used. An example of this is shown in Figure \ref{fbreak-example}.
\label{fbreak-example}
\end{figure}
+\subsection{Write Start, First Final and Error}
+
+\begin{verbatim}
+write start;
+write first_final;
+write error;
+\end{verbatim}
+\verbspace
+
+These three write statements provide an alternative means of accessing the
+\verb|start|, \verb|first_final| and \verb|error| states. If there are many
+different machine specifications in one file it is easy to get the prefix for
+these wrong. This is especially true if the state machine boilerplate is
+frequently made by a copy-paste-edit process. These write statements allow the
+problem to be avoided. They can be used as follows:
+
+\verbspace
+
+{
+\small
+\begin{verbatim}
+/* Did parsing succeed? */
+if ( cs < %%{ write first_final; }%% ) {
+ result = ERR_PARSE_ERROR;
+ goto fail;
+}
+\end{verbatim}
+}
+
\subsection{Write Init}
\begin{verbatim}
written out in the generated code. Defines are used for C and constant integers
are used for D, Java and Ruby. See Section \ref{import} for a description of the
import statement.
-
+
\section{Maintaining Pointers to Input Data}
In the creation of any parser it is not uncommon to require the collection of
construction has been used somewhere in the machine then it is possible to
take advantage of the required prefix maintenance code in the driver program to
ensure pointers to the input are always valid. If laying down a pointer one can
-set \verb|tokstart| at the same spot or ahead of it. When data is shifted in
+set \verb|ts| at the same spot or ahead of it. When data is shifted in
between loops the user must also shift the pointer. In this way it is possible
to maintain pointers to the input that will always be consistent.
partially read line and processing continues from the beginning of the line.
An example of line-oriented processing is given in Figure \ref{line-oriented}.
+\section{Specifying the Host Language}
-\section{Running the Executables}
-
-Ragel is broken down into two parts: a frontend that compiles machines and
-emits them in an XML format, and a backend that generates code or a Graphviz
-Dot file from the XML data. The \verb|ragel| program normally manages the
-execution of the backend program to generate code. However, if the intermediate
-file format is needed, it can emitted with the \verb|-f| option to the
-\verb|ragel| program.
-
-The purpose of the XML-based intermediate format is to allow users to inspect
-their compiled state machines and to interface Ragel to other tools such as
-custom visualizers, code generators or analysis tools. The split also serves to
-reduce the complexity of the Ragel program by strictly separating the data
-structures and algorithms that are used to compile machines from those that are
-used to generate code.
-
-\vspace{10pt}
-
-\noindent The frontend program \verb|ragel| takes as an argument the host
-language, compiles the state machine, then calls the appropriate backend program
-for code generation. The host language options are:
+The \verb|ragel| program has a number of options for specifying the host
+language. The host-language options are:
\begin{itemize}
\item \verb|-C | for C/C++/Objective-C code (default)
\item \verb|-D | for D code.
\item \verb|-J | for Java code.
\item \verb|-R | for Ruby code.
+\item \verb|-A | for C\# code.
\end{itemize}
-\noindent There are four code backend programs. These are:
-
-\begin{itemize}
-\item \verb|rlgen-cd | generate code for the C-based and D languages.
-\item \verb|rlgen-java | generate code for the Java language.
-\item \verb|rlgen-ruby | generate code for the Ruby language.
-\item \verb|rlgen-dot | generate a Graphviz Dot file.
-\end{itemize}
-
-\section{Choosing a Generated Code Style (C/D/Java only)}
+\section{Choosing a Generated Code Style}
\label{genout}
There are three styles of code output to choose from. Code style affects the
\verbspace
\begin{center}
-\begin{tabular}{|c|c|}
+\begin{tabular}{|c|c|c|}
\hline
-\multicolumn{2}{|c|}{\bf Code Output Style Options} \\
+\multicolumn{3}{|c|}{\bf Code Output Style Options} \\
\hline
-\verb|-T0|&binary search table-driven\\
+\verb|-T0|&binary search table-driven&C/D/Java/Ruby/C\#\\
\hline
-\verb|-T1|&binary search, expanded actions\\
+\verb|-T1|&binary search, expanded actions&C/D/Ruby/C\#\\
\hline
-\verb|-F0|&flat table-driven\\
+\verb|-F0|&flat table-driven&C/D/Ruby/C\#\\
\hline
-\verb|-F1|&flat table, expanded actions\\
+\verb|-F1|&flat table, expanded actions&C/D/Ruby/C\#\\
\hline
-\verb|-G0|&goto-driven\\
+\verb|-G0|&goto-driven&C/D/C\#\\
\hline
-\verb|-G1|&goto, expanded actions\\
+\verb|-G1|&goto, expanded actions&C/D/C\#\\
\hline
-\verb|-G2|&goto, in-place actions\\
+\verb|-G2|&goto, in-place actions&C/D\\
\hline
\end{tabular}
\end{center}
% GENERATE: call
% %%{
-% machine call;
+% machine call;
\begin{inline_code}
\begin{verbatim}
action return { fret; }
% %% write data;
% void f()
% {
-% %% write init;
-% %% write exec;
+% %% write init;
+% %% write exec;
% }
% END GENERATE
scanners must be immediately instantiated. They cannot be defined inline or
referenced by another expression. Scanners must be jumped to or called.
-Scanners rely on the \verb|tokstart|, \verb|tokend| and \verb|act|
+Scanners rely on the \verb|ts|, \verb|te| and \verb|act|
variables to be present so that they can backtrack and make pointers to the
matched text available to the user. If input is processed using multiple calls
to the execute code then the user must ensure that when a token is only
partially matched that the prefix is preserved on the subsequent invocation of
the execute code.
-The \verb|tokstart| variable must be defined as a pointer to the input data.
+The \verb|ts| variable must be defined as a pointer to the input data.
It is used for recording where the current token match begins. This variable
may be used in action code for retrieving the text of the current match. Ragel
ensures that in between tokens and outside of the longest-match machines that
this pointer is set to null. In between calls to the execute code the user must
-check if \verb|tokstart| is set and if so, ensure that the data it points to is
+check if \verb|ts| is set and if so, ensure that the data it points to is
preserved ahead of the next buffer block. This is described in more detail
below.
-The \verb|tokend| variable must also be defined as a pointer to the input data.
+The \verb|te| variable must also be defined as a pointer to the input data.
It is used for recording where a match ends and where scanning of the next
token should begin. This can also be used in action code for retrieving the
text of the current match.
\setlength{\parskip}{0pt}
\item Read a block of input data.
\item Run the execute code.
-\item If \verb|tokstart| is set, the execute code will expect the incomplete
+\item If \verb|ts| is set, the execute code will expect the incomplete
token to be preserved ahead of the buffer on the next invocation of the execute
code.
\begin{itemize}
-\item Shift the data beginning at \verb|tokstart| and ending at \verb|pe| to the
+\item Shift the data beginning at \verb|ts| and ending at \verb|pe| to the
beginning of the input buffer.
-\item Reset \verb|tokstart| to the beginning of the buffer.
-\item Shift \verb|tokend| by the distance from the old value of \verb|tokstart|
-to the new value. The \verb|tokend| variable may or may not be valid. There is
+\item Reset \verb|ts| to the beginning of the buffer.
+\item Shift \verb|te| by the distance from the old value of \verb|ts|
+to the new value. The \verb|te| variable may or may not be valid. There is
no way to know if it holds a meaningful value because it is not kept at null
when it is not in use. It can be shifted regardless.
\end{itemize}
\begin{verbatim}
a) A stream "of characters" to be scanned.
| | |
- p tokstart pe
+ p ts pe
b) "of characters" to be scanned.
| | |
- tokstart p pe
+ ts p pe
\end{verbatim}
\caption{Following an invocation of the execute code there may be a partially
matched token (a). The data of the partially matched token
exit(1);
}
- if ( tokstart == 0 )
+ if ( ts == 0 )
have = 0;
else {
/* There is a prefix to preserve, shift it over. */
- have = pe - tokstart;
- memmove( inbuf, tokstart, have );
- tokend = inbuf + (tokend-tokstart);
- tokstart = inbuf;
+ have = pe - ts;
+ memmove( inbuf, ts, have );
+ te = inbuf + (te-ts);
+ ts = inbuf;
}
}
\end{verbatim}