% % Copyright 2001-2009 Adrian Thurston % % This file is part of Ragel. % % Ragel is free software; you can redistribute it and/or modify % it under the terms of the GNU General Public License as published by % the Free Software Foundation; either version 2 of the License, or % (at your option) any later version. % % Ragel is distributed in the hope that it will be useful, % but WITHOUT ANY WARRANTY; without even the implied warranty of % MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the % GNU General Public License for more details. % % You should have received a copy of the GNU General Public License % along with Ragel; if not, write to the Free Software % Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA % TODO: Need a section on the different strategies for handline recursion. \documentclass[letterpaper,11pt,oneside]{book} \usepackage{graphicx} \usepackage{comment} \usepackage{multicol} \usepackage[ colorlinks=true, linkcolor=black, citecolor=green, filecolor=black, urlcolor=black]{hyperref} \topmargin -0.20in \oddsidemargin 0in \textwidth 6.5in \textheight 9in \setlength{\parskip}{0pt} \setlength{\topsep}{0pt} \setlength{\partopsep}{0pt} \setlength{\itemsep}{0pt} \input{version} \newcommand{\verbspace}{\vspace{10pt}} \newcommand{\graphspace}{\vspace{10pt}} \renewcommand\floatpagefraction{.99} \renewcommand\topfraction{.99} \renewcommand\bottomfraction{.99} \renewcommand\textfraction{.01} \setcounter{totalnumber}{50} \setcounter{topnumber}{50} \setcounter{bottomnumber}{50} \newenvironment{inline_code}{\def\baselinestretch{1}\vspace{12pt}\small}{} \begin{document} % % Title page % \thispagestyle{empty} \begin{center} \vspace*{3in} {\huge Ragel State Machine Compiler}\\ \vspace*{12pt} {\Large User Guide}\\ \vspace{1in} by\\ \vspace{12pt} {\large Adrian Thurston}\\ \end{center} \clearpage \pagenumbering{roman} % % License page % \chapter*{License} Ragel version \version, \pubdate\\ Copyright \copyright\ 2003-2007 Adrian Thurston \vspace{6mm} {\bf\it\noindent This document is part of Ragel, and as such, this document is released under the terms of the GNU General Public License as published by the Free Software Foundation; either version 2 of the License, or (at your option) any later version.} \vspace{5pt} {\bf\it\noindent Ragel is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.} \vspace{5pt} {\bf\it\noindent You should have received a copy of the GNU General Public License along with Ragel; if not, write to the Free Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA} % % Table of contents % \clearpage \tableofcontents \clearpage % % Chapter 1 % \pagenumbering{arabic} \chapter{Introduction} \section{Abstract} Regular expressions are used heavily in practice for the purpose of specifying parsers. They are normally used as black boxes linked together with program logic. User actions are executed in between invocations of the regular expression engine. Adding actions before a pattern terminates requires patterns to be broken and pasted back together with program logic. The more user actions are needed, the less the advantages of regular expressions are seen. Ragel is a software development tool that allows user actions to be embedded into the transitions of a regular expression's corresponding state machine, eliminating the need to switch from the regular expression engine and user code execution environment and back again. As a result, expressions can be maximally continuous. One is free to specify an entire parser using a single regular expression. The single-expression model affords concise and elegant descriptions of languages and the generation of very simple, fast and robust code. Ragel compiles executable finite state machines from a high level regular language notation. Ragel targets C, C++, Objective-C, D, Go, Java and Ruby. In addition to building state machines from regular expressions, Ragel allows the programmer to directly specify state machines with state charts. These two notations may be freely combined. There are also facilities for controlling nondeterminism in the resulting machines and building scanners using patterns that themselves have embedded actions. Ragel can produce code that is small and runs very fast. Ragel can handle integer-sized alphabets and can compile very large state machines. \section{Motivation} When a programmer is faced with the task of producing a parser for a context-free language there are many tools to choose from. It is quite common to generate useful and efficient parsers for programming languages from a formal grammar. It is also quite common for programmers to avoid such tools when making parsers for simple computer languages, such as file formats and communication protocols. Such languages are often regular and tools for processing the context-free languages are viewed as too heavyweight for the purpose of parsing regular languages. The extra run-time effort required for supporting the recursive nature of context-free languages is wasted. When we turn to the regular expression-based parsing tools, such as Lex, Re2C, and scripting languages such as Sed, Awk and Perl we find that they are split into two levels: a regular expression matching engine and some kind of program logic for linking patterns together. For example, a Lex program is composed of sets of regular expressions. The implied program logic repeatedly attempts to match a pattern in the current set. When a match is found the associated user code executed. It requires the user to consider a language as a sequence of independent tokens. Scripting languages and regular expression libraries allow one to link patterns together using arbitrary program code. This is very flexible and powerful, however we can be more concise and clear if we avoid gluing together regular expressions with if statements and while loops. This model of execution, where the runtime alternates between regular expression matching and user code exectution places restrictions on when action code may be executed. Since action code can only be associated with complete patterns, any action code that must be executed before an entire pattern is matched requires that the pattern be broken into smaller units. Instead of being forced to disrupt the regular expression syntax and write smaller expressions, it is desirable to retain a single expression and embed code for performing actions directly into the transitions that move over the characters. After all, capable programmers are astutely aware of the machinery underlying their programs, so why not provide them with access to that machinery? To achieve this we require an action execution model for associating code with the sub-expressions of a regular expression in a way that does not disrupt its syntax. The primary goal of Ragel is to provide developers with an ability to embed actions into the transitions and states of a regular expression's state machine in support of the definition of entire parsers or large sections of parsers using a single regular expression. From the regular expression we gain a clear and concise statement of our language. From the state machine we obtain a very fast and robust executable that lends itself to many kinds of analysis and visualization. \section{Overview} Ragel is a language for specifying state machines. The Ragel program is a compiler that assembles a state machine definition to executable code. Ragel is based on the principle that any regular language can be converted to a deterministic finite state automaton. Since every regular language has a state machine representation and vice versa, the terms regular language and state machine (or just machine) will be used interchangeably in this document. Ragel outputs machines to C, C++, Objective-C, D, Go, Java or Ruby code. The output is designed to be generic and is not bound to any particular input or processing method. A Ragel machine expects to have data passed to it in buffer blocks. When there is no more input, the machine can be queried for acceptance. In this way, a Ragel machine can be used to simply recognize a regular language like a regular expression library. By embedding code into the regular language, a Ragel machine can also be used to parse input. The Ragel language has many operators for constructing and manipulating machines. Machines are built up from smaller machines, to bigger ones, to the final machine representing the language that needs to be recognized or parsed. The core state machine construction operators are those found in most theory of computation textbooks. They date back to the 1950s and are widely studied. They are based on set operations and permit one to think of languages as a set of strings. They are Union, Intersection, Difference, Concatenation and Kleene Star. Put together, these operators make up what most people know as regular expressions. Ragel also provides a scanner construction operator and provides operators for explicitly constructing machines using a state chart method. In the state chart method, one joins machines together without any implied transitions and then explicitly specifies where epsilon transitions should be drawn. The state machine manipulation operators are specific to Ragel. They allow the programmer to access the states and transitions of regular language's corresponding machine. There are two uses of the manipulation operators. The first and primary use is to embed code into transitions and states, allowing the programmer to specify the actions of the state machine. Ragel attempts to make the action embedding facility as intuitive as possible. To do so, a number of issues need to be addressed. For example, when making a nondeterministic specification into a DFA using machines that have embedded actions, new transitions are often made that have the combined actions of several source transitions. Ragel ensures that multiple actions associated with a single transition are ordered consistently with respect to the order of reference and the natural ordering implied by the construction operators. The second use of the manipulation operators is to assign priorities to transitions. Priorities provide a convenient way of controlling any nondeterminism introduced by the construction operators. Suppose two transitions leave from the same state and go to distinct target states on the same character. If these transitions are assigned conflicting priorities, then during the determinization process the transition with the higher priority will take precedence over the transition with the lower priority. The lower priority transition gets abandoned. The transitions would otherwise be combined into a new transition that goes to a new state that is a combination of the original target states. Priorities are often required for segmenting machines. The most common uses of priorities have been encoded into a set of simple operators that should be used instead of priority embeddings whenever possible. For the purposes of embedding, Ragel divides transitions and states into different classes. There are four operators for embedding actions and priorities into the transitions of a state machine. It is possible to embed into entering transitions, finishing transitions, all transitions and leaving transitions. The embedding into leaving transitions is a special case. These transition embeddings get stored in the final states of a machine. They are transferred to any transitions that are made going out of the machine by future concatenation or kleene star operations. There are several more operators for embedding actions into states. Like the transition embeddings, there are various different classes of states that the embedding operators access. For example, one can access start states, final states or all states, among others. Unlike the transition embeddings, there are several different types of state action embeddings. These are executed at various different times during the processing of input. It is possible to embed actions that are exectued on transitions into a state, on transitions out of a state, on transitions taken on the error event, or on transitions taken on the EOF event. Within actions, it is possible to influence the behaviour of the state machine. The user can write action code that jumps or calls to another portion of the machine, changes the current character being processed, or breaks out of the processing loop. With the state machine calling feature Ragel can be used to parse languages that are not regular. For example, one can parse balanced parentheses by calling into a parser when an open parenthesis character is seen and returning to the state on the top of the stack when the corresponding closing parenthesis character is seen. More complicated context-free languages such as expressions in C are out of the scope of Ragel. Ragel also provides a scanner construction operator that can be used to build scanners much the same way that Lex is used. The Ragel generated code, which relies on user-defined variables for backtracking, repeatedly tries to match patterns to the input, favouring longer patterns over shorter ones and patterns that appear ahead of others when the lengths of the possible matches are identical. When a pattern is matched the associated action is executed. The key distinguishing feature between scanners in Ragel and scanners in Lex is that Ragel patterns may be arbitrary Ragel expressions and can therefore contain embedded code. With a Ragel-based scanner the user need not wait until the end of a pattern before user code can be executed. Scanners do take Ragel out of the domain of pure state machines and require the user to maintain the backtracking related variables. However, scanners integrate well with regular state machine instantiations. They can be called to or jumped to only when needed, or they can be called out of or jumped out of when a simpler, pure state machine model is appropriate. Two types of output code style are available. Ragel can produce a table-driven machine or a directly executable machine. The directly executable machine is much faster than the table-driven. On the other hand, the table-driven machine is more compact and less demanding on the host language compiler. It is better suited to compiling large state machines. \section{Related Work} Lex is perhaps the best-known tool for constructing parsers from regular expressions. In the Lex processing model, generated code attempts to match one of the user's regular expression patterns, favouring longer matches over shorter ones. Once a match is made it then executes the code associated with the pattern and consumes the matching string. This process is repeated until the input is fully consumed. Through the use of start conditions, related sets of patterns may be defined. The active set may be changed at any time. This allows the user to define different lexical regions. It also allows the user to link patterns together by requiring that some patterns come before others. This is quite like a concatenation operation. However, use of Lex for languages that require a considerable amount of pattern concatenation is inappropriate. In such cases a Lex program deteriorates into a manually specified state machine, where start conditions define the states and pattern actions define the transitions. Lex is therefore best suited to parsing tasks where the language to be parsed can be described in terms of regions of tokens. Lex is useful in many scenarios and has undoubtedly stood the test of time. There are, however, several drawbacks to using Lex. Lex can impose too much overhead for parsing applications where buffering is not required because all the characters are available in a single string. In these cases there is structure to the language to be parsed and a parser specification tool can help, but employing a heavyweight processing loop that imposes a stream ``pull'' model and dynamic input buffer allocation is inappropriate. An example of this kind of scenario is the conversion of floating point numbers contained in a string to their corresponding numerical values. Another drawback is the very issue that Ragel attempts to solve. It is not possible to execute a user action while matching a character contained inside a pattern. For example, if scanning a programming language and string literals can contain newlines which must be counted, a Lex user must break up a string literal pattern so as to associate an action with newlines. This forces the definition of a new start condition. Alternatively the user can reprocess the text of the matched string literal to count newlines. \begin{comment} How ragel is different from Lex. %Like Re2c, Ragel provides a simple execution model that does not make any %assumptions as to how the input is collected. Also, Ragel does not do any %buffering in the generated code. Consequently there are no dependencies on %external functions such as \verb|malloc|. %If buffering is required it can be manually implemented by embedding actions %that copy the current character to a buffer, or data can be passed to the %parser using known block boundaries. If the longest-match operator is used, %Ragel requires the user to ensure that the ending portion of the input buffer %is preserved when the buffer is exhaused before a token is fully matched. The %user should move the token prefix to a new memory location, such as back to the %beginning of the input buffer, then place the subsequently read input %immediately after the prefix. %These properties of Ragel make it more work to write a program that requires %the longest-match operator or buffering of input, however they make Ragel a %more flexible tool that can produce very simple and fast-running programs under %a variety of input acquisition arrangements. %In Ragel, it is not necessary %to introduce start conditions to concatenate tokens and retain action %execution. Ragel allows one to structure a parser as a series of tokens, but %does not require it. %Like Lex and Re2C, Ragel is able to process input using a longest-match %execution model, however the core of the Ragel language specifies parsers at a %much lower level. This core is built around a pure state machine model. When %building basic machines there is no implied algorithm for processing input %other than to move from state to state on the transitions of the machine. This %core of pure state machine operations makes Ragel well suited to handling %parsing problems not based on token scanning. Should one need to use a %longest-match model, the functionality is available and the lower level state %machine construction facilities can be used to specify the patterns of a %longest-match machine. %This is not possible in Ragel. One can only program %a longest-match instantiation with a fixed set of rules. One can jump to %another longest-match machine that employs the same machine definitions in the %construction of its rules, however no states will be shared. %In Ragel, input may be re-parsed using a %different machine, but since the action to be executed is associated with %transitions of the compiled state machine, the longest-match construction does %not permit a single rule to be excluded from the active set. It cannot be done %ahead of time nor in the excluded rule's action. \end{comment} The Re2C program defines an input processing model similar to that of Lex. Re2C focuses on making generated state machines run very fast and integrate easily into any program, free of dependencies. Re2C generates directly executable code and is able to claim that generated parsers run nearly as fast as their hand-coded equivalents. This is very important for user adoption, as programmers are reluctant to use a tool when a faster alternative exists. A consideration to ease of use is also important because developers need the freedom to integrate the generated code as they see fit. Many scripting languages provide ways of composing parsers by linking regular expressions using program logic. For example, Sed and Awk are two established Unix scripting tools that allow the programmer to exploit regular expressions for the purpose of locating and extracting text of interest. High-level programming languages such as Perl, Python, PHP and Ruby all provide regular expression libraries that allow the user to combine regular expressions with arbitrary code. In addition to supporting the linking of regular expressions with arbitrary program logic, the Perl programming language permits the embedding of code into regular expressions. Perl embeddings do not translate into the embedding of code into deterministic state machines. Perl regular expressions are in fact not fully compiled to deterministic machines when embedded code is involved. They are instead interpreted and involve backtracking. This is shown by the following Perl program. When it is fed the input \verb|abcd| the interpretor attempts to match the first alternative, printing \verb|a1 b1|. When this possibility fails it backtracks and tries the second possibility, printing \verb|a2 b2|, at which point it succeeds. \begin{inline_code} \begin{verbatim} print "YES\n" if ( =~ /( a (?{ print "a1 "; }) b (?{ print "b1 "; }) cX ) | ( a (?{ print "a2 "; }) b (?{ print "b2 "; }) cd )/x ) \end{verbatim} \end{inline_code} \verbspace In Ragel there is no regular expression interpretor. Aside from the scanner operator, all Ragel expressions are made into deterministic machines and the run time simply moves from state to state as it consumes input. An equivalent parser expressed in Ragel would attempt both of the alternatives concurrently, printing \verb|a1 a2 b1 b2|. \section{Development Status} Ragel is a relatively new tool and is under continuous development. As a rough release guide, minor revision number changes are for implementation improvements and feature additions. Major revision number changes are for implementation and language changes that do not preserve backwards compatibility. Though in the past this has not always held true: changes that break code have crept into minor version number changes. Typically, the documentation lags behind the development in the interest of documenting only the lasting features. The latest changes are always documented in the ChangeLog file. \chapter{Constructing State Machines} \section{Ragel State Machine Specifications} A Ragel input file consists of a program in the host language that contains embedded machine specifications. Ragel normally passes input straight to output. When it sees a machine specification it stops to read the Ragel statements and possibly generate code in place of the specification. Afterwards it continues to pass input through. There can be any number of FSM specifications in an input file. A multi-line FSM spec starts with \verb|%%{| and ends with \verb|}%%|. A single-line FSM spec starts with \verb|%%| and ends at the first newline. While Ragel is looking for FSM specifications it does basic lexical analysis on the surrounding input. It interprets literal strings and comments so a \verb|%%| sequence in either of those will not trigger the parsing of an FSM specification. Ragel does not pass the input through any preprocessor nor does it interpret preprocessor directives itself so includes, defines and ifdef logic cannot be used to alter the parse of a Ragel input file. It is therefore not possible to use an \verb|#if 0| directive to comment out a machine as is commonly done in C code. As an alternative, a machine can be prevented from causing any generated output by commenting out write statements. In Figure \ref{cmd-line-parsing}, a multi-line specification is used to define the machine and single line specifications are used to trigger the writing of the machine data and execution code. \begin{figure} \begin{multicols}{2} \small \begin{verbatim} #include #include %%{ machine foo; main := ( 'foo' | 'bar' ) 0 @{ res = 1; }; }%% %% write data; \end{verbatim} \columnbreak \begin{verbatim} int main( int argc, char **argv ) { int cs, res = 0; if ( argc > 1 ) { char *p = argv[1]; char *pe = p + strlen(p) + 1; %% write init; %% write exec; } printf("result = %i\n", res ); return 0; } \end{verbatim} \end{multicols} \caption{Parsing a command line argument.} \label{cmd-line-parsing} \end{figure} \subsection{Naming Ragel Blocks} \begin{verbatim} machine fsm_name; \end{verbatim} \verbspace The \verb|machine| statement gives the name of the FSM. If present in a specification, this statement must appear first. If a machine specification does not have a name then Ragel uses the previous specification name. If no previous specification name exists then this is an error. Because FSM specifications persist in memory, a machine's statements can be spread across multiple machine specifications. This allows one to break up a machine across several files or draw in statements that are common to multiple machines using the \verb|include| statement. \subsection{Machine Definition} \label{definition} \begin{verbatim} = ; \end{verbatim} \verbspace The machine definition statement associates an FSM expression with a name. Machine expressions assigned to names can later be referenced in other expressions. A definition statement on its own does not cause any states to be generated. It is simply a description of a machine to be used later. States are generated only when a definition is instantiated, which happens when a definition is referenced in an instantiated expression. \subsection{Machine Instantiation} \label{instantiation} \begin{verbatim} := ; \end{verbatim} \verbspace The machine instantiation statement generates a set of states representing an expression. Each instantiation generates a distinct set of states. The starting state of the instantiation is written in the data section of the generated code using the instantiation name. If a machine named \verb|main| is instantiated, its start state is used as the specification's start state and is assigned to the \verb|cs| variable by the \verb|write init| command. If no \verb|main| machine is given, the start state of the last machine instantiation to appear is used as the specification's start state. From outside the execution loop, control may be passed to any machine by assigning the entry point to the \verb|cs| variable. From inside the execution loop, control may be passed to any machine instantiation using \verb|fcall|, \verb|fgoto| or \verb|fnext| statements. \subsection{Including Ragel Code} \begin{verbatim} include FsmName "inputfile.rl"; \end{verbatim} \verbspace The \verb|include| statement can be used to draw in the statements of another FSM specification. Both the name and input file are optional, however at least one must be given. Without an FSM name, the given input file is searched for an FSM of the same name as the current specification. Without an input file the current file is searched for a machine of the given name. If both are present, the given input file is searched for a machine of the given name. Ragel searches for included files from the location of the current file. Additional directories can be added to the search path using the \verb|-I| option. \subsection{Importing Definitions} \label{import} \begin{verbatim} import "inputfile.h"; \end{verbatim} \verbspace The \verb|import| statement scrapes a file for sequences of tokens that match the following forms. Ragel treats these forms as state machine definitions. \begin{itemize} \setlength{\itemsep}{-2mm} \item \verb|name '=' number| \item \verb|name '=' lit_string| \item \verb|'define' name number| \item \verb|'define' name lit_string| \end{itemize} If the input file is a Ragel program then tokens inside any Ragel specifications are ignored. See Section \ref{export} for a description of exporting machine definitions. Ragel searches for imported files from the location of the current file. Additional directories can be added to the search path using the \verb|-I| option. \section{Lexical Analysis of a Ragel Block} \label{lexing} Within a machine specification the following lexical rules apply to the input. \begin{itemize} \item The \verb|#| symbol begins a comment that terminates at the next newline. \item The symbols \verb|""|, \verb|''|, \verb|//|, \verb|[]| behave as the delimiters of literal strings. Within them, the following escape sequences are interpreted: \verb| \0 \a \b \t \n \v \f \r| A backslash at the end of a line joins the following line onto the current. A backslash preceding any other character removes special meaning. This applies to terminating characters and to special characters in regular expression literals. As an exception, regular expression literals do not support escape sequences as the operands of a range within a list. See the bullet on regular expressions in Section \ref{basic}. \item The symbols \verb|{}| delimit a block of host language code that will be embedded into the machine as an action. Within the block of host language code, basic lexical analysis of comments and strings is done in order to correctly find the closing brace of the block. With the exception of FSM commands embedded in code blocks, the entire block is preserved as is for identical reproduction in the output code. \item The pattern \verb|[+-]?[0-9]+| denotes an integer in decimal format. Integers used for specifying machines may be negative only if the alphabet type is signed. Integers used for specifying priorities may be positive or negative. \item The pattern \verb|0x[0-9A-Fa-f]+| denotes an integer in hexadecimal format. \item The keywords are \verb|access|, \verb|action|, \verb|alphtype|, \verb|getkey|, \verb|write|, \verb|machine| and \verb|include|. \item The pattern \verb|[a-zA-Z_][a-zA-Z_0-9]*| denotes an identifier. %\item The allowable symbols are: % %\verb/ ( ) ! ^ * ? + : -> - | & . , := = ; > @ $ % /\\ %\verb| >/ $/ %/ / >! $! %! !|\\ %\verb| >^ $^ %^ <^ @^ <>^ >~ $~ %~ <~ @~ <>~|\\ %\verb| >* $* %* <* @* <>*| \item Any amount of whitespace may separate tokens. \end{itemize} %\section{Parse of an FSM Specification} %The following statements are possible within an FSM specification. The %requirements for trailing semicolons loosely follow that of C. %A block %specifying code does not require a trailing semicolon. An expression %statement does require a trailing semicolon. \section{Basic Machines} \label{basic} The basic machines are the base operands of regular language expressions. They are the smallest unit to which machine construction and manipulation operators can be applied. \begin{itemize} \item \verb|'hello'| -- Concatenation Literal. Produces a machine that matches the sequence of characters in the quoted string. If there are 5 characters there will be 6 states chained together with the characters in the string. See Section \ref{lexing} for information on valid escape sequences. % GENERATE: bmconcat % OPT: -p % %%{ % machine bmconcat; \begin{comment} \begin{verbatim} main := 'hello'; \end{verbatim} \end{comment} % }%% % END GENERATE \begin{center} \includegraphics[scale=0.55]{bmconcat} \end{center} It is possible to make a concatenation literal case-insensitive by appending an \verb|i| to the string, for example \verb|'cmd'i|. \item \verb|"hello"| -- Identical to the single quoted version. \item \verb|[hello]| -- Or Expression. Produces a union of characters. There will be two states with a transition for each unique character between the two states. The \verb|[]| delimiters behave like the quotes of a literal string. For example, \verb|[ \t]| means tab or space. The \verb|or| expression supports character ranges with the \verb|-| symbol as a separator. The meaning of the union can be negated using an initial \verb|^| character as in standard regular expressions. See Section \ref{lexing} for information on valid escape sequences in \verb|or| expressions. % GENERATE: bmor % OPT: -p % %%{ % machine bmor; \begin{comment} \begin{verbatim} main := [hello]; \end{verbatim} \end{comment} % }%% % END GENERATE \begin{center} \includegraphics[scale=0.55]{bmor} \end{center} \item \verb|''|, \verb|""|, and \verb|[]| -- Zero Length Machine. Produces a machine that matches the zero length string. Zero length machines have one state that is both a start state and a final state. % GENERATE: bmnull % OPT: -p % %%{ % machine bmnull; \begin{comment} \begin{verbatim} main := ''; \end{verbatim} \end{comment} % }%% % END GENERATE \begin{center} \includegraphics[scale=0.55]{bmnull} \end{center} % FIXME: More on the range of values here. \item \verb|42| -- Numerical Literal. Produces a two state machine with one transition on the given number. The number may be in decimal or hexadecimal format and should be in the range allowed by the alphabet type. The minimum and maximum values permitted are defined by the host machine that Ragel is compiled on. For example, numbers in a \verb|short| alphabet on an i386 machine should be in the range \verb|-32768| to \verb|32767|. % GENERATE: bmnum % %%{ % machine bmnum; \begin{comment} \begin{verbatim} main := 42; \end{verbatim} \end{comment} % }%% % END GENERATE \begin{center} \includegraphics[scale=0.55]{bmnum} \end{center} \item \verb|/simple_regex/| -- Regular Expression. Regular expressions are parsed as a series of expressions that are concatenated together. Each concatenated expression may be a literal character, the ``any'' character specified by the \verb|.| symbol, or a union of characters specified by the \verb|[]| delimiters. If the first character of a union is \verb|^| then it matches any character not in the list. Within a union, a range of characters can be given by separating the first and last characters of the range with the \verb|-| symbol. Each concatenated machine may have repetition specified by following it with the \verb|*| symbol. The standard escape sequences described in Section \ref{lexing} are supported everywhere in regular expressions except as the operands of a range within in a list. This notation also supports the \verb|i| trailing option. Use it to produce case-insensitive machines, as in \verb|/GET/i|. Ragel does not support very complex regular expressions because the desired results can always be achieved using the more general machine construction operators listed in Section \ref{machconst}. The following diagram shows the result of compiling \verb|/ab*[c-z].*[123]/|. \verb|DEF| represents the default transition, which is taken if no other transition can be taken. % GENERATE: bmregex % OPT: -p % %%{ % machine bmregex; \begin{comment} \begin{verbatim} main := /ab*[c-z].*[123]/; \end{verbatim} \end{comment} % }%% % END GENERATE \begin{center} \includegraphics[scale=0.55]{bmregex} \end{center} \item \verb|'a' .. 'z'| -- Range. Produces a machine that matches any characters in the specified range. Allowable upper and lower bounds of the range are concatenation literals of length one and numerical literals. For example, \verb|0x10..0x20|, \verb|0..63|, and \verb|'a'..'z'| are valid ranges. The bounds should be in the range allowed by the alphabet type. % GENERATE: bmrange % OPT: -p % %%{ % machine bmrange; \begin{comment} \begin{verbatim} main := 'a' .. 'z'; \end{verbatim} \end{comment} % }%% % END GENERATE \begin{center} \includegraphics[scale=0.55]{bmrange} \end{center} \item \verb|variable_name| -- Lookup the machine definition assigned to the variable name given and use an instance of it. See Section \ref{definition} for an important note on what it means to reference a variable name. \item \verb|builtin_machine| -- There are several built-in machines available for use. They are all two state machines for the purpose of matching common classes of characters. They are: \begin{itemize} \item \verb|any | -- Any character in the alphabet. \item \verb|ascii | -- Ascii characters. \verb|0..127| \item \verb|extend| -- Ascii extended characters. This is the range \verb|-128..127| for signed alphabets and the range \verb|0..255| for unsigned alphabets. \item \verb|alpha | -- Alphabetic characters. \verb|[A-Za-z]| \item \verb|digit | -- Digits. \verb|[0-9]| \item \verb|alnum | -- Alpha numerics. \verb|[0-9A-Za-z]| \item \verb|lower | -- Lowercase characters. \verb|[a-z]| \item \verb|upper | -- Uppercase characters. \verb|[A-Z]| \item \verb|xdigit| -- Hexadecimal digits. \verb|[0-9A-Fa-f]| \item \verb|cntrl | -- Control characters. \verb|0..31| \item \verb|graph | -- Graphical characters. \verb|[!-~]| \item \verb|print | -- Printable characters. \verb|[ -~]| \item \verb|punct | -- Punctuation. Graphical characters that are not alphanumerics. \verb|[!-/:-@[-`{-~]| \item \verb|space | -- Whitespace. \verb|[\t\v\f\n\r ]| \item \verb|zlen | -- Zero length string. \verb|""| \item \verb|empty | -- Empty set. Matches nothing. \verb|^any| \end{itemize} \end{itemize} \section{Operator Precedence} The following table shows operator precedence from lowest to highest. Operators in the same precedence group are evaluated from left to right. \verbspace \begin{tabular}{|c|c|c|} \hline 1&\verb| , |&Join\\ \hline 2&\verb/ | & - --/&Union, Intersection and Subtraction\\ \hline 3&\verb| . <: :> :>> |&Concatenation\\ \hline 4&\verb| : |&Label\\ \hline 5&\verb| -> |&Epsilon Transition\\ \hline &\verb| > @ $ % |&Transitions Actions and Priorities\\ \cline{2-3} &\verb| >/ $/ %/ / |&EOF Actions\\ \cline{2-3} 6&\verb| >! $! %! ! |&Global Error Actions\\ \cline{2-3} &\verb| >^ $^ %^ <^ @^ <>^ |&Local Error Actions\\ \cline{2-3} &\verb| >~ $~ %~ <~ @~ <>~ |&To-State Actions\\ \cline{2-3} &\verb| >* $* %* <* @* <>* |&From-State Action\\ \hline 7&\verb| * ** ? + {n} {,n} {n,} {n,m} |&Repetition\\ \hline 8&\verb| ! ^ |&Negation and Character-Level Negation\\ \hline 9&\verb| ( ) |&Grouping\\ \hline \end{tabular} \section{Regular Language Operators} \label{machconst} When using Ragel it is helpful to have a sense of how it constructs machines. The determinization process can produce results that seem unusual to someone not familiar with the NFA to DFA conversion algorithm. In this section we describe Ragel's state machine operators. Though the operators are defined using epsilon transitions, it should be noted that this is for discussion only. The epsilon transitions described in this section do not persist, but are immediately removed by the determinization process which is executed at every operation. Ragel does not make use of any nondeterministic intermediate state machines. To create an epsilon transition between two states \verb|x| and \verb|y| is to copy all of the properties of \verb|y| into \verb|x|. This involves drawing in all of \verb|y|'s to-state actions, EOF actions, etc., in addition to its transitions. If \verb|x| and \verb|y| both have a transition out on the same character, then the transitions must be combined. During transition combination a new transition is made that goes to a new state that is the combination of both target states. The new combination state is created using the same epsilon transition method. The new state has an epsilon transition drawn to all the states that compose it. Since the creation of new epsilon transitions may be triggered every time an epsilon transition is drawn, the process of drawing epsilon transitions is repeated until there are no more epsilon transitions to be made. A very common error that is made when using Ragel is to make machines that do too much. That is, to create machines that have unintentional nondetermistic properties. This usually results from being unaware of the common strings between machines that are combined together using the regular language operators. This can involve never leaving a machine, causing its actions to be propagated through all the following states. Or it can involve an alternation where both branches are unintentionally taken simultaneously. This problem forces one to think hard about the language that needs to be matched. To guard against this kind of problem one must ensure that the machine specification is divided up using boundaries that do not allow ambiguities from one portion of the machine to the next. See Chapter \ref{controlling-nondeterminism} for more on this problem and how to solve it. The Graphviz tool is an immense help when debugging improperly compiled machines or otherwise learning how to use Ragel. Graphviz Dot files can be generated from Ragel programs using the \verb|-V| option. See Section \ref{visualization} for more information. \subsection{Union} \verb/expr | expr/ \verbspace The union operation produces a machine that matches any string in machine one or machine two. The operation first creates a new start state. Epsilon transitions are drawn from the new start state to the start states of both input machines. The resulting machine has a final state set equivalent to the union of the final state sets of both input machines. In this operation, there is the opportunity for nondeterminism among both branches. If there are strings, or prefixes of strings that are matched by both machines then the new machine will follow both parts of the alternation at once. The union operation is shown below. \graphspace \begin{center} \includegraphics{opor} \end{center} \graphspace The following example demonstrates the union of three machines representing common tokens. % GENERATE: exor % OPT: -p % %%{ % machine exor; \begin{inline_code} \begin{verbatim} # Hex digits, decimal digits, or identifiers main := '0x' xdigit+ | digit+ | alpha alnum*; \end{verbatim} \end{inline_code} % }%% % END GENERATE \graphspace \begin{center} \includegraphics[scale=0.55]{exor} \end{center} \subsection{Intersection} \verb|expr & expr| \verbspace Intersection produces a machine that matches any string that is in both machine one and machine two. To achieve intersection, a union is performed on the two machines. After the result has been made deterministic, any final state that is not a combination of final states from both machines has its final state status revoked. To complete the operation, paths that do not lead to a final state are pruned from the machine. Therefore, if there are any such paths in either of the expressions they will be removed by the intersection operator. Intersection can be used to require that two independent patterns be simultaneously satisfied as in the following example. % GENERATE: exinter % OPT: -p % %%{ % machine exinter; \begin{inline_code} \begin{verbatim} # Match lines four characters wide that contain # words separated by whitespace. main := /[^\n][^\n][^\n][^\n]\n/* & (/[a-z][a-z]*/ | [ \n])**; \end{verbatim} \end{inline_code} % }%% % END GENERATE \graphspace \begin{center} \includegraphics[scale=0.55]{exinter} \end{center} \subsection{Difference} \verb|expr - expr| \verbspace The difference operation produces a machine that matches strings that are in machine one but are not in machine two. To achieve subtraction, a union is performed on the two machines. After the result has been made deterministic, any final state that came from machine two or is a combination of states involving a final state from machine two has its final state status revoked. As with intersection, the operation is completed by pruning any path that does not lead to a final state. The following example demonstrates the use of subtraction to exclude specific cases from a set. \verbspace % GENERATE: exsubtr % OPT: -p % %%{ % machine exsubtr; \begin{inline_code} \begin{verbatim} # Subtract keywords from identifiers. main := /[a-z][a-z]*/ - ( 'for' | 'int' ); \end{verbatim} \end{inline_code} % }%% % END GENERATE \graphspace \begin{center} \includegraphics[scale=0.55]{exsubtr} \end{center} \graphspace \subsection{Strong Difference} \label{strong_difference} \verb|expr -- expr| \verbspace Strong difference produces a machine that matches any string of the first machine that does not have any string of the second machine as a substring. In the following example, strong subtraction is used to excluded \verb|CRLF| from a sequence. In the corresponding visualization, the label \verb|DEF| is short for default. The default transition is taken if no other transition can be taken. % GENERATE: exstrongsubtr % OPT: -p % %%{ % machine exstrongsubtr; \begin{inline_code} \begin{verbatim} crlf = '\r\n'; main := [a-z]+ ':' ( any* -- crlf ) crlf; \end{verbatim} \end{inline_code} % }%% % END GENERATE \graphspace \begin{center} \includegraphics[scale=0.55]{exstrongsubtr} \end{center} \graphspace This operator is equivalent to the following. \verbspace \begin{verbatim} expr - ( any* expr any* ) \end{verbatim} \subsection{Concatenation} \verb|expr . expr| \verbspace Concatenation produces a machine that matches all the strings in machine one followed by all the strings in machine two. Concatenation draws epsilon transitions from the final states of the first machine to the start state of the second machine. The final states of the first machine lose their final state status, unless the start state of the second machine is final as well. Concatenation is the default operator. Two machines next to each other with no operator between them results in concatenation. \graphspace \begin{center} \includegraphics{opconcat} \end{center} \graphspace The opportunity for nondeterministic behaviour results from the possibility of the final states of the first machine accepting a string that is also accepted by the start state of the second machine. The most common scenario in which this happens is the concatenation of a machine that repeats some pattern with a machine that gives a terminating string, but the repetition machine does not exclude the terminating string. The example in Section \ref{strong_difference} guards against this. Another example is the expression \verb|("'" any* "'")|. When executed the thread of control will never leave the \verb|any*| machine. This is a problem especially if actions are embedded to process the characters of the \verb|any*| component. In the following example, the first machine is always active due to the nondeterministic nature of concatenation. This particular nondeterminism is intended however because we wish to permit EOF strings before the end of the input. % GENERATE: exconcat % OPT: -p % %%{ % machine exconcat; \begin{inline_code} \begin{verbatim} # Require an eof marker on the last line. main := /[^\n]*\n/* . 'EOF\n'; \end{verbatim} \end{inline_code} % }%% % END GENERATE \graphspace \begin{center} \includegraphics[scale=0.55]{exconcat} \end{center} \graphspace \noindent {\bf Note:} There is a language ambiguity involving concatenation and subtraction. Because concatenation is the default operator for two adjacent machines there is an ambiguity between subtraction of a positive numerical literal and concatenation of a negative numerical literal. For example, \verb|(x-7)| could be interpreted as \verb|(x . -7)| or \verb|(x - 7)|. In the Ragel language, the subtraction operator always takes precedence over concatenation of a negative literal. We adhere to the rule that the default concatenation operator takes effect only when there are no other operators between two machines. Beware of writing machines such as \verb|(any -1)| when what is desired is a concatenation of \verb|any| and \verb|-1|. Instead write \verb|(any . -1)| or \verb|(any (-1))|. If in doubt of the meaning of your program do not rely on the default concatenation operator; always use the \verb|.| symbol. \subsection{Kleene Star} \verb|expr*| \verbspace The machine resulting from the Kleene Star operator will match zero or more repetitions of the machine it is applied to. It creates a new start state and an additional final state. Epsilon transitions are drawn between the new start state and the old start state, between the new start state and the new final state, and between the final states of the machine and the new start state. After the machine is made deterministic the effect is of the final states getting all the transitions of the start state. \graphspace \begin{center} \includegraphics{opstar} \end{center} \graphspace The possibility for nondeterministic behaviour arises if the final states have transitions on any of the same characters as the start state. This is common when applying kleene star to an alternation of tokens. Like the other problems arising from nondeterministic behavior, this is discussed in more detail in Chapter \ref{controlling-nondeterminism}. This particular problem can also be solved by using the longest-match construction discussed in Section \ref{generating-scanners} on scanners. In this example, there is no nondeterminism introduced by the exterior kleene star due to the newline at the end of the regular expression. Without the newline the exterior kleene star would be redundant and there would be ambiguity between repeating the inner range of the regular expression and the entire regular expression. Though it would not cause a problem in this case, unnecessary nondeterminism in the kleene star operator often causes undesired results for new Ragel users and must be guarded against. % GENERATE: exstar % OPT: -p % %%{ % machine exstar; \begin{inline_code} \begin{verbatim} # Match any number of lines with only lowercase letters. main := /[a-z]*\n/*; \end{verbatim} \end{inline_code} % }%% % END GENERATE \graphspace \begin{center} \includegraphics[scale=0.55]{exstar} \end{center} \graphspace \subsection{One Or More Repetition} \verb|expr+| \verbspace This operator produces the concatenation of the machine with the kleene star of itself. The result will match one or more repetitions of the machine. The plus operator is equivalent to \verb|(expr . expr*)|. % GENERATE: explus % OPT: -p % %%{ % machine explus; \begin{inline_code} \begin{verbatim} # Match alpha-numeric words. main := alnum+; \end{verbatim} \end{inline_code} % }%% % END GENERATE \graphspace \begin{center} \includegraphics[scale=0.55]{explus} \end{center} \graphspace \subsection{Optional} \verb|expr?| \verbspace The {\em optional} operator produces a machine that accepts the machine given or the zero length string. The optional operator is equivalent to \verb/(expr | '' )/. In the following example the optional operator is used to possibly extend a token. % GENERATE: exoption % OPT: -p % %%{ % machine exoption; \begin{inline_code} \begin{verbatim} # Match integers or floats. main := digit+ ('.' digit+)?; \end{verbatim} \end{inline_code} % }%% % END GENERATE \graphspace \begin{center} \includegraphics[scale=0.55]{exoption} \end{center} \graphspace \subsection{Repetition} \begin{tabbing} \noindent \verb|expr {n}| \hspace{16pt}\=-- Exactly N copies of expr.\\ \noindent \verb|expr {,n}| \>-- Zero to N copies of expr.\\ \noindent \verb|expr {n,}| \>-- N or more copies of expr.\\ \noindent \verb|expr {n,m}| \>-- N to M copies of expr. \end{tabbing} \subsection{Negation} \verb|!expr| \verbspace Negation produces a machine that matches any string not matched by the given machine. Negation is equivalent to \verb|(any* - expr)|. % GENERATE: exnegate % OPT: -p % %%{ % machine exnegate; \begin{inline_code} \begin{verbatim} # Accept anything but a string beginning with a digit. main := ! ( digit any* ); \end{verbatim} \end{inline_code} % }%% % END GENERATE \graphspace \begin{center} \includegraphics[scale=0.55]{exnegate} \end{center} \graphspace \subsection{Character-Level Negation} \verb|^expr| \verbspace Character-level negation produces a machine that matches any single character not matched by the given machine. Character-Level Negation is equivalent to \verb|(any - expr)|. It must be applied only to machines that match strings of length one. \section{State Machine Minimization} State machine minimization is the process of finding the minimal equivalent FSM accepting the language. Minimization reduces the number of states in machines by merging equivalent states. It does not change the behaviour of the machine in any way. It will cause some states to be merged into one because they are functionally equivalent. State minimization is on by default. It can be turned off with the \verb|-n| option. The algorithm implemented is similar to Hopcroft's state minimization algorithm. Hopcroft's algorithm assumes a finite alphabet that can be listed in memory, whereas Ragel supports arbitrary integer alphabets that cannot be listed in memory. Though exact analysis is very difficult, Ragel minimization runs close to $O(n \times log(n))$ and requires $O(n)$ temporary storage where $n$ is the number of states. \section{Visualization} \label{visualization} %In many cases, practical %parsing programs will be too large to completely visualize with Graphviz. The %proper approach is to reduce the language to the smallest subset possible that %still exhibits the characteristics that one wishes to learn about or to fix. %This can be done without modifying the source code using the \verb|-M| and %\verb|-S| options. If a machine cannot be easily reduced, %embeddings of unique actions can be very useful for tracing a %particular component of a larger machine specification, since action names are %written out on transition labels. Ragel is able to emit compiled state machines in Graphviz's Dot file format. This is done using the \verb|-V| option. Graphviz support allows users to perform incremental visualization of their parsers. User actions are displayed on transition labels of the graph. If the final graph is too large to be meaningful, or even drawn, the user is able to inspect portions of the parser by naming particular regular expression definitions with the \verb|-S| and \verb|-M| options to the \verb|ragel| program. Use of Graphviz greatly improves the Ragel programming experience. It allows users to learn Ragel by experimentation and also to track down bugs caused by unintended nondeterminism. Ragel has another option to help debugging. The \verb|-x| option causes Ragel to emit the compiled machine in an XML format. \chapter{User Actions} Ragel permits the user to embed actions into the transitions of a regular expression's corresponding state machine. These actions are executed when the generated code moves over a transition. Like the regular expression operators, the action embedding operators are fully compositional. They take a state machine and an action as input, embed the action and yield a new state machine that can be used in the construction of other machines. Due to the compositional nature of embeddings, the user has complete freedom in the placement of actions. A machine's transitions are categorized into four classes. The action embedding operators access the transitions defined by these classes. The {\em entering transition} operator \verb|>| isolates the start state, then embeds an action into all transitions leaving it. The {\em finishing transition} operator \verb|@| embeds an action into all transitions going into a final state. The {\em all transition} operator \verb|$| embeds an action into all transitions of an expression. The {\em leaving transition} operator \verb|%| provides access to the yet-unmade transitions moving out of the machine via the final states. \section{Embedding Actions} \begin{verbatim} action ActionName { /* Code an action here. */ count += 1; } \end{verbatim} \verbspace The action statement defines a block of code that can be embedded into an FSM. Action names can be referenced by the action embedding operators in expressions. Though actions need not be named in this way (literal blocks of code can be embedded directly when building machines), defining reusable blocks of code whenever possible is good practice because it potentially increases the degree to which the machine can be minimized. Within an action some Ragel expressions and statements are parsed and translated. These allow the user to interact with the machine from action code. See Section \ref{vals} for a complete list of statements and values available in code blocks. \subsection{Entering Action} \verb|expr > action| \verbspace The entering action operator embeds an action into all transitions that enter into the machine from the start state. If the start state is final, then the action is also embedded into the start state as a leaving action. This means that if a machine accepts the zero-length string and control passes through the start state then the entering action is executed. Note that this can happen on both a following character and on the EOF event. In some machines the start state has transtions coming in from within the machine. In these cases the start state is first isolated from the rest of the machine ensuring that the entering actions are exected once only. \verbspace % GENERATE: exstact % OPT: -p % %%{ % machine exstact; \begin{inline_code} \begin{verbatim} # Execute A at the beginning of a string of alpha. action A {} main := ( lower* >A ) . ' '; \end{verbatim} \end{inline_code} % }%% % END GENERATE \graphspace \begin{center} \includegraphics[scale=0.55]{exstact} \end{center} \graphspace \subsection{Finishing Action} \verb|expr @ action| \verbspace The finishing action operator embeds an action into any transitions that move the machine into a final state. Further input may move the machine out of the final state, but keep it in the machine. Therefore finishing actions may be executed more than once if a machine has any internal transitions out of a final state. In the following example the final state has no transitions out and the finishing action is executed only once. % GENERATE: exdoneact % OPT: -p % %%{ % machine exdoneact; % action A {} \begin{inline_code} \begin{verbatim} # Execute A when the trailing space is seen. main := ( lower* ' ' ) @A; \end{verbatim} \end{inline_code} % }%% % END GENERATE \graphspace \begin{center} \includegraphics[scale=0.55]{exdoneact} \end{center} \graphspace \subsection{All Transition Action} \verb|expr $ action| \verbspace The all transition operator embeds an action into all transitions of a machine. The action is executed whenever a transition of the machine is taken. In the following example, A is executed on every character matched. % GENERATE: exallact % OPT: -p % %%{ % machine exallact; % action A {} \begin{inline_code} \begin{verbatim} # Execute A on any characters of the machine. main := ( 'm1' | 'm2' ) $A; \end{verbatim} \end{inline_code} % }%% % END GENERATE \graphspace \begin{center} \includegraphics[scale=0.55]{exallact} \end{center} \graphspace \subsection{Leaving Actions} \label{out-actions} \verb|expr % action| \verbspace The leaving action operator queues an action for embedding into the transitions that go out of a machine via a final state. The action is first stored in the machine's final states and is later transferred to any transitions that are made going out of the machine by a kleene star or concatenation operation. If a final state of the machine is still final when compilation is complete then the leaving action is also embedded as an EOF action. Therefore, leaving the machine is defined as either leaving on a character or as state machine acceptance. This operator allows one to associate an action with the termination of a sequence, without being concerned about what particular character terminates the sequence. In the following example, A is executed when leaving the alpha machine on the newline character. % GENERATE: exoutact1 % OPT: -p % %%{ % machine exoutact1; % action A {} \begin{inline_code} \begin{verbatim} # Match a word followed by a newline. Execute A when # finishing the word. main := ( lower+ %A ) . '\n'; \end{verbatim} \end{inline_code} % }%% % END GENERATE \graphspace \begin{center} \includegraphics[scale=0.55]{exoutact1} \end{center} \graphspace In the following example, the \verb|term_word| action could be used to register the appearance of a word and to clear the buffer that the \verb|lower| action used to store the text of it. % GENERATE: exoutact2 % OPT: -p % %%{ % machine exoutact2; % action lower {} % action space {} % action term_word {} % action newline {} \begin{inline_code} \begin{verbatim} word = ( [a-z] @lower )+ %term_word; main := word ( ' ' @space word )* '\n' @newline; \end{verbatim} \end{inline_code} % }%% % END GENERATE \graphspace \begin{center} \includegraphics[scale=0.55]{exoutact2} \end{center} \graphspace In this final example of the action embedding operators, A is executed upon entering the alpha machine, B is executed on all transitions of the alpha machine, C is executed when the alpha machine is exited by moving into the newline machine and N is executed when the newline machine moves into a final state. % GENERATE: exaction % OPT: -p % %%{ % machine exaction; % action A {} % action B {} % action C {} % action N {} \begin{inline_code} \begin{verbatim} # Execute A on starting the alpha machine, B on every transition # moving through it and C upon finishing. Execute N on the newline. main := ( lower* >A $B %C ) . '\n' @N; \end{verbatim} \end{inline_code} % }%% % END GENERATE \graphspace \begin{center} \includegraphics[scale=0.55]{exaction} \end{center} \graphspace \section{State Action Embedding Operators} The state embedding operators allow one to embed actions into states. Like the transition embedding operators, there are several different classes of states that the operators access. The meanings of the symbols are similar to the meanings of the symbols used for the transition embedding operators. The design of the state selections was driven by a need to cover the states of an expression with exactly one error action. Unlike the transition embedding operators, the state embedding operators are also distinguished by the different kinds of events that embedded actions can be associated with. Therefore the state embedding operators have two components. The first, which is the first one or two characters, specifies the class of states that the action will be embedded into. The second component specifies the type of event the action will be executed on. The symbols of the second component also have equivalent kewords. \vspace{10pt} \def\fakeitem{\hspace*{12pt}$\bullet$\hspace*{10pt}} \begin{minipage}{\textwidth} \begin{multicols}{2} \raggedcolumns \noindent The different classes of states are:\\ \fakeitem \verb|> | -- the start state\\ \fakeitem \verb|< | -- any state except the start state\\ \fakeitem \verb|$ | -- all states\\ \fakeitem \verb|% | -- final states\\ \fakeitem \verb|@ | -- any state except final states\\ \fakeitem \verb|<>| -- any except start and final (middle) \columnbreak \noindent The different kinds of embeddings are:\\ \fakeitem \verb|~| -- to-state actions (\verb|to|)\\ \fakeitem \verb|*| -- from-state actions (\verb|from|)\\ \fakeitem \verb|/| -- EOF actions (\verb|eof|)\\ \fakeitem \verb|!| -- error actions (\verb|err|)\\ \fakeitem \verb|^| -- local error actions (\verb|lerr|)\\ \end{multicols} \end{minipage} \subsection{To-State and From-State Actions} \subsubsection{To-State Actions} \def\sasp{\hspace*{40pt}} \sasp\verb|>~action >to(name) >to{...} | -- the start state\\ \sasp\verb|<~action ~action <>to(name) <>to{...}| -- any except start and final (middle) \vspace{12pt} To-state actions are executed whenever the state machine moves into the specified state, either by a natural movement over a transition or by an action-based transfer of control such as \verb|fgoto|. They are executed after the in-transition's actions but before the current character is advanced and tested against the end of the input block. To-state embeddings stay with the state. They are irrespective of the state's current set of transitions and any future transitions that may be added in or out of the state. Note that the setting of the current state variable \verb|cs| outside of the execute code is not considered by Ragel as moving into a state and consequently the to-state actions of the new current state are not executed. This includes the initialization of the current state when the machine begins. This is because the entry point into the machine execution code is after the execution of to-state actions. \subsubsection{From-State Actions} \sasp\verb|>*action >from(name) >from{...} | -- the start state\\ \sasp\verb|<*action *action <>from(name) <>from{...}| -- any except start and final (middle) \vspace{12pt} From-state actions are executed whenever the state machine takes a transition from a state, either to itself or to some other state. These actions are executed immediately after the current character is tested against the input block end marker and before the transition to take is sought based on the current character. From-state actions are therefore executed even if a transition cannot be found and the machine moves into the error state. Like to-state embeddings, from-state embeddings stay with the state. \subsection{EOF Actions} \sasp\verb|>/action >eof(name) >eof{...} | -- the start state\\ \sasp\verb|/action <>eof(name) <>eof{...}| -- any except start and final (middle) \vspace{12pt} The EOF action embedding operators enable the user to embed actions that are executed at the end of the input stream. EOF actions are stored in states and generated in the \verb|write exec| block. They are run when \verb|p == pe == eof| as the execute block is finishing. EOF actions are free to adjust \verb|p| and jump to another part of the machine to restart execution. \subsection{Handling Errors} In many applications it is useful to be able to react to parsing errors. The user may wish to print an error message that depends on the context. It may also be desirable to consume input in an attempt to return the input stream to some known state and resume parsing. To support error handling and recovery, Ragel provides error action embedding operators. There are two kinds of error actions: global error actions and local error actions. Error actions can be used to simply report errors, or by jumping to a machine instantiation that consumes input, can attempt to recover from errors. \subsubsection{Global Error Actions} \sasp\verb|>!action >err(name) >err{...} | -- the start state\\ \sasp\verb|!action <>err(name) <>err{...}| -- any except start and final (middle) \vspace{12pt} Global error actions are stored in the states they are embedded into until compilation is complete. They are then transferred to the transitions that move into the error state. These transitions are taken on all input characters that are not already covered by the state's transitions. If a state with an error action is not final when compilation is complete, then the action is also embedded as an EOF action. Error actions can be used to recover from errors by jumping back into the machine with \verb|fgoto| and optionally altering \verb|p|. \subsubsection{Local Error Actions} \sasp\verb|>^action >lerr(name) >lerr{...} | -- the start state\\ \sasp\verb|<^action ^action <>lerr(name) <>lerr{...}| -- any except start and final (middle) \vspace{12pt} Like global error actions, local error actions are also stored in the states they are embedded into until a transfer point. The transfer point is different however. Each local error action embedding is associated with a name. When a machine definition has been fully constructed, all local error action embeddings associated with the same name as the machine definition are transferred to the error transitions. At this time they are also embedded as EOF actions in the case of non-final states. Local error actions can be used to specify an action to take when a particular section of a larger state machine fails to match. A particular machine definition's ``thread'' may die and the local error actions executed, however the machine as a whole may continue to match input. There are two forms of local error action embeddings. In the first form the name defaults to the current machine. In the second form the machine name can be specified. This is useful when it is more convenient to specify the local error action in a sub-definition that is used to construct the machine definition that the local error action is associated with. To embed local error actions and explicitly state the machine definition on which the transfer is to happen use \verb|(name, action)| as the action. \subsubsection{Example} The following example uses error actions to report an error and jump to a machine that consumes the remainder of the line when parsing fails. After consuming the line, the error recovery machine returns to the main loop. % GENERATE: erract % %%{ % machine erract; % ws = ' '; % address = 'foo@bar.com'; % date = 'Monday May 12'; \begin{inline_code} \begin{verbatim} action cmd_err { printf( "command error\n" ); fhold; fgoto line; } action from_err { printf( "from error\n" ); fhold; fgoto line; } action to_err { printf( "to error\n" ); fhold; fgoto line; } line := [^\n]* '\n' @{ fgoto main; }; main := ( ( 'from' @err(cmd_err) ( ws+ address ws+ date '\n' ) $err(from_err) | 'to' @err(cmd_err) ( ws+ address '\n' ) $err(to_err) ) )*; \end{verbatim} \end{inline_code} % }%% % %% write data; % void f() % { % %% write init; % %% write exec; % } % END GENERATE \section{Action Ordering and Duplicates} When combining expressions that have embedded actions it is often the case that a number of actions must be executed on a single input character. For example, following a concatenation the leaving action of the left expression and the entering action of the right expression will be embedded into one transition. This requires a method of ordering actions that is intuitive and predictable for the user, and repeatable for the compiler. We associate with the embedding of each action a unique timestamp that is used to order actions that appear together on a single transition in the final state machine. To accomplish this we recursively traverse the parse tree of regular expressions and assign timestamps to action embeddings. References to machine definitions are followed in the traversal. When we visit a parse tree node we assign timestamps to all {\em entering} action embeddings, recurse on the parse tree, then assign timestamps to the remaining {\em all}, {\em finishing}, and {\em leaving} embeddings in the order in which they appear. By default Ragel does not permit a single action to appear multiple times in an action list. When the final machine has been created, actions that appear more than once in a single transition, to-state, from-state or EOF action list have their duplicates removed. The first appearance of the action is preserved. This is useful in a number of scenarios. First, it allows us to union machines with common prefixes without worrying about the action embeddings in the prefix being duplicated. Second, it prevents leaving actions from being transferred multiple times. This can happen when a machine is repeated, then followed with another machine that begins with a common character. For example: \verbspace \begin{verbatim} word = [a-z]+ %act; main := word ( '\n' word )* '\n\n'; \end{verbatim} \verbspace Note that Ragel does not compare action bodies to determine if they have identical program text. It simply checks for duplicates using each action block's unique location in the program. The removal of duplicates can be turned off using the \verb|-d| option. \section{Values and Statements Available in Code Blocks} \label{vals} \noindent The following values are available in code blocks: \begin{itemize} \item \verb|fpc| -- A pointer to the current character. This is equivalent to accessing the \verb|p| variable. \item \verb|fc| -- The current character. This is equivalent to the expression \verb|(*p)|. \item \verb|fcurs| -- An integer value representing the current state. This value should only be read from. To move to a different place in the machine from action code use the \verb|fgoto|, \verb|fnext| or \verb|fcall| statements. Outside of the machine execution code the \verb|cs| variable may be modified. \item \verb|ftargs| -- An integer value representing the target state. This value should only be read from. Again, \verb|fgoto|, \verb|fnext| and \verb|fcall| can be used to move to a specific entry point. \item \verb|fentry(