Ragel State Machine Compiler User Guide

In today’s computing landscape, regular expressions are used heavily for the purpose of specifying parsers. They are normally treated as black boxes, linked together with program logic. User code is executed in between invocations of the regular expression engine. To add code before a pattern terminates, the programmer is required to break patterns and paste them back together with program logic. The more inline code needed, the less the advantages of regular expressions are seen.

Ragel is a software development tool that allows user code to be embedded into the transitions of a regular expression’s corresponding state machine, eliminating the need to switch from the regular expression engine to the user code execution environment, and then 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, GNU ASM x86-64, Java, Ruby, C#, OCaml, Crack, Rust, Julia and JavaScript

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.

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 execution 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.

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, GNU ASM x86-64, Java, Ruby, C#, OCaml, Crack, Rust, Julia and JavaScript 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 executed 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.

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 %%{ and ends with }%%. A single-line FSM spec starts with %% 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 %% 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 #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 the example below, 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. This example shows parsing of a command line argument.

Within a machine specification the following lexical rules apply to the input.

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.

The following table shows operator precedence from lowest to highest. Operators in the same precedence group are evaluated from left to right.

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 x and y is to copy all of the properties of y into x. This involves drawing in all of y's to-state actions, EOF actions, etc., in addition to its transitions. If x and 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 nondeterministic 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 the chapter on 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 -V option. See the section on Visualization for more information.

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 -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 * log(n)) and requires O(n) temporary storage where $n$ is the number of states.

Ragel is able to emit compiled state machines in Graphviz’s Dot file format. This is done using the -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 -S and -M options to the 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 -x option causes Ragel to emit the compiled machine in an XML format.

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 Values and Statements for a complete list of values and statements available in code blocks.

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 keywords.

The different classes of states are:

The different kinds of embeddings are:

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 entering action embeddings, recurse on the parse tree, then assign timestamps to the remaining all, finishing, and 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:

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 -d option.

The following values are available in code blocks:

The following statements are available in code blocks:

Once actions with control-flow commands are embedded into a machine, the user must exercise caution when using the machine as the operand to other machine construction operators. If an action jumps to another state then unioning any transition that executes that action with another transition that follows some other path will cause that other path to be lost. Using commands that manually jump around a machine takes us out of the domain of regular languages because transitions that the machine construction operators are not aware of are introduced. These commands should therefore be used with caution.

A priority mechanism was devised and built into the determinization process, specifically for the purpose of allowing the user to control nondeterminism. Priorities are integer values embedded into transitions. When the determinization process is combining transitions that have different priorities, the transition with the higher priority is preserved and the transition with the lower priority is dropped.

Unfortunately, priorities can have unintended side effects because their operation requires that they linger in transitions indefinitely. They must linger because the Ragel program cannot know when the user is finished with a priority embedding. A solution whereby they are explicitly deleted after use is conceivable; however this is not very user-friendly. Priorities were therefore made into named entities. Only priorities with the same name are allowed to interact. This allows any number of priorities to coexist in one machine for the purpose of controlling various different regular expression operations and eliminates the need to ever delete them. Such a scheme allows the user to choose a unique name, embed two different priority values using that name and be confident that the priority embedding will be free of any side effects.

In the first form of priority embedding, the name defaults to the name of the machine definition that the priority is assigned in. In this sense priorities are by default local to the current machine definition or instantiation. Beware of using this form in a longest-match machine, since there is only one name for the entire set of longest match patterns. In the second form the priority’s name can be specified, allowing priority interaction across machine definition boundaries.

The second form of priority assignment allows the programmer to specify the name to which the priority is assigned.

Priority embeddings are a very expressive mechanism. At the same time they can be very confusing for the user. They force the user to imagine the transitions inside two interacting expressions and work out the precise effects of the operations between them. When we consider that this problem is worsened by the potential for side effects caused by unintended priority name collisions, we see that exposing the user to priorities is undesirable.

