%
-% 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
For the purposes of embedding, Ragel divides transitions and states into
different classes. There are four operators for embedding actions and
priorities into the transitions of a state machine. It is possible to embed
-into entering transitions, finishing transitions, all transitions and pending out
-transitions. The embedding of pending out transitions is a special case.
+into entering transitions, finishing transitions, all transitions and leaving
+transitions. The embedding into leaving transitions is a special case.
These transition embeddings get stored in the final states of a machine. They
are transferred to any transitions that are made going out of the machine by
-a concatenation or kleene star operation.
+future concatenation or kleene star operations.
There are several more operators for embedding actions into states. Like the
transition embeddings, there are various different classes of states that the
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
expression's corresponding state machine. These actions are executed when the
generated code moves over a transition. Like the regular expression operators,
the action embedding operators are fully compositional. They take a state
-machine and an action as input, embed the action, and yield a new state machine
+machine and an action as input, embed the action and yield a new state machine
that can be used in the construction of other machines. Due to the
compositional nature of embeddings, the user has complete freedom in the
placement of actions.
-A machine's transitions are categorized into four classes, The action embedding
-operators access the transitions defined by these classes. The {\em starting
+A machine's transitions are categorized into four classes. The action embedding
+operators access the transitions defined by these classes. The {\em entering
transition} operator \verb|>| isolates the start state, then embeds an action
into all transitions leaving it. The {\em finishing transition} operator
\verb|@| embeds an action into all transitions going into a final state. The
{\em all transition} operator \verb|$| embeds an action into all transitions of
-an expression. The {\em pending out transition} operator \verb|%| provides
-access to yet-unmade leaving transitions.
+an expression. The {\em leaving transition} operator \verb|%| provides access
+to the yet-unmade transitions moving out of the machine via the final states.
\section{Embedding Actions}
expressions. Though actions need not be named in this way (literal blocks
of code can be embedded directly when building machines), defining reusable
blocks of code whenever possible is good practice because it potentially increases the
-degree to which the machine can be minimized. Within an action some Ragel expressions
-and statements are parsed and translated. These allow the user to interact with the machine
-from action code. See Section \ref{vals} for a complete list of statements and
-values available in code blocks.
+degree to which the machine can be minimized.
+
+Within an action some Ragel expressions and statements are parsed and
+translated. These allow the user to interact with the machine from action code.
+See Section \ref{vals} for a complete list of statements and values available
+in code blocks.
\subsection{Entering Action}
that enter into the machine from the start state. If the start state is final,
then the action is also embedded into the start state as a leaving action. This
means that if a machine accepts the zero-length string and control passes
-through it then the entering action is still executed. Note
+through the start state then the entering action is executed. Note
that this can happen on both a following character and on the EOF event.
In some machines the start state has transtions coming in from within the
machine. In these cases the start state is first isolated from the rest of the
-machine ensuring that the entering actions are not re-executed.
+machine ensuring that the entering actions are exected once only.
\verbspace
\verb|expr @ action|
\verbspace
-The finishing action operator embeds an action into any transitions that go into a
-final state. Whether or not the machine accepts is not determined at the point
-the action is executed. Further input may move the machine out of the accepting
-state, but keep it in the machine. As in the following example, the
-into-final-state operator is most often used when no lookahead is necessary.
+The finishing action operator embeds an action into any transitions that move
+the machine into a final state. Further input may move the machine out of the
+final state, but keep it in the machine. Therefore finishing actions may be
+executed more than once if a machine has any internal transitions out of a
+final state. In the following example the final state has no transitions out
+and the finishing action is executed only once.
% GENERATE: exdoneact
% OPT: -p
% action A {}
\begin{inline_code}
\begin{verbatim}
-# Execute A on any characters of machine one or two.
+# Execute A on any characters of the machine.
main := ( 'm1' | 'm2' ) $A;
\end{verbatim}
\end{inline_code}
\graphspace
-\subsection{Pending Out (Leaving) Actions}
+\subsection{Leaving Actions}
\label{out-actions}
\verb|expr % action|
\verbspace
-The pending out action operator queues an action for embedding into the
-transitions that leave a machine. The action is first stored in the final
-states of the machine and is later transferred to any transitions that are made
-going out of the machine. The transfer can be caused either by a concatenation
-or kleene star operation. If a final state is still final when compilation is
-complete then the pending out action is also embedded as an EOF action into the
-final state. Therefore, leaving the machine is defined as either leaving on a
-character or as state machine acceptance.
+The leaving action operator queues an action for embedding into the transitions
+that go out of a machine via a final state. The action is first stored in
+the machine's final states and is later transferred to any transitions that are
+made going out of the machine by a kleene star or concatenation operation.
+
+If a final state of the machine is still final when compilation is complete
+then the leaving action is also embedded as an EOF action. Therefore, leaving
+the machine is defined as either leaving on a character or as state machine
+acceptance.
This operator allows one to associate an action with the termination of a
sequence, without being concerned about what particular character terminates
The state embedding operators allow one to embed actions into states. Like the
transition embedding operators, there are several different classes of states
that the operators access. The meanings of the symbols are similar to the
-meanings of the symbols used by the transition embedding operators. The design
+meanings of the symbols used for the transition embedding operators. The design
of the state selections was driven by a need to cover the states of an
-expression with a single error action.
+expression with exactly one error action.
Unlike the transition embedding operators, the state embedding operators are
also distinguished by the different kinds of events that embedded actions can
may also be desirable to consume input in an attempt to return the input stream
to some known state and resume parsing. To support error handling and recovery,
Ragel provides error action embedding operators. There are two kinds of error
-actions, regular (global) error actions and local error actions.
+actions: global error actions and local error actions.
Error actions can be used to simply report errors, or by jumping to a machine
instantiation that consumes input, can attempt to recover from errors.
\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)
name defaults to the current machine. In the second form the machine name can
be specified. This is useful when it is more convenient to specify the local
error action in a sub-definition that is used to construct the machine
-definition where the transfer should happen. To embed local error actions and
-explicitly state the machine on which the transfer is to happen use
+definition that the local error action is associated with. To embed local
+error actions and
+explicitly state the machine definition on which the transfer is to happen use
\verb|(name, action)| as the action.
\subsubsection{Example}
% 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
When combining expressions that have embedded actions it is often the case that
a number of actions must be executed on a single input character. For example,
-following a concatenation the pending out action of the left expression and the
+following a concatenation the leaving action of the left expression and the
entering action of the right expression will be embedded into one transition.
This requires a method of ordering actions that is intuitive and
predictable for the user, and repeatable for the compiler.
{\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 or EOF action list have their duplicates removed.
+once in a single transition, to-state, from-state or EOF action list have their
+duplicates removed.
The first appearance of the action is preserved. This is useful in a number of
scenarios. First, it allows us to union machines with common prefixes without
worrying about the action embeddings in the prefix being duplicated. Second, it
-prevents pending out actions from being transferred multiple times. This can
+prevents leaving actions from being transferred multiple times. This can
happen when a machine is repeated, then followed with another machine that
begins with a common character. For example:
word = [a-z]+ %act;
main := word ( '\n' word )* '\n\n';
\end{verbatim}
+\verbspace
Note that Ragel does not compare action bodies to determine if they have
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}
constant. This number is suitable for later use in control flow transfer
statements that take an expression. This value should not be compared against
the current state because any given label can have multiple states representing
-it. The value returned by \verb|fentry| will be one of the possibly multiple states the
-label represents.
+it. The value returned by \verb|fentry| can be any one of the multiple states that
+it represents.
\end{itemize}
\noindent The following statements are available in code blocks:
the declaration of a call stack. An array of integers named \verb|stack| and a
single integer named \verb|top| must be declared. With the \verb|fcall|
construct, control is immediately transferred to the destination state.
+See section \ref{modularization} for more information.
\item \verb|fcall *<expr>;| -- Push the current state and jump to the entry
point given by \verb|<expr>|. The expression must evaluate to an integer value
\item \verb|fret;| -- Return to the target state of the transition on which the
last \verb|fcall| was made. Use of \verb|fret| requires the declaration of a
-call stack with \verb|fstack| in the struct block. 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.
+call stack. Control is immediately transferred to the destination state.
+
+\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}
then unioning any transition that executes that action with another transition
that follows some other path will cause that other path to be lost. Using
commands that manually jump around a machine takes us out of the domain of
-regular languages because transitions that may be conditional and that the
+regular languages because transitions that the
machine construction operators are not aware of are introduced. These
commands should therefore be used with caution.
current subset of the parser may be executed, causing problems for the
programmer.
-Tools that are based on regular expression engines and used for
+Tools that are based on regular expression engines and that are used for
recognition tasks will usually function as intended regardless of the presence
of ambiguities. It is quite common for users of scripting languages to write
regular expressions that are heavily ambiguous and it generally does not
\item \verb|expr > int| -- Sets starting transitions to have priority int.
\item \verb|expr @ int| -- Sets transitions that go into a final state to have priority int.
\item \verb|expr $ int| -- Sets all transitions to have priority int.
-\item \verb|expr % int| -- Sets pending out transitions from final states to
-have priority int.\\ When a transition is made going out of the machine (either
-by concatenation or kleene star) its priority is immediately set to the pending
-out priority.
+\item \verb|expr % int| -- Sets leaving transitions to
+have priority int. When a transition is made going out of the machine (either
+by concatenation or kleene star) its priority is immediately set to the
+leaving priority.
\end{itemize}
The second form of priority assignment allows the programmer to specify the name
\item \verb|expr > (name, int)| -- Starting transitions.
\item \verb|expr @ (name, int)| -- Finishing transitions (into a final state).
\item \verb|expr $ (name, int)| -- All transitions.
-\item \verb|expr % (name, int)| -- Pending out transitions.
+\item \verb|expr % (name, int)| -- Leaving transitions.
\end{itemize}
\section{Guarded Operators that Encapsulate Priorities}
effects of the operations between them. When we consider
that this problem is worsened by the
potential for side effects caused by unintended priority name collisions, we
-see that exposing the user to priorities is rather undesirable.
+see that exposing the user to priorities is undesirable.
Fortunately, in practice the use of priorities has been necessary only in a
small number of scenarios. This allows us to encapsulate their functionality
\verb|**| compound symbol. This
guarded operator embeds a high
priority into all transitions of the machine.
-A lower priority is then embedded into pending out transitions
-(in a manner similar to pending out action embeddings, described in Section
-\ref{out-actions}). When the kleene star operator makes the epsilon transitions from
-the final states into the start state, the lower priority will be transferred
+A lower priority is then embedded into the leaving transitions. When the
+kleene star operator makes the epsilon transitions from
+the final states into the new start state, the lower priority will be transferred
to the epsilon transitions. In cases where following an epsilon transition
out of a final state conflicts with an existing transition out of a final
state, the epsilon transition will be dropped.
priority to all transitions
of the first machine and a high priority to the starting transitions of the
second machine. This operator is useful if from the final states of the first
-machine, it is possible to accept the characters in the start transitions of
+machine it is possible to accept the characters in the entering transitions of
the second machine. This operator effectively terminates the first machine
immediately upon starting the second machine, where otherwise they would be
pursued concurrently. In the following example, entry-guarded concatenation is
\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}
\verbspace
When the kleene star is applied, transitions that go out of the machine and
-back into it are made. These are assigned a priority of zero by the pending out
+back into it are made. These are assigned a priority of zero by the leaving
transition mechanism. This is less than the priority of one assigned to the
-transitions leaving the final states but not leaving the machine. When two of
-these transitions clash on the same character, the differing priorities cause
-the transition that stays in the machine to take precedence. The transition
+transitions leaving the final states but not leaving the machine. When
+these transitions clash on the same character, the
+transition that stays in the machine takes precedence. The transition
that wraps around is dropped.
Note that this operator does not build a scanner in the traditional sense
-because there is never any backtracking. To build a scanner in the traditional
-sense use the Longest-Match machine construction described in Section
+because there is never any backtracking. To build a scanner with backtracking
+use the Longest-Match machine construction described in Section
\ref{generating-scanners}.
\chapter{Interface to Host Program}
The Ragel code generator is very flexible. The generated code has no
-dependencies and can be inserted in any function, perhaps inside a loop if so
+dependencies and can be inserted in any function, perhaps inside a loop if
desired. The user is responsible for declaring and initializing a number of
required variables, including the current state and the pointer to the input
stream. These can live in any scope. Control of the input processing loop is
\section{Variables Used by Ragel}
-There are a number of variables which Ragel expects the user to declare. At a
+There are a number of variables that Ragel expects the user to declare. At a
very minimum the \verb|cs|, \verb|p| and \verb|pe| variables must be declared.
In Java and Ruby code the \verb|data| variable must also be declared. If
+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|cs| - Current state. This must be an integer and it should persist
across invocations of the machine when the data is broken into blocks that are
-processed independently.
+processed independently. This variable may be modified from outside the
+execution loop, but not from within.
\item \verb|p| - Data pointer. In C/D code this variable is expected to be a
pointer to the character data to process. It should be initialized to the
\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}
\verbspace
The alphtype statement specifies the alphabet data type that the machine
-operates on. During the compilation of the machine, integer literals are expected to
-be in the range of possible values of the alphtype. Supported alphabet types
-are \verb|char|, \verb|unsigned char|, \verb|short|, \verb|unsigned short|,
-\verb|int|, \verb|unsigned int|, \verb|long|, and \verb|unsigned long|.
-The default is \verb|char|.
+operates on. During the compilation of the machine, integer literals are
+expected to be in the range of possible values of the alphtype. The default
+is always \verb|char|.
+
+\begin{multicols}{2}
+\setlength{\columnseprule}{1pt}
+C/C++/Objective-C:
+\begin{verbatim}
+ char unsigned char
+ short unsigned short
+ int unsigned int
+ long unsigned long
+\end{verbatim}
+
+Java:
+\begin{verbatim}
+ char
+ byte
+ short
+ int
+\end{verbatim}
+
+
+\columnbreak
+
+D:
+\begin{verbatim}
+ char
+ byte ubyte
+ short ushort
+ wchar
+ int uint
+ dchar
+\end{verbatim}
+
+Ruby:
+\begin{verbatim}
+ char
+ int
+\end{verbatim}
+\end{multicols}
\section{Getkey Statement}
\end{verbatim}
\verbspace
-Specify to Ragel how to retrieve the character that the machine operates on
+This statement specifies to Ragel how to retrieve the current character from
from the pointer to the current element (\verb|p|). Any expression that returns
a value of the alphabet type
may be used. The getkey statement may be used for looking into element
\end{verbatim}
\verbspace
-The access statement allows one to tell Ragel how the generated code should
+The access statement specifies how the generated code should
access the machine data that is persistent across processing buffer blocks.
-This includes all variables except \verb|p| and \verb|pe|. This includes
-\verb|cs|, \verb|top|, \verb|stack|, \verb|tokstart|, \verb|tokend| and \verb|act|.
-This is useful if a machine is to be encapsulated inside a
-structure in C code. The access statement can be used to give the name of
+This applies to all variables except \verb|p|, \verb|pe| and \verb|eof|. This includes
+\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.
\section{Variable Statement}
\end{verbatim}
\verbspace
-The variable statement allows one to tell ragel how to access a specific
+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|cs|,
-\verb|top|, \verb|stack|, \verb|tokstart|, \verb|tokend| and \verb|act|.
+used by Ragel can be changed. This includes \verb|p|, \verb|pe|, \verb|eof|, \verb|cs|,
+\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}
\begin{verbatim}
prepush {
- /* stack growing code */
+ /* stack growing code */
}
\end{verbatim}
\verbspace
\begin{verbatim}
postpop {
- /* stack shrinking code */
+ /* stack shrinking code */
}
\end{verbatim}
\verbspace
\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 EOF action
-execution code. A write statement may appear before a machine is fully defined.
+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}.
machine.
\end{itemize}
+\begin{figure}
+\small
+\begin{verbatim}
+#include <stdio.h>
+%% machine foo;
+%% write data;
+int main( int argc, char **argv )
+{
+ int cs, res = 0;
+ if ( argc > 1 ) {
+ char *p = argv[1];
+ %%{
+ main :=
+ [a-z]+
+ 0 @{ res = 1; fbreak; };
+ write init;
+ write exec noend;
+ }%%
+ }
+ printf("execute = %i\n", res );
+ return 0;
+}
+\end{verbatim}
+\caption{Use of {\tt noend} write option and the {\tt fbreak} statement for
+processing a string.}
+\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}
-write init;
+write init [options];
\end{verbatim}
\verbspace
The write exec statement causes Ragel to emit the state machine's execution code.
Ragel expects several variables to be available to this code. At a very minimum, the
generated code needs access to the current character position \verb|p|, the ending
-position \verb|pe| and the current state \verb|cs|, though \verb|pe|
-can be excluded by specifying the \verb|noend| write option.
+position \verb|pe| and the current state \verb|cs| (though \verb|pe|
+can be omitted using the \verb|noend| write option).
The \verb|p| variable is the cursor that the execute code will
used to traverse the input. The \verb|pe| variable should be set up to point to one
position past the last valid character in the buffer.
seen. The example in Figure \ref{fbreak-example} shows the use of the
\verb|noend| write option and the \verb|fbreak| statement for processing a string.
-\begin{figure}
-\small
-\begin{verbatim}
-#include <stdio.h>
-%% machine foo;
-int main( int argc, char **argv )
-{
- %% write data noerror nofinal;
- int cs, res = 0;
- if ( argc > 1 ) {
- char *p = argv[1];
- %%{
- main :=
- [a-z]+
- 0 @{ res = 1; fbreak; };
- write init;
- write exec noend;
- }%%
- }
- printf("execute = %i\n", res );
- return 0;
-}
-\end{verbatim}
-\caption{Use of {\tt noend} write option and the {\tt fbreak} statement for
-processing a string.}
-\label{fbreak-example}
-\end{figure}
-
\subsection{Write Exports}
\label{export}
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 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 is called \verb|ragel|. It takes as an argument the host
-language. This can be:
+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 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}
\chapter{Beyond the Basic Model}
\section{Parser Modularization}
+\label{modularization}
It is possible to use Ragel's machine construction and action embedding
operators to specify an entire parser using a single regular expression. In
many cases this is the desired way to specify a parser in Ragel. However, in
-some scenarios, the language to parse may be so large that it is difficult to
-think about it as a single regular expression. It may shift between distinct
+some scenarios the language to parse may be so large that it is difficult to
+think about it as a single regular expression. It may also shift between distinct
parsing strategies, in which case modularization into several coherent blocks
of the language may be appropriate.
% 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
\section{Referencing Names}
\label{labels}
-This section describes how to reference names in epsilon transitions and
+This section describes how to reference names in epsilon transitions (Section
+\ref{state-charts}) and
action-based control-flow statements such as \verb|fgoto|. There is a hierarchy
of names implied in a Ragel specification. At the top level are the machine
instantiations. Beneath the instantiations are labels and references to machine
Scanners are very much intertwined with regular-languages and their
corresponding processors. For this reason Ragel supports the definition of
-Scanners. The generated code will repeatedly attempt to match patterns from a
+scanners. The generated code will repeatedly attempt to match patterns from a
list, favouring longer patterns over shorter patterns. In the case of
equal-length matches, the generated code will favour patterns that appear ahead
of others. When a scanner makes a match it executes the user code associated
difference is that a scanner is able to backtrack to match a previously matched
shorter string when the pursuit of a longer string fails. For this reason the
scanner construction operator is not a pure state machine construction
-operator. It relies on several variables which enable it to backtrack and make
+operator. It relies on several variables that enable it to backtrack and make
pointers to the matched input text available to the user. For this reason
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|
-variables to be present so that it can backtrack and make pointers to the
+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
\label{preserve_example}
\end{figure}
-Since scanners attempt to make the longest possible match of input, in some
-cases they are not able to identify a token upon parsing its final character,
-they must wait for a lookahead character. For example if trying to match words,
-the token match must be triggered on following whitespace in case more
-characters of the word have yet to come. The user must therefore arrange for an
-EOF character to be sent to the scanner to flush out any token that has not yet
-been matched. The user can exclude a single character from the entire scanner
-and use this character as the EOF character, possibly specifying an EOF action.
-For most scanners, zero is a suitable choice for the EOF character.
-
-Alternatively, if whitespace is not significant and ignored by the scanner, the
-final real token can be flushed out by simply sending an additional whitespace
-character on the end of the stream. If the real stream ends with whitespace
-then it will simply be extended and ignored. If it does not, then the last real token is
-guaranteed to be flushed and the dummy EOF whitespace ignored.
+Since scanners attempt to make the longest possible match of input, patterns
+such as identifiers require one character of lookahead in order to trigger a
+match. In the case of the last token in the input stream the user must ensure
+that the \verb|eof| variable is set so that the final token is flushed out.
+
An example scanner processing loop is given in Figure \ref{scanner-loop}.
\begin{figure}
cin.read( p, space );
int len = cin.gcount();
- /* If no data was read, send the EOF character. */
+ char *pe = p + len;
+ char *eof = 0;
+
+ /* If no data was read indicate EOF. */
if ( len == 0 ) {
- p[0] = 0, len++;
+ eof = pe;
done = true;
}
- char *pe = p + len;
%% write exec;
- if ( cs == RagelScan_error ) {
+ if ( cs == Scanner_error ) {
/* Machine failed before finding a token. */
cerr << "PARSE ERROR" << endl;
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}
\end{figure}
\section{State Charts}
+\label{state-charts}
In addition to supporting the construction of state machines using regular
languages, Ragel provides a way to manually specify state machines using
Ragel allows one to take this state map simplification approach. We can build
state machines using a state map model and implement portions of the state map
using regular languages. In place of any transition in the state machine,
-entire sub-state machines can be given. These can encapsulate functionality
+entire sub-machines can be given. These can encapsulate functionality
defined elsewhere. An important aspect of the Ragel approach is that when we
wrap up a collection of states using a regular expression we do not lose
access to the states and transitions. We can still execute code on the
\section{Implementing Lookahead}
There are a few strategies for implementing lookahead in Ragel programs.
-Pending out actions, which are described in Section \ref{out-actions}, can be
+Leaving actions, which are described in Section \ref{out-actions}, can be
used as a form of lookahead. Ragel also provides the \verb|fhold| directive
which can be used in actions to prevent the machine from advancing over the
current character. It is also possible to manually adjust the current character
projects / external / ragel.git / blobdiff