Awesome

Most of this document is excepted from Ragel 6.8 document, copyright belongs to the original author Adrian Thurston.

Ragel Cheat Sheet

Ragel compiles executable finite state machines from a high level regular language notation to C, C++, Objective-C, D, Go, Java and Ruby code.

Construction State Machines

A multi-line FSM spec starts with %%{ and ends with }%%. A single-line FSM spec starts with %% and ends at the first newline.

#include <string.h>
#include <stdio.h>
%%{
	machine foo;
	main :=
		( ’foo’ | ’bar’ )
		0 @{ res = 1; };
}%%

%% write data;

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;
}

Machine Definition

<name> = <expression>;

Machine Instantiation

<name> := <expression>;

Ragel Block Lexical Analysis

Basic Machines

• ’hello’ - Concatenation Literal
• "hello" - Identical to the single quoted version
• [hello] - Produces a union of characters
• ’’, "", and [] - Zero Length Machine
• 42 - Numerical Literal
• /simple_regex/ - Regular Expression. This notation also supports the i trailing option. Use it to produce case-insensitive machines, as in /GET/i.
• ’a’ .. ’z’ - Range
• variable_name - – Lookup the machine definition assigned to the variable name given and use an instance of it

builtin_machine

• any - Any character in the alphabet.
• ascii - Ascii characters. 0..127
• extend - Ascii extended characters. This is the range -128..127 for signed alphabets and the range 0..255 for unsigned alphabets.
• alpha - Alphabetic characters. [A-Za-z]
• digit - Digits. [0-9]
• alnum - Alpha numerics. [0-9A-Za-z]
• lower - Lowercase characters. [a-z]
• upper - Uppercase characters. [A-Z]
• xdigit - Hexadecimal digits. [0-9A-Fa-f]
• cntrl - Control characters. 0..31
• graph - Graphical characters. [!-~]
• print - Printable characters. [ -~]
• punct - Punctuation. Graphical characters that are not alphanumerics. [!-/:-@[-‘{-~]
• space - Whitespace. [\t\v\f\n\r ]
• zlen - Zero length string. ""
• empty - Empty set. Matches nothing. ^any

Regular Language Operators

Union

expr | expr

The union operation produces a machine that matches any string in machine one or machine two

Intersection

expr & expr

Intersection produces a machine that matches any string that is in both machine one and machine two

Difference

expr - expr

The difference operation produces a machine that matches strings that are in machine one but are not in machine two

For example: (any - space)*

Strong Difference

expr -- expr

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

Concatenation

expr . expr

Concatenation produces a machine that matches all the strings in machine one followed by all the strings in machine two

Kleene Star

expr*

The machine resulting from the Kleene Star operator will match zero or more repetitions of the machine it is applied to

One Or More Repetition

expr+

Optional expr?

Repetition

• expr {n} – Exactly N copies of expr.
• expr {,n} – Zero to N copies of expr.
• expr {n,} – N or more copies of expr.
• expr {n,m} – N to M copies of expr.

Negation

!expr

Negation produces a machine that matches any string not matched by the given machine. Negation is equivalent to (any* - expr).

Character-Level Negation

^expr

Character-Level Negation is equivalent to (any - expr)

User Actions

Two ways of using action

1.  main := ( lower* >{ printf("action lower"); }) . ' ';
   

2.  action A { printf("action lower"); }
    main := ( lower* >A) . ' ';
    
   

Transition actions

• expr > action Entering Action
• expr @ action Finishing Action
• expr $ action All Transition Action
• expr % action Leaving Actions

State actions

The different classes of states are:

• \> – the start state
• < – any state except the start state
• $ – all states
• % – final states
• @ – any state except final states
• <> – any except start and final (middle)

The different kinds of embeddings are:

• ~ – to-state actions (to)
• \* – from-state actions (from)
• / – EOF actions (eof)
• ! – error actions (err)
• ^ – local error actions (lerr)

To-State Actions

• \>~action >to(name) >to{...} – the start state
• <~action <to(name) <to{...} – any state except the start state
• $~action $to(name) $to{...} – all states
• %~action %to(name) %to{...} – final states
• @~action @to(name) @to{...} – any state except final states
• <>~action <>to(name) <>to{...} – any except start and final (middle)

From-State Actions

• \>*action >from(name) >from{...} – the start state
• <*action <from(name) <from{...} – any state except the start state
• $*action $from(name) $from{...} – all states
• %*action %from(name) %from{...} – final states
• @*action @from(name) @from{...} – any state except final states
• <>*action <>from(name) <>from{...} – any except start and final (middle)

EOF Actions

• \>/action >eof(name) >eof{...} – the start state
• </action <eof(name) <eof{...} – any state except the start state
• $/action $eof(name) $eof{...} – all states
• %/action %eof(name) %eof{...} – final states
• @/action @eof(name) @eof{...} – any state except final states
• <>/action <>eof(name) <>eof{...} – any except start and final (middle)

Global Error Actions

• \>!action >err(name) >err{...} – the start state
• <!action <err(name) <err{...} – any state except the start state
• $!action $err(name) $err{...} – all states
• %!action %err(name) %err{...} – final states
• @!action @err(name) @err{...} – any state except final states
• <>!action <>err(name) <>err{...} – any except start and final (middle)

Local Error Actions

• \>^action >lerr(name) >lerr{...} – the start state
• <^action <lerr(name) <lerr{...} – any state except the start state
• $^action $lerr(name) $lerr{...} – all states
• %^action %lerr(name) %lerr{...} – final states
• @^action @lerr(name) @lerr{...} – any state except final states
• <>^action <>lerr(name) <>lerr{...} – any except start and final (middle)

Values and Statements Available in Code Blocks

Controlling Nondeterminism

Guarded Operators

Entry-Guarded Concatenation

expr :> expr

Finish-Guarded Concatenation

expr :>> expr

Left-Guarded Concatenation

expr <: expr

Longest-Match Kleene Star

expr**

This version of kleene star puts a higher priority on staying in the machine versus wrapping around and starting over.

Operator Precedence

Interface to Host Program

Write

%%{
machine foo;
write data;
}%%

void init(...) {
    ...
    %% write init;
    ...
}

int parse(...) {
    ...
    %% write exec;
    ...
}

Access Statement

access fsm->;

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.

Alphtype Statement

alphtype unsigned char;

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.

Code generation

Debugging

The most effective way to debug Ragel grammar is to generate a transition graph from Ragel file using Ragel and Graphviz.

ragel -Vp a.rl -o a.dot
dot a.dot -Tpng -o a.png

-V: to generate a dot file

-p: use character labels instead of number labels

Get better graphs

If the final graph is too large to be meaningful, the use is able to inspect portions of the parser by naming particular regular expression definition with -S and -M options.

Using machine name:

ragel -Vp -S [machine_name] a.rl -o a.dot

Or using rule name:

ragel -Vp -M [rule_name] a.rl -o a.dot

Misc

• Ragel vim grammar highlight: https://github.com/jneen/ragel.vim
• 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.
• Ragel 6.8 document http://www.colm.net/files/ragel/ragel-guide-6.8.pdf