Fortunately, in practice the use of priorities has been necessary only in a small number of scenarios. This allows us to encapsulate their functionality into a small set of operators and fully hide them from the user. This is advantageous from a language design point of view because it greatly simplifies the design.

Going back to the C comment example, we can now properly specify it using a guarded concatenation operator which we call finish-guarded concatenation. From the user’s point of view, this operator terminates the first machine when the second machine moves into a final state. It chooses a unique name and uses it to embed a low priority into all transitions of the first machine. A higher priority is then embedded into the transitions of the second machine that enter into a final state. The following example yields a machine identical to the example in the section on Controlling Nondeterminism.

Another guarded operator is left-guarded concatenation, given by the <: compound symbol. This operator places a higher priority on all transitions of the first machine. This is useful if one must forcibly separate two lists that contain common elements. For example, one may need to tokenize a stream, but first consume leading whitespace.

Ragel also includes a longest-match kleene star operator, given by the ** compound symbol. This guarded operator embeds a high priority into all transitions of the machine. A lower priority is then embedded into the leaving transitions. When the kleene star operator makes the epsilon transitions from the final states into the new start state, the lower priority will be transferred to the epsilon transitions. In cases where following an epsilon transition out of a final state conflicts with an existing transition out of a final state, the epsilon transition will be dropped.

Other guarded operators are conceivable, such as guards on union that cause one alternative to take precedence over another. These may be implemented when it is clear they constitute a frequently used operation. In the next section we discuss the explicit specification of state machines using state charts.

There are a number of variables that Ragel expects the user to declare. At a very minimum the cs, p and pe variables must be declared. In Go, Java, Ruby and OCaml code the data variable must also be declared. If EOF actions are used then the eof variable is required. If stack-based state machine control flow statements are used then the stack and top variables are required. If a scanner is declared then the act, ts and te variables must be declared.

The alphtype statement specifies the alphabet data type that the machine operates on. During the compilation of the machine, integer literals are expected to be in the range of possible values of the alphtype. The default is char for all languages except Go where the default is byte and OCaml where the default is int.

C/C++/Objective-C:

Go:

Ruby:

Java:

D:

OCaml:

This statement specifies to Ragel how to retrieve the current character from from the pointer to the current element (p). Any expression that returns a value of the alphabet type may be used. The getkey statement may be used for looking into element structures or for translating the character to process. The getkey expression defaults to (*p). In goto-driven machines the getkey expression may be evaluated more than once per element processed, therefore it should not incur a large cost nor preclude optimization.

The access statement specifies how the generated code should access the machine data that is persistent across processing buffer blocks. This applies to all variables except p, pe and eof. This includes cs, top, stack, ts, te and act. The access statement is useful if a machine is to be encapsulated inside a structure in C code. It can be used to give the name of a pointer to the structure.

The variable statement specifies how to access a specific variable. All of the variables that are declared by the user and used by Ragel can be changed. This includes p, pe, eof, cs, top, stack, ts, te and act. In Go, Ruby, Java and OCaml code generation the data variable can also be changed.

The prepush statement allows the user to supply stack management code that is written out during the generation of fcall, immediately before the current state is pushed to the stack. This statement can be used to test the number of available spaces and dynamically grow the stack if necessary.

The postpop statement allows the user to supply stack management code that is written out during the generation of fret, immediately after the next state is popped from the stack. This statement can be used to dynamically shrink the stack.

The write statement is used to generate parts of the machine. There are seven components that can be generated by a write statement. These components make up the state machine’s data, initialization code, execution code, and export definitions. A write statement may appear before a machine is fully defined. This allows one to write out the data first then later define the machine where it is used. See the fbreak Example.

In the creation of any parser it is not uncommon to require the collection of the data being parsed. It is always possible to collect data into a growable buffer as the machine moves over it, however the copying of data is a somewhat wasteful use of processor cycles. The most efficient way to collect data from the parser is to set pointers into the input then later reference them. This poses a problem for uses of Ragel where the input data arrives in blocks, such as over a socket or from a file. If a pointer is set in one buffer block but must be used while parsing a following buffer block, some extra consideration to correctness must be made.

