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