"Fossies" - the Fresh Open Source Software Archive

Member "ragel-6.10/doc/ragel-guide.tex" (24 Mar 2017, 145262 Bytes) of package /linux/misc/ragel-6.10.tar.gz:

As a special service "Fossies" has tried to format the requested source page into HTML format using (guessed) TeX and LaTeX source code syntax highlighting (style: standard) with prefixed line numbers. Alternatively you can here view or download the uninterpreted source code file.

    1 %
    2 %   Copyright 2001-2009 Adrian Thurston <thurston@complang.org>
    3 %
    5 %   This file is part of Ragel.
    6 %
    7 %   Ragel is free software; you can redistribute it and/or modify
    8 %   it under the terms of the GNU General Public License as published by
    9 %   the Free Software Foundation; either version 2 of the License, or
   10 %   (at your option) any later version.
   11 %
   12 %   Ragel is distributed in the hope that it will be useful,
   13 %   but WITHOUT ANY WARRANTY; without even the implied warranty of
   15 %   GNU General Public License for more details.
   16 %
   17 %   You should have received a copy of the GNU General Public License
   18 %   along with Ragel; if not, write to the Free Software
   19 %   Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA 
   21 % TODO: Need a section on the different strategies for handline recursion.
   23 \documentclass[letterpaper,11pt,oneside]{book}
   24 \usepackage{graphicx}
   25 \usepackage{comment}
   26 \usepackage{multicol}
   27 \usepackage[
   28     colorlinks=true,
   29     linkcolor=black,
   30     citecolor=green,
   31     filecolor=black,
   32     urlcolor=black]{hyperref}
   34 \topmargin -0.20in
   35 \oddsidemargin 0in
   36 \textwidth 6.5in
   37 \textheight 9in
   39 \setlength{\parskip}{0pt}
   40 \setlength{\topsep}{0pt}
   41 \setlength{\partopsep}{0pt}
   42 \setlength{\itemsep}{0pt}
   44 \input{version}
   46 \newcommand{\verbspace}{\vspace{10pt}}
   47 \newcommand{\graphspace}{\vspace{10pt}}
   49 \renewcommand\floatpagefraction{.99}
   50 \renewcommand\topfraction{.99}
   51 \renewcommand\bottomfraction{.99}
   52 \renewcommand\textfraction{.01}   
   53 \setcounter{totalnumber}{50}
   54 \setcounter{topnumber}{50}
   55 \setcounter{bottomnumber}{50}
   57 \newenvironment{inline_code}{\def\baselinestretch{1}\vspace{12pt}\small}{}
   59 \begin{document}
   61 %
   62 % Title page
   63 %
   64 \thispagestyle{empty}
   65 \begin{center}
   66 \vspace*{3in}
   67 {\huge Ragel State Machine Compiler}\\
   68 \vspace*{12pt}
   69 {\Large User Guide}\\
   70 \vspace{1in}
   71 by\\
   72 \vspace{12pt}
   73 {\large Adrian Thurston}\\
   74 \end{center}
   75 \clearpage
   77 \pagenumbering{roman}
   79 %
   80 % License page
   81 %
   82 \chapter*{License}
   83 Ragel version \version, \pubdate\\
   84 Copyright \copyright\ 2003-2007 Adrian Thurston
   85 \vspace{6mm}
   87 {\bf\it\noindent This document is part of Ragel, and as such, this document is
   88 released under the terms of the GNU General Public License as published by the
   89 Free Software Foundation; either version 2 of the License, or (at your option)
   90 any later version.}
   92 \vspace{5pt}
   94 {\bf\it\noindent Ragel is distributed in the hope that it will be useful, but
   95 WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
   96 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License for more
   97 details.}
   99 \vspace{5pt}
  101 {\bf\it\noindent You should have received a copy of the GNU General Public
  102 License along with Ragel; if not, write to the Free Software Foundation, Inc.,
  103 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA}
  105 %
  106 % Table of contents
  107 %
  108 \clearpage
  109 \tableofcontents
  110 \clearpage
  112 %
  113 % Chapter 1
  114 %
  116 \pagenumbering{arabic}
  118 \chapter{Introduction}
  120 \section{Abstract}
  122 Regular expressions are used heavily in practice for the purpose of specifying
  123 parsers. They are normally used as black boxes linked together with program
  124 logic.  User actions are executed in between invocations of the regular
  125 expression engine. Adding actions before a pattern terminates requires patterns
  126 to be broken and pasted back together with program logic. The more user actions
  127 are needed, the less the advantages of regular expressions are seen. 
  129 Ragel is a software development tool that allows user actions to be 
  130 embedded into the transitions of a regular expression's corresponding state
  131 machine, eliminating the need to switch from the regular expression engine and
  132 user code execution environment and back again. As a result, expressions can be
  133 maximally continuous.  One is free to specify an entire parser using a single
  134 regular expression.  The single-expression model affords concise and elegant
  135 descriptions of languages and the generation of very simple, fast and robust
  136 code.  Ragel compiles executable finite state machines from a high level regular language
  137 notation. Ragel targets C, C++, Objective-C, D, Go, Java and Ruby.
  139 In addition to building state machines from regular expressions, Ragel allows
  140 the programmer to directly specify state machines with state charts. These two
  141 notations may be freely combined. There are also facilities for controlling
  142 nondeterminism in the resulting machines and building scanners using patterns
  143 that themselves have embedded actions. Ragel can produce code that is small and
  144 runs very fast. Ragel can handle integer-sized alphabets and can compile very
  145 large state machines.
  147 \section{Motivation}
  149 When a programmer is faced with the task of producing a parser for a
  150 context-free language there are many tools to choose from. It is quite common
  151 to generate useful and efficient parsers for programming languages from a
  152 formal grammar. It is also quite common for programmers to avoid such tools
  153 when making parsers for simple computer languages, such as file formats and
  154 communication protocols.  Such languages are often regular and tools for
  155 processing the context-free languages are viewed as too heavyweight for the
  156 purpose of parsing regular languages. The extra run-time effort required for
  157 supporting the recursive nature of context-free languages is wasted.
  159 When we turn to the regular expression-based parsing tools, such as Lex, Re2C,
  160 and scripting languages such as Sed, Awk and Perl we find that they are split
  161 into two levels: a regular expression matching engine and some kind of program
  162 logic for linking patterns together.  For example, a Lex program is composed of
  163 sets of regular expressions. The implied program logic repeatedly attempts to
  164 match a pattern in the current set. When a match is found the associated user
  165 code executed. It requires the user to consider a language as a sequence of
  166 independent tokens. Scripting languages and regular expression libraries allow
  167 one to link patterns together using arbitrary program code.  This is very
  168 flexible and powerful, however we can be more concise and clear if we avoid
  169 gluing together regular expressions with if statements and while loops.
  171 This model of execution, where the runtime alternates between regular
  172 expression matching and user code exectution places restrictions on when
  173 action code may be executed. Since action code can only be associated with
  174 complete patterns, any action code that must be executed before an entire
  175 pattern is matched requires that the pattern be broken into smaller units.
  176 Instead of being forced to disrupt the regular expression syntax and write
  177 smaller expressions, it is desirable to retain a single expression and embed
  178 code for performing actions directly into the transitions that move over the
  179 characters. After all, capable programmers are astutely aware of the machinery
  180 underlying their programs, so why not provide them with access to that
  181 machinery? To achieve this we require an action execution model for associating
  182 code with the sub-expressions of a regular expression in a way that does not
  183 disrupt its syntax.
  185 The primary goal of Ragel is to provide developers with an ability to embed
  186 actions into the transitions and states of a regular expression's state machine
  187 in support of the definition of entire parsers or large sections of parsers
  188 using a single regular expression.  From the regular expression we gain a clear
  189 and concise statement of our language. From the state machine we obtain a very
  190 fast and robust executable that lends itself to many kinds of analysis and
  191 visualization.
  193 \section{Overview}
  195 Ragel is a language for specifying state machines. The Ragel program is a
  196 compiler that assembles a state machine definition to executable code.  Ragel
  197 is based on the principle that any regular language can be converted to a
  198 deterministic finite state automaton. Since every regular language has a state
  199 machine representation and vice versa, the terms regular language and state
  200 machine (or just machine) will be used interchangeably in this document.
  202 Ragel outputs machines to C, C++, Objective-C, D, Go, Java or Ruby code. The output is
  203 designed to be generic and is not bound to any particular input or processing
  204 method. A Ragel machine expects to have data passed to it in buffer blocks.
  205 When there is no more input, the machine can be queried for acceptance.  In
  206 this way, a Ragel machine can be used to simply recognize a regular language
  207 like a regular expression library. By embedding code into the regular language,
  208 a Ragel machine can also be used to parse input.
  210 The Ragel language has many operators for constructing and manipulating
  211 machines. Machines are built up from smaller machines, to bigger ones, to the
  212 final machine representing the language that needs to be recognized or parsed.
  214 The core state machine construction operators are those found in most theory
  215 of computation textbooks. They date back to the 1950s and are widely studied.
  216 They are based on set operations and permit one to think of languages as a set
  217 of strings. They are Union, Intersection, Difference, Concatenation and Kleene
  218 Star. Put together, these operators make up what most people know as regular
  219 expressions. Ragel also provides a scanner construction operator 
  220 and provides operators for explicitly constructing machines
  221 using a state chart method. In the state chart method, one joins machines
  222 together without any implied transitions and then explicitly specifies where
  223 epsilon transitions should be drawn.
  225 The state machine manipulation operators are specific to Ragel. They allow the
  226 programmer to access the states and transitions of regular language's
  227 corresponding machine. There are two uses of the manipulation operators. The
  228 first and primary use is to embed code into transitions and states, allowing
  229 the programmer to specify the actions of the state machine.
  231 Ragel attempts to make the action embedding facility as intuitive as possible.
  232 To do so, a number of issues need to be addressed.  For example, when making a
  233 nondeterministic specification into a DFA using machines that have embedded
  234 actions, new transitions are often made that have the combined actions of
  235 several source transitions. Ragel ensures that multiple actions associated with
  236 a single transition are ordered consistently with respect to the order of
  237 reference and the natural ordering implied by the construction operators.
  239 The second use of the manipulation operators is to assign priorities to
  240 transitions. Priorities provide a convenient way of controlling any
  241 nondeterminism introduced by the construction operators. Suppose two
  242 transitions leave from the same state and go to distinct target states on the
  243 same character. If these transitions are assigned conflicting priorities, then
  244 during the determinization process the transition with the higher priority will
  245 take precedence over the transition with the lower priority. The lower priority
  246 transition gets abandoned. The transitions would otherwise be combined into a new
  247 transition that goes to a new state that is a combination of the original
  248 target states. Priorities are often required for segmenting machines. The most
  249 common uses of priorities have been encoded into a set of simple operators
  250 that should be used instead of priority embeddings whenever possible.
  252 For the purposes of embedding, Ragel divides transitions and states into
  253 different classes. There are four operators for embedding actions and
  254 priorities into the transitions of a state machine. It is possible to embed
  255 into entering transitions, finishing transitions, all transitions and leaving
  256 transitions. The embedding into leaving transitions is a special case.
  257 These transition embeddings get stored in the final states of a machine.  They
  258 are transferred to any transitions that are made going out of the machine by
  259 future concatenation or kleene star operations.
  261 There are several more operators for embedding actions into states. Like the
  262 transition embeddings, there are various different classes of states that the
  263 embedding operators access. For example, one can access start states, final
  264 states or all states, among others. Unlike the transition embeddings, there are
  265 several different types of state action embeddings. These are executed at
  266 various different times during the processing of input. It is possible to embed
  267 actions that are exectued on transitions into a state, on transitions out of a
  268 state, on transitions taken on the error event, or on transitions taken on the
  269 EOF event.
  271 Within actions, it is possible to influence the behaviour of the state machine.
  272 The user can write action code that jumps or calls to another portion of the
  273 machine, changes the current character being processed, or breaks out of the
  274 processing loop. With the state machine calling feature Ragel can be used to
  275 parse languages that are not regular. For example, one can parse balanced
  276 parentheses by calling into a parser when an open parenthesis character is seen
  277 and returning to the state on the top of the stack when the corresponding
  278 closing parenthesis character is seen. More complicated context-free languages
  279 such as expressions in C are out of the scope of Ragel. 
  281 Ragel also provides a scanner construction operator that can be used to build
  282 scanners much the same way that Lex is used. The Ragel generated code, which
  283 relies on user-defined variables for backtracking, repeatedly tries to match
  284 patterns to the input, favouring longer patterns over shorter ones and patterns
  285 that appear ahead of others when the lengths of the possible matches are
  286 identical. When a pattern is matched the associated action is executed. 
  288 The key distinguishing feature between scanners in Ragel and scanners in Lex is
  289 that Ragel patterns may be arbitrary Ragel expressions and can therefore
  290 contain embedded code. With a Ragel-based scanner the user need not wait until
  291 the end of a pattern before user code can be executed.
  293 Scanners do take Ragel out of the domain of pure state machines and require the
  294 user to maintain the backtracking related variables.  However, scanners
  295 integrate well with regular state machine instantiations. They can be called to
  296 or jumped to only when needed, or they can be called out of or jumped out of
  297 when a simpler, pure state machine model is appropriate.
  299 Two types of output code style are available. Ragel can produce a table-driven
  300 machine or a directly executable machine. The directly executable machine is
  301 much faster than the table-driven. On the other hand, the table-driven machine
  302 is more compact and less demanding on the host language compiler. It is better
  303 suited to compiling large state machines.
  305 \section{Related Work}
  307 Lex is perhaps the best-known tool for constructing parsers from regular
  308 expressions. In the Lex processing model, generated code attempts to match one
  309 of the user's regular expression patterns, favouring longer matches over
  310 shorter ones. Once a match is made it then executes the code associated with
  311 the pattern and consumes the matching string.  This process is repeated until
  312 the input is fully consumed. 
  314 Through the use of start conditions, related sets of patterns may be defined.
  315 The active set may be changed at any time.  This allows the user to define
  316 different lexical regions. It also allows the user to link patterns together by
  317 requiring that some patterns come before others.  This is quite like a
  318 concatenation operation. However, use of Lex for languages that require a
  319 considerable amount of pattern concatenation is inappropriate. In such cases a
  320 Lex program deteriorates into a manually specified state machine, where start
  321 conditions define the states and pattern actions define the transitions.  Lex
  322 is therefore best suited to parsing tasks where the language to be parsed can
  323 be described in terms of regions of tokens. 
  325 Lex is useful in many scenarios and has undoubtedly stood the test of time.
  326 There are, however, several drawbacks to using Lex.  Lex can impose too much
  327 overhead for parsing applications where buffering is not required because all
  328 the characters are available in a single string.  In these cases there is
  329 structure to the language to be parsed and a parser specification tool can
  330 help, but employing a heavyweight processing loop that imposes a stream
  331 ``pull'' model and dynamic input buffer allocation is inappropriate.  An
  332 example of this kind of scenario is the conversion of floating point numbers
  333 contained in a string to their corresponding numerical values.
  335 Another drawback is the very issue that Ragel attempts to solve.
  336 It is not possible to execute a user action while
  337 matching a character contained inside a pattern. For example, if scanning a
  338 programming language and string literals can contain newlines which must be
  339 counted, a Lex user must break up a string literal pattern so as to associate
  340 an action with newlines. This forces the definition of a new start condition.
  341 Alternatively the user can reprocess the text of the matched string literal to
  342 count newlines. 
  344 \begin{comment}
  345 How ragel is different from Lex.
  347 %Like Re2c, Ragel provides a simple execution model that does not make any
  348 %assumptions as to how the input is collected.  Also, Ragel does not do any
  349 %buffering in the generated code. Consequently there are no dependencies on
  350 %external functions such as \verb|malloc|. 
  352 %If buffering is required it can be manually implemented by embedding actions
  353 %that copy the current character to a buffer, or data can be passed to the
  354 %parser using known block boundaries. If the longest-match operator is used,
  355 %Ragel requires the user to ensure that the ending portion of the input buffer
  356 %is preserved when the buffer is exhaused before a token is fully matched. The
  357 %user should move the token prefix to a new memory location, such as back to the
  358 %beginning of the input buffer, then place the subsequently read input
  359 %immediately after the prefix.
  361 %These properties of Ragel make it more work to write a program that requires
  362 %the longest-match operator or buffering of input, however they make Ragel a
  363 %more flexible tool that can produce very simple and fast-running programs under
  364 %a variety of input acquisition arrangements.
  366 %In Ragel, it is not necessary
  367 %to introduce start conditions to concatenate tokens and retain action
  368 %execution. Ragel allows one to structure a parser as a series of tokens, but
  369 %does not require it.
  371 %Like Lex and Re2C, Ragel is able to process input using a longest-match
  372 %execution model, however the core of the Ragel language specifies parsers at a
  373 %much lower level. This core is built around a pure state machine model. When
  374 %building basic machines there is no implied algorithm for processing input
  375 %other than to move from state to state on the transitions of the machine. This
  376 %core of pure state machine operations makes Ragel well suited to handling
  377 %parsing problems not based on token scanning. Should one need to use a
  378 %longest-match model, the functionality is available and the lower level state
  379 %machine construction facilities can be used to specify the patterns of a
  380 %longest-match machine.
  382 %This is not possible in Ragel. One can only program
  383 %a longest-match instantiation with a fixed set of rules. One can jump to
  384 %another longest-match machine that employs the same machine definitions in the
  385 %construction of its rules, however no states will be shared.
  387 %In Ragel, input may be re-parsed using a
  388 %different machine, but since the action to be executed is associated with
  389 %transitions of the compiled state machine, the longest-match construction does
  390 %not permit a single rule to be excluded from the active set. It cannot be done
  391 %ahead of time nor in the excluded rule's action.
  392 \end{comment}
  394 The Re2C program defines an input processing model similar to that of Lex.
  395 Re2C focuses on making generated state machines run very fast and
  396 integrate easily into any program, free of dependencies.  Re2C generates
  397 directly executable code and is able to claim that generated parsers run nearly
  398 as fast as their hand-coded equivalents.  This is very important for user
  399 adoption, as programmers are reluctant to use a tool when a faster alternative
  400 exists.  A consideration to ease of use is also important because developers
  401 need the freedom to integrate the generated code as they see fit. 
  403 Many scripting languages provide ways of composing parsers by linking regular
  404 expressions using program logic. For example, Sed and Awk are two established
  405 Unix scripting tools that allow the programmer to exploit regular expressions
  406 for the purpose of locating and extracting text of interest. High-level
  407 programming languages such as Perl, Python, PHP and Ruby all provide regular
  408 expression libraries that allow the user to combine regular expressions with
  409 arbitrary code.
  411 In addition to supporting the linking of regular expressions with arbitrary
  412 program logic, the Perl programming language permits the embedding of code into
  413 regular expressions. Perl embeddings do not translate into the embedding of
  414 code into deterministic state machines. Perl regular expressions are in fact
  415 not fully compiled to deterministic machines when embedded code is involved.
  416 They are instead interpreted and involve backtracking. This is shown by the
  417 following Perl program. When it is fed the input \verb|abcd| the interpretor
  418 attempts to match the first alternative, printing \verb|a1 b1|.  When this
  419 possibility fails it backtracks and tries the second possibility, printing
  420 \verb|a2 b2|, at which point it succeeds.
  422 \begin{inline_code}
  423 \begin{verbatim}
  424 print "YES\n" if ( <STDIN> =~
  425         /( a (?{ print "a1 "; }) b (?{ print "b1 "; }) cX ) |
  426          ( a (?{ print "a2 "; }) b (?{ print "b2 "; }) cd )/x )
  427 \end{verbatim}
  428 \end{inline_code}
  429 \verbspace
  431 In Ragel there is no regular expression interpretor. Aside from the scanner
  432 operator, all Ragel expressions are made into deterministic machines and the
  433 run time simply moves from state to state as it consumes input. An equivalent
  434 parser expressed in Ragel would attempt both of the alternatives concurrently,
  435 printing \verb|a1 a2 b1 b2|.
  437 \section{Development Status}
  439 Ragel is a relatively new tool and is under continuous development. As a rough
  440 release guide, minor revision number changes are for implementation
  441 improvements and feature additions. Major revision number changes are for
  442 implementation and language changes that do not preserve backwards
  443 compatibility. Though in the past this has not always held true: changes that
  444 break code have crept into minor version number changes. Typically, the
  445 documentation lags behind the development in the interest of documenting only
  446 the lasting features. The latest changes are always documented in the ChangeLog
  447 file. 
  449 \chapter{Constructing State Machines}
  451 \section{Ragel State Machine Specifications}
  453 A Ragel input file consists of a program in the host language that contains embedded machine
  454 specifications.  Ragel normally passes input straight to output.  When it sees
  455 a machine specification it stops to read the Ragel statements and possibly generate
  456 code in place of the specification.
  457 Afterwards it continues to pass input through.  There
  458 can be any number of FSM specifications in an input file. A multi-line FSM spec
  459 starts with \verb|%%{| and ends with \verb|}%%|. A single-line FSM spec starts
  460 with \verb|%%| and ends at the first newline.  
  462 While Ragel is looking for FSM specifications it does basic lexical analysis on
  463 the surrounding input. It interprets literal strings and comments so a
  464 \verb|%%| sequence in either of those will not trigger the parsing of an FSM
  465 specification. Ragel does not pass the input through any preprocessor nor does it
  466 interpret preprocessor directives itself so includes, defines and ifdef logic
  467 cannot be used to alter the parse of a Ragel input file. It is therefore not
  468 possible to use an \verb|#if 0| directive to comment out a machine as is
  469 commonly done in C code. As an alternative, a machine can be prevented from
  470 causing any generated output by commenting out write statements.
  472 In Figure \ref{cmd-line-parsing}, a multi-line specification is used to define the
  473 machine and single line specifications are used to trigger the writing of the machine
  474 data and execution code.
  476 \begin{figure}
  477 \begin{multicols}{2}
  478 \small
  479 \begin{verbatim}
  480 #include <string.h>
  481 #include <stdio.h>
  483 %%{ 
  484     machine foo;
  485     main := 
  486         ( 'foo' | 'bar' ) 
  487         0 @{ res = 1; };
  488 }%%
  490 %% write data;
  491 \end{verbatim}
  492 \columnbreak
  493 \begin{verbatim}
  494 int main( int argc, char **argv )
  495 {
  496     int cs, res = 0;
  497     if ( argc > 1 ) {
  498         char *p = argv[1];
  499         char *pe = p + strlen(p) + 1;
  500         %% write init;
  501         %% write exec;
  502     }
  503     printf("result = %i\n", res );
  504     return 0;
  505 }
  506 \end{verbatim}
  507 \end{multicols}
  508 \caption{Parsing a command line argument.}
  509 \label{cmd-line-parsing}
  510 \end{figure}
  512 \subsection{Naming Ragel Blocks}
  514 \begin{verbatim}
  515 machine fsm_name;
  516 \end{verbatim}
  517 \verbspace
  519 The \verb|machine| statement gives the name of the FSM. If present in a
  520 specification, this statement must appear first. If a machine specification
  521 does not have a name then Ragel uses the previous specification name.  If no
  522 previous specification name exists then this is an error. Because FSM
  523 specifications persist in memory, a machine's statements can be spread across
  524 multiple machine specifications.  This allows one to break up a machine across
  525 several files or draw in statements that are common to multiple machines using
  526 the \verb|include| statement.
  528 \subsection{Machine Definition}
  529 \label{definition}
  531 \begin{verbatim}
  532 <name> = <expression>;
  533 \end{verbatim}
  534 \verbspace
  536 The machine definition statement associates an FSM expression with a name. Machine
  537 expressions assigned to names can later be referenced in other expressions. A
  538 definition statement on its own does not cause any states to be generated. It is simply a
  539 description of a machine to be used later. States are generated only when a definition is
  540 instantiated, which happens when a definition is referenced in an instantiated
  541 expression. 
  543 \subsection{Machine Instantiation}
  544 \label{instantiation}
  546 \begin{verbatim}
  547 <name> := <expression>;
  548 \end{verbatim}
  549 \verbspace
  551 The machine instantiation statement generates a set of states representing an
  552 expression. Each instantiation generates a distinct set of states.  The starting
  553 state of the instantiation is written in the data section of the generated code
  554 using the instantiation name.  If a machine named
  555 \verb|main| is instantiated, its start state is used as the
  556 specification's start state and is assigned to the \verb|cs| variable by the
  557 \verb|write init| command. If no \verb|main| machine is given, the start state
  558 of the last machine instantiation to appear is used as the specification's
  559 start state.
  561 From outside the execution loop, control may be passed to any machine by
  562 assigning the entry point to the \verb|cs| variable.  From inside the execution
  563 loop, control may be passed to any machine instantiation using \verb|fcall|,
  564 \verb|fgoto| or \verb|fnext| statements.
  566 \subsection{Including Ragel Code}
  568 \begin{verbatim}
  569 include FsmName "inputfile.rl";
  570 \end{verbatim}
  571 \verbspace
  573 The \verb|include| statement can be used to draw in the statements of another FSM
  574 specification. Both the name and input file are optional, however at least one
  575 must be given. Without an FSM name, the given input file is searched for an FSM
  576 of the same name as the current specification. Without an input file the
  577 current file is searched for a machine of the given name. If both are present,
  578 the given input file is searched for a machine of the given name.
  580 Ragel searches for included files from the location of the current file.
  581 Additional directories can be added to the search path using the \verb|-I|
  582 option.
  584 \subsection{Importing Definitions}
  585 \label{import}
  587 \begin{verbatim}
  588 import "inputfile.h";
  589 \end{verbatim}
  590 \verbspace
  592 The \verb|import| statement scrapes a file for sequences of tokens that match
  593 the following forms. Ragel treats these forms as state machine definitions.
  595 \begin{itemize}
  596     \setlength{\itemsep}{-2mm}
  597     \item \verb|name '=' number|
  598     \item \verb|name '=' lit_string|
  599     \item \verb|'define' name number|
  600     \item \verb|'define' name lit_string|
  601 \end{itemize}
  603 If the input file is a Ragel program then tokens inside any Ragel
  604 specifications are ignored. See Section \ref{export} for a description of
  605 exporting machine definitions.
  607 Ragel searches for imported files from the location of the current file.
  608 Additional directories can be added to the search path using the \verb|-I|
  609 option.
  611 \section{Lexical Analysis of a Ragel Block}
  612 \label{lexing}
  614 Within a machine specification the following lexical rules apply to the input.
  616 \begin{itemize}
  618 \item The \verb|#| symbol begins a comment that terminates at the next newline.
  620 \item The symbols \verb|""|, \verb|''|, \verb|//|, \verb|[]| behave as the
  621 delimiters of literal strings. Within them, the following escape sequences 
  622 are interpreted: 
  624 \verb|    \0 \a \b \t \n \v \f \r|
  626 A backslash at the end of a line joins the following line onto the current. A
  627 backslash preceding any other character removes special meaning. This applies
  628 to terminating characters and to special characters in regular expression
  629 literals. As an exception, regular expression literals do not support escape
  630 sequences as the operands of a range within a list. See the bullet on regular
  631 expressions in Section \ref{basic}.
  633 \item The symbols \verb|{}| delimit a block of host language code that will be
  634 embedded into the machine as an action.  Within the block of host language
  635 code, basic lexical analysis of comments and strings is done in order to
  636 correctly find the closing brace of the block. With the exception of FSM
  637 commands embedded in code blocks, the entire block is preserved as is for
  638 identical reproduction in the output code.
  640 \item The pattern \verb|[+-]?[0-9]+| denotes an integer in decimal format.
  641 Integers used for specifying machines may be negative only if the alphabet type
  642 is signed. Integers used for specifying priorities may be positive or negative.
  644 \item The pattern \verb|0x[0-9A-Fa-f]+| denotes an integer in hexadecimal
  645 format.
  647 \item The keywords are \verb|access|, \verb|action|, \verb|alphtype|,
  648 \verb|getkey|, \verb|write|, \verb|machine| and \verb|include|.
  650 \item The pattern \verb|[a-zA-Z_][a-zA-Z_0-9]*| denotes an identifier.
  652 %\item The allowable symbols are:
  653 %
  654 %\verb/    ( ) ! ^ * ? + : -> - | & . , := = ; > @ $ % /\\
  655 %\verb|    >/  $/  %/  </  @/  <>/ >!  $!  %!  <!  @!  <>!|\\
  656 %\verb|    >^  $^  %^  <^  @^  <>^ >~  $~  %~  <~  @~  <>~|\\
  657 %\verb|    >*  $*  %*  <*  @*  <>*|
  659 \item Any amount of whitespace may separate tokens.
  661 \end{itemize}
  663 %\section{Parse of an FSM Specification}
  665 %The following statements are possible within an FSM specification. The
  666 %requirements for trailing semicolons loosely follow that of C. 
  667 %A block
  668 %specifying code does not require a trailing semicolon. An expression
  669 %statement does require a trailing semicolon.
  672 \section{Basic Machines}
  673 \label{basic}
  675 The basic machines are the base operands of regular language expressions. They
  676 are the smallest unit to which machine construction and manipulation operators
  677 can be applied.
  679 \begin{itemize}
  681 \item \verb|'hello'| -- Concatenation Literal. Produces a machine that matches
  682 the sequence of characters in the quoted string. If there are 5 characters
  683 there will be 6 states chained together with the characters in the string. See
  684 Section \ref{lexing} for information on valid escape sequences. 
  686 % GENERATE: bmconcat
  687 % OPT: -p
  688 % %%{
  689 % machine bmconcat;
  690 \begin{comment}
  691 \begin{verbatim}
  692 main := 'hello';
  693 \end{verbatim}
  694 \end{comment}
  695 % }%%
  698 \begin{center}
  699 \includegraphics[scale=0.55]{bmconcat}
  700 \end{center}
  702 It is possible
  703 to make a concatenation literal case-insensitive by appending an \verb|i| to
  704 the string, for example \verb|'cmd'i|.
  706 \item \verb|"hello"| -- Identical to the single quoted version.
  708 \item \verb|[hello]| -- Or Expression. Produces a union of characters.  There
  709 will be two states with a transition for each unique character between the two states.
  710 The \verb|[]| delimiters behave like the quotes of a literal string. For example, 
  711 \verb|[ \t]| means tab or space. The \verb|or| expression supports character ranges
  712 with the \verb|-| symbol as a separator. The meaning of the union can be negated
  713 using an initial \verb|^| character as in standard regular expressions. 
  714 See Section \ref{lexing} for information on valid escape sequences
  715 in \verb|or| expressions.
  717 % GENERATE: bmor
  718 % OPT: -p
  719 % %%{
  720 % machine bmor;
  721 \begin{comment}
  722 \begin{verbatim}
  723 main := [hello];
  724 \end{verbatim}
  725 \end{comment}
  726 % }%%
  729 \begin{center}
  730 \includegraphics[scale=0.55]{bmor}
  731 \end{center}
  733 \item \verb|''|, \verb|""|, and \verb|[]| -- Zero Length Machine.  Produces a machine
  734 that matches the zero length string. Zero length machines have one state that is both
  735 a start state and a final state.
  737 % GENERATE: bmnull
  738 % OPT: -p
  739 % %%{
  740 % machine bmnull;
  741 \begin{comment}
  742 \begin{verbatim}
  743 main := '';
  744 \end{verbatim}
  745 \end{comment}
  746 % }%%
  749 \begin{center}
  750 \includegraphics[scale=0.55]{bmnull}
  751 \end{center}
  753 % FIXME: More on the range of values here.
  754 \item \verb|42| -- Numerical Literal. Produces a two state machine with one
  755 transition on the given number. The number may be in decimal or hexadecimal
  756 format and should be in the range allowed by the alphabet type. The minimum and
  757 maximum values permitted are defined by the host machine that Ragel is compiled
  758 on. For example, numbers in a \verb|short| alphabet on an i386 machine should
  759 be in the range \verb|-32768| to \verb|32767|.
  761 % GENERATE: bmnum
  762 % %%{
  763 % machine bmnum;
  764 \begin{comment}
  765 \begin{verbatim}
  766 main := 42;
  767 \end{verbatim}
  768 \end{comment}
  769 % }%%
  772 \begin{center}
  773 \includegraphics[scale=0.55]{bmnum}
  774 \end{center}
  776 \item \verb|/simple_regex/| -- Regular Expression. Regular expressions are
  777 parsed as a series of expressions that are concatenated together. Each
  778 concatenated expression
  779 may be a literal character, the ``any'' character specified by the \verb|.|
  780 symbol, or a union of characters specified by the \verb|[]| delimiters. If the
  781 first character of a union is \verb|^| then it matches any character not in the
  782 list. Within a union, a range of characters can be given by separating the first
  783 and last characters of the range with the \verb|-| symbol. Each
  784 concatenated machine may have repetition specified by following it with the
  785 \verb|*| symbol. The standard escape sequences described in Section
  786 \ref{lexing} are supported everywhere in regular expressions except as the
  787 operands of a range within in a list. This notation also supports the \verb|i|
  788 trailing option. Use it to produce case-insensitive machines, as in \verb|/GET/i|.
  790 Ragel does not support very complex regular expressions because the desired
  791 results can always be achieved using the more general machine construction
  792 operators listed in Section \ref{machconst}. The following diagram shows the
  793 result of compiling \verb|/ab*[c-z].*[123]/|. \verb|DEF| represents the default
  794 transition, which is taken if no other transition can be taken. 
  797 % GENERATE: bmregex
  798 % OPT: -p
  799 % %%{
  800 % machine bmregex;
  801 \begin{comment}
  802 \begin{verbatim}
  803 main := /ab*[c-z].*[123]/;
  804 \end{verbatim}
  805 \end{comment}
  806 % }%%
  809 \begin{center}
  810 \includegraphics[scale=0.55]{bmregex}
  811 \end{center}
  813 \item \verb|'a' .. 'z'| -- Range. Produces a machine that matches any
  814 characters in the specified range.  Allowable upper and lower bounds of the
  815 range are concatenation literals of length one and numerical literals.  For
  816 example, \verb|0x10..0x20|, \verb|0..63|, and \verb|'a'..'z'| are valid ranges.
  817 The bounds should be in the range allowed by the alphabet type.
  819 % GENERATE: bmrange
  820 % OPT: -p
  821 % %%{
  822 % machine bmrange;
  823 \begin{comment}
  824 \begin{verbatim}
  825 main := 'a' .. 'z';
  826 \end{verbatim}
  827 \end{comment}
  828 % }%%
  831 \begin{center}
  832 \includegraphics[scale=0.55]{bmrange}
  833 \end{center}
  836 \item \verb|variable_name| -- Lookup the machine definition assigned to the
  837 variable name given and use an instance of it. See Section \ref{definition} for
  838 an important note on what it means to reference a variable name.
  840 \item \verb|builtin_machine| -- There are several built-in machines available
  841 for use. They are all two state machines for the purpose of matching common
  842 classes of characters. They are:
  844 \begin{itemize}
  846 \item \verb|any   | -- Any character in the alphabet.
  848 \item \verb|ascii | -- Ascii characters. \verb|0..127|
  850 \item \verb|extend| -- Ascii extended characters. This is the range
  851 \verb|-128..127| for signed alphabets and the range \verb|0..255| for unsigned
  852 alphabets.
  854 \item \verb|alpha | -- Alphabetic characters. \verb|[A-Za-z]|
  856 \item \verb|digit | -- Digits. \verb|[0-9]|
  858 \item \verb|alnum | -- Alpha numerics. \verb|[0-9A-Za-z]|
  860 \item \verb|lower | -- Lowercase characters. \verb|[a-z]|
  862 \item \verb|upper | -- Uppercase characters. \verb|[A-Z]|
  864 \item \verb|xdigit| -- Hexadecimal digits. \verb|[0-9A-Fa-f]|
  866 \item \verb|cntrl | -- Control characters. \verb|0..31|
  868 \item \verb|graph | -- Graphical characters. \verb|[!-~]|
  870 \item \verb|print | -- Printable characters. \verb|[ -~]|
  872 \item \verb|punct | -- Punctuation. Graphical characters that are not alphanumerics.
  873 \verb|[!-/:-@[-`{-~]|
  875 \item \verb|space | -- Whitespace. \verb|[\t\v\f\n\r ]|
  877 \item \verb|zlen  | -- Zero length string. \verb|""|
  879 \item \verb|empty | -- Empty set. Matches nothing. \verb|^any|
  881 \end{itemize}
  882 \end{itemize}
  884 \section{Operator Precedence}
  885 The following table shows operator precedence from lowest to highest. Operators
  886 in the same precedence group are evaluated from left to right.
  888 \verbspace
  889 \begin{tabular}{|c|c|c|}
  890 \hline
  891 1&\verb| , |&Join\\
  892 \hline
  893 2&\verb/ | & - --/&Union, Intersection and Subtraction\\
  894 \hline
  895 3&\verb| . <: :> :>> |&Concatenation\\
  896 \hline
  897 4&\verb| : |&Label\\
  898 \hline
  899 5&\verb| -> |&Epsilon Transition\\
  900 \hline
  901 &\verb| >  @  $  % |&Transitions Actions and Priorities\\
  902 \cline{2-3}
  903 &\verb| >/  $/  %/  </  @/  <>/ |&EOF Actions\\
  904 \cline{2-3}
  905 6&\verb| >!  $!  %!  <!  @!  <>! |&Global Error Actions\\
  906 \cline{2-3}
  907 &\verb| >^  $^  %^  <^  @^  <>^ |&Local Error Actions\\
  908 \cline{2-3}
  909 &\verb| >~  $~  %~  <~  @~  <>~ |&To-State Actions\\
  910 \cline{2-3}
  911 &\verb| >*  $*  %*  <*  @*  <>* |&From-State Action\\
  912 \hline
  913 7&\verb| * ** ? + {n} {,n} {n,} {n,m} |&Repetition\\
  914 \hline
  915 8&\verb| ! ^ |&Negation and Character-Level Negation\\
  916 \hline
  917 9&\verb| ( <expr> ) |&Grouping\\
  918 \hline
  919 \end{tabular}
  921 \section{Regular Language Operators}
  922 \label{machconst}
  924 When using Ragel it is helpful to have a sense of how it constructs machines.
  925 The determinization process can produce results that seem unusual to someone
  926 not familiar with the NFA to DFA conversion algorithm. In this section we
  927 describe Ragel's state machine operators. Though the operators are defined
  928 using epsilon transitions, it should be noted that this is for discussion only.
  929 The epsilon transitions described in this section do not persist, but are
  930 immediately removed by the determinization process which is executed at every
  931 operation. Ragel does not make use of any nondeterministic intermediate state
  932 machines. 
  934 To create an epsilon transition between two states \verb|x| and \verb|y| is to
  935 copy all of the properties of \verb|y| into \verb|x|. This involves drawing in
  936 all of \verb|y|'s to-state actions, EOF actions, etc., in addition to its
  937 transitions. If \verb|x| and \verb|y| both have a transition out on the same
  938 character, then the transitions must be combined.  During transition
  939 combination a new transition is made that goes to a new state that is the
  940 combination of both target states. The new combination state is created using
  941 the same epsilon transition method.  The new state has an epsilon transition
  942 drawn to all the states that compose it. Since the creation of new epsilon
  943 transitions may be triggered every time an epsilon transition is drawn, the
  944 process of drawing epsilon transitions is repeated until there are no more
  945 epsilon transitions to be made.
  947 A very common error that is made when using Ragel is to make machines that do
  948 too much. That is, to create machines that have unintentional
  949 nondetermistic properties. This usually results from being unaware of the common strings
  950 between machines that are combined together using the regular language
  951 operators. This can involve never leaving a machine, causing its actions to be
  952 propagated through all the following states. Or it can involve an alternation
  953 where both branches are unintentionally taken simultaneously.
  955 This problem forces one to think hard about the language that needs to be
  956 matched. To guard against this kind of problem one must ensure that the machine
  957 specification is divided up using boundaries that do not allow ambiguities from
  958 one portion of the machine to the next. See Chapter
  959 \ref{controlling-nondeterminism} for more on this problem and how to solve it.
  961 The Graphviz tool is an immense help when debugging improperly compiled
  962 machines or otherwise learning how to use Ragel. Graphviz Dot files can be
  963 generated from Ragel programs using the \verb|-V| option. See Section
  964 \ref{visualization} for more information.
  967 \subsection{Union}
  969 \verb/expr | expr/
  970 \verbspace
  972 The union operation produces a machine that matches any string in machine one
  973 or machine two. The operation first creates a new start state. Epsilon
  974 transitions are drawn from the new start state to the start states of both
  975 input machines.  The resulting machine has a final state set equivalent to the
  976 union of the final state sets of both input machines. In this operation, there
  977 is the opportunity for nondeterminism among both branches. If there are
  978 strings, or prefixes of strings that are matched by both machines then the new
  979 machine will follow both parts of the alternation at once. The union operation is
  980 shown below.
  982 \graphspace
  983 \begin{center}
  984 \includegraphics{opor}
  985 \end{center}
  986 \graphspace
  988 The following example demonstrates the union of three machines representing
  989 common tokens.
  991 % GENERATE: exor
  992 % OPT: -p
  993 % %%{
  994 % machine exor;
  995 \begin{inline_code}
  996 \begin{verbatim}
  997 # Hex digits, decimal digits, or identifiers
  998 main := '0x' xdigit+ | digit+ | alpha alnum*;
  999 \end{verbatim}
 1000 \end{inline_code}
 1001 % }%%
 1004 \graphspace
 1005 \begin{center}
 1006 \includegraphics[scale=0.55]{exor}
 1007 \end{center}
 1009 \subsection{Intersection}
 1011 \verb|expr & expr|
 1012 \verbspace
 1014 Intersection produces a machine that matches any
 1015 string that is in both machine one and machine two. To achieve intersection, a
 1016 union is performed on the two machines. After the result has been made
 1017 deterministic, any final state that is not a combination of final states from
 1018 both machines has its final state status revoked. To complete the operation,
 1019 paths that do not lead to a final state are pruned from the machine. Therefore,
 1020 if there are any such paths in either of the expressions they will be removed
 1021 by the intersection operator.  Intersection can be used to require that two
 1022 independent patterns be simultaneously satisfied as in the following example.
 1024 % GENERATE: exinter
 1025 % OPT: -p
 1026 % %%{
 1027 % machine exinter;
 1028 \begin{inline_code}
 1029 \begin{verbatim}
 1030 # Match lines four characters wide that contain 
 1031 # words separated by whitespace.
 1032 main :=
 1033     /[^\n][^\n][^\n][^\n]\n/* &
 1034     (/[a-z][a-z]*/ | [ \n])**;
 1035 \end{verbatim}
 1036 \end{inline_code}
 1037 % }%%
 1040 \graphspace
 1041 \begin{center}
 1042 \includegraphics[scale=0.55]{exinter}
 1043 \end{center}
 1045 \subsection{Difference}
 1047 \verb|expr - expr|
 1048 \verbspace
 1050 The difference operation produces a machine that matches
 1051 strings that are in machine one but are not in machine two. To achieve subtraction,
 1052 a union is performed on the two machines. After the result has been made
 1053 deterministic, any final state that came from machine two or is a combination
 1054 of states involving a final state from machine two has its final state status
 1055 revoked. As with intersection, the operation is completed by pruning any path
 1056 that does not lead to a final state.  The following example demonstrates the
 1057 use of subtraction to exclude specific cases from a set.
 1059 \verbspace
 1061 % GENERATE: exsubtr
 1062 % OPT: -p
 1063 % %%{
 1064 % machine exsubtr;
 1065 \begin{inline_code}
 1066 \begin{verbatim}
 1067 # Subtract keywords from identifiers.
 1068 main := /[a-z][a-z]*/ - ( 'for' | 'int' );
 1069 \end{verbatim}
 1070 \end{inline_code}
 1071 % }%%
 1074 \graphspace
 1075 \begin{center}
 1076 \includegraphics[scale=0.55]{exsubtr}
 1077 \end{center}
 1078 \graphspace
 1081 \subsection{Strong Difference}
 1082 \label{strong_difference}
 1084 \verb|expr -- expr|
 1085 \verbspace
 1087 Strong difference produces a machine that matches any string of the first
 1088 machine that does not have any string of the second machine as a substring. In
 1089 the following example, strong subtraction is used to excluded \verb|CRLF| from
 1090 a sequence. In the corresponding visualization, the label \verb|DEF| is short
 1091 for default. The default transition is taken if no other transition can be
 1092 taken.
 1094 % GENERATE: exstrongsubtr
 1095 % OPT: -p
 1096 % %%{
 1097 % machine exstrongsubtr;
 1098 \begin{inline_code}
 1099 \begin{verbatim}
 1100 crlf = '\r\n';
 1101 main := [a-z]+ ':' ( any* -- crlf ) crlf;
 1102 \end{verbatim}
 1103 \end{inline_code}
 1104 % }%%
 1107 \graphspace
 1108 \begin{center}
 1109 \includegraphics[scale=0.55]{exstrongsubtr}
 1110 \end{center}
 1111 \graphspace
 1113 This operator is equivalent to the following.
 1115 \verbspace
 1116 \begin{verbatim}
 1117 expr - ( any* expr any* )
 1118 \end{verbatim}
 1120 \subsection{Concatenation}
 1122 \verb|expr . expr|
 1123 \verbspace
 1125 Concatenation produces a machine that matches all the strings in machine one followed by all
 1126 the strings in machine two.  Concatenation draws epsilon transitions from the
 1127 final states of the first machine to the start state of the second machine. The
 1128 final states of the first machine lose their final state status, unless the
 1129 start state of the second machine is final as well. 
 1130 Concatenation is the default operator. Two machines next to each other with no
 1131 operator between them results in concatenation.
 1133 \graphspace
 1134 \begin{center}
 1135 \includegraphics{opconcat}
 1136 \end{center}
 1137 \graphspace
 1139 The opportunity for nondeterministic behaviour results from the possibility of
 1140 the final states of the first machine accepting a string that is also accepted
 1141 by the start state of the second machine.
 1142 The most common scenario in which this happens is the
 1143 concatenation of a machine that repeats some pattern with a machine that gives
 1144 a terminating string, but the repetition machine does not exclude the
 1145 terminating string. The example in Section \ref{strong_difference}
 1146 guards against this. Another example is the expression \verb|("'" any* "'")|.
 1147 When executed the thread of control will
 1148 never leave the \verb|any*| machine.  This is a problem especially if actions
 1149 are embedded to process the characters of the \verb|any*| component.
 1151 In the following example, the first machine is always active due to the
 1152 nondeterministic nature of concatenation. This particular nondeterminism is intended
 1153 however because we wish to permit EOF strings before the end of the input.
 1155 % GENERATE: exconcat
 1156 % OPT: -p
 1157 % %%{
 1158 % machine exconcat;
 1159 \begin{inline_code}
 1160 \begin{verbatim}
 1161 # Require an eof marker on the last line.
 1162 main := /[^\n]*\n/* . 'EOF\n';
 1163 \end{verbatim}
 1164 \end{inline_code}
 1165 % }%%
 1168 \graphspace
 1169 \begin{center}
 1170 \includegraphics[scale=0.55]{exconcat}
 1171 \end{center}
 1172 \graphspace
 1174 \noindent {\bf Note:} There is a language
 1175 ambiguity involving concatenation and subtraction. Because concatenation is the 
 1176 default operator for two
 1177 adjacent machines there is an ambiguity between subtraction of
 1178 a positive numerical literal and concatenation of a negative numerical literal.
 1179 For example, \verb|(x-7)| could be interpreted as \verb|(x . -7)| or 
 1180 \verb|(x - 7)|. In the Ragel language, the subtraction operator always takes precedence
 1181 over concatenation of a negative literal. We adhere to the rule that the default
 1182 concatenation operator takes effect only when there are no other operators between
 1183 two machines. Beware of writing machines such as \verb|(any -1)| when what is
 1184 desired is a concatenation of \verb|any| and \verb|-1|. Instead write 
 1185 \verb|(any . -1)| or \verb|(any (-1))|. If in doubt of the meaning of your program do not
 1186 rely on the default concatenation operator; always use the \verb|.| symbol.
 1189 \subsection{Kleene Star}
 1191 \verb|expr*|
 1192 \verbspace
 1194 The machine resulting from the Kleene Star operator will match zero or more
 1195 repetitions of the machine it is applied to.
 1196 It creates a new start state and an additional final
 1197 state.  Epsilon transitions are drawn between the new start state and the old start
 1198 state, between the new start state and the new final state, and
 1199 between the final states of the machine and the new start state.  After the
 1200 machine is made deterministic the effect is of the final states getting all the
 1201 transitions of the start state. 
 1203 \graphspace
 1204 \begin{center}
 1205 \includegraphics{opstar}
 1206 \end{center}
 1207 \graphspace
 1209 The possibility for nondeterministic behaviour arises if the final states have
 1210 transitions on any of the same characters as the start state.  This is common
 1211 when applying kleene star to an alternation of tokens. Like the other problems
 1212 arising from nondeterministic behavior, this is discussed in more detail in Chapter
 1213 \ref{controlling-nondeterminism}. This particular problem can also be solved
 1214 by using the longest-match construction discussed in Section 
 1215 \ref{generating-scanners} on scanners.
 1217 In this 
 1218 example, there is no nondeterminism introduced by the exterior kleene star due to
 1219 the newline at the end of the regular expression. Without the newline the
 1220 exterior kleene star would be redundant and there would be ambiguity between
 1221 repeating the inner range of the regular expression and the entire regular
 1222 expression. Though it would not cause a problem in this case, unnecessary
 1223 nondeterminism in the kleene star operator often causes undesired results for
 1224 new Ragel users and must be guarded against.
 1226 % GENERATE: exstar
 1227 % OPT: -p
 1228 % %%{
 1229 % machine exstar;
 1230 \begin{inline_code}
 1231 \begin{verbatim}
 1232 # Match any number of lines with only lowercase letters.
 1233 main := /[a-z]*\n/*;
 1234 \end{verbatim}
 1235 \end{inline_code}
 1236 % }%%
 1239 \graphspace
 1240 \begin{center}
 1241 \includegraphics[scale=0.55]{exstar}
 1242 \end{center}
 1243 \graphspace
 1245 \subsection{One Or More Repetition}
 1247 \verb|expr+|
 1248 \verbspace
 1250 This operator produces the concatenation of the machine with the kleene star of
 1251 itself. The result will match one or more repetitions of the machine. The plus
 1252 operator is equivalent to \verb|(expr . expr*)|.  
 1254 % GENERATE: explus
 1255 % OPT: -p
 1256 % %%{
 1257 % machine explus;
 1258 \begin{inline_code}
 1259 \begin{verbatim}
 1260 # Match alpha-numeric words.
 1261 main := alnum+;
 1262 \end{verbatim}
 1263 \end{inline_code}
 1264 % }%%
 1267 \graphspace
 1268 \begin{center}
 1269 \includegraphics[scale=0.55]{explus}
 1270 \end{center}
 1271 \graphspace
 1273 \subsection{Optional}
 1275 \verb|expr?|
 1276 \verbspace
 1278 The {\em optional} operator produces a machine that accepts the machine
 1279 given or the zero length string. The optional operator is equivalent to
 1280 \verb/(expr | '' )/. In the following example the optional operator is used to
 1281 possibly extend a token.
 1283 % GENERATE: exoption
 1284 % OPT: -p
 1285 % %%{
 1286 % machine exoption;
 1287 \begin{inline_code}
 1288 \begin{verbatim}
 1289 # Match integers or floats.
 1290 main := digit+ ('.' digit+)?;
 1291 \end{verbatim}
 1292 \end{inline_code}
 1293 % }%%
 1296 \graphspace
 1297 \begin{center}
 1298 \includegraphics[scale=0.55]{exoption}
 1299 \end{center}
 1300 \graphspace
 1303 \subsection{Repetition}
 1305 \begin{tabbing}
 1306 \noindent \verb|expr {n}| \hspace{16pt}\=-- Exactly N copies of expr.\\
 1308 \noindent \verb|expr {,n}| \>-- Zero to N copies of expr.\\
 1310 \noindent \verb|expr {n,}| \>-- N or more copies of expr.\\
 1312 \noindent \verb|expr {n,m}| \>-- N to M copies of expr.
 1313 \end{tabbing}
 1315 \subsection{Negation}
 1317 \verb|!expr|
 1318 \verbspace
 1320 Negation produces a machine that matches any string not matched by the given
 1321 machine. Negation is equivalent to \verb|(any* - expr)|.
 1323 % GENERATE: exnegate
 1324 % OPT: -p
 1325 % %%{
 1326 % machine exnegate;
 1327 \begin{inline_code}
 1328 \begin{verbatim}
 1329 # Accept anything but a string beginning with a digit.
 1330 main := ! ( digit any* );
 1331 \end{verbatim}
 1332 \end{inline_code}
 1333 % }%%
 1336 \graphspace
 1337 \begin{center}
 1338 \includegraphics[scale=0.55]{exnegate}
 1339 \end{center}
 1340 \graphspace
 1343 \subsection{Character-Level Negation}
 1345 \verb|^expr|
 1346 \verbspace
 1348 Character-level negation produces a machine that matches any single character
 1349 not matched by the given machine. Character-Level Negation is equivalent to
 1350 \verb|(any - expr)|. It must be applied only to machines that match strings of
 1351 length one.
 1353 \section{State Machine Minimization}
 1355 State machine minimization is the process of finding the minimal equivalent FSM accepting
 1356 the language. Minimization reduces the number of states in machines
 1357 by merging equivalent states. It does not change the behaviour of the machine
 1358 in any way. It will cause some states to be merged into one because they are
 1359 functionally equivalent. State minimization is on by default. It can be turned
 1360 off with the \verb|-n| option.
 1362 The algorithm implemented is similar to Hopcroft's state minimization
 1363 algorithm. Hopcroft's algorithm assumes a finite alphabet that can be listed in
 1364 memory, whereas Ragel supports arbitrary integer alphabets that cannot be
 1365 listed in memory. Though exact analysis is very difficult, Ragel minimization
 1366 runs close to $O(n \times log(n))$ and requires $O(n)$ temporary storage where
 1367 $n$ is the number of states.
 1369 \section{Visualization}
 1370 \label{visualization}
 1372 %In many cases, practical
 1373 %parsing programs will be too large to completely visualize with Graphviz.  The
 1374 %proper approach is to reduce the language to the smallest subset possible that
 1375 %still exhibits the characteristics that one wishes to learn about or to fix.
 1376 %This can be done without modifying the source code using the \verb|-M| and
 1377 %\verb|-S| options. If a machine cannot be easily reduced,
 1378 %embeddings of unique actions can be very useful for tracing a
 1379 %particular component of a larger machine specification, since action names are
 1380 %written out on transition labels.
 1382 Ragel is able to emit compiled state machines in Graphviz's Dot file format.
 1383 This is done using the \verb|-V| option.
 1384 Graphviz support allows users to perform
 1385 incremental visualization of their parsers. User actions are displayed on
 1386 transition labels of the graph. 
 1388 If the final graph is too large to be
 1389 meaningful, or even drawn, the user is able to inspect portions of the parser
 1390 by naming particular regular expression definitions with the \verb|-S| and
 1391 \verb|-M| options to the \verb|ragel| program. Use of Graphviz greatly
 1392 improves the Ragel programming experience. It allows users to learn Ragel by
 1393 experimentation and also to track down bugs caused by unintended
 1394 nondeterminism.
 1396 Ragel has another option to help debugging. The \verb|-x| option causes Ragel
 1397 to emit the compiled machine in an XML format.
 1399 \chapter{User Actions}
 1401 Ragel permits the user to embed actions into the transitions of a regular
 1402 expression's corresponding state machine. These actions are executed when the
 1403 generated code moves over a transition.  Like the regular expression operators,
 1404 the action embedding operators are fully compositional. They take a state
 1405 machine and an action as input, embed the action and yield a new state machine
 1406 that can be used in the construction of other machines. Due to the
 1407 compositional nature of embeddings, the user has complete freedom in the
 1408 placement of actions.
 1410 A machine's transitions are categorized into four classes. The action embedding
 1411 operators access the transitions defined by these classes.  The {\em entering
 1412 transition} operator \verb|>| isolates the start state, then embeds an action
 1413 into all transitions leaving it. The {\em finishing transition} operator
 1414 \verb|@| embeds an action into all transitions going into a final state.  The
 1415 {\em all transition} operator \verb|$| embeds an action into all transitions of
 1416 an expression. The {\em leaving transition} operator \verb|%| provides access
 1417 to the yet-unmade transitions moving out of the machine via the final states. 
 1419 \section{Embedding Actions}
 1421 \begin{verbatim}
 1422 action ActionName {
 1423     /* Code an action here. */
 1424     count += 1;
 1425 }
 1426 \end{verbatim}
 1427 \verbspace
 1429 The action statement defines a block of code that can be embedded into an FSM.
 1430 Action names can be referenced by the action embedding operators in
 1431 expressions. Though actions need not be named in this way (literal blocks
 1432 of code can be embedded directly when building machines), defining reusable
 1433 blocks of code whenever possible is good practice because it potentially increases the
 1434 degree to which the machine can be minimized. 
 1436 Within an action some Ragel expressions and statements are parsed and
 1437 translated. These allow the user to interact with the machine from action code.
 1438 See Section \ref{vals} for a complete list of statements and values available
 1439 in code blocks. 
 1441 \subsection{Entering Action}
 1443 \verb|expr > action| 
 1444 \verbspace
 1446 The entering action operator embeds an action into all transitions
 1447 that enter into the machine from the start state. If the start state is final,
 1448 then the action is also embedded into the start state as a leaving action. This
 1449 means that if a machine accepts the zero-length string and control passes
 1450 through the start state then the entering action is executed. Note
 1451 that this can happen on both a following character and on the EOF event.
 1453 In some machines the start state has transtions coming in from within the
 1454 machine. In these cases the start state is first isolated from the rest of the
 1455 machine ensuring that the entering actions are exected once only.
 1457 \verbspace
 1459 % GENERATE: exstact
 1460 % OPT: -p
 1461 % %%{
 1462 % machine exstact;
 1463 \begin{inline_code}
 1464 \begin{verbatim}
 1465 # Execute A at the beginning of a string of alpha.
 1466 action A {}
 1467 main := ( lower* >A ) . ' ';
 1468 \end{verbatim}
 1469 \end{inline_code}
 1470 % }%%
 1473 \graphspace
 1474 \begin{center}
 1475 \includegraphics[scale=0.55]{exstact}
 1476 \end{center}
 1477 \graphspace
 1479 \subsection{Finishing Action}
 1481 \verb|expr @ action|
 1482 \verbspace
 1484 The finishing action operator embeds an action into any transitions that move
 1485 the machine into a final state. Further input may move the machine out of the
 1486 final state, but keep it in the machine. Therefore finishing actions may be
 1487 executed more than once if a machine has any internal transitions out of a
 1488 final state. In the following example the final state has no transitions out
 1489 and the finishing action is executed only once.
 1491 % GENERATE: exdoneact
 1492 % OPT: -p
 1493 % %%{
 1494 % machine exdoneact;
 1495 % action A {}
 1496 \begin{inline_code}
 1497 \begin{verbatim}
 1498 # Execute A when the trailing space is seen.
 1499 main := ( lower* ' ' ) @A;
 1500 \end{verbatim}
 1501 \end{inline_code}
 1502 % }%%
 1505 \graphspace
 1506 \begin{center}
 1507 \includegraphics[scale=0.55]{exdoneact}
 1508 \end{center}
 1509 \graphspace
 1512 \subsection{All Transition Action}
 1514 \verb|expr $ action|
 1515 \verbspace
 1517 The all transition operator embeds an action into all transitions of a machine.
 1518 The action is executed whenever a transition of the machine is taken. In the
 1519 following example, A is executed on every character matched.
 1521 % GENERATE: exallact
 1522 % OPT: -p
 1523 % %%{
 1524 % machine exallact;
 1525 % action A {}
 1526 \begin{inline_code}
 1527 \begin{verbatim}
 1528 # Execute A on any characters of the machine.
 1529 main := ( 'm1' | 'm2' ) $A;
 1530 \end{verbatim}
 1531 \end{inline_code}
 1532 % }%%
 1535 \graphspace
 1536 \begin{center}
 1537 \includegraphics[scale=0.55]{exallact}
 1538 \end{center}
 1539 \graphspace
 1542 \subsection{Leaving Actions}
 1543 \label{out-actions}
 1545 \verb|expr % action|
 1546 \verbspace
 1548 The leaving action operator queues an action for embedding into the transitions
 1549 that go out of a machine via a final state. The action is first stored in
 1550 the machine's final states and is later transferred to any transitions that are
 1551 made going out of the machine by a kleene star or concatenation operation.
 1553 If a final state of the machine is still final when compilation is complete
 1554 then the leaving action is also embedded as an EOF action. Therefore, leaving
 1555 the machine is defined as either leaving on a character or as state machine
 1556 acceptance.
 1558 This operator allows one to associate an action with the termination of a
 1559 sequence, without being concerned about what particular character terminates
 1560 the sequence. In the following example, A is executed when leaving the alpha
 1561 machine on the newline character.
 1563 % GENERATE: exoutact1
 1564 % OPT: -p
 1565 % %%{
 1566 % machine exoutact1;
 1567 % action A {}
 1568 \begin{inline_code}
 1569 \begin{verbatim}
 1570 # Match a word followed by a newline. Execute A when 
 1571 # finishing the word.
 1572 main := ( lower+ %A ) . '\n';
 1573 \end{verbatim}
 1574 \end{inline_code}
 1575 % }%%
 1578 \graphspace
 1579 \begin{center}
 1580 \includegraphics[scale=0.55]{exoutact1}
 1581 \end{center}
 1582 \graphspace
 1584 In the following example, the \verb|term_word| action could be used to register
 1585 the appearance of a word and to clear the buffer that the \verb|lower| action used
 1586 to store the text of it.
 1588 % GENERATE: exoutact2
 1589 % OPT: -p
 1590 % %%{
 1591 % machine exoutact2;
 1592 % action lower {}
 1593 % action space {}
 1594 % action term_word {}
 1595 % action newline {}
 1596 \begin{inline_code}
 1597 \begin{verbatim}
 1598 word = ( [a-z] @lower )+ %term_word;
 1599 main := word ( ' ' @space word )* '\n' @newline;
 1600 \end{verbatim}
 1601 \end{inline_code}
 1602 % }%%
 1605 \graphspace
 1606 \begin{center}
 1607 \includegraphics[scale=0.55]{exoutact2}
 1608 \end{center}
 1609 \graphspace
 1611 In this final example of the action embedding operators, A is executed upon entering
 1612 the alpha machine, B is executed on all transitions of the
 1613 alpha machine, C is executed when the alpha machine is exited by moving into the
 1614 newline machine and N is executed when the newline machine moves into a final
 1615 state.  
 1617 % GENERATE: exaction
 1618 % OPT: -p
 1619 % %%{
 1620 % machine exaction;
 1621 % action A {}
 1622 % action B {}
 1623 % action C {}
 1624 % action N {}
 1625 \begin{inline_code}
 1626 \begin{verbatim}
 1627 # Execute A on starting the alpha machine, B on every transition 
 1628 # moving through it and C upon finishing. Execute N on the newline.
 1629 main := ( lower* >A $B %C ) . '\n' @N;
 1630 \end{verbatim}
 1631 \end{inline_code}
 1632 % }%%
 1635 \graphspace
 1636 \begin{center}
 1637 \includegraphics[scale=0.55]{exaction}
 1638 \end{center}
 1639 \graphspace
 1642 \section{State Action Embedding Operators}
 1644 The state embedding operators allow one to embed actions into states. Like the
 1645 transition embedding operators, there are several different classes of states
 1646 that the operators access. The meanings of the symbols are similar to the
 1647 meanings of the symbols used for the transition embedding operators. The design
 1648 of the state selections was driven by a need to cover the states of an
 1649 expression with exactly one error action.
 1651 Unlike the transition embedding operators, the state embedding operators are
 1652 also distinguished by the different kinds of events that embedded actions can
 1653 be associated with. Therefore the state embedding operators have two
 1654 components.  The first, which is the first one or two characters, specifies the
 1655 class of states that the action will be embedded into. The second component
 1656 specifies the type of event the action will be executed on. The symbols of the
 1657 second component also have equivalent kewords. 
 1659 \vspace{10pt}
 1661 \def\fakeitem{\hspace*{12pt}$\bullet$\hspace*{10pt}}
 1663 \begin{minipage}{\textwidth}
 1664 \begin{multicols}{2}
 1665 \raggedcolumns
 1666 \noindent The different classes of states are:\\
 1667 \fakeitem \verb|> | -- the start state\\
 1668 \fakeitem \verb|< | -- any state except the start state\\
 1669 \fakeitem \verb|$ | -- all states\\
 1670 \fakeitem \verb|% | -- final states\\
 1671 \fakeitem \verb|@ | -- any state except final states\\
 1672 \fakeitem \verb|<>| -- any except start and final (middle)
 1674 \columnbreak
 1676 \noindent The different kinds of embeddings are:\\
 1677 \fakeitem \verb|~| -- to-state actions (\verb|to|)\\
 1678 \fakeitem \verb|*| -- from-state actions (\verb|from|)\\
 1679 \fakeitem \verb|/| -- EOF actions (\verb|eof|)\\
 1680 \fakeitem \verb|!| -- error actions (\verb|err|)\\
 1681 \fakeitem \verb|^| -- local error actions (\verb|lerr|)\\
 1682 \end{multicols}
 1683 \end{minipage}
 1685 \subsection{To-State and From-State Actions}
 1687 \subsubsection{To-State Actions}
 1689 \def\sasp{\hspace*{40pt}}
 1691 \sasp\verb|>~action      >to(name)      >to{...} | -- the start state\\
 1692 \sasp\verb|<~action      <to(name)      <to{...} | -- any state except the start state\\
 1693 \sasp\verb|$~action      $to(name)      $to{...} | -- all states\\
 1694 \sasp\verb|%~action      %to(name)      %to{...} | -- final states\\
 1695 \sasp\verb|@~action      @to(name)      @to{...} | -- any state except final states\\
 1696 \sasp\verb|<>~action     <>to(name)     <>to{...}| -- any except start and final (middle)
 1697 \vspace{12pt}
 1700 To-state actions are executed whenever the state machine moves into the
 1701 specified state, either by a natural movement over a transition or by an
 1702 action-based transfer of control such as \verb|fgoto|. They are executed after the
 1703 in-transition's actions but before the current character is advanced and
 1704 tested against the end of the input block. To-state embeddings stay with the
 1705 state. They are irrespective of the state's current set of transitions and any
 1706 future transitions that may be added in or out of the state.
 1708 Note that the setting of the current state variable \verb|cs| outside of the
 1709 execute code is not considered by Ragel as moving into a state and consequently
 1710 the to-state actions of the new current state are not executed. This includes
 1711 the initialization of the current state when the machine begins.  This is
 1712 because the entry point into the machine execution code is after the execution
 1713 of to-state actions.
 1715 \subsubsection{From-State Actions}
 1717 \sasp\verb|>*action     >from(name)     >from{...} | -- the start state\\
 1718 \sasp\verb|<*action     <from(name)     <from{...} | -- any state except the start state\\
 1719 \sasp\verb|$*action     $from(name)     $from{...} | -- all states\\
 1720 \sasp\verb|%*action     %from(name)     %from{...} | -- final states\\
 1721 \sasp\verb|@*action     @from(name)     @from{...} | -- any state except final states\\
 1722 \sasp\verb|<>*action    <>from(name)    <>from{...}| -- any except start and final (middle)
 1723 \vspace{12pt}
 1725 From-state actions are executed whenever the state machine takes a transition from a
 1726 state, either to itself or to some other state. These actions are executed
 1727 immediately after the current character is tested against the input block end
 1728 marker and before the transition to take is sought based on the current
 1729 character. From-state actions are therefore executed even if a transition
 1730 cannot be found and the machine moves into the error state.  Like to-state
 1731 embeddings, from-state embeddings stay with the state.
 1733 \subsection{EOF Actions}
 1735 \sasp\verb|>/action     >eof(name)     >eof{...} | -- the start state\\
 1736 \sasp\verb|</action     <eof(name)     <eof{...} | -- any state except the start state\\
 1737 \sasp\verb|$/action     $eof(name)     $eof{...} | -- all states\\
 1738 \sasp\verb|%/action     %eof(name)     %eof{...} | -- final states\\
 1739 \sasp\verb|@/action     @eof(name)     @eof{...} | -- any state except final states\\
 1740 \sasp\verb|<>/action    <>eof(name)    <>eof{...}| -- any except start and final (middle)
 1741 \vspace{12pt}
 1743 The EOF action embedding operators enable the user to embed actions that are
 1744 executed at the end of the input stream. EOF actions are stored in states and
 1745 generated in the \verb|write exec| block. They are run when \verb|p == pe == eof|
 1746 as the execute block is finishing. EOF actions are free to adjust \verb|p| and
 1747 jump to another part of the machine to restart execution.
 1749 \subsection{Handling Errors}
 1751 In many applications it is useful to be able to react to parsing errors.  The
 1752 user may wish to print an error message that depends on the context.  It
 1753 may also be desirable to consume input in an attempt to return the input stream
 1754 to some known state and resume parsing. To support error handling and recovery,
 1755 Ragel provides error action embedding operators. There are two kinds of error
 1756 actions: global error actions and local error actions.
 1757 Error actions can be used to simply report errors, or by jumping to a machine
 1758 instantiation that consumes input, can attempt to recover from errors.  
 1760 \subsubsection{Global Error Actions}
 1762 \sasp\verb|>!action     >err(name)     >err{...} | -- the start state\\
 1763 \sasp\verb|<!action     <err(name)     <err{...} | -- any state except the start state\\
 1764 \sasp\verb|$!action     $err(name)     $err{...} | -- all states\\
 1765 \sasp\verb|%!action     %err(name)     %err{...} | -- final states\\
 1766 \sasp\verb|@!action     @err(name)     @err{...} | -- any state except final states\\
 1767 \sasp\verb|<>!action    <>err(name)    <>err{...}| -- any except start and final (middle)
 1768 \vspace{12pt}
 1770 Global error actions are stored in the states they are embedded into until
 1771 compilation is complete. They are then transferred to the transitions that move
 1772 into the error state. These transitions are taken on all input characters that
 1773 are not already covered by the state's transitions. If a state with an error
 1774 action is not final when compilation is complete, then the action is also
 1775 embedded as an EOF action.
 1777 Error actions can be used to recover from errors by jumping back into the
 1778 machine with \verb|fgoto| and optionally altering \verb|p|.
 1780 \subsubsection{Local Error Actions}
 1782 \sasp\verb|>^action     >lerr(name)     >lerr{...} | -- the start state\\
 1783 \sasp\verb|<^action     <lerr(name)     <lerr{...} | -- any state except the start state\\
 1784 \sasp\verb|$^action     $lerr(name)     $lerr{...} | -- all states\\
 1785 \sasp\verb|%^action     %lerr(name)     %lerr{...} | -- final states\\
 1786 \sasp\verb|@^action     @lerr(name)     @lerr{...} | -- any state except final states\\
 1787 \sasp\verb|<>^action    <>lerr(name)    <>lerr{...}| -- any except start and final (middle)
 1788 \vspace{12pt}
 1790 Like global error actions, local error actions are also stored in the states
 1791 they are embedded into until a transfer point. The transfer point is different
 1792 however. Each local error action embedding is associated with a name. When a
 1793 machine definition has been fully constructed, all local error action
 1794 embeddings associated with the same name as the machine definition are
 1795 transferred to the error transitions. At this time they are also embedded as
 1796 EOF actions in the case of non-final states.
 1798 Local error actions can be used to specify an action to take when a particular
 1799 section of a larger state machine fails to match. A particular machine
 1800 definition's ``thread'' may die and the local error actions executed, however
 1801 the machine as a whole may continue to match input.
 1803 There are two forms of local error action embeddings. In the first form the
 1804 name defaults to the current machine. In the second form the machine name can
 1805 be specified.  This is useful when it is more convenient to specify the local
 1806 error action in a sub-definition that is used to construct the machine
 1807 definition that the local error action is associated with. To embed local 
 1808 error actions and
 1809 explicitly state the machine definition on which the transfer is to happen use
 1810 \verb|(name, action)| as the action.
 1812 \subsubsection{Example}
 1814 The following example uses error actions to report an error and jump to a
 1815 machine that consumes the remainder of the line when parsing fails. After
 1816 consuming the line, the error recovery machine returns to the main loop.
 1818 % GENERATE: erract
 1819 % %%{
 1820 %   machine erract;
 1821 %   ws = ' ';
 1822 %   address = 'foo@bar.com';
 1823 %   date = 'Monday May 12';
 1824 \begin{inline_code}
 1825 \begin{verbatim}
 1826 action cmd_err { 
 1827     printf( "command error\n" ); 
 1828     fhold; fgoto line;
 1829 }
 1830 action from_err { 
 1831     printf( "from error\n" ); 
 1832     fhold; fgoto line; 
 1833 }
 1834 action to_err { 
 1835     printf( "to error\n" ); 
 1836     fhold; fgoto line;
 1837 }
 1839 line := [^\n]* '\n' @{ fgoto main; };
 1841 main := (
 1842     (
 1843         'from' @err(cmd_err) 
 1844             ( ws+ address ws+ date '\n' ) $err(from_err) |
 1845         'to' @err(cmd_err)
 1846             ( ws+ address '\n' ) $err(to_err)
 1847     ) 
 1848 )*;
 1849 \end{verbatim}
 1850 \end{inline_code}
 1851 % }%%
 1852 % %% write data;
 1853 % void f()
 1854 % {
 1855 %   %% write init;
 1856 %   %% write exec;
 1857 % }
 1862 \section{Action Ordering and Duplicates}
 1864 When combining expressions that have embedded actions it is often the case that
 1865 a number of actions must be executed on a single input character. For example,
 1866 following a concatenation the leaving action of the left expression and the
 1867 entering action of the right expression will be embedded into one transition.
 1868 This requires a method of ordering actions that is intuitive and
 1869 predictable for the user, and repeatable for the compiler. 
 1871 We associate with the embedding of each action a unique timestamp that is
 1872 used to order actions that appear together on a single transition in the final
 1873 state machine. To accomplish this we recursively traverse the parse tree of
 1874 regular expressions and assign timestamps to action embeddings. References to
 1875 machine definitions are followed in the traversal. When we visit a
 1876 parse tree node we assign timestamps to all {\em entering} action embeddings,
 1877 recurse on the parse tree, then assign timestamps to the remaining {\em all},
 1878 {\em finishing}, and {\em leaving} embeddings in the order in which they
 1879 appear.
 1881 By default Ragel does not permit a single action to appear multiple times in an action
 1882 list. When the final machine has been created, actions that appear more than
 1883 once in a single transition, to-state, from-state or EOF action list have their
 1884 duplicates removed.
 1885 The first appearance of the action is preserved. This is useful in a number of
 1886 scenarios. First, it allows us to union machines with common prefixes without
 1887 worrying about the action embeddings in the prefix being duplicated. Second, it
 1888 prevents leaving actions from being transferred multiple times. This can
 1889 happen when a machine is repeated, then followed with another machine that
 1890 begins with a common character. For example:
 1892 \verbspace
 1893 \begin{verbatim}
 1894 word = [a-z]+ %act;
 1895 main := word ( '\n' word )* '\n\n';
 1896 \end{verbatim}
 1897 \verbspace
 1899 Note that Ragel does not compare action bodies to determine if they have
 1900 identical program text. It simply checks for duplicates using each action
 1901 block's unique location in the program.
 1903 The removal of duplicates can be turned off using the \verb|-d| option.
 1905 \section{Values and Statements Available in Code Blocks}
 1906 \label{vals}
 1908 \noindent The following values are available in code blocks:
 1910 \begin{itemize}
 1911 \item \verb|fpc| -- A pointer to the current character. This is equivalent to
 1912 accessing the \verb|p| variable.
 1914 \item \verb|fc| -- The current character. This is equivalent to the expression \verb|(*p)|.
 1916 \item \verb|fcurs| -- An integer value representing the current state. This
 1917 value should only be read from. To move to a different place in the machine
 1918 from action code use the \verb|fgoto|, \verb|fnext| or \verb|fcall| statements.
 1919 Outside of the machine execution code the \verb|cs| variable may be modified.
 1921 \item \verb|ftargs| -- An integer value representing the target state. This
 1922 value should only be read from. Again, \verb|fgoto|, \verb|fnext| and
 1923 \verb|fcall| can be used to move to a specific entry point.
 1925 \item \verb|fentry(<label>)| -- Retrieve an integer value representing the
 1926 entry point \verb|label|. The integer value returned will be a compile time
 1927 constant. This number is suitable for later use in control flow transfer
 1928 statements that take an expression. This value should not be compared against
 1929 the current state because any given label can have multiple states representing
 1930 it. The value returned by \verb|fentry| can be any one of the multiple states that
 1931 it represents.
 1932 \end{itemize}
 1934 \noindent The following statements are available in code blocks:
 1936 \begin{itemize}
 1938 \item \verb|fhold;| -- Do not advance over the current character. If processing
 1939 data in multiple buffer blocks, the \verb|fhold| statement should only be used
 1940 once in the set of actions executed on a character.  Multiple calls may result
 1941 in backing up over the beginning of the buffer block. The \verb|fhold|
 1942 statement does not imply any transfer of control. It is equivalent to the
 1943 \verb|p--;| statement. 
 1945 \item \verb|fexec <expr>;| -- Set the next character to process. This can be
 1946 used to backtrack to previous input or advance ahead.
 1947 Unlike \verb|fhold|, which can be used
 1948 anywhere, \verb|fexec| requires the user to ensure that the target of the
 1949 backtrack is in the current buffer block or is known to be somewhere ahead of
 1950 it. The machine will continue iterating forward until \verb|pe| is arrived at,
 1951 \verb|fbreak| is called or the machine moves into the error state. In actions
 1952 embedded into transitions, the \verb|fexec| statement is equivalent to setting
 1953 \verb|p| to one position ahead of the next character to process.  If the user
 1954 also modifies \verb|pe|, it is possible to change the buffer block entirely.
 1956 \item \verb|fgoto <label>;| -- Jump to an entry point defined by
 1957 \verb|<label>|.  The \verb|fgoto| statement immediately transfers control to
 1958 the destination state.
 1960 \item \verb|fgoto *<expr>;| -- Jump to an entry point given by \verb|<expr>|.
 1961 The expression must evaluate to an integer value representing a state.
 1963 \item \verb|fnext <label>;| -- Set the next state to be the entry point defined
 1964 by \verb|label|.  The \verb|fnext| statement does not immediately jump to the
 1965 specified state. Any action code following the statement is executed.
 1967 \item \verb|fnext *<expr>;| -- Set the next state to be the entry point given
 1968 by \verb|<expr>|. The expression must evaluate to an integer value representing
 1969 a state.
 1971 \item \verb|fcall <label>;| -- Push the target state and jump to the entry
 1972 point defined by \verb|<label>|.  The next \verb|fret| will jump to the target
 1973 of the transition on which the call was made. Use of \verb|fcall| requires
 1974 the declaration of a call stack. An array of integers named \verb|stack| and a
 1975 single integer named \verb|top| must be declared. With the \verb|fcall|
 1976 construct, control is immediately transferred to the destination state.
 1977 See section \ref{modularization} for more information.
 1979 \item \verb|fcall *<expr>;| -- Push the current state and jump to the entry
 1980 point given by \verb|<expr>|. The expression must evaluate to an integer value
 1981 representing a state.
 1983 \item \verb|fret;| -- Return to the target state of the transition on which the
 1984 last \verb|fcall| was made.  Use of \verb|fret| requires the declaration of a
 1985 call stack. Control is immediately transferred to the destination state.
 1987 \item \verb|fbreak;| -- Advance \verb|p|, save the target state to \verb|cs|
 1988 and immediately break out of the execute loop. This statement is useful
 1989 in conjunction with the \verb|noend| write option. Rather than process input
 1990 until \verb|pe| is arrived at, the fbreak statement
 1991 can be used to stop processing from an action.  After an \verb|fbreak|
 1992 statement the \verb|p| variable will point to the next character in the input. The
 1993 current state will be the target of the current transition. Note that \verb|fbreak|
 1994 causes the target state's to-state actions to be skipped.
 1996 \end{itemize}
 1998 \noindent {\bf Note:} Once actions with control-flow commands are embedded into a
 1999 machine, the user must exercise caution when using the machine as the operand
 2000 to other machine construction operators. If an action jumps to another state
 2001 then unioning any transition that executes that action with another transition
 2002 that follows some other path will cause that other path to be lost. Using
 2003 commands that manually jump around a machine takes us out of the domain of
 2004 regular languages because transitions that the
 2005 machine construction operators are not aware of are introduced.  These
 2006 commands should therefore be used with caution.
 2009 \chapter{Controlling Nondeterminism}
 2010 \label{controlling-nondeterminism}
 2012 Along with the flexibility of arbitrary action embeddings comes a need to
 2013 control nondeterminism in regular expressions. If a regular expression is
 2014 ambiguous, then sub-components of a parser other than the intended parts may become
 2015 active. This means that actions that are irrelevant to the
 2016 current subset of the parser may be executed, causing problems for the
 2017 programmer.
 2019 Tools that are based on regular expression engines and that are used for
 2020 recognition tasks will usually function as intended regardless of the presence
 2021 of ambiguities. It is quite common for users of scripting languages to write
 2022 regular expressions that are heavily ambiguous and it generally does not
 2023 matter. As long as one of the potential matches is recognized, there can be any
 2024 number of other matches present.  In some parsing systems the run-time engine
 2025 can employ a strategy for resolving ambiguities, for example always pursuing
 2026 the longest possible match and discarding others.
 2028 In Ragel, there is no regular expression run-time engine, just a simple state
 2029 machine execution model. When we begin to embed actions and face the
 2030 possibility of spurious action execution, it becomes clear that controlling
 2031 nondeterminism at the machine construction level is very important. Consider
 2032 the following example.
 2034 % GENERATE: lines1
 2035 % OPT: -p
 2036 % %%{
 2037 % machine lines1;
 2038 % action first {}
 2039 % action tail {}
 2040 % word = [a-z]+;
 2041 \begin{inline_code}
 2042 \begin{verbatim}
 2043 ws = [\n\t ];
 2044 line = word $first ( ws word $tail )* '\n';
 2045 lines = line*;
 2046 \end{verbatim}
 2047 \end{inline_code}
 2048 % main := lines;
 2049 % }%%
 2052 \begin{center}
 2053 \includegraphics[scale=0.53]{lines1}
 2054 \end{center}
 2055 \graphspace
 2057 Since the \verb|ws| expression includes the newline character, we will
 2058 not finish the \verb|line| expression when a newline character is seen. We will
 2059 simultaneously pursue the possibility of matching further words on the same
 2060 line and the possibility of matching a second line. Evidence of this fact is 
 2061 in the state tables. On several transitions both the \verb|first| and
 2062 \verb|tail| actions are executed.  The solution here is simple: exclude
 2063 the newline character from the \verb|ws| expression. 
 2065 % GENERATE: lines2
 2066 % OPT: -p
 2067 % %%{
 2068 % machine lines2;
 2069 % action first {}
 2070 % action tail {}
 2071 % word = [a-z]+;
 2072 \begin{inline_code}
 2073 \begin{verbatim}
 2074 ws = [\t ];
 2075 line = word $first ( ws word $tail )* '\n';
 2076 lines = line*;
 2077 \end{verbatim}
 2078 \end{inline_code}
 2079 % main := lines;
 2080 % }%%
 2083 \begin{center}
 2084 \includegraphics[scale=0.55]{lines2}
 2085 \end{center}
 2086 \graphspace
 2088 Solving this kind of problem is straightforward when the ambiguity is created
 2089 by strings that are a single character long.  When the ambiguity is created by
 2090 strings that are multiple characters long we have a more difficult problem.
 2091 The following example is an incorrect attempt at a regular expression for C
 2092 language comments. 
 2094 % GENERATE: comments1
 2095 % OPT: -p
 2096 % %%{
 2097 % machine comments1;
 2098 % action comm {}
 2099 \begin{inline_code}
 2100 \begin{verbatim}
 2101 comment = '/*' ( any @comm )* '*/';
 2102 main := comment ' ';
 2103 \end{verbatim}
 2104 \end{inline_code}
 2105 % }%%
 2108 \begin{center}
 2109 \includegraphics[scale=0.55]{comments1}
 2110 \end{center}
 2111 \graphspace
 2113 Using standard concatenation, we will never leave the \verb|any*| expression.
 2114 We will forever entertain the possibility that a \verb|'*/'| string that we see
 2115 is contained in a longer comment and that, simultaneously, the comment has
 2116 ended.  The concatenation of the \verb|comment| machine with \verb|SP| is done
 2117 to show this. When we match space, we are also still matching the comment body.
 2119 One way to approach the problem is to exclude the terminating string
 2120 from the \verb|any*| expression using set difference. We must be careful to
 2121 exclude not just the terminating string, but any string that contains it as a
 2122 substring. A verbose, but proper specification of a C comment parser is given
 2123 by the following regular expression. 
 2125 % GENERATE: comments2
 2126 % OPT: -p
 2127 % %%{
 2128 % machine comments2;
 2129 % action comm {}
 2130 \begin{inline_code}
 2131 \begin{verbatim}
 2132 comment = '/*' ( ( any @comm )* - ( any* '*/' any* ) ) '*/';
 2133 \end{verbatim}
 2134 \end{inline_code}
 2135 % main := comment;
 2136 % }%%
 2139 \graphspace
 2140 \begin{center}
 2141 \includegraphics[scale=0.55]{comments2}
 2142 \end{center}
 2143 \graphspace
 2145 Note that Ragel's strong subtraction operator \verb|--| can also be used here.
 2146 In doing this subtraction we have phrased the problem of controlling non-determinism in
 2147 terms of excluding strings common to two expressions that interact when
 2148 combined.
 2149 We can also phrase the problem in terms of the transitions of the state
 2150 machines that implement these expressions. During the concatenation of
 2151 \verb|any*| and \verb|'*/'| we will be making transitions that are composed of
 2152 both the loop of the first expression and the final character of the second.
 2153 At this time we want the transition on the \verb|'/'| character to take precedence
 2154 over and disallow the transition that originated in the \verb|any*| loop.
 2156 In another parsing problem, we wish to implement a lightweight tokenizer that we can
 2157 utilize in the composition of a larger machine. For example, some HTTP headers
 2158 have a token stream as a sub-language. The following example is an attempt
 2159 at a regular expression-based tokenizer that does not function correctly due to
 2160 unintended nondeterminism.
 2162 \newpage
 2164 % GENERATE: smallscanner
 2165 % OPT: -p
 2166 % %%{
 2167 % machine smallscanner;
 2168 % action start_str {}
 2169 % action on_char {}
 2170 % action finish_str {}
 2171 \begin{inline_code}
 2172 \begin{verbatim}
 2173 header_contents = ( 
 2174     lower+ >start_str $on_char %finish_str | 
 2175     ' '
 2176 )*;
 2177 \end{verbatim}
 2178 \end{inline_code}
 2179 % main := header_contents;
 2180 % }%%
 2183 \begin{center}
 2184 \includegraphics[scale=0.55]{smallscanner}
 2185 \end{center}
 2186 \graphspace
 2188 In this case, the problem with using a standard kleene star operation is that
 2189 there is an ambiguity between extending a token and wrapping around the machine
 2190 to begin a new token. Using the standard operator, we get an undesirable
 2191 nondeterministic behaviour. Evidence of this can be seen on the transition out
 2192 of state one to itself.  The transition extends the string, and simultaneously,
 2193 finishes the string only to immediately begin a new one.  What is required is
 2194 for the
 2195 transitions that represent an extension of a token to take precedence over the
 2196 transitions that represent the beginning of a new token. For this problem
 2197 there is no simple solution that uses standard regular expression operators.
 2199 \section{Priorities}
 2201 A priority mechanism was devised and built into the determinization
 2202 process, specifically for the purpose of allowing the user to control
 2203 nondeterminism.  Priorities are integer values embedded into transitions. When
 2204 the determinization process is combining transitions that have different
 2205 priorities, the transition with the higher priority is preserved and the
 2206 transition with the lower priority is dropped.
 2208 Unfortunately, priorities can have unintended side effects because their
 2209 operation requires that they linger in transitions indefinitely. They must linger
 2210 because the Ragel program cannot know when the user is finished with a priority
 2211 embedding.  A solution whereby they are explicitly deleted after use is
 2212 conceivable; however this is not very user-friendly.  Priorities were therefore
 2213 made into named entities. Only priorities with the same name are allowed to
 2214 interact.  This allows any number of priorities to coexist in one machine for
 2215 the purpose of controlling various different regular expression operations and
 2216 eliminates the need to ever delete them. Such a scheme allows the user to
 2217 choose a unique name, embed two different priority values using that name
 2218 and be confident that the priority embedding will be free of any side effects.
 2220 In the first form of priority embedding the name defaults to the name of the machine
 2221 definition that the priority is assigned in. In this sense priorities are by
 2222 default local to the current machine definition or instantiation. Beware of
 2223 using this form in a longest-match machine, since there is only one name for
 2224 the entire set of longest match patterns. In the second form the priority's
 2225 name can be specified, allowing priority interaction across machine definition
 2226 boundaries.
 2228 \begin{itemize}
 2229 \setlength{\parskip}{0in}
 2230 \item \verb|expr > int| -- Sets starting transitions to have priority int.
 2231 \item \verb|expr @ int| -- Sets transitions that go into a final state to have priority int. 
 2232 \item \verb|expr $ int| -- Sets all transitions to have priority int.
 2233 \item \verb|expr % int| -- Sets leaving transitions to
 2234 have priority int. When a transition is made going out of the machine (either
 2235 by concatenation or kleene star) its priority is immediately set to the 
 2236 leaving priority.  
 2237 \end{itemize}
 2239 The second form of priority assignment allows the programmer to specify the name
 2240 to which the priority is assigned.
 2242 \begin{itemize}
 2243 \setlength{\parskip}{0in}
 2244 \item \verb|expr > (name, int)| -- Starting transitions.
 2245 \item \verb|expr @ (name, int)| -- Finishing transitions (into a final state).
 2246 \item \verb|expr $ (name, int)| -- All transitions.
 2247 \item \verb|expr % (name, int)| -- Leaving transitions.
 2248 \end{itemize}
 2250 \section{Guarded Operators that Encapsulate Priorities}
 2252 Priority embeddings are a very expressive mechanism. At the same time they
 2253 can be very confusing for the user. They force the user to imagine
 2254 the transitions inside two interacting expressions and work out the precise
 2255 effects of the operations between them. When we consider
 2256 that this problem is worsened by the
 2257 potential for side effects caused by unintended priority name collisions, we
 2258 see that exposing the user to priorities is undesirable.
 2260 Fortunately, in practice the use of priorities has been necessary only in a
 2261 small number of scenarios.  This allows us to encapsulate their functionality
 2262 into a small set of operators and fully hide them from the user. This is
 2263 advantageous from a language design point of view because it greatly simplifies
 2264 the design.  
 2266 Going back to the C comment example, we can now properly specify
 2267 it using a guarded concatenation operator which we call {\em finish-guarded
 2268 concatenation}. From the user's point of view, this operator terminates the
 2269 first machine when the second machine moves into a final state.  It chooses a
 2270 unique name and uses it to embed a low priority into all
 2271 transitions of the first machine. A higher priority is then embedded into the
 2272 transitions of the second machine that enter into a final state. The following
 2273 example yields a machine identical to the example in Section 
 2274 \ref{controlling-nondeterminism}.
 2276 \begin{inline_code}
 2277 \begin{verbatim}
 2278 comment = '/*' ( any @comm )* :>> '*/';
 2279 \end{verbatim}
 2280 \end{inline_code}
 2282 \graphspace
 2283 \begin{center}
 2284 \includegraphics[scale=0.55]{comments2}
 2285 \end{center}
 2286 \graphspace
 2288 Another guarded operator is {\em left-guarded concatenation}, given by the
 2289 \verb|<:| compound symbol. This operator places a higher priority on all
 2290 transitions of the first machine. This is useful if one must forcibly separate
 2291 two lists that contain common elements. For example, one may need to tokenize a
 2292 stream, but first consume leading whitespace.
 2294 Ragel also includes a {\em longest-match kleene star} operator, given by the
 2295 \verb|**| compound symbol. This 
 2296 guarded operator embeds a high
 2297 priority into all transitions of the machine. 
 2298 A lower priority is then embedded into the leaving transitions.  When the
 2299 kleene star operator makes the epsilon transitions from
 2300 the final states into the new start state, the lower priority will be transferred
 2301 to the epsilon transitions. In cases where following an epsilon transition
 2302 out of a final state conflicts with an existing transition out of a final
 2303 state, the epsilon transition will be dropped.
 2305 Other guarded operators are conceivable, such as guards on union that cause one
 2306 alternative to take precedence over another. These may be implemented when it
 2307 is clear they constitute a frequently used operation.
 2308 In the next section we discuss the explicit specification of state machines
 2309 using state charts.
 2311 \subsection{Entry-Guarded Concatenation}
 2313 \verb|expr :> expr| 
 2314 \verbspace
 2316 This operator concatenates two machines, but first assigns a low
 2317 priority to all transitions
 2318 of the first machine and a high priority to the starting transitions of the
 2319 second machine. This operator is useful if from the final states of the first
 2320 machine it is possible to accept the characters in the entering transitions of
 2321 the second machine. This operator effectively terminates the first machine
 2322 immediately upon starting the second machine, where otherwise they would be
 2323 pursued concurrently. In the following example, entry-guarded concatenation is
 2324 used to move out of a machine that matches everything at the first sign of an
 2325 end-of-input marker.
 2327 % GENERATE: entryguard
 2328 % OPT: -p
 2329 % %%{
 2330 % machine entryguard;
 2331 \begin{inline_code}
 2332 \begin{verbatim}
 2333 # Leave the catch-all machine on the first character of FIN.
 2334 main := any* :> 'FIN';
 2335 \end{verbatim}
 2336 \end{inline_code}
 2337 % }%%
 2340 \begin{center}
 2341 \includegraphics[scale=0.55]{entryguard}
 2342 \end{center}
 2343 \graphspace
 2345 Entry-guarded concatenation is equivalent to the following:
 2347 \verbspace
 2348 \begin{verbatim}
 2349 expr $(unique_name,0) . expr >(unique_name,1)
 2350 \end{verbatim}
 2352 \subsection{Finish-Guarded Concatenation}
 2354 \verb|expr :>> expr|
 2355 \verbspace
 2357 This operator is
 2358 like the previous operator, except the higher priority is placed on the final
 2359 transitions of the second machine. This is useful if one wishes to entertain
 2360 the possibility of continuing to match the first machine right up until the
 2361 second machine enters a final state. In other words it terminates the first
 2362 machine only when the second accepts. In the following example, finish-guarded
 2363 concatenation causes the move out of the machine that matches everything to be
 2364 delayed until the full end-of-input marker has been matched.
 2366 % GENERATE: finguard
 2367 % OPT: -p
 2368 % %%{
 2369 % machine finguard;
 2370 \begin{inline_code}
 2371 \begin{verbatim}
 2372 # Leave the catch-all machine on the last character of FIN.
 2373 main := any* :>> 'FIN';
 2374 \end{verbatim}
 2375 \end{inline_code}
 2376 % }%%
 2379 \begin{center}
 2380 \includegraphics[scale=0.55]{finguard}
 2381 \end{center}
 2382 \graphspace
 2384 Finish-guarded concatenation is equivalent to the following, with one
 2385 exception. If the right machine's start state is final, the higher priority is
 2386 also embedded into it as a leaving priority. This prevents the left machine
 2387 from persisting via the zero-length string.
 2389 \verbspace
 2390 \begin{verbatim}
 2391 expr $(unique_name,0) . expr @(unique_name,1)
 2392 \end{verbatim}
 2394 \subsection{Left-Guarded Concatenation}
 2396 \verb|expr <: expr| 
 2397 \verbspace
 2399 This operator places
 2400 a higher priority on the left expression. It is useful if you want to prefix a
 2401 sequence with another sequence composed of some of the same characters. For
 2402 example, one can consume leading whitespace before tokenizing a sequence of
 2403 whitespace-separated words as in:
 2405 % GENERATE: leftguard
 2406 % OPT: -p
 2407 % %%{
 2408 % machine leftguard;
 2409 % action alpha {}
 2410 % action ws {}
 2411 % action start {}
 2412 % action fin {}
 2413 \begin{inline_code}
 2414 \begin{verbatim}
 2415 main := ( ' '* >start %fin ) <: ( ' ' $ws | [a-z] $alpha )*;
 2416 \end{verbatim}
 2417 \end{inline_code}
 2418 % }%%
 2421 \graphspace
 2422 \begin{center}
 2423 \includegraphics[scale=0.55]{leftguard}
 2424 \end{center}
 2425 \graphspace
 2427 Left-guarded concatenation is equivalent to the following:
 2429 \verbspace
 2430 \begin{verbatim}
 2431 expr $(unique_name,1) . expr >(unique_name,0)
 2432 \end{verbatim}
 2433 \verbspace
 2435 \subsection{Longest-Match Kleene Star}
 2436 \label{longest_match_kleene_star}
 2438 \verb|expr**| 
 2439 \verbspace
 2441 This version of kleene star puts a higher priority on staying in the
 2442 machine versus wrapping around and starting over. The LM kleene star is useful
 2443 when writing simple tokenizers.  These machines are built by applying the
 2444 longest-match kleene star to an alternation of token patterns, as in the
 2445 following.
 2447 \verbspace
 2449 % GENERATE: lmkleene
 2450 % OPT: -p
 2451 % %%{
 2452 % machine exfinpri;
 2453 % action A {}
 2454 % action B {}
 2455 \begin{inline_code}
 2456 \begin{verbatim}
 2457 # Repeat tokens, but make sure to get the longest match.
 2458 main := (
 2459     lower ( lower | digit )* %A | 
 2460     digit+ %B | 
 2461     ' '
 2462 )**;
 2463 \end{verbatim}
 2464 \end{inline_code}
 2465 % }%%
 2468 \begin{center}
 2469 \includegraphics[scale=0.55]{lmkleene}
 2470 \end{center}
 2471 \graphspace
 2473 If a regular kleene star were used the machine above would not be able to
 2474 distinguish between extending a word and beginning a new one.  This operator is
 2475 equivalent to:
 2477 \verbspace
 2478 \begin{verbatim}
 2479 ( expr $(unique_name,1) %(unique_name,0) )*
 2480 \end{verbatim}
 2481 \verbspace
 2483 When the kleene star is applied, transitions that go out of the machine and
 2484 back into it are made. These are assigned a priority of zero by the leaving 
 2485 transition mechanism. This is less than the priority of one assigned to the
 2486 transitions leaving the final states but not leaving the machine. When 
 2487 these transitions clash on the same character, the 
 2488 transition that stays in the machine takes precedence.  The transition
 2489 that wraps around is dropped.
 2491 Note that this operator does not build a scanner in the traditional sense
 2492 because there is never any backtracking. To build a scanner with backtracking
 2493 use the Longest-Match machine construction described in Section
 2494 \ref{generating-scanners}.
 2496 \chapter{Interface to Host Program}
 2498 The Ragel code generator is very flexible. The generated code has no
 2499 dependencies and can be inserted in any function, perhaps inside a loop if
 2500 desired.  The user is responsible for declaring and initializing a number of
 2501 required variables, including the current state and the pointer to the input
 2502 stream. These can live in any scope. Control of the input processing loop is
 2503 also possible: the user may break out of the processing loop and return to it
 2504 at any time.
 2506 In the case of the C, D, and Go host languages, Ragel is able to generate very
 2507 fast-running code that implements state machines as directly executable code.
 2508 Since very large files strain the host language compiler, table-based code
 2509 generation is also supported. In the future we hope to provide a partitioned,
 2510 directly executable format that is able to reduce the burden on the host
 2511 compiler by splitting large machines across multiple functions.
 2513 In the case of Java and Ruby, table-based code generation is the only code
 2514 style supported. In the future this may be expanded to include other code
 2515 styles.
 2517 Ragel can be used to parse input in one block, or it can be used to parse input
 2518 in a sequence of blocks as it arrives from a file or socket.  Parsing the input
 2519 in a sequence of blocks brings with it a few responsibilities. If the parser
 2520 utilizes a scanner, care must be taken to not break the input stream anywhere
 2521 but token boundaries.  If pointers to the input stream are taken during
 2522 parsing, care must be taken to not use a pointer that has been invalidated by
 2523 movement to a subsequent block.  If the current input data pointer is moved
 2524 backwards it must not be moved past the beginning of the current block.
 2526 Figure \ref{basic-example} shows a simple Ragel program that does not have any
 2527 actions. The example tests the first argument of the program against a number
 2528 pattern and then prints the machine's acceptance status.
 2530 \begin{figure}
 2531 \small
 2532 \begin{verbatim}
 2533 #include <stdio.h>
 2534 #include <string.h>
 2535 %%{
 2536     machine foo;
 2537     write data;
 2538 }%%
 2539 int main( int argc, char **argv )
 2540 {
 2541     int cs;
 2542     if ( argc > 1 ) {
 2543         char *p = argv[1];
 2544         char *pe = p + strlen( p );
 2545         %%{ 
 2546             main := [0-9]+ ( '.' [0-9]+ )?;
 2548             write init;
 2549             write exec;
 2550         }%%
 2551     }
 2552     printf("result = %i\n", cs >= foo_first_final );
 2553     return 0;
 2554 }
 2555 \end{verbatim}
 2556 \caption{A basic Ragel example without any actions.}
 2557 \label{basic-example}
 2558 \end{figure}
 2560 \section{Variables Used by Ragel}
 2562 There are a number of variables that Ragel expects the user to declare. At a
 2563 very minimum the \verb|cs|, \verb|p| and \verb|pe| variables must be declared.
 2564 In Go, Java and Ruby code the \verb|data| variable must also be declared. If
 2565 EOF actions are used then the \verb|eof| variable is required. If
 2566 stack-based state machine control flow statements are used then the
 2567 \verb|stack| and \verb|top| variables are required. If a scanner is declared
 2568 then the \verb|act|, \verb|ts| and \verb|te| variables must be
 2569 declared.
 2571 \begin{itemize}
 2573 \item \verb|cs| - Current state. This must be an integer and it should persist
 2574 across invocations of the machine when the data is broken into blocks that are
 2575 processed independently. This variable may be modified from outside the
 2576 execution loop, but not from within.
 2578 \item \verb|p| - Data pointer. In C/D code this variable is expected to be a
 2579 pointer to the character data to process. It should be initialized to the
 2580 beginning of the data block on every run of the machine. In Go, Java and Ruby it is
 2581 used as an offset to \verb|data| and must be an integer. In this case it should
 2582 be initialized to zero on every run of the machine.
 2584 \item \verb|pe| - Data end pointer. This should be initialized to \verb|p| plus
 2585 the data length on every run of the machine. In Go, Java and Ruby code this should
 2586 be initialized to the data length.
 2588 \item \verb|eof| - End of file pointer. This should be set to \verb|pe| when
 2589 the buffer block being processed is the last one, otherwise it should be set to
 2590 null. In Go, Java and Ruby code \verb|-1| must be used instead of null. If the EOF
 2591 event can be known only after the final buffer block has been processed, then
 2592 it is possible to set \verb|p = pe = eof| and run the execute block.
 2594 \item \verb|data| - This variable is only required in Go, Java and Ruby code. It
 2595 must be an array containting the data to process.
 2597 \item \verb|stack| - This must be an array of integers. It is used to store
 2598 integer values representing states. If the stack must resize dynamically the
 2599 Pre-push and Post-Pop statements can be used to do this (Sections
 2600 \ref{prepush} and \ref{postpop}).
 2602 \item \verb|top| - This must be an integer value and will be used as an offset
 2603 to \verb|stack|, giving the next available spot on the top of the stack.
 2605 \item \verb|act| - This must be an integer value. It is a variable sometimes
 2606 used by scanner code to keep track of the most recent successful pattern match.
 2608 \item \verb|ts| - This must be a pointer to character data. In Go, Java and
 2609 Ruby code this must be an integer. See Section \ref{generating-scanners} for
 2610 more information.
 2612 \item \verb|te| - Also a pointer to character data.
 2614 \end{itemize}
 2616 \section{Alphtype Statement}
 2618 \begin{verbatim}
 2619 alphtype unsigned int;
 2620 \end{verbatim}
 2621 \verbspace
 2623 The alphtype statement specifies the alphabet data type that the machine
 2624 operates on. During the compilation of the machine, integer literals are
 2625 expected to be in the range of possible values of the alphtype. The default
 2626 is \verb|char| for all languages except Go where the default is \verb|byte|.
 2628 \begin{multicols}{2}
 2629 \setlength{\columnseprule}{1pt} 
 2630 C/C++/Objective-C:
 2631 \begin{verbatim}
 2632           char      unsigned char      
 2633           short     unsigned short
 2634           int       unsigned int
 2635           long      unsigned long
 2636 \end{verbatim}
 2638 Go:
 2639 \begin{verbatim}
 2640           byte
 2641           int8      uint8
 2642           int16     uint16
 2643           int32     uint32
 2644           int64     uint64
 2645           rune
 2646 \end{verbatim}
 2648 Ruby: 
 2649 \begin{verbatim}
 2650           char 
 2651           int
 2652 \end{verbatim}
 2654 \columnbreak
 2656 Java:
 2657 \begin{verbatim}
 2658           char 
 2659           byte 
 2660           short 
 2661           int
 2662 \end{verbatim}
 2664 D:
 2665 \begin{verbatim}
 2666           char 
 2667           byte      ubyte   
 2668           short     ushort 
 2669           wchar 
 2670           int       uint 
 2671           dchar
 2672 \end{verbatim}
 2674 \end{multicols}
 2676 \section{Getkey Statement}
 2678 \begin{verbatim}
 2679 getkey fpc->id;
 2680 \end{verbatim}
 2681 \verbspace
 2683 This statement specifies to Ragel how to retrieve the current character from 
 2684 from the pointer to the current element (\verb|p|). Any expression that returns
 2685 a value of the alphabet type
 2686 may be used. The getkey statement may be used for looking into element
 2687 structures or for translating the character to process. The getkey expression
 2688 defaults to \verb|(*p)|. In goto-driven machines the getkey expression may be
 2689 evaluated more than once per element processed, therefore it should not incur a
 2690 large cost nor preclude optimization.
 2692 \section{Access Statement}
 2694 \begin{verbatim}
 2695 access fsm->;
 2696 \end{verbatim}
 2697 \verbspace
 2699 The access statement specifies how the generated code should
 2700 access the machine data that is persistent across processing buffer blocks.
 2701 This applies to all variables except \verb|p|, \verb|pe| and \verb|eof|. This includes
 2702 \verb|cs|, \verb|top|, \verb|stack|, \verb|ts|, \verb|te| and \verb|act|.
 2703 The access statement is useful if a machine is to be encapsulated inside a
 2704 structure in C code. It can be used to give the name of
 2705 a pointer to the structure.
 2707 \section{Variable Statement}
 2709 \begin{verbatim}
 2710 variable p fsm->p;
 2711 \end{verbatim}
 2712 \verbspace
 2714 The variable statement specifies how to access a specific
 2715 variable. All of the variables that are declared by the user and
 2716 used by Ragel can be changed. This includes \verb|p|, \verb|pe|, \verb|eof|, \verb|cs|,
 2717 \verb|top|, \verb|stack|, \verb|ts|, \verb|te| and \verb|act|.
 2718 In Go, Ruby and Java code generation the \verb|data| variable can also be changed.
 2720 \section{Pre-Push Statement}
 2721 \label{prepush}
 2723 \begin{verbatim}
 2724 prepush { 
 2725     /* stack growing code */
 2726 }
 2727 \end{verbatim}
 2728 \verbspace
 2730 The prepush statement allows the user to supply stack management code that is
 2731 written out during the generation of fcall, immediately before the current
 2732 state is pushed to the stack. This statement can be used to test the number of
 2733 available spaces and dynamically grow the stack if necessary.
 2735 \section{Post-Pop Statement}
 2736 \label{postpop}
 2738 \begin{verbatim}
 2739 postpop { 
 2740     /* stack shrinking code */
 2741 }
 2742 \end{verbatim}
 2743 \verbspace
 2745 The postpop statement allows the user to supply stack management code that is
 2746 written out during the generation of fret, immediately after the next state is
 2747 popped from the stack. This statement can be used to dynamically shrink the
 2748 stack.
 2750 \section{Write Statement}
 2751 \label{write-statement}
 2753 \begin{verbatim}
 2754 write <component> [options];
 2755 \end{verbatim}
 2756 \verbspace
 2758 The write statement is used to generate parts of the machine. 
 2759 There are seven
 2760 components that can be generated by a write statement. These components make up the
 2761 state machine's data, initialization code, execution code, and export definitions.
 2762 A write statement may appear before a machine is fully defined.
 2763 This allows one to write out the data first then later define the machine where
 2764 it is used. An example of this is shown in Figure \ref{fbreak-example}.
 2766 \subsection{Write Data}
 2767 \begin{verbatim}
 2768 write data [options];
 2769 \end{verbatim}
 2770 \verbspace
 2772 The write data statement causes Ragel to emit the constant static data needed
 2773 by the machine. In table-driven output styles (see Section \ref{genout}) this
 2774 is a collection of arrays that represent the states and transitions of the
 2775 machine.  In goto-driven machines much less data is emitted. At the very
 2776 minimum a start state \verb|name_start| is generated.  All variables written
 2777 out in machine data have both the \verb|static| and \verb|const| properties and
 2778 are prefixed with the name of the machine and an
 2779 underscore. The data can be placed inside a class, inside a function, or it can
 2780 be defined as global data.
 2782 Two variables are written that may be used to test the state of the machine
 2783 after a buffer block has been processed. The \verb|name_error| variable gives
 2784 the id of the state that the machine moves into when it cannot find a valid
 2785 transition to take. The machine immediately breaks out of the processing loop when
 2786 it finds itself in the error state. The error variable can be compared to the
 2787 current state to determine if the machine has failed to parse the input. If the
 2788 machine is complete, that is from every state there is a transition to a proper
 2789 state on every possible character of the alphabet, then no error state is required
 2790 and this variable will be set to -1.
 2792 The \verb|name_first_final| variable stores the id of the first final state. All of the
 2793 machine's states are sorted by their final state status before having their ids
 2794 assigned. Checking if the machine has accepted its input can then be done by
 2795 checking if the current state is greater-than or equal to the first final
 2796 state.
 2798 Data generation has several options:
 2800 \begin{itemize}
 2801 \setlength{\itemsep}{-2mm}
 2802 \item \verb|noerror  | - Do not generate the integer variable that gives the
 2803 id of the error state.
 2804 \item \verb|nofinal  | - Do not generate the integer variable that gives the
 2805 id of the first final state.
 2806 \item \verb|noentry  | - Do not generate the integer variables that give the
 2807 values of the entry points.
 2808 \item \verb|noprefix | - Do not prefix the variable names with the name of the
 2809 machine.
 2810 \end{itemize}
 2812 \begin{figure}
 2813 \small
 2814 \begin{verbatim}
 2815 #include <stdio.h>
 2816 %% machine foo;
 2817 %% write data;
 2818 int main( int argc, char **argv )
 2819 {
 2820     int cs, res = 0;
 2821     if ( argc > 1 ) {
 2822         char *p = argv[1];
 2823         %%{ 
 2824             main := 
 2825                 [a-z]+ 
 2826                 0 @{ res = 1; fbreak; };
 2827             write init;
 2828             write exec noend;
 2829         }%%
 2830     }
 2831     printf("execute = %i\n", res );
 2832     return 0;
 2833 }
 2834 \end{verbatim}
 2835 \caption{Use of {\tt noend} write option and the {\tt fbreak} statement for
 2836 processing a string.}
 2837 \label{fbreak-example}
 2838 \end{figure}
 2840 \subsection{Write Start, First Final and Error}
 2842 \begin{verbatim}
 2843 write start;
 2844 write first_final;
 2845 write error;
 2846 \end{verbatim}
 2847 \verbspace
 2849 These three write statements provide an alternative means of accessing the
 2850 \verb|start|, \verb|first_final| and \verb|error| states. If there are many
 2851 different machine specifications in one file it is easy to get the prefix for
 2852 these wrong. This is especially true if the state machine boilerplate is
 2853 frequently made by a copy-paste-edit process. These write statements allow the
 2854 problem to be avoided. They can be used as follows:
 2856 \verbspace
 2858 {
 2859 \small
 2860 \begin{verbatim}
 2861 /* Did parsing succeed? */
 2862 if ( cs < %%{ write first_final; }%% ) {
 2863     result = ERR_PARSE_ERROR;
 2864     goto fail;
 2865 }
 2866 \end{verbatim}
 2867 }
 2870 \subsection{Write Init}
 2871 \begin{verbatim}
 2872 write init [options];
 2873 \end{verbatim}
 2874 \verbspace
 2876 The write init statement causes Ragel to emit initialization code. This should
 2877 be executed once before the machine is started. At a very minimum this sets the
 2878 current state to the start state. If other variables are needed by the
 2879 generated code, such as call stack variables or scanner management
 2880 variables, they are also initialized here.
 2882 The \verb|nocs| option to the write init statement will cause ragel to skip
 2883 intialization of the cs variable. This is useful if the user wishes to use
 2884 custom logic to decide which state the specification should start in.
 2886 \subsection{Write Exec}
 2887 \begin{verbatim}
 2888 write exec [options];
 2889 \end{verbatim}
 2890 \verbspace
 2892 The write exec statement causes Ragel to emit the state machine's execution code.
 2893 Ragel expects several variables to be available to this code. At a very minimum, the
 2894 generated code needs access to the current character position \verb|p|, the ending
 2895 position \verb|pe| and the current state \verb|cs| (though \verb|pe|
 2896 can be omitted using the \verb|noend| write option).
 2897 The \verb|p| variable is the cursor that the execute code will
 2898 used to traverse the input. The \verb|pe| variable should be set up to point to one
 2899 position past the last valid character in the buffer.
 2901 Other variables are needed when certain features are used. For example using
 2902 the \verb|fcall| or \verb|fret| statements requires \verb|stack| and
 2903 \verb|top| variables to be defined. If a longest-match construction is used,
 2904 variables for managing backtracking are required.
 2906 The write exec statement has one option. The \verb|noend| option tells Ragel
 2907 to generate code that ignores the end position \verb|pe|. In this
 2908 case the user must explicitly break out of the processing loop using
 2909 \verb|fbreak|, otherwise the machine will continue to process characters until
 2910 it moves into the error state. This option is useful if one wishes to process a
 2911 null terminated string. Rather than traverse the string to discover then length
 2912 before processing the input, the user can break out when the null character is
 2913 seen.  The example in Figure \ref{fbreak-example} shows the use of the
 2914 \verb|noend| write option and the \verb|fbreak| statement for processing a string.
 2916 \subsection{Write Exports}
 2917 \label{export}
 2919 \begin{verbatim}
 2920 write exports;
 2921 \end{verbatim}
 2922 \verbspace
 2924 The export feature can be used to export simple machine definitions. Machine definitions
 2925 are marked for export using the \verb|export| keyword.
 2927 \verbspace
 2928 \begin{verbatim}
 2929 export machine_to_export = 0x44;
 2930 \end{verbatim}
 2931 \verbspace
 2933 When the write exports statement is used these machines are 
 2934 written out in the generated code. Defines are used for C and constant integers
 2935 are used for D, Java and Ruby. See Section \ref{import} for a description of the
 2936 import statement.
 2938 \section{Maintaining Pointers to Input Data}
 2940 In the creation of any parser it is not uncommon to require the collection of
 2941 the data being parsed.  It is always possible to collect data into a growable
 2942 buffer as the machine moves over it, however the copying of data is a somewhat
 2943 wasteful use of processor cycles. The most efficient way to collect data from
 2944 the parser is to set pointers into the input then later reference them.  This
 2945 poses a problem for uses of Ragel where the input data arrives in blocks, such
 2946 as over a socket or from a file. If a pointer is set in one buffer block but
 2947 must be used while parsing a following buffer block, some extra consideration
 2948 to correctness must be made.
 2950 The scanner constructions exhibit this problem, requiring the maintenance
 2951 code described in Section \ref{generating-scanners}. If a longest-match
 2952 construction has been used somewhere in the machine then it is possible to
 2953 take advantage of the required prefix maintenance code in the driver program to
 2954 ensure pointers to the input are always valid. If laying down a pointer one can
 2955 set \verb|ts| at the same spot or ahead of it. When data is shifted in
 2956 between loops the user must also shift the pointer.  In this way it is possible
 2957 to maintain pointers to the input that will always be consistent.
 2959 \begin{figure}
 2960 \small
 2961 \begin{verbatim}
 2962     int have = 0;
 2963     while ( 1 ) {
 2964         char *p, *pe, *data = buf + have;
 2965         int len, space = BUFSIZE - have;
 2967         if ( space == 0 ) { 
 2968             fprintf(stderr, "BUFFER OUT OF SPACE\n");
 2969             exit(1);
 2970         }
 2972         len = fread( data, 1, space, stdin );
 2973         if ( len == 0 )
 2974             break;
 2976         /* Find the last newline by searching backwards. */
 2977         p = buf;
 2978         pe = data + len - 1;
 2979         while ( *pe != '\n' && pe >= buf )
 2980             pe--;
 2981         pe += 1;
 2983         %% write exec;
 2985         /* How much is still in the buffer? */
 2986         have = data + len - pe;
 2987         if ( have > 0 )
 2988             memmove( buf, pe, have );
 2990         if ( len < space )
 2991             break;
 2992     }
 2993 \end{verbatim}
 2994 \caption{An example of line-oriented processing.}
 2995 \label{line-oriented}
 2996 \end{figure}
 2998 In general, there are two approaches for guaranteeing the consistency of
 2999 pointers to input data. The first approach is the one just described;
 3000 lay down a marker from an action,
 3001 then later ensure that the data the marker points to is preserved ahead of
 3002 the buffer on the next execute invocation. This approach is good because it
 3003 allows the parser to decide on the pointer-use boundaries, which can be
 3004 arbitrarily complex parsing conditions. A downside is that it requires any
 3005 pointers that are set to be corrected in between execute invocations.
 3007 The alternative is to find the pointer-use boundaries before invoking the execute
 3008 routine, then pass in the data using these boundaries. For example, if the
 3009 program must perform line-oriented processing, the user can scan backwards from
 3010 the end of an input block that has just been read in and process only up to the
 3011 first found newline. On the next input read, the new data is placed after the
 3012 partially read line and processing continues from the beginning of the line.
 3013 An example of line-oriented processing is given in Figure \ref{line-oriented}.
 3015 \section{Specifying the Host Language}
 3017 The \verb|ragel| program has a number of options for specifying the host
 3018 language. The host-language options are:
 3020 \begin{itemize}
 3021 \item \verb|-C  | for C/C++/Objective-C code (default)
 3022 \item \verb|-D  | for D code.
 3023 \item \verb|-Z  | for Go code.
 3024 \item \verb|-J  | for Java code.
 3025 \item \verb|-R  | for Ruby code.
 3026 \item \verb|-A  | for C\# code.
 3027 \end{itemize}
 3029 \section{Choosing a Generated Code Style}
 3030 \label{genout}
 3032 There are three styles of code output to choose from. Code style affects the
 3033 size and speed of the compiled binary. Changing code style does not require any
 3034 change to the Ragel program. There are two table-driven formats and a goto
 3035 driven format.
 3037 In addition to choosing a style to emit, there are various levels of action
 3038 code reuse to choose from.  The maximum reuse levels (\verb|-T0|, \verb|-F0|
 3039 and \verb|-G0|) ensure that no FSM action code is ever duplicated by encoding
 3040 each transition's action list as static data and iterating
 3041 through the lists on every transition. This will normally result in a smaller
 3042 binary. The less action reuse options (\verb|-T1|, \verb|-F1| and \verb|-G1|)
 3043 will usually produce faster running code by expanding each transition's action
 3044 list into a single block of code, eliminating the need to iterate through the
 3045 lists. This duplicates action code instead of generating the logic necessary
 3046 for reuse. Consequently the binary will be larger. However, this tradeoff applies to
 3047 machines with moderate to dense action lists only. If a machine's transitions
 3048 frequently have less than two actions then the less reuse options will actually
 3049 produce both a smaller and a faster running binary due to less action sharing
 3050 overhead. The best way to choose the appropriate code style for your
 3051 application is to perform your own tests.
 3053 The table-driven FSM represents the state machine as constant static data. There are
 3054 tables of states, transitions, indices and actions. The current state is
 3055 stored in a variable. The execution is simply a loop that looks up the current
 3056 state, looks up the transition to take, executes any actions and moves to the
 3057 target state. In general, the table-driven FSM can handle any machine, produces
 3058 a smaller binary and requires a less expensive host language compile, but
 3059 results in slower running code.  Since the table-driven format is the most
 3060 flexible it is the default code style.
 3062 The flat table-driven machine is a table-based machine that is optimized for
 3063 small alphabets. Where the regular table machine uses the current character as
 3064 the key in a binary search for the transition to take, the flat table machine
 3065 uses the current character as an index into an array of transitions. This is
 3066 faster in general, however is only suitable if the span of possible characters
 3067 is small.
 3069 The goto-driven FSM represents the state machine using goto and switch
 3070 statements. The execution is a flat code block where the transition to take is
 3071 computed using switch statements and directly executable binary searches.  In
 3072 general, the goto FSM produces faster code but results in a larger binary and a
 3073 more expensive host language compile.
 3075 The goto-driven format has an additional action reuse level (\verb|-G2|) that
 3076 writes actions directly into the state transitioning logic rather than putting
 3077 all the actions together into a single switch. Generally this produces faster
 3078 running code because it allows the machine to encode the current state using
 3079 the processor's instruction pointer. Again, sparse machines may actually
 3080 compile to smaller binaries when \verb|-G2| is used due to less state and
 3081 action management overhead. For many parsing applications \verb|-G2| is the
 3082 preferred output format.
 3084 \verbspace
 3085 \begin{center}
 3086 \begin{tabular}{|c|c|c|}
 3087 \hline
 3088 \multicolumn{3}{|c|}{\bf Code Output Style Options} \\
 3089 \hline
 3090 \verb|-T0|&binary search table-driven&C/D/Java/Ruby/C\#/Go\\
 3091 \hline
 3092 \verb|-T1|&binary search, expanded actions&C/D/Ruby/C\#/Go\\
 3093 \hline
 3094 \verb|-F0|&flat table-driven&C/D/Ruby/C\#/Go\\
 3095 \hline
 3096 \verb|-F1|&flat table, expanded actions&C/D/Ruby/C\#/Go\\
 3097 \hline
 3098 \verb|-G0|&goto-driven&C/D/C\#/Go\\
 3099 \hline
 3100 \verb|-G1|&goto, expanded actions&C/D/C\#/Go\\
 3101 \hline
 3102 \verb|-G2|&goto, in-place actions&C/D/Go\\
 3103 \hline
 3104 \end{tabular}
 3105 \end{center}
 3107 \chapter{Beyond the Basic Model}
 3109 \section{Parser Modularization}
 3110 \label{modularization}
 3112 It is possible to use Ragel's machine construction and action embedding
 3113 operators to specify an entire parser using a single regular expression. In
 3114 many cases this is the desired way to specify a parser in Ragel. However, in
 3115 some scenarios the language to parse may be so large that it is difficult to
 3116 think about it as a single regular expression. It may also shift between distinct
 3117 parsing strategies, in which case modularization into several coherent blocks
 3118 of the language may be appropriate.
 3120 It may also be the case that patterns that compile to a large number of states
 3121 must be used in a number of different contexts and referencing them in each
 3122 context results in a very large state machine. In this case, an ability to reuse
 3123 parsers would reduce code size.
 3125 To address this, distinct regular expressions may be instantiated and linked
 3126 together by means of a jumping and calling mechanism. This mechanism is
 3127 analogous to the jumping to and calling of processor instructions. A jump
 3128 command, given in action code, causes control to be immediately passed to
 3129 another portion of the machine by way of setting the current state variable. A
 3130 call command causes the target state of the current transition to be pushed to
 3131 a state stack before control is transferred.  Later on, the original location
 3132 may be returned to with a return statement. In the following example, distinct
 3133 state machines are used to handle the parsing of two types of headers.
 3135 % GENERATE: call
 3136 % %%{
 3137 %   machine call;
 3138 \begin{inline_code}
 3139 \begin{verbatim}
 3140 action return { fret; }
 3141 action call_date { fcall date; }
 3142 action call_name { fcall name; }
 3144 # A parser for date strings.
 3145 date := [0-9][0-9] '/' 
 3146         [0-9][0-9] '/' 
 3147         [0-9][0-9][0-9][0-9] '\n' @return;
 3149 # A parser for name strings.
 3150 name := ( [a-zA-Z]+ | ' ' )** '\n' @return;
 3152 # The main parser.
 3153 headers = 
 3154     ( 'from' | 'to' ) ':' @call_name | 
 3155     ( 'departed' | 'arrived' ) ':' @call_date;
 3157 main := headers*;
 3158 \end{verbatim}
 3159 \end{inline_code}
 3160 % }%%
 3161 % %% write data;
 3162 % void f()
 3163 % {
 3164 %   %% write init;
 3165 %   %% write exec;
 3166 % }
 3169 Calling and jumping should be used carefully as they are operations that take
 3170 one out of the domain of regular languages. A machine that contains a call or
 3171 jump statement in one of its actions should be used as an argument to a machine
 3172 construction operator only with considerable care. Since DFA transitions may
 3173 actually represent several NFA transitions, a call or jump embedded in one
 3174 machine can inadvertently terminate another machine that it shares prefixes
 3175 with. Despite this danger, theses statements have proven useful for tying
 3176 together sub-parsers of a language into a parser for the full language,
 3177 especially for the purpose of modularizing code and reducing the number of
 3178 states when the machine contains frequently recurring patterns.
 3180 Section \ref{vals} describes the jump and call statements that are used to
 3181 transfer control. These statements make use of two variables that must be
 3182 declared by the user, \verb|stack| and \verb|top|. The \verb|stack| variable
 3183 must be an array of integers and \verb|top| must be a single integer, which
 3184 will point to the next available space in \verb|stack|. Sections \ref{prepush}
 3185 and \ref{postpop} describe the Pre-Push and Post-Pop statements which can be
 3186 used to implement a dynamically resizable array.
 3188 \section{Referencing Names}
 3189 \label{labels}
 3191 This section describes how to reference names in epsilon transitions (Section
 3192 \ref{state-charts}) and
 3193 action-based control-flow statements such as \verb|fgoto|. There is a hierarchy
 3194 of names implied in a Ragel specification.  At the top level are the machine
 3195 instantiations. Beneath the instantiations are labels and references to machine
 3196 definitions. Beneath those are more labels and references to definitions, and
 3197 so on.
 3199 Any name reference may contain multiple components separated with the \verb|::|
 3200 compound symbol.  The search for the first component of a name reference is
 3201 rooted at the join expression that the epsilon transition or action embedding
 3202 is contained in. If the name reference is not contained in a join,
 3203 the search is rooted at the machine definition that the epsilon transition or
 3204 action embedding is contained in. Each component after the first is searched
 3205 for beginning at the location in the name tree that the previous reference
 3206 component refers to.
 3208 In the case of action-based references, if the action is embedded more than
 3209 once, the local search is performed for each embedding and the result is the
 3210 union of all the searches. If no result is found for action-based references then
 3211 the search is repeated at the root of the name tree.  Any action-based name
 3212 search may be forced into a strictly global search by prefixing the name
 3213 reference with \verb|::|.
 3215 The final component of the name reference must resolve to a unique entry point.
 3216 If a name is unique in the entire name tree it can be referenced as is. If it
 3217 is not unique it can be specified by qualifying it with names above it in the
 3218 name tree. However, it can always be renamed.
 3220 % FIXME: Should fit this in somewhere.
 3221 % Some kinds of name references are illegal. Cannot call into longest-match
 3222 % machine, can only call its start state. Cannot make a call to anywhere from
 3223 % any part of a longest-match machine except a rule's action. This would result
 3224 % in an eventual return to some point inside a longest-match other than the
 3225 % start state. This is banned for the same reason a call into the LM machine is
 3226 % banned.
 3229 \section{Scanners}
 3230 \label{generating-scanners}
 3232 Scanners are very much intertwined with regular-languages and their
 3233 corresponding processors. For this reason Ragel supports the definition of
 3234 scanners.  The generated code will repeatedly attempt to match patterns from a
 3235 list, favouring longer patterns over shorter patterns.  In the case of
 3236 equal-length matches, the generated code will favour patterns that appear ahead
 3237 of others. When a scanner makes a match it executes the user code associated
 3238 with the match, consumes the input then resumes scanning.
 3240 \verbspace
 3241 \begin{verbatim}
 3242 <machine_name> := |* 
 3243         pattern1 => action1;
 3244         pattern2 => action2;
 3245         ...
 3246     *|;
 3247 \end{verbatim}
 3248 \verbspace
 3250 On the surface, Ragel scanners are similar to those defined by Lex. Though
 3251 there is a key distinguishing feature: patterns may be arbitrary Ragel
 3252 expressions and can therefore contain embedded code. With a Ragel-based scanner
 3253 the user need not wait until the end of a pattern before user code can be
 3254 executed.
 3256 Scanners can be used to process sub-languages, as well as for tokenizing
 3257 programming languages. In the following example a scanner is used to tokenize
 3258 the contents of a header field.
 3260 \begin{inline_code}
 3261 \begin{verbatim}
 3262 word = [a-z]+;
 3263 head_name = 'Header';
 3265 header := |*
 3266     word;
 3267     ' ';
 3268     '\n' => { fret; };
 3269 *|;
 3271 main := ( head_name ':' @{ fcall header; } )*;
 3272 \end{verbatim}
 3273 \end{inline_code}
 3274 \verbspace
 3276 The scanner construction has a purpose similar to the longest-match kleene star
 3277 operator \verb|**|. The key
 3278 difference is that a scanner is able to backtrack to match a previously matched
 3279 shorter string when the pursuit of a longer string fails.  For this reason the
 3280 scanner construction operator is not a pure state machine construction
 3281 operator. It relies on several variables that enable it to backtrack and make
 3282 pointers to the matched input text available to the user.  For this reason
 3283 scanners must be immediately instantiated. They cannot be defined inline or
 3284 referenced by another expression. Scanners must be jumped to or called.
 3286 Scanners rely on the \verb|ts|, \verb|te| and \verb|act|
 3287 variables to be present so that they can backtrack and make pointers to the
 3288 matched text available to the user. If input is processed using multiple calls
 3289 to the execute code then the user must ensure that when a token is only
 3290 partially matched that the prefix is preserved on the subsequent invocation of
 3291 the execute code.
 3293 The \verb|ts| variable must be defined as a pointer to the input data.
 3294 It is used for recording where the current token match begins. This variable
 3295 may be used in action code for retrieving the text of the current match.  Ragel
 3296 ensures that in between tokens and outside of the longest-match machines that
 3297 this pointer is set to null. In between calls to the execute code the user must
 3298 check if \verb|ts| is set and if so, ensure that the data it points to is
 3299 preserved ahead of the next buffer block. This is described in more detail
 3300 below.
 3302 The \verb|te| variable must also be defined as a pointer to the input data.
 3303 It is used for recording where a match ends and where scanning of the next
 3304 token should begin. This can also be used in action code for retrieving the
 3305 text of the current match.
 3307 The \verb|act| variable must be defined as an integer type. It is used for
 3308 recording the identity of the last pattern matched when the scanner must go
 3309 past a matched pattern in an attempt to make a longer match. If the longer
 3310 match fails it may need to consult the \verb|act| variable. In some cases, use 
 3311 of the \verb|act|
 3312 variable can be avoided because the value of the current state is enough
 3313 information to determine which token to accept, however in other cases this is
 3314 not enough and so the \verb|act| variable is used. 
 3316 When the longest-match operator is in use, the user's driver code must take on
 3317 some buffer management functions. The following algorithm gives an overview of
 3318 the steps that should be taken to properly use the longest-match operator.
 3320 \begin{itemize}
 3321 \setlength{\parskip}{0pt}
 3322 \item Read a block of input data.
 3323 \item Run the execute code.
 3324 \item If \verb|ts| is set, the execute code will expect the incomplete
 3325 token to be preserved ahead of the buffer on the next invocation of the execute
 3326 code.  
 3327 \begin{itemize}
 3328 \item Shift the data beginning at \verb|ts| and ending at \verb|pe| to the
 3329 beginning of the input buffer.
 3330 \item Reset \verb|ts| to the beginning of the buffer. 
 3331 \item Shift \verb|te| by the distance from the old value of \verb|ts|
 3332 to the new value. The \verb|te| variable may or may not be valid.  There is
 3333 no way to know if it holds a meaningful value because it is not kept at null
 3334 when it is not in use. It can be shifted regardless.
 3335 \end{itemize}
 3336 \item Read another block of data into the buffer, immediately following any
 3337 preserved data.
 3338 \item Run the scanner on the new data.
 3339 \end{itemize}
 3341 Figure \ref{preserve_example} shows the required handling of an input stream in
 3342 which a token is broken by the input block boundaries. After processing up to
 3343 and including the ``t'' of ``characters'', the prefix of the string token must be
 3344 retained and processing should resume at the ``e'' on the next iteration of
 3345 the execute code.
 3347 If one uses a large input buffer for collecting input then the number of times
 3348 the shifting must be done will be small. Furthermore, if one takes care not to
 3349 define tokens that are allowed to be very long and instead processes these
 3350 items using pure state machines or sub-scanners, then only a small amount of
 3351 data will ever need to be shifted.
 3353 \begin{figure}
 3354 \begin{verbatim}
 3355       a)           A stream "of characters" to be scanned.
 3356                    |        |          |
 3357                    p        ts         pe
 3359       b)           "of characters" to be scanned.
 3360                    |          |        |
 3361                    ts         p        pe
 3362 \end{verbatim}
 3363 \caption{Following an invocation of the execute code there may be a partially
 3364 matched token (a). The data of the partially matched token 
 3365 must be preserved ahead of the new data on the next invocation (b).}
 3366 \label{preserve_example}
 3367 \end{figure}
 3369 Since scanners attempt to make the longest possible match of input, patterns
 3370 such as identifiers require one character of lookahead in order to trigger a
 3371 match. In the case of the last token in the input stream the user must ensure
 3372 that the \verb|eof| variable is set so that the final token is flushed out.
 3374 An example scanner processing loop is given in Figure \ref{scanner-loop}.
 3376 \begin{figure}
 3377 \small
 3378 \begin{verbatim}
 3379     int have = 0;
 3380     bool done = false;
 3381     while ( !done ) {
 3382         /* How much space is in the buffer? */
 3383         int space = BUFSIZE - have;
 3384         if ( space == 0 ) {
 3385             /* Buffer is full. */
 3386             cerr << "TOKEN TOO BIG" << endl;
 3387             exit(1);
 3388         }
 3390         /* Read in a block after any data we already have. */
 3391         char *p = inbuf + have;
 3392         cin.read( p, space );
 3393         int len = cin.gcount();
 3395         char *pe = p + len;
 3396         char *eof = 0;
 3398         /* If no data was read indicate EOF. */
 3399         if ( len == 0 ) {
 3400             eof = pe;
 3401             done = true;
 3402         }
 3404         %% write exec;
 3406         if ( cs == Scanner_error ) {
 3407             /* Machine failed before finding a token. */
 3408             cerr << "PARSE ERROR" << endl;
 3409             exit(1);
 3410         }
 3412         if ( ts == 0 )
 3413             have = 0;
 3414         else {
 3415             /* There is a prefix to preserve, shift it over. */
 3416             have = pe - ts;
 3417             memmove( inbuf, ts, have );
 3418             te = inbuf + (te-ts);
 3419             ts = inbuf;
 3420         }
 3421     }
 3422 \end{verbatim}
 3423 \caption{A processing loop for a scanner.}
 3424 \label{scanner-loop}
 3425 \end{figure}
 3427 \section{State Charts}
 3428 \label{state-charts}
 3430 In addition to supporting the construction of state machines using regular
 3431 languages, Ragel provides a way to manually specify state machines using
 3432 state charts.  The comma operator combines machines together without any
 3433 implied transitions. The user can then manually link machines by specifying
 3434 epsilon transitions with the \verb|->| operator.  Epsilon transitions are drawn
 3435 between the final states of a machine and entry points defined by labels.  This
 3436 makes it possible to build machines using the explicit state-chart method while
 3437 making minimal changes to the Ragel language. 
 3439 An interesting feature of Ragel's state chart construction method is that it
 3440 can be mixed freely with regular expression constructions. A state chart may be
 3441 referenced from within a regular expression, or a regular expression may be
 3442 used in the definition of a state chart transition.
 3444 \subsection{Join}
 3446 \verb|expr , expr , ...|
 3447 \verbspace
 3449 Join a list of machines together without
 3450 drawing any transitions, without setting up a start state, and without
 3451 designating any final states. Transitions between the machines may be specified
 3452 using labels and epsilon transitions. The start state must be explicity
 3453 specified with the ``start'' label. Final states may be specified with an
 3454 epsilon transition to the implicitly created ``final'' state. The join
 3455 operation allows one to build machines using a state chart model.
 3457 \subsection{Label}
 3459 \verb|label: expr| 
 3460 \verbspace
 3462 Attaches a label to an expression. Labels can be
 3463 used as the target of epsilon transitions and explicit control transfer
 3464 statements such as \verb|fgoto| and \verb|fnext| in action
 3465 code.
 3467 \subsection{Epsilon}
 3469 \verb|expr -> label| 
 3470 \verbspace
 3472 Draws an epsilon transition to the state defined
 3473 by \verb|label|.  Epsilon transitions are made deterministic when join
 3474 operators are evaluated. Epsilon transitions that are not in a join operation
 3475 are made deterministic when the machine definition that contains the epsilon is
 3476 complete. See Section \ref{labels} for information on referencing labels.
 3478 \subsection{Simplifying State Charts}
 3480 There are two benefits to providing state charts in Ragel. The first is that it
 3481 allows us to take a state chart with a full listing of states and transitions
 3482 and simplify it in selective places using regular expressions.
 3484 The state chart method of specifying parsers is very common.  It is an
 3485 effective programming technique for producing robust code. The key disadvantage
 3486 becomes clear when one attempts to comprehend a large parser specified in this
 3487 way.  These programs usually require many lines, causing logic to be spread out
 3488 over large distances in the source file. Remembering the function of a large
 3489 number of states can be difficult and organizing the parser in a sensible way
 3490 requires discipline because branches and repetition present many file layout
 3491 options.  This kind of programming takes a specification with inherent
 3492 structure such as looping, alternation and concatenation and expresses it in a
 3493 flat form. 
 3495 If we could take an isolated component of a manually programmed state chart,
 3496 that is, a subset of states that has only one entry point, and implement it
 3497 using regular language operators then we could eliminate all the explicit
 3498 naming of the states contained in it. By eliminating explicitly named states
 3499 and replacing them with higher-level specifications we simplify a state machine
 3500 specification.
 3502 For example, sometimes chains of states are needed, with only a small number of
 3503 possible characters appearing along the chain. These can easily be replaced
 3504 with a concatenation of characters. Sometimes a group of common states
 3505 implement a loop back to another single portion of the machine. Rather than
 3506 manually duplicate all the transitions that loop back, we may be able to
 3507 express the loop using a kleene star operator.
 3509 Ragel allows one to take this state map simplification approach. We can build
 3510 state machines using a state map model and implement portions of the state map
 3511 using regular languages. In place of any transition in the state machine,
 3512 entire sub-machines can be given. These can encapsulate functionality
 3513 defined elsewhere. An important aspect of the Ragel approach is that when we
 3514 wrap up a collection of states using a regular expression we do not lose
 3515 access to the states and transitions. We can still execute code on the
 3516 transitions that we have encapsulated.
 3518 \subsection{Dropping Down One Level of Abstraction}
 3519 \label{down}
 3521 The second benefit of incorporating state charts into Ragel is that it permits
 3522 us to bypass the regular language abstraction if we need to. Ragel's action
 3523 embedding operators are sometimes insufficient for expressing certain parsing
 3524 tasks.  In the same way that is useful for C language programmers to drop down
 3525 to assembly language programming using embedded assembler, it is sometimes
 3526 useful for the Ragel programmer to drop down to programming with state charts.
 3528 In the following example, we wish to buffer the characters of an XML CDATA
 3529 sequence. The sequence is terminated by the string \verb|]]>|. The challenge
 3530 in our application is that we do not wish the terminating characters to be
 3531 buffered. An expression of the form \verb|any* @buffer :>> ']]>'| will not work
 3532 because the buffer will always contain the characters \verb|]]| on the end.
 3533 Instead, what we need is to delay the buffering of \hspace{0.25mm} \verb|]|
 3534 characters until a time when we
 3535 abandon the terminating sequence and go back into the main loop. There is no
 3536 easy way to express this using Ragel's regular expression and action embedding
 3537 operators, and so an ability to drop down to the state chart method is useful.
 3539 % GENERATE: dropdown
 3540 % OPT: -p
 3541 % %%{
 3542 % machine dropdown;
 3543 \begin{inline_code}
 3544 \begin{verbatim}
 3545 action bchar { buff( fpc ); }    # Buffer the current character.
 3546 action bbrack1 { buff( "]" ); }
 3547 action bbrack2 { buff( "]]" ); }
 3549 CDATA_body =
 3550 start: (
 3551      ']' -> one |
 3552      (any-']') @bchar ->start
 3553 ),
 3554 one: (
 3555      ']' -> two |
 3556      [^\]] @bbrack1 @bchar ->start
 3557 ),
 3558 two: (
 3559      '>' -> final |
 3560      ']' @bbrack1 -> two |
 3561      [^>\]] @bbrack2 @bchar ->start
 3562 );
 3563 \end{verbatim}
 3564 \end{inline_code}
 3565 % main := CDATA_body;
 3566 % }%%
 3569 \graphspace
 3570 \begin{center}
 3571 \includegraphics[scale=0.55]{dropdown}
 3572 \end{center}
 3575 \section{Semantic Conditions}
 3576 \label{semantic}
 3578 Many communication protocols contain variable-length fields, where the length
 3579 of the field is given ahead of the field as a value. This
 3580 problem cannot be expressed using regular languages because of its
 3581 context-dependent nature. The prevalence of variable-length fields in
 3582 communication protocols motivated us to introduce semantic conditions into
 3583 the Ragel language.
 3585 A semantic condition is a block of user code that is interpreted as an
 3586 expression and evaluated immediately
 3587 before a transition is taken. If the code returns a value of true, the
 3588 transition may be taken.  We can now embed code that extracts the length of a
 3589 field, then proceed to match $n$ data values.
 3591 % GENERATE: conds1
 3592 % OPT: -p
 3593 % %%{
 3594 % machine conds1;
 3595 % number = digit+;
 3596 \begin{inline_code}
 3597 \begin{verbatim}
 3598 action rec_num { i = 0; n = getnumber(); }
 3599 action test_len { i++ < n }
 3600 data_fields = (
 3601     'd' 
 3602     [0-9]+ %rec_num 
 3603     ':'
 3604     ( [a-z] when test_len )*
 3605 )**;
 3606 \end{verbatim}
 3607 \end{inline_code}
 3608 % main := data_fields;
 3609 % }%%
 3612 \begin{center}
 3613 \includegraphics[scale=0.55]{conds1}
 3614 \end{center}
 3615 \graphspace
 3617 The Ragel implementation of semantic conditions does not force us to give up the
 3618 compositional property of Ragel definitions. For example, a machine that tests
 3619 the length of a field using conditions can be unioned with another machine
 3620 that accepts some of the same strings, without the two machines interfering with
 3621 one another. The user need not be concerned about whether or not the result of the
 3622 semantic condition will affect the matching of the second machine.
 3624 To see this, first consider that when a user associates a condition with an
 3625 existing transition, the transition's label is translated from the base character
 3626 to its corresponding value in the space that represents ``condition $c$ true''. Should
 3627 the determinization process combine a state that has a conditional transition
 3628 with another state that has a transition on the same input character but
 3629 without a condition, then the condition-less transition first has its label
 3630 translated into two values, one to its corresponding value in the space that
 3631 represents ``condition $c$ true'' and another to its corresponding value in the
 3632 space that represents ``condition $c$ false''. It
 3633 is then safe to combine the two transitions. This is shown in the following
 3634 example.  Two intersecting patterns are unioned, one with a condition and one
 3635 without. The condition embedded in the first pattern does not affect the second
 3636 pattern.
 3638 % GENERATE: conds2
 3639 % OPT: -p
 3640 % %%{
 3641 % machine conds2;
 3642 % number = digit+;
 3643 \begin{inline_code}
 3644 \begin{verbatim}
 3645 action test_len { i++ < n }
 3646 action one { /* accept pattern one */ }
 3647 action two { /* accept pattern two */ }
 3648 patterns = 
 3649     ( [a-z] when test_len )+ %one |
 3650     [a-z][a-z0-9]* %two;
 3651 main := patterns '\n';
 3652 \end{verbatim}
 3653 \end{inline_code}
 3654 % }%%
 3657 \begin{center}
 3658 \includegraphics[scale=0.55]{conds2}
 3659 \end{center}
 3660 \graphspace
 3662 There are many more potential uses for semantic conditions. The user is free to
 3663 use arbitrary code and may therefore perform actions such as looking up names
 3664 in dictionaries, validating input using external parsing mechanisms or
 3665 performing checks on the semantic structure of input seen so far. In the
 3666 next section we describe how Ragel accommodates several common parser
 3667 engineering problems.
 3669 \vspace{10pt}
 3671 \noindent {\large\bf Note:} The semantic condition feature works only with
 3672 alphabet types that are smaller in width than the \verb|long| type. To
 3673 implement semantic conditions Ragel needs to be able to allocate characters
 3674 from the alphabet space. Ragel uses these allocated characters to express
 3675 "character C with condition P true" or "C with P false." Since internally Ragel
 3676 uses longs to store characters there is no room left in the alphabet space
 3677 unless an alphabet type smaller than long is used.
 3679 \section{Implementing Lookahead}
 3681 There are a few strategies for implementing lookahead in Ragel programs.
 3682 Leaving actions, which are described in Section \ref{out-actions}, can be
 3683 used as a form of lookahead.  Ragel also provides the \verb|fhold| directive
 3684 which can be used in actions to prevent the machine from advancing over the
 3685 current character. It is also possible to manually adjust the current character
 3686 position by shifting it backwards using \verb|fexec|, however when this is
 3687 done, care must be taken not to overstep the beginning of the current buffer
 3688 block. In both the use of \verb|fhold| and \verb|fexec| the user must be
 3689 cautious of combining the resulting machine with another in such a way that the
 3690 transition on which the current position is adjusted is not combined with a
 3691 transition from the other machine.
 3693 \section{Parsing Recursive Language Structures}
 3695 In general Ragel cannot handle recursive structures because the grammar is
 3696 interpreted as a regular language. However, depending on what needs to be
 3697 parsed it is sometimes practical to implement the recursive parts using manual
 3698 coding techniques. This often works in cases where the recursive structures are
 3699 simple and easy to recognize, such as in the balancing of parentheses
 3701 One approach to parsing recursive structures is to use actions that increment
 3702 and decrement counters or otherwise recognize the entry to and exit from
 3703 recursive structures and then jump to the appropriate machine defnition using
 3704 \verb|fcall| and \verb|fret|. Alternatively, semantic conditions can be used to
 3705 test counter variables.
 3707 A more traditional approach is to call a separate parsing function (expressed
 3708 in the host language) when a recursive structure is entered, then later return
 3709 when the end is recognized.
 3711 \end{document}