The scanner constructions exhibit this problem, requiring the maintenance code described in Generating Scanners. If a longest-match construction has been used somewhere in the machine then it is possible to take advantage of the required prefix maintenance code in the driver program to ensure pointers to the input are always valid. If laying down a pointer one can set ts at the same spot or ahead of it. When data is shifted in between loops the user must also shift the pointer. In this way it is possible to maintain pointers to the input that will always be consistent.

In general, there are two approaches for guaranteeing the consistency of pointers to input data. The first approach is the one just described; lay down a marker from an action, then later ensure that the data the marker points to is preserved ahead of the buffer on the next execute invocation. This approach is good because it allows the parser to decide on the pointer-use boundaries, which can be arbitrarily complex parsing conditions. A downside is that it requires any pointers that are set to be corrected in between execute invocations.

The alternative is to find the pointer-use boundaries before invoking the execute routine, then pass in the data using these boundaries. For example, if the program must perform line-oriented processing, the user can scan backwards from the end of an input block that has just been read in and process only up to the first found newline. On the next input read, the new data is placed after the partially read line and processing continues from the beginning of the line. An example of line-oriented processing is given below.

The ragel program has a number of options for specifying the host language. The host-language options are:

There are three styles of code output to choose from. Code style affects the size and speed of the compiled binary. Changing code style does not require any change to the Ragel program. There are two table-driven formats and a goto driven format.

In addition to choosing a style to emit, there are various levels of action code reuse to choose from. The maximum reuse levels (-T0, -F0 and -G0) ensure that no FSM action code is ever duplicated by encoding each transition’s action list as static data and iterating through the lists on every transition. This will normally result in a smaller binary. The less action reuse options (-T1, -F1 and -G1) will usually produce faster running code by expanding each transition’s action list into a single block of code, eliminating the need to iterate through the lists. This duplicates action code instead of generating the logic necessary for reuse. Consequently the binary will be larger. However, this tradeoff applies to machines with moderate to dense action lists only. If a machine’s transitions frequently have less than two actions then the less reuse options will actually produce both a smaller and a faster running binary due to less action sharing overhead. The best way to choose the appropriate code style for your application is to perform your own tests.

The table-driven FSM represents the state machine as constant static data. There are tables of states, transitions, indices and actions. The current state is stored in a variable. The execution is simply a loop that looks up the current state, looks up the transition to take, executes any actions and moves to the target state. In general, the table-driven FSM can handle any machine, produces a smaller binary and requires a less expensive host language compile, but results in slower running code. Since the table-driven format is the most flexible it is the default code style.

The flat table-driven machine is a table-based machine that is optimized for small alphabets. Where the regular table machine uses the current character as the key in a binary search for the transition to take, the flat table machine uses the current character as an index into an array of transitions. This is faster in general, however is only suitable if the span of possible characters is small.

The goto-driven FSM represents the state machine using goto and switch statements. The execution is a flat code block where the transition to take is computed using switch statements and directly executable binary searches. In general, the goto FSM produces faster code but results in a larger binary and a more expensive host language compile.

The goto-driven format has an additional action reuse level (-G2) that writes actions directly into the state transitioning logic rather than putting all the actions together into a single switch. Generally this produces faster running code because it allows the machine to encode the current state using the processor’s instruction pointer. Again, sparse machines may actually compile to smaller binaries when -G2 is used due to less state and action management overhead. For many parsing applications -G2 is the preferred output format.

Code Output Style Options

Due to limitations of the host languages, not all styles are supported for all host languages. The following table shows what is supported.

It is possible to use Ragel’s machine construction and action embedding operators to specify an entire parser using a single regular expression. In many cases this is the desired way to specify a parser in Ragel. However, in some scenarios the language to parse may be so large that it is difficult to think about it as a single regular expression. It may also shift between distinct parsing strategies, in which case modularization into several coherent blocks of the language may be appropriate.

It may also be the case that patterns that compile to a large number of states must be used in a number of different contexts and referencing them in each context results in a very large state machine. In this case, an ability to reuse parsers would reduce code size.

To address this, distinct regular expressions may be instantiated and linked together by means of a jumping and calling mechanism. This mechanism is analogous to the jumping to and calling of processor instructions. A jump command, given in action code, causes control to be immediately passed to another portion of the machine by way of setting the current state variable. A call command causes the target state of the current transition to be pushed to a state stack before control is transferred. Later on, the original location may be returned to with a return statement. In the following example, distinct state machines are used to handle the parsing of two types of headers.

Calling and jumping should be used carefully as they are operations that take one out of the domain of regular languages. A machine that contains a call or jump statement in one of its actions should be used as an argument to a machine construction operator only with considerable care. Since DFA transitions may actually represent several NFA transitions, a call or jump embedded in one machine can inadvertently terminate another machine that it shares prefixes with. Despite this danger, theses statements have proven useful for tying together sub-parsers of a language into a parser for the full language, especially for the purpose of modularizing code and reducing the number of states when the machine contains frequently recurring patterns.

The section on Embedded Values and Statements describes the jump and call statements that are used to transfer control. These statements make use of two variables that must be declared by the user, stack and top. The stack variable must be an array of integers and top must be a single integer, which will point to the next available space in stack. The Pre-Push and Post-Pop statements which can be used to implement a dynamically resizable array.

This section describes how to reference names in epsilon transitions (State Charts) and action-based control-flow statements such as fgoto. There is a hierarchy of names implied in a Ragel specification. At the top level are the machine instantiations. Beneath the instantiations are labels and references to machine definitions. Beneath those are more labels and references to definitions, and so on.

Any name reference may contain multiple components separated with the :: compound symbol. The search for the first component of a name reference is rooted at the join expression that the epsilon transition or action embedding is contained in. If the name reference is not contained in a join, the search is rooted at the machine definition that the epsilon transition or action embedding is contained in. Each component after the first is searched for beginning at the location in the name tree that the previous reference component refers to.

In the case of action-based references, if the action is embedded more than once, the local search is performed for each embedding and the result is the union of all the searches. If no result is found for action-based references then the search is repeated at the root of the name tree. Any action-based name search may be forced into a strictly global search by prefixing the name reference with ::.

The final component of the name reference must resolve to a unique entry point. If a name is unique in the entire name tree it can be referenced as is. If it is not unique it can be specified by qualifying it with names above it in the name tree. However, it can always be renamed.

Scanners are very much intertwined with regular-languages and their corresponding processors. For this reason Ragel supports the definition of scanners. The generated code will repeatedly attempt to match patterns from a list, favouring longer patterns over shorter patterns. In the case of equal-length matches, the generated code will favour patterns that appear ahead of others. When a scanner makes a match it executes the user code associated with the match, consumes the input then resumes scanning.

On the surface, Ragel scanners are similar to those defined by Lex. Though there is a key distinguishing feature: 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 can be used to process sub-languages, as well as for tokenizing programming languages. In the following example a scanner is used to tokenize the contents of a header field.

The scanner construction has a purpose similar to the longest-match kleene star operator **. The key difference is that a scanner is able to backtrack to match a previously matched shorter string when the pursuit of a longer string fails. For this reason the scanner construction operator is not a pure state machine construction operator. It relies on several variables that enable it to backtrack and make pointers to the matched input text available to the user. For this reason scanners must be immediately instantiated. They cannot be defined inline or referenced by another expression. Scanners must be jumped to or called.

Scanners rely on the ts, te and act variables to be present so that they can backtrack and make pointers to the matched text available to the user. If input is processed using multiple calls to the execute code then the user must ensure that when a token is only partially matched that the prefix is preserved on the subsequent invocation of the execute code.

The ts variable must be defined as a pointer to the input data. It is used for recording where the current token match begins. This variable may be used in action code for retrieving the text of the current match. Ragel ensures that in between tokens and outside of the longest-match machines that this pointer is set to null. In between calls to the execute code the user must check if ts is set and if so, ensure that the data it points to is preserved ahead of the next buffer block. This is described in more detail below.

The te variable must also be defined as a pointer to the input data. It is used for recording where a match ends and where scanning of the next token should begin. This can also be used in action code for retrieving the text of the current match.

The act variable must be defined as an integer type. It is used for recording the identity of the last pattern matched when the scanner must go past a matched pattern in an attempt to make a longer match. If the longer match fails it may need to consult the act variable. In some cases, use of the act variable can be avoided because the value of the current state is enough information to determine which token to accept, however in other cases this is not enough and so the act variable is used.

When the longest-match operator is in use, the user’s driver code must take on some buffer management functions. The following algorithm gives an overview of the steps that should be taken to properly use the longest-match operator.

The following listing shows the required handling of an input stream in which a token is broken by the input block boundaries. After processing up to and including the “t” of “characters”, the prefix of the string token must be retained and processing should resume at the “e” on the next iteration of the execute code.

If one uses a large input buffer for collecting input then the number of times the shifting must be done will be small. Furthermore, if one takes care not to define tokens that are allowed to be very long and instead processes these items using pure state machines or sub-scanners, then only a small amount of data will ever need to be shifted.

Following an invocation of the execute code there may be a partially matched token (a). The data of the partially matched token must be preserved ahead of the new data on the next invocation (b).

Since scanners attempt to make the longest possible match of input, patterns such as identifiers require one character of lookahead in order to trigger a match. In the case of the last token in the input stream the user must ensure that the eof variable is set so that the final token is flushed out.

The following is an an example scanner processing loop.

In addition to supporting the construction of state machines using regular languages, Ragel provides a way to manually specify state machines using state charts. The comma operator combines machines together without any implied transitions. The user can then manually link machines by specifying epsilon transitions with the -> operator. Epsilon transitions are drawn between the final states of a machine and entry points defined by labels. This makes it possible to build machines using the explicit state-chart method while making minimal changes to the Ragel language.

An interesting feature of Ragel’s state chart construction method is that it can be mixed freely with regular expression constructions. A state chart may be referenced from within a regular expression, or a regular expression may be used in the definition of a state chart transition.

New in Ragel 7 are features for specifying non-deterministic machines. Prior to this, ragel always produced DFAs, so these features represent a departure from the standard runtime model. They allow us to cope with very large state machines, without having to compromise on the language matched, or devise some techniques outside of the ragel language.

The NFA features require that the programmer make available nfa_bp, nfa_len and nfa_count variables. See the section Varibles Used by Ragel

Note that NFA features are non compatible with non-contiguous buffer blocks. It requires being able to set p to some previously stashed value. If the buffer is no longer available, ragel will attempt to backtrack into invalid data.

There are a few strategies for implementing lookahead in Ragel programs. Leaving actions, which are described in Leaving Actions, can be used as a form of lookahead. Ragel also provides the fhold directive which can be used in actions to prevent the machine from advancing over the current character. It is also possible to manually adjust the current character position by shifting it backwards using fexec, however when this is done, care must be taken not to overstep the beginning of the current buffer block. In both the use of fhold and fexec the user must be cautious of combining the resulting machine with another in such a way that the transition on which the current position is adjusted is not combined with a transition from the other machine.

In general Ragel cannot handle recursive structures because the grammar is interpreted as a regular language. However, depending on what needs to be parsed it is sometimes practical to implement the recursive parts using manual coding techniques. This often works in cases where the recursive structures are simple and easy to recognize, such as in the balancing of parentheses.

One approach to parsing recursive structures is to use actions that increment and decrement counters or otherwise recognize the entry to and exit from recursive structures and then jump to the appropriate machine defnition using fcall and fret. Alternatively, semantic conditions can be used to test counter variables.

A more traditional approach is to call a separate parsing function (expressed in the host language) when a recursive structure is entered, then later return when the end is recognized.