"Fossies" - the Fresh Open Source Software Archive

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

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

    1 %
2 %   Copyright 2001-2009 Adrian Thurston <thurston@complang.org>
3 %
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[
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}
71 by\\
72 \vspace{12pt}
73 {\large Adrian Thurston}\\
74 \end{center}
75 \clearpage
76
77 \pagenumbering{roman}
78
79 %
80 % License page
81 %
83 Ragel version \version, \pubdate\\
85 \vspace{6mm}
86
87 {\bf\it\noindent This document is part of Ragel, and as such, this document is
88 released under the terms of the GNU General Public License as published by the
89 Free Software Foundation; either version 2 of the License, or (at your option)
90 any later version.}
91
92 \vspace{5pt}
93
94 {\bf\it\noindent Ragel is distributed in the hope that it will be useful, but
95 WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
96 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License for more
97 details.}
98
99 \vspace{5pt}
100
101 {\bf\it\noindent You should have received a copy of the GNU General Public
102 License along with Ragel; if not, write to the Free Software Foundation, Inc.,
103 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA}
104
105 %
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
122 Regular expressions are used heavily in practice for the purpose of specifying
123 parsers. They are normally used as black boxes linked together with program
124 logic.  User actions are executed in between invocations of the regular
125 expression engine. Adding actions before a pattern terminates requires patterns
126 to be broken and pasted back together with program logic. The more user actions
127 are needed, the less the advantages of regular expressions are seen.
128
129 Ragel is a software development tool that allows user actions to be
130 embedded into the transitions of a regular expression's corresponding state
131 machine, eliminating the need to switch from the regular expression engine and
132 user code execution environment and back again. As a result, expressions can be
133 maximally continuous.  One is free to specify an entire parser using a single
134 regular expression.  The single-expression model affords concise and elegant
135 descriptions of languages and the generation of very simple, fast and robust
136 code.  Ragel compiles executable finite state machines from a high level regular language
137 notation. Ragel targets C, C++, Objective-C, D, Go, Java and Ruby.
138
139 In addition to building state machines from regular expressions, Ragel allows
140 the programmer to directly specify state machines with state charts. These two
141 notations may be freely combined. There are also facilities for controlling
142 nondeterminism in the resulting machines and building scanners using patterns
143 that themselves have embedded actions. Ragel can produce code that is small and
144 runs very fast. Ragel can handle integer-sized alphabets and can compile very
145 large state machines.
146
147 \section{Motivation}
148
149 When a programmer is faced with the task of producing a parser for a
150 context-free language there are many tools to choose from. It is quite common
151 to generate useful and efficient parsers for programming languages from a
152 formal grammar. It is also quite common for programmers to avoid such tools
153 when making parsers for simple computer languages, such as file formats and
154 communication protocols.  Such languages are often regular and tools for
155 processing the context-free languages are viewed as too heavyweight for the
156 purpose of parsing regular languages. The extra run-time effort required for
157 supporting the recursive nature of context-free languages is wasted.
158
159 When we turn to the regular expression-based parsing tools, such as Lex, Re2C,
160 and scripting languages such as Sed, Awk and Perl we find that they are split
161 into two levels: a regular expression matching engine and some kind of program
162 logic for linking patterns together.  For example, a Lex program is composed of
163 sets of regular expressions. The implied program logic repeatedly attempts to
164 match a pattern in the current set. When a match is found the associated user
165 code executed. It requires the user to consider a language as a sequence of
166 independent tokens. Scripting languages and regular expression libraries allow
167 one to link patterns together using arbitrary program code.  This is very
168 flexible and powerful, however we can be more concise and clear if we avoid
169 gluing together regular expressions with if statements and while loops.
170
171 This model of execution, where the runtime alternates between regular
172 expression matching and user code exectution places restrictions on when
173 action code may be executed. Since action code can only be associated with
174 complete patterns, any action code that must be executed before an entire
175 pattern is matched requires that the pattern be broken into smaller units.
176 Instead of being forced to disrupt the regular expression syntax and write
177 smaller expressions, it is desirable to retain a single expression and embed
178 code for performing actions directly into the transitions that move over the
179 characters. After all, capable programmers are astutely aware of the machinery
180 underlying their programs, so why not provide them with access to that
181 machinery? To achieve this we require an action execution model for associating
182 code with the sub-expressions of a regular expression in a way that does not
183 disrupt its syntax.
184
185 The primary goal of Ragel is to provide developers with an ability to embed
186 actions into the transitions and states of a regular expression's state machine
187 in support of the definition of entire parsers or large sections of parsers
188 using a single regular expression.  From the regular expression we gain a clear
189 and concise statement of our language. From the state machine we obtain a very
190 fast and robust executable that lends itself to many kinds of analysis and
191 visualization.
192
193 \section{Overview}
194
195 Ragel is a language for specifying state machines. The Ragel program is a
196 compiler that assembles a state machine definition to executable code.  Ragel
197 is based on the principle that any regular language can be converted to a
198 deterministic finite state automaton. Since every regular language has a state
199 machine representation and vice versa, the terms regular language and state
200 machine (or just machine) will be used interchangeably in this document.
201
202 Ragel outputs machines to C, C++, Objective-C, D, Go, Java or Ruby code. The output is
203 designed to be generic and is not bound to any particular input or processing
204 method. A Ragel machine expects to have data passed to it in buffer blocks.
205 When there is no more input, the machine can be queried for acceptance.  In
206 this way, a Ragel machine can be used to simply recognize a regular language
207 like a regular expression library. By embedding code into the regular language,
208 a Ragel machine can also be used to parse input.
209
210 The Ragel language has many operators for constructing and manipulating
211 machines. Machines are built up from smaller machines, to bigger ones, to the
212 final machine representing the language that needs to be recognized or parsed.
213
214 The core state machine construction operators are those found in most theory
215 of computation textbooks. They date back to the 1950s and are widely studied.
216 They are based on set operations and permit one to think of languages as a set
217 of strings. They are Union, Intersection, Difference, Concatenation and Kleene
218 Star. Put together, these operators make up what most people know as regular
219 expressions. Ragel also provides a scanner construction operator
220 and provides operators for explicitly constructing machines
221 using a state chart method. In the state chart method, one joins machines
222 together without any implied transitions and then explicitly specifies where
223 epsilon transitions should be drawn.
224
225 The state machine manipulation operators are specific to Ragel. They allow the
226 programmer to access the states and transitions of regular language's
227 corresponding machine. There are two uses of the manipulation operators. The
228 first and primary use is to embed code into transitions and states, allowing
229 the programmer to specify the actions of the state machine.
230
231 Ragel attempts to make the action embedding facility as intuitive as possible.
232 To do so, a number of issues need to be addressed.  For example, when making a
233 nondeterministic specification into a DFA using machines that have embedded
234 actions, new transitions are often made that have the combined actions of
235 several source transitions. Ragel ensures that multiple actions associated with
236 a single transition are ordered consistently with respect to the order of
237 reference and the natural ordering implied by the construction operators.
238
239 The second use of the manipulation operators is to assign priorities to
240 transitions. Priorities provide a convenient way of controlling any
241 nondeterminism introduced by the construction operators. Suppose two
242 transitions leave from the same state and go to distinct target states on the
243 same character. If these transitions are assigned conflicting priorities, then
244 during the determinization process the transition with the higher priority will
245 take precedence over the transition with the lower priority. The lower priority
246 transition gets abandoned. The transitions would otherwise be combined into a new
247 transition that goes to a new state that is a combination of the original
248 target states. Priorities are often required for segmenting machines. The most
249 common uses of priorities have been encoded into a set of simple operators
250 that should be used instead of priority embeddings whenever possible.
251
252 For the purposes of embedding, Ragel divides transitions and states into
253 different classes. There are four operators for embedding actions and
254 priorities into the transitions of a state machine. It is possible to embed
255 into entering transitions, finishing transitions, all transitions and leaving
256 transitions. The embedding into leaving transitions is a special case.
257 These transition embeddings get stored in the final states of a machine.  They
258 are transferred to any transitions that are made going out of the machine by
259 future concatenation or kleene star operations.
260
261 There are several more operators for embedding actions into states. Like the
262 transition embeddings, there are various different classes of states that the
263 embedding operators access. For example, one can access start states, final
264 states or all states, among others. Unlike the transition embeddings, there are
265 several different types of state action embeddings. These are executed at
266 various different times during the processing of input. It is possible to embed
267 actions that are exectued on transitions into a state, on transitions out of a
268 state, on transitions taken on the error event, or on transitions taken on the
269 EOF event.
270
271 Within actions, it is possible to influence the behaviour of the state machine.
272 The user can write action code that jumps or calls to another portion of the
273 machine, changes the current character being processed, or breaks out of the
274 processing loop. With the state machine calling feature Ragel can be used to
275 parse languages that are not regular. For example, one can parse balanced
276 parentheses by calling into a parser when an open parenthesis character is seen
277 and returning to the state on the top of the stack when the corresponding
278 closing parenthesis character is seen. More complicated context-free languages
279 such as expressions in C are out of the scope of Ragel.
280
281 Ragel also provides a scanner construction operator that can be used to build
282 scanners much the same way that Lex is used. The Ragel generated code, which
283 relies on user-defined variables for backtracking, repeatedly tries to match
284 patterns to the input, favouring longer patterns over shorter ones and patterns
285 that appear ahead of others when the lengths of the possible matches are
286 identical. When a pattern is matched the associated action is executed.
287
288 The key distinguishing feature between scanners in Ragel and scanners in Lex is
289 that Ragel patterns may be arbitrary Ragel expressions and can therefore
290 contain embedded code. With a Ragel-based scanner the user need not wait until
291 the end of a pattern before user code can be executed.
292
293 Scanners do take Ragel out of the domain of pure state machines and require the
294 user to maintain the backtracking related variables.  However, scanners
295 integrate well with regular state machine instantiations. They can be called to
296 or jumped to only when needed, or they can be called out of or jumped out of
297 when a simpler, pure state machine model is appropriate.
298
299 Two types of output code style are available. Ragel can produce a table-driven
300 machine or a directly executable machine. The directly executable machine is
301 much faster than the table-driven. On the other hand, the table-driven machine
302 is more compact and less demanding on the host language compiler. It is better
303 suited to compiling large state machines.
304
305 \section{Related Work}
306
307 Lex is perhaps the best-known tool for constructing parsers from regular
308 expressions. In the Lex processing model, generated code attempts to match one
309 of the user's regular expression patterns, favouring longer matches over
310 shorter ones. Once a match is made it then executes the code associated with
311 the pattern and consumes the matching string.  This process is repeated until
312 the input is fully consumed.
313
314 Through the use of start conditions, related sets of patterns may be defined.
315 The active set may be changed at any time.  This allows the user to define
316 different lexical regions. It also allows the user to link patterns together by
317 requiring that some patterns come before others.  This is quite like a
318 concatenation operation. However, use of Lex for languages that require a
319 considerable amount of pattern concatenation is inappropriate. In such cases a
320 Lex program deteriorates into a manually specified state machine, where start
321 conditions define the states and pattern actions define the transitions.  Lex
322 is therefore best suited to parsing tasks where the language to be parsed can
323 be described in terms of regions of tokens.
324
325 Lex is useful in many scenarios and has undoubtedly stood the test of time.
326 There are, however, several drawbacks to using Lex.  Lex can impose too much
327 overhead for parsing applications where buffering is not required because all
328 the characters are available in a single string.  In these cases there is
329 structure to the language to be parsed and a parser specification tool can
330 help, but employing a heavyweight processing loop that imposes a stream
331 pull'' model and dynamic input buffer allocation is inappropriate.  An
332 example of this kind of scenario is the conversion of floating point numbers
333 contained in a string to their corresponding numerical values.
334
335 Another drawback is the very issue that Ragel attempts to solve.
336 It is not possible to execute a user action while
337 matching a character contained inside a pattern. For example, if scanning a
338 programming language and string literals can contain newlines which must be
339 counted, a Lex user must break up a string literal pattern so as to associate
340 an action with newlines. This forces the definition of a new start condition.
341 Alternatively the user can reprocess the text of the matched string literal to
342 count newlines.
343
344 \begin{comment}
345 How 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
394 The Re2C program defines an input processing model similar to that of Lex.
395 Re2C focuses on making generated state machines run very fast and
396 integrate easily into any program, free of dependencies.  Re2C generates
397 directly executable code and is able to claim that generated parsers run nearly
398 as fast as their hand-coded equivalents.  This is very important for user
399 adoption, as programmers are reluctant to use a tool when a faster alternative
400 exists.  A consideration to ease of use is also important because developers
401 need the freedom to integrate the generated code as they see fit.
402
403 Many scripting languages provide ways of composing parsers by linking regular
404 expressions using program logic. For example, Sed and Awk are two established
405 Unix scripting tools that allow the programmer to exploit regular expressions
406 for the purpose of locating and extracting text of interest. High-level
407 programming languages such as Perl, Python, PHP and Ruby all provide regular
408 expression libraries that allow the user to combine regular expressions with
409 arbitrary code.
410
411 In addition to supporting the linking of regular expressions with arbitrary
412 program logic, the Perl programming language permits the embedding of code into
413 regular expressions. Perl embeddings do not translate into the embedding of
414 code into deterministic state machines. Perl regular expressions are in fact
415 not fully compiled to deterministic machines when embedded code is involved.
416 They are instead interpreted and involve backtracking. This is shown by the
417 following Perl program. When it is fed the input \verb|abcd| the interpretor
418 attempts to match the first alternative, printing \verb|a1 b1|.  When this
419 possibility fails it backtracks and tries the second possibility, printing
420 \verb|a2 b2|, at which point it succeeds.
421
422 \begin{inline_code}
423 \begin{verbatim}
424 print "YES\n" if ( <STDIN> =~
425         /( a (?{ print "a1 "; }) b (?{ print "b1 "; }) cX ) |
426          ( a (?{ print "a2 "; }) b (?{ print "b2 "; }) cd )/x )
427 \end{verbatim}
428 \end{inline_code}
429 \verbspace
430
431 In Ragel there is no regular expression interpretor. Aside from the scanner
432 operator, all Ragel expressions are made into deterministic machines and the
433 run time simply moves from state to state as it consumes input. An equivalent
434 parser expressed in Ragel would attempt both of the alternatives concurrently,
435 printing \verb|a1 a2 b1 b2|.
436
437 \section{Development Status}
438
439 Ragel is a relatively new tool and is under continuous development. As a rough
440 release guide, minor revision number changes are for implementation
441 improvements and feature additions. Major revision number changes are for
442 implementation and language changes that do not preserve backwards
443 compatibility. Though in the past this has not always held true: changes that
444 break code have crept into minor version number changes. Typically, the
445 documentation lags behind the development in the interest of documenting only
446 the lasting features. The latest changes are always documented in the ChangeLog
447 file.
448
449 \chapter{Constructing State Machines}
450
451 \section{Ragel State Machine Specifications}
452
453 A Ragel input file consists of a program in the host language that contains embedded machine
454 specifications.  Ragel normally passes input straight to output.  When it sees
455 a machine specification it stops to read the Ragel statements and possibly generate
456 code in place of the specification.
457 Afterwards it continues to pass input through.  There
458 can be any number of FSM specifications in an input file. A multi-line FSM spec
459 starts with \verb|%%{| and ends with \verb|}%%|. A single-line FSM spec starts
460 with \verb|%%| and ends at the first newline.
461
462 While Ragel is looking for FSM specifications it does basic lexical analysis on
463 the surrounding input. It interprets literal strings and comments so a
464 \verb|%%| sequence in either of those will not trigger the parsing of an FSM
465 specification. Ragel does not pass the input through any preprocessor nor does it
466 interpret preprocessor directives itself so includes, defines and ifdef logic
467 cannot be used to alter the parse of a Ragel input file. It is therefore not
468 possible to use an \verb|#if 0| directive to comment out a machine as is
469 commonly done in C code. As an alternative, a machine can be prevented from
470 causing any generated output by commenting out write statements.
471
472 In Figure \ref{cmd-line-parsing}, a multi-line specification is used to define the
473 machine and single line specifications are used to trigger the writing of the machine
474 data and execution code.
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}
494 int main( int argc, char **argv )
495 {
496     int cs, res = 0;
497     if ( argc > 1 ) {
498         char *p = argv[1];
499         char *pe = p + strlen(p) + 1;
500         %% write init;
501         %% write exec;
502     }
503     printf("result = %i\n", res );
504     return 0;
505 }
506 \end{verbatim}
507 \end{multicols}
508 \caption{Parsing a command line argument.}
509 \label{cmd-line-parsing}
510 \end{figure}
511
512 \subsection{Naming Ragel Blocks}
513
514 \begin{verbatim}
515 machine fsm_name;
516 \end{verbatim}
517 \verbspace
518
519 The \verb|machine| statement gives the name of the FSM. If present in a
520 specification, this statement must appear first. If a machine specification
521 does not have a name then Ragel uses the previous specification name.  If no
522 previous specification name exists then this is an error. Because FSM
523 specifications persist in memory, a machine's statements can be spread across
524 multiple machine specifications.  This allows one to break up a machine across
525 several files or draw in statements that are common to multiple machines using
526 the \verb|include| statement.
527
528 \subsection{Machine Definition}
529 \label{definition}
530
531 \begin{verbatim}
532 <name> = <expression>;
533 \end{verbatim}
534 \verbspace
535
536 The machine definition statement associates an FSM expression with a name. Machine
537 expressions assigned to names can later be referenced in other expressions. A
538 definition statement on its own does not cause any states to be generated. It is simply a
539 description of a machine to be used later. States are generated only when a definition is
540 instantiated, which happens when a definition is referenced in an instantiated
541 expression.
542
543 \subsection{Machine Instantiation}
544 \label{instantiation}
545
546 \begin{verbatim}
547 <name> := <expression>;
548 \end{verbatim}
549 \verbspace
550
551 The machine instantiation statement generates a set of states representing an
552 expression. Each instantiation generates a distinct set of states.  The starting
553 state of the instantiation is written in the data section of the generated code
554 using the instantiation name.  If a machine named
555 \verb|main| is instantiated, its start state is used as the
556 specification's start state and is assigned to the \verb|cs| variable by the
557 \verb|write init| command. If no \verb|main| machine is given, the start state
558 of the last machine instantiation to appear is used as the specification's
559 start state.
560
561 From outside the execution loop, control may be passed to any machine by
562 assigning the entry point to the \verb|cs| variable.  From inside the execution
563 loop, control may be passed to any machine instantiation using \verb|fcall|,
564 \verb|fgoto| or \verb|fnext| statements.
565
566 \subsection{Including Ragel Code}
567
568 \begin{verbatim}
569 include FsmName "inputfile.rl";
570 \end{verbatim}
571 \verbspace
572
573 The \verb|include| statement can be used to draw in the statements of another FSM
574 specification. Both the name and input file are optional, however at least one
575 must be given. Without an FSM name, the given input file is searched for an FSM
576 of the same name as the current specification. Without an input file the
577 current file is searched for a machine of the given name. If both are present,
578 the given input file is searched for a machine of the given name.
579
580 Ragel searches for included files from the location of the current file.
581 Additional directories can be added to the search path using the \verb|-I|
582 option.
583
584 \subsection{Importing Definitions}
585 \label{import}
586
587 \begin{verbatim}
588 import "inputfile.h";
589 \end{verbatim}
590 \verbspace
591
592 The \verb|import| statement scrapes a file for sequences of tokens that match
593 the following forms. Ragel treats these forms as state machine definitions.
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
603 If the input file is a Ragel program then tokens inside any Ragel
604 specifications are ignored. See Section \ref{export} for a description of
605 exporting machine definitions.
606
607 Ragel searches for imported files from the location of the current file.
608 Additional directories can be added to the search path using the \verb|-I|
609 option.
610
611 \section{Lexical Analysis of a Ragel Block}
612 \label{lexing}
613
614 Within 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
621 delimiters of literal strings. Within them, the following escape sequences
622 are interpreted:
623
624 \verb|    \0 \a \b \t \n \v \f \r|
625
626 A backslash at the end of a line joins the following line onto the current. A
627 backslash preceding any other character removes special meaning. This applies
628 to terminating characters and to special characters in regular expression
629 literals. As an exception, regular expression literals do not support escape
630 sequences as the operands of a range within a list. See the bullet on regular
631 expressions in Section \ref{basic}.
632
633 \item The symbols \verb|{}| delimit a block of host language code that will be
634 embedded into the machine as an action.  Within the block of host language
635 code, basic lexical analysis of comments and strings is done in order to
636 correctly find the closing brace of the block. With the exception of FSM
637 commands embedded in code blocks, the entire block is preserved as is for
638 identical reproduction in the output code.
639
640 \item The pattern \verb|[+-]?[0-9]+| denotes an integer in decimal format.
641 Integers used for specifying machines may be negative only if the alphabet type
642 is signed. Integers used for specifying priorities may be positive or negative.
643
644 \item The pattern \verb|0x[0-9A-Fa-f]+| denotes an integer in hexadecimal
645 format.
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
675 The basic machines are the base operands of regular language expressions. They
676 are the smallest unit to which machine construction and manipulation operators
677 can be applied.
678
679 \begin{itemize}
680
681 \item \verb|'hello'| -- Concatenation Literal. Produces a machine that matches
682 the sequence of characters in the quoted string. If there are 5 characters
683 there will be 6 states chained together with the characters in the string. See
684 Section \ref{lexing} for information on valid escape sequences.
685
686 % GENERATE: bmconcat
687 % OPT: -p
688 % %%{
689 % machine bmconcat;
690 \begin{comment}
691 \begin{verbatim}
692 main := 'hello';
693 \end{verbatim}
694 \end{comment}
695 % }%%
696 % END GENERATE
697
698 \begin{center}
699 \includegraphics[scale=0.55]{bmconcat}
700 \end{center}
701
702 It is possible
703 to make a concatenation literal case-insensitive by appending an \verb|i| to
704 the string, for example \verb|'cmd'i|.
705
706 \item \verb|"hello"| -- Identical to the single quoted version.
707
708 \item \verb|[hello]| -- Or Expression. Produces a union of characters.  There
709 will be two states with a transition for each unique character between the two states.
710 The \verb|[]| delimiters behave like the quotes of a literal string. For example,
711 \verb|[ \t]| means tab or space. The \verb|or| expression supports character ranges
712 with the \verb|-| symbol as a separator. The meaning of the union can be negated
713 using an initial \verb|^| character as in standard regular expressions.
714 See Section \ref{lexing} for information on valid escape sequences
715 in \verb|or| expressions.
716
717 % GENERATE: bmor
718 % OPT: -p
719 % %%{
720 % machine bmor;
721 \begin{comment}
722 \begin{verbatim}
723 main := [hello];
724 \end{verbatim}
725 \end{comment}
726 % }%%
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
734 that matches the zero length string. Zero length machines have one state that is both
735 a start state and a final state.
736
737 % GENERATE: bmnull
738 % OPT: -p
739 % %%{
740 % machine bmnull;
741 \begin{comment}
742 \begin{verbatim}
743 main := '';
744 \end{verbatim}
745 \end{comment}
746 % }%%
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
755 transition on the given number. The number may be in decimal or hexadecimal
756 format and should be in the range allowed by the alphabet type. The minimum and
757 maximum values permitted are defined by the host machine that Ragel is compiled
758 on. For example, numbers in a \verb|short| alphabet on an i386 machine should
759 be in the range \verb|-32768| to \verb|32767|.
760
761 % GENERATE: bmnum
762 % %%{
763 % machine bmnum;
764 \begin{comment}
765 \begin{verbatim}
766 main := 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
777 parsed as a series of expressions that are concatenated together. Each
778 concatenated expression
779 may be a literal character, the any'' character specified by the \verb|.|
780 symbol, or a union of characters specified by the \verb|[]| delimiters. If the
781 first character of a union is \verb|^| then it matches any character not in the
782 list. Within a union, a range of characters can be given by separating the first
783 and last characters of the range with the \verb|-| symbol. Each
784 concatenated machine may have repetition specified by following it with the
785 \verb|*| symbol. The standard escape sequences described in Section
786 \ref{lexing} are supported everywhere in regular expressions except as the
787 operands of a range within in a list. This notation also supports the \verb|i|
788 trailing option. Use it to produce case-insensitive machines, as in \verb|/GET/i|.
789
790 Ragel does not support very complex regular expressions because the desired
791 results can always be achieved using the more general machine construction
792 operators listed in Section \ref{machconst}. The following diagram shows the
793 result of compiling \verb|/ab*[c-z].*[123]/|. \verb|DEF| represents the default
794 transition, which is taken if no other transition can be taken.
795
796
797 % GENERATE: bmregex
798 % OPT: -p
799 % %%{
800 % machine bmregex;
801 \begin{comment}
802 \begin{verbatim}
803 main := /ab*[c-z].*[123]/;
804 \end{verbatim}
805 \end{comment}
806 % }%%
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
814 characters in the specified range.  Allowable upper and lower bounds of the
815 range are concatenation literals of length one and numerical literals.  For
816 example, \verb|0x10..0x20|, \verb|0..63|, and \verb|'a'..'z'| are valid ranges.
817 The bounds should be in the range allowed by the alphabet type.
818
819 % GENERATE: bmrange
820 % OPT: -p
821 % %%{
822 % machine bmrange;
823 \begin{comment}
824 \begin{verbatim}
825 main := 'a' .. 'z';
826 \end{verbatim}
827 \end{comment}
828 % }%%
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
837 variable name given and use an instance of it. See Section \ref{definition} for
838 an important note on what it means to reference a variable name.
839
840 \item \verb|builtin_machine| -- There are several built-in machines available
841 for use. They are all two state machines for the purpose of matching common
842 classes of characters. They are:
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
852 alphabets.
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}
885 The following table shows operator precedence from lowest to highest. Operators
886 in the same precedence group are evaluated from left to right.
887
888 \verbspace
889 \begin{tabular}{|c|c|c|}
890 \hline
891 1&\verb| , |&Join\\
892 \hline
893 2&\verb/ | & - --/&Union, Intersection and Subtraction\\
894 \hline
895 3&\verb| . <: :> :>> |&Concatenation\\
896 \hline
897 4&\verb| : |&Label\\
898 \hline
899 5&\verb| -> |&Epsilon Transition\\
900 \hline
901 &\verb| >  @  $% |&Transitions Actions and Priorities\\ 902 \cline{2-3} 903 &\verb| >/$/  %/  </  @/  <>/ |&EOF Actions\\
904 \cline{2-3}
905 6&\verb| >!  $! %! <! @! <>! |&Global Error Actions\\ 906 \cline{2-3} 907 &\verb| >^$^  %^  <^  @^  <>^ |&Local Error Actions\\
908 \cline{2-3}
909 &\verb| >~  $~ %~ <~ @~ <>~ |&To-State Actions\\ 910 \cline{2-3} 911 &\verb| >*$*  %*  <*  @*  <>* |&From-State Action\\
912 \hline
913 7&\verb| * ** ? + {n} {,n} {n,} {n,m} |&Repetition\\
914 \hline
915 8&\verb| ! ^ |&Negation and Character-Level Negation\\
916 \hline
917 9&\verb| ( <expr> ) |&Grouping\\
918 \hline
919 \end{tabular}
920
921 \section{Regular Language Operators}
922 \label{machconst}
923
924 When using Ragel it is helpful to have a sense of how it constructs machines.
925 The determinization process can produce results that seem unusual to someone
926 not familiar with the NFA to DFA conversion algorithm. In this section we
927 describe Ragel's state machine operators. Though the operators are defined
928 using epsilon transitions, it should be noted that this is for discussion only.
929 The epsilon transitions described in this section do not persist, but are
930 immediately removed by the determinization process which is executed at every
931 operation. Ragel does not make use of any nondeterministic intermediate state
932 machines.
933
934 To create an epsilon transition between two states \verb|x| and \verb|y| is to
935 copy all of the properties of \verb|y| into \verb|x|. This involves drawing in
936 all of \verb|y|'s to-state actions, EOF actions, etc., in addition to its
937 transitions. If \verb|x| and \verb|y| both have a transition out on the same
938 character, then the transitions must be combined.  During transition
939 combination a new transition is made that goes to a new state that is the
940 combination of both target states. The new combination state is created using
941 the same epsilon transition method.  The new state has an epsilon transition
942 drawn to all the states that compose it. Since the creation of new epsilon
943 transitions may be triggered every time an epsilon transition is drawn, the
944 process of drawing epsilon transitions is repeated until there are no more
945 epsilon transitions to be made.
946
947 A very common error that is made when using Ragel is to make machines that do
948 too much. That is, to create machines that have unintentional
949 nondetermistic properties. This usually results from being unaware of the common strings
950 between machines that are combined together using the regular language
951 operators. This can involve never leaving a machine, causing its actions to be
952 propagated through all the following states. Or it can involve an alternation
953 where both branches are unintentionally taken simultaneously.
954
955 This problem forces one to think hard about the language that needs to be
956 matched. To guard against this kind of problem one must ensure that the machine
957 specification is divided up using boundaries that do not allow ambiguities from
958 one portion of the machine to the next. See Chapter
959 \ref{controlling-nondeterminism} for more on this problem and how to solve it.
960
961 The Graphviz tool is an immense help when debugging improperly compiled
962 machines or otherwise learning how to use Ragel. Graphviz Dot files can be
963 generated from Ragel programs using the \verb|-V| option. See Section
965
966
967 \subsection{Union}
968
969 \verb/expr | expr/
970 \verbspace
971
972 The union operation produces a machine that matches any string in machine one
973 or machine two. The operation first creates a new start state. Epsilon
974 transitions are drawn from the new start state to the start states of both
975 input machines.  The resulting machine has a final state set equivalent to the
976 union of the final state sets of both input machines. In this operation, there
977 is the opportunity for nondeterminism among both branches. If there are
978 strings, or prefixes of strings that are matched by both machines then the new
979 machine will follow both parts of the alternation at once. The union operation is
980 shown below.
981
982 \graphspace
983 \begin{center}
984 \includegraphics{opor}
985 \end{center}
986 \graphspace
987
988 The following example demonstrates the union of three machines representing
989 common 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
998 main := '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
1014 Intersection produces a machine that matches any
1015 string that is in both machine one and machine two. To achieve intersection, a
1016 union is performed on the two machines. After the result has been made
1017 deterministic, any final state that is not a combination of final states from
1018 both machines has its final state status revoked. To complete the operation,
1019 paths that do not lead to a final state are pruned from the machine. Therefore,
1020 if there are any such paths in either of the expressions they will be removed
1021 by the intersection operator.  Intersection can be used to require that two
1022 independent patterns be simultaneously satisfied as in the following example.
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.
1032 main :=
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
1050 The difference operation produces a machine that matches
1051 strings that are in machine one but are not in machine two. To achieve subtraction,
1052 a union is performed on the two machines. After the result has been made
1053 deterministic, any final state that came from machine two or is a combination
1054 of states involving a final state from machine two has its final state status
1055 revoked. As with intersection, the operation is completed by pruning any path
1056 that does not lead to a final state.  The following example demonstrates the
1057 use of subtraction to exclude specific cases from a set.
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.
1068 main := /[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
1087 Strong difference produces a machine that matches any string of the first
1088 machine that does not have any string of the second machine as a substring. In
1089 the following example, strong subtraction is used to excluded \verb|CRLF| from
1090 a sequence. In the corresponding visualization, the label \verb|DEF| is short
1091 for default. The default transition is taken if no other transition can be
1092 taken.
1093
1094 % GENERATE: exstrongsubtr
1095 % OPT: -p
1096 % %%{
1097 % machine exstrongsubtr;
1098 \begin{inline_code}
1099 \begin{verbatim}
1100 crlf = '\r\n';
1101 main := [a-z]+ ':' ( any* -- crlf ) crlf;
1102 \end{verbatim}
1103 \end{inline_code}
1104 % }%%
1105 % END GENERATE
1106
1107 \graphspace
1108 \begin{center}
1109 \includegraphics[scale=0.55]{exstrongsubtr}
1110 \end{center}
1111 \graphspace
1112
1113 This operator is equivalent to the following.
1114
1115 \verbspace
1116 \begin{verbatim}
1117 expr - ( any* expr any* )
1118 \end{verbatim}
1119
1120 \subsection{Concatenation}
1121
1122 \verb|expr . expr|
1123 \verbspace
1124
1125 Concatenation produces a machine that matches all the strings in machine one followed by all
1126 the strings in machine two.  Concatenation draws epsilon transitions from the
1127 final states of the first machine to the start state of the second machine. The
1128 final states of the first machine lose their final state status, unless the
1129 start state of the second machine is final as well.
1130 Concatenation is the default operator. Two machines next to each other with no
1131 operator between them results in concatenation.
1132
1133 \graphspace
1134 \begin{center}
1135 \includegraphics{opconcat}
1136 \end{center}
1137 \graphspace
1138
1139 The opportunity for nondeterministic behaviour results from the possibility of
1140 the final states of the first machine accepting a string that is also accepted
1141 by the start state of the second machine.
1142 The most common scenario in which this happens is the
1143 concatenation of a machine that repeats some pattern with a machine that gives
1144 a terminating string, but the repetition machine does not exclude the
1145 terminating string. The example in Section \ref{strong_difference}
1146 guards against this. Another example is the expression \verb|("'" any* "'")|.
1147 When executed the thread of control will
1148 never leave the \verb|any*| machine.  This is a problem especially if actions
1149 are embedded to process the characters of the \verb|any*| component.
1150
1151 In the following example, the first machine is always active due to the
1152 nondeterministic nature of concatenation. This particular nondeterminism is intended
1153 however because we wish to permit EOF strings before the end of the input.
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.
1162 main := /[^\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
1175 ambiguity involving concatenation and subtraction. Because concatenation is the
1176 default operator for two
1177 adjacent machines there is an ambiguity between subtraction of
1178 a positive numerical literal and concatenation of a negative numerical literal.
1179 For example, \verb|(x-7)| could be interpreted as \verb|(x . -7)| or
1180 \verb|(x - 7)|. In the Ragel language, the subtraction operator always takes precedence
1181 over concatenation of a negative literal. We adhere to the rule that the default
1182 concatenation operator takes effect only when there are no other operators between
1183 two machines. Beware of writing machines such as \verb|(any -1)| when what is
1184 desired is a concatenation of \verb|any| and \verb|-1|. Instead write
1185 \verb|(any . -1)| or \verb|(any (-1))|. If in doubt of the meaning of your program do not
1186 rely on the default concatenation operator; always use the \verb|.| symbol.
1187
1188
1189 \subsection{Kleene Star}
1190
1191 \verb|expr*|
1192 \verbspace
1193
1194 The machine resulting from the Kleene Star operator will match zero or more
1195 repetitions of the machine it is applied to.
1196 It creates a new start state and an additional final
1197 state.  Epsilon transitions are drawn between the new start state and the old start
1198 state, between the new start state and the new final state, and
1199 between the final states of the machine and the new start state.  After the
1200 machine is made deterministic the effect is of the final states getting all the
1201 transitions of the start state.
1202
1203 \graphspace
1204 \begin{center}
1205 \includegraphics{opstar}
1206 \end{center}
1207 \graphspace
1208
1209 The possibility for nondeterministic behaviour arises if the final states have
1210 transitions on any of the same characters as the start state.  This is common
1211 when applying kleene star to an alternation of tokens. Like the other problems
1212 arising from nondeterministic behavior, this is discussed in more detail in Chapter
1213 \ref{controlling-nondeterminism}. This particular problem can also be solved
1214 by using the longest-match construction discussed in Section
1215 \ref{generating-scanners} on scanners.
1216
1217 In this
1218 example, there is no nondeterminism introduced by the exterior kleene star due to
1219 the newline at the end of the regular expression. Without the newline the
1220 exterior kleene star would be redundant and there would be ambiguity between
1221 repeating the inner range of the regular expression and the entire regular
1222 expression. Though it would not cause a problem in this case, unnecessary
1223 nondeterminism in the kleene star operator often causes undesired results for
1224 new Ragel users and must be guarded against.
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.
1233 main := /[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
1250 This operator produces the concatenation of the machine with the kleene star of
1251 itself. The result will match one or more repetitions of the machine. The plus
1252 operator is equivalent to \verb|(expr . expr*)|.
1253
1254 % GENERATE: explus
1255 % OPT: -p
1256 % %%{
1257 % machine explus;
1258 \begin{inline_code}
1259 \begin{verbatim}
1260 # Match alpha-numeric words.
1261 main := alnum+;
1262 \end{verbatim}
1263 \end{inline_code}
1264 % }%%
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
1278 The {\em optional} operator produces a machine that accepts the machine
1279 given or the zero length string. The optional operator is equivalent to
1280 \verb/(expr | '' )/. In the following example the optional operator is used to
1281 possibly extend a token.
1282
1283 % GENERATE: exoption
1284 % OPT: -p
1285 % %%{
1286 % machine exoption;
1287 \begin{inline_code}
1288 \begin{verbatim}
1289 # Match integers or floats.
1290 main := digit+ ('.' digit+)?;
1291 \end{verbatim}
1292 \end{inline_code}
1293 % }%%
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
1320 Negation produces a machine that matches any string not matched by the given
1321 machine. 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.
1330 main := ! ( 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
1348 Character-level negation produces a machine that matches any single character
1349 not matched by the given machine. Character-Level Negation is equivalent to
1350 \verb|(any - expr)|. It must be applied only to machines that match strings of
1351 length one.
1352
1353 \section{State Machine Minimization}
1354
1355 State machine minimization is the process of finding the minimal equivalent FSM accepting
1356 the language. Minimization reduces the number of states in machines
1357 by merging equivalent states. It does not change the behaviour of the machine
1358 in any way. It will cause some states to be merged into one because they are
1359 functionally equivalent. State minimization is on by default. It can be turned
1360 off with the \verb|-n| option.
1361
1362 The algorithm implemented is similar to Hopcroft's state minimization
1363 algorithm. Hopcroft's algorithm assumes a finite alphabet that can be listed in
1364 memory, whereas Ragel supports arbitrary integer alphabets that cannot be
1365 listed in memory. Though exact analysis is very difficult, Ragel minimization
1366 runs close to $O(n \times log(n))$ and requires $O(n)$ temporary storage where
1367 $n$ is the number of states.
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
1382 Ragel is able to emit compiled state machines in Graphviz's Dot file format.
1383 This is done using the \verb|-V| option.
1384 Graphviz support allows users to perform
1385 incremental visualization of their parsers. User actions are displayed on
1386 transition labels of the graph.
1387
1388 If the final graph is too large to be
1389 meaningful, or even drawn, the user is able to inspect portions of the parser
1390 by naming particular regular expression definitions with the \verb|-S| and
1391 \verb|-M| options to the \verb|ragel| program. Use of Graphviz greatly
1392 improves the Ragel programming experience. It allows users to learn Ragel by
1393 experimentation and also to track down bugs caused by unintended
1394 nondeterminism.
1395
1396 Ragel has another option to help debugging. The \verb|-x| option causes Ragel
1397 to emit the compiled machine in an XML format.
1398
1399 \chapter{User Actions}
1400
1401 Ragel permits the user to embed actions into the transitions of a regular
1402 expression's corresponding state machine. These actions are executed when the
1403 generated code moves over a transition.  Like the regular expression operators,
1404 the action embedding operators are fully compositional. They take a state
1405 machine and an action as input, embed the action and yield a new state machine
1406 that can be used in the construction of other machines. Due to the
1407 compositional nature of embeddings, the user has complete freedom in the
1408 placement of actions.
1409
1410 A machine's transitions are categorized into four classes. The action embedding
1411 operators access the transitions defined by these classes.  The {\em entering
1412 transition} operator \verb|>| isolates the start state, then embeds an action
1413 into all transitions leaving it. The {\em finishing transition} operator
1414 \verb|@| embeds an action into all transitions going into a final state.  The
1415 {\em all transition} operator \verb|$| embeds an action into all transitions of 1416 an expression. The {\em leaving transition} operator \verb|%| provides access 1417 to the yet-unmade transitions moving out of the machine via the final states. 1418 1419 \section{Embedding Actions} 1420 1421 \begin{verbatim} 1422 action ActionName { 1423 /* Code an action here. */ 1424 count += 1; 1425 } 1426 \end{verbatim} 1427 \verbspace 1428 1429 The action statement defines a block of code that can be embedded into an FSM. 1430 Action names can be referenced by the action embedding operators in 1431 expressions. Though actions need not be named in this way (literal blocks 1432 of code can be embedded directly when building machines), defining reusable 1433 blocks of code whenever possible is good practice because it potentially increases the 1434 degree to which the machine can be minimized. 1435 1436 Within an action some Ragel expressions and statements are parsed and 1437 translated. These allow the user to interact with the machine from action code. 1438 See Section \ref{vals} for a complete list of statements and values available 1439 in code blocks. 1440 1441 \subsection{Entering Action} 1442 1443 \verb|expr > action| 1444 \verbspace 1445 1446 The entering action operator embeds an action into all transitions 1447 that enter into the machine from the start state. If the start state is final, 1448 then the action is also embedded into the start state as a leaving action. This 1449 means that if a machine accepts the zero-length string and control passes 1450 through the start state then the entering action is executed. Note 1451 that this can happen on both a following character and on the EOF event. 1452 1453 In some machines the start state has transtions coming in from within the 1454 machine. In these cases the start state is first isolated from the rest of the 1455 machine ensuring that the entering actions are exected once only. 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. 1466 action A {} 1467 main := ( 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 1484 The finishing action operator embeds an action into any transitions that move 1485 the machine into a final state. Further input may move the machine out of the 1486 final state, but keep it in the machine. Therefore finishing actions may be 1487 executed more than once if a machine has any internal transitions out of a 1488 final state. In the following example the final state has no transitions out 1489 and the finishing action is executed only once. 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. 1499 main := ( 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
1517 The all transition operator embeds an action into all transitions of a machine.
1518 The action is executed whenever a transition of the machine is taken. In the
1519 following example, A is executed on every character matched.
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.
1529 main := ( '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 1548 The leaving action operator queues an action for embedding into the transitions 1549 that go out of a machine via a final state. The action is first stored in 1550 the machine's final states and is later transferred to any transitions that are 1551 made going out of the machine by a kleene star or concatenation operation. 1552 1553 If a final state of the machine is still final when compilation is complete 1554 then the leaving action is also embedded as an EOF action. Therefore, leaving 1555 the machine is defined as either leaving on a character or as state machine 1556 acceptance. 1557 1558 This operator allows one to associate an action with the termination of a 1559 sequence, without being concerned about what particular character terminates 1560 the sequence. In the following example, A is executed when leaving the alpha 1561 machine on the newline character. 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. 1572 main := ( 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 1584 In the following example, the \verb|term_word| action could be used to register 1585 the appearance of a word and to clear the buffer that the \verb|lower| action used 1586 to store the text of it. 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} 1598 word = ( [a-z] @lower )+ %term_word; 1599 main := 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 1611 In this final example of the action embedding operators, A is executed upon entering 1612 the alpha machine, B is executed on all transitions of the 1613 alpha machine, C is executed when the alpha machine is exited by moving into the 1614 newline machine and N is executed when the newline machine moves into a final 1615 state. 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. 1629 main := ( 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
1644 The state embedding operators allow one to embed actions into states. Like the
1645 transition embedding operators, there are several different classes of states
1646 that the operators access. The meanings of the symbols are similar to the
1647 meanings of the symbols used for the transition embedding operators. The design
1648 of the state selections was driven by a need to cover the states of an
1649 expression with exactly one error action.
1650
1651 Unlike the transition embedding operators, the state embedding operators are
1652 also distinguished by the different kinds of events that embedded actions can
1653 be associated with. Therefore the state embedding operators have two
1654 components.  The first, which is the first one or two characters, specifies the
1655 class of states that the action will be embedded into. The second component
1656 specifies the type of event the action will be executed on. The symbols of the
1657 second component also have equivalent kewords.
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
1700 To-state actions are executed whenever the state machine moves into the
1701 specified state, either by a natural movement over a transition or by an
1702 action-based transfer of control such as \verb|fgoto|. They are executed after the
1703 in-transition's actions but before the current character is advanced and
1704 tested against the end of the input block. To-state embeddings stay with the
1705 state. They are irrespective of the state's current set of transitions and any
1706 future transitions that may be added in or out of the state.
1707
1708 Note that the setting of the current state variable \verb|cs| outside of the
1709 execute code is not considered by Ragel as moving into a state and consequently
1710 the to-state actions of the new current state are not executed. This includes
1711 the initialization of the current state when the machine begins.  This is
1712 because the entry point into the machine execution code is after the execution
1713 of to-state actions.
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 1725 From-state actions are executed whenever the state machine takes a transition from a 1726 state, either to itself or to some other state. These actions are executed 1727 immediately after the current character is tested against the input block end 1728 marker and before the transition to take is sought based on the current 1729 character. From-state actions are therefore executed even if a transition 1730 cannot be found and the machine moves into the error state. Like to-state 1731 embeddings, from-state embeddings stay with the state. 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
1743 The EOF action embedding operators enable the user to embed actions that are
1744 executed at the end of the input stream. EOF actions are stored in states and
1745 generated in the \verb|write exec| block. They are run when \verb|p == pe == eof|
1746 as the execute block is finishing. EOF actions are free to adjust \verb|p| and
1747 jump to another part of the machine to restart execution.
1748
1749 \subsection{Handling Errors}
1750
1751 In many applications it is useful to be able to react to parsing errors.  The
1752 user may wish to print an error message that depends on the context.  It
1753 may also be desirable to consume input in an attempt to return the input stream
1754 to some known state and resume parsing. To support error handling and recovery,
1755 Ragel provides error action embedding operators. There are two kinds of error
1756 actions: global error actions and local error actions.
1757 Error actions can be used to simply report errors, or by jumping to a machine
1758 instantiation that consumes input, can attempt to recover from errors.
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 1770 Global error actions are stored in the states they are embedded into until 1771 compilation is complete. They are then transferred to the transitions that move 1772 into the error state. These transitions are taken on all input characters that 1773 are not already covered by the state's transitions. If a state with an error 1774 action is not final when compilation is complete, then the action is also 1775 embedded as an EOF action. 1776 1777 Error actions can be used to recover from errors by jumping back into the 1778 machine with \verb|fgoto| and optionally altering \verb|p|. 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
1790 Like global error actions, local error actions are also stored in the states
1791 they are embedded into until a transfer point. The transfer point is different
1792 however. Each local error action embedding is associated with a name. When a
1793 machine definition has been fully constructed, all local error action
1794 embeddings associated with the same name as the machine definition are
1795 transferred to the error transitions. At this time they are also embedded as
1796 EOF actions in the case of non-final states.
1797
1798 Local error actions can be used to specify an action to take when a particular
1799 section of a larger state machine fails to match. A particular machine
1800 definition's thread'' may die and the local error actions executed, however
1801 the machine as a whole may continue to match input.
1802
1803 There are two forms of local error action embeddings. In the first form the
1804 name defaults to the current machine. In the second form the machine name can
1805 be specified.  This is useful when it is more convenient to specify the local
1806 error action in a sub-definition that is used to construct the machine
1807 definition that the local error action is associated with. To embed local
1808 error actions and
1809 explicitly state the machine definition on which the transfer is to happen use
1810 \verb|(name, action)| as the action.
1811
1812 \subsubsection{Example}
1813
1814 The following example uses error actions to report an error and jump to a
1815 machine that consumes the remainder of the line when parsing fails. After
1816 consuming the line, the error recovery machine returns to the main loop.
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}
1826 action cmd_err {
1827     printf( "command error\n" );
1828     fhold; fgoto line;
1829 }
1830 action from_err {
1831     printf( "from error\n" );
1832     fhold; fgoto line;
1833 }
1834 action to_err {
1835     printf( "to error\n" );
1836     fhold; fgoto line;
1837 }
1838
1839 line := [^\n]* '\n' @{ fgoto main; };
1840
1841 main := (
1842     (
1843         'from' @err(cmd_err)
1844             ( ws+ address ws+ date '\n' ) $err(from_err) | 1845 'to' @err(cmd_err) 1846 ( ws+ address '\n' )$err(to_err)
1847     )
1848 )*;
1849 \end{verbatim}
1850 \end{inline_code}
1851 % }%%
1852 % %% write data;
1853 % void f()
1854 % {
1855 %   %% write init;
1856 %   %% write exec;
1857 % }
1858 % END GENERATE
1859
1860
1861
1862 \section{Action Ordering and Duplicates}
1863
1864 When combining expressions that have embedded actions it is often the case that
1865 a number of actions must be executed on a single input character. For example,
1866 following a concatenation the leaving action of the left expression and the
1867 entering action of the right expression will be embedded into one transition.
1868 This requires a method of ordering actions that is intuitive and
1869 predictable for the user, and repeatable for the compiler.
1870
1871 We associate with the embedding of each action a unique timestamp that is
1872 used to order actions that appear together on a single transition in the final
1873 state machine. To accomplish this we recursively traverse the parse tree of
1874 regular expressions and assign timestamps to action embeddings. References to
1875 machine definitions are followed in the traversal. When we visit a
1876 parse tree node we assign timestamps to all {\em entering} action embeddings,
1877 recurse on the parse tree, then assign timestamps to the remaining {\em all},
1878 {\em finishing}, and {\em leaving} embeddings in the order in which they
1879 appear.
1880
1881 By default Ragel does not permit a single action to appear multiple times in an action
1882 list. When the final machine has been created, actions that appear more than
1883 once in a single transition, to-state, from-state or EOF action list have their
1884 duplicates removed.
1885 The first appearance of the action is preserved. This is useful in a number of
1886 scenarios. First, it allows us to union machines with common prefixes without
1887 worrying about the action embeddings in the prefix being duplicated. Second, it
1888 prevents leaving actions from being transferred multiple times. This can
1889 happen when a machine is repeated, then followed with another machine that
1890 begins with a common character. For example:
1891
1892 \verbspace
1893 \begin{verbatim}
1894 word = [a-z]+ %act;
1895 main := word ( '\n' word )* '\n\n';
1896 \end{verbatim}
1897 \verbspace
1898
1899 Note that Ragel does not compare action bodies to determine if they have
1900 identical program text. It simply checks for duplicates using each action
1901 block's unique location in the program.
1902
1903 The 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
1912 accessing 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
1917 value should only be read from. To move to a different place in the machine
1918 from action code use the \verb|fgoto|, \verb|fnext| or \verb|fcall| statements.
1919 Outside of the machine execution code the \verb|cs| variable may be modified.
1920
1921 \item \verb|ftargs| -- An integer value representing the target state. This
1922 value should only be read from. Again, \verb|fgoto|, \verb|fnext| and
1923 \verb|fcall| can be used to move to a specific entry point.
1924
1925 \item \verb|fentry(<label>)| -- Retrieve an integer value representing the
1926 entry point \verb|label|. The integer value returned will be a compile time
1927 constant. This number is suitable for later use in control flow transfer
1928 statements that take an expression. This value should not be compared against
1929 the current state because any given label can have multiple states representing
1930 it. The value returned by \verb|fentry| can be any one of the multiple states that
1931 it represents.
1932 \end{itemize}
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
1939 data in multiple buffer blocks, the \verb|fhold| statement should only be used
1940 once in the set of actions executed on a character.  Multiple calls may result
1941 in backing up over the beginning of the buffer block. The \verb|fhold|
1942 statement does not imply any transfer of control. It is equivalent to the
1943 \verb|p--;| statement.
1944
1945 \item \verb|fexec <expr>;| -- Set the next character to process. This can be
1946 used to backtrack to previous input or advance ahead.
1947 Unlike \verb|fhold|, which can be used
1948 anywhere, \verb|fexec| requires the user to ensure that the target of the
1949 backtrack is in the current buffer block or is known to be somewhere ahead of
1950 it. The machine will continue iterating forward until \verb|pe| is arrived at,
1951 \verb|fbreak| is called or the machine moves into the error state. In actions
1952 embedded into transitions, the \verb|fexec| statement is equivalent to setting
1953 \verb|p| to one position ahead of the next character to process.  If the user
1954 also modifies \verb|pe|, it is possible to change the buffer block entirely.
1955
1956 \item \verb|fgoto <label>;| -- Jump to an entry point defined by
1957 \verb|<label>|.  The \verb|fgoto| statement immediately transfers control to
1958 the destination state.
1959
1960 \item \verb|fgoto *<expr>;| -- Jump to an entry point given by \verb|<expr>|.
1961 The expression must evaluate to an integer value representing a state.
1962
1963 \item \verb|fnext <label>;| -- Set the next state to be the entry point defined
1964 by \verb|label|.  The \verb|fnext| statement does not immediately jump to the
1965 specified state. Any action code following the statement is executed.
1966
1967 \item \verb|fnext *<expr>;| -- Set the next state to be the entry point given
1968 by \verb|<expr>|. The expression must evaluate to an integer value representing
1969 a state.
1970
1971 \item \verb|fcall <label>;| -- Push the target state and jump to the entry
1972 point defined by \verb|<label>|.  The next \verb|fret| will jump to the target
1973 of the transition on which the call was made. Use of \verb|fcall| requires
1974 the declaration of a call stack. An array of integers named \verb|stack| and a
1975 single integer named \verb|top| must be declared. With the \verb|fcall|
1976 construct, control is immediately transferred to the destination state.
1977 See section \ref{modularization} for more information.
1978
1979 \item \verb|fcall *<expr>;| -- Push the current state and jump to the entry
1980 point given by \verb|<expr>|. The expression must evaluate to an integer value
1981 representing a state.
1982
1983 \item \verb|fret;| -- Return to the target state of the transition on which the
1984 last \verb|fcall| was made.  Use of \verb|fret| requires the declaration of a
1985 call stack. Control is immediately transferred to the destination state.
1986
1987 \item \verb|fbreak;| -- Advance \verb|p|, save the target state to \verb|cs|
1988 and immediately break out of the execute loop. This statement is useful
1989 in conjunction with the \verb|noend| write option. Rather than process input
1990 until \verb|pe| is arrived at, the fbreak statement
1991 can be used to stop processing from an action.  After an \verb|fbreak|
1992 statement the \verb|p| variable will point to the next character in the input. The
1993 current state will be the target of the current transition. Note that \verb|fbreak|
1994 causes the target state's to-state actions to be skipped.
1995
1996 \end{itemize}
1997
1998 \noindent {\bf Note:} Once actions with control-flow commands are embedded into a
1999 machine, the user must exercise caution when using the machine as the operand
2000 to other machine construction operators. If an action jumps to another state
2001 then unioning any transition that executes that action with another transition
2002 that follows some other path will cause that other path to be lost. Using
2003 commands that manually jump around a machine takes us out of the domain of
2004 regular languages because transitions that the
2005 machine construction operators are not aware of are introduced.  These
2006 commands should therefore be used with caution.
2007
2008
2009 \chapter{Controlling Nondeterminism}
2010 \label{controlling-nondeterminism}
2011
2012 Along with the flexibility of arbitrary action embeddings comes a need to
2013 control nondeterminism in regular expressions. If a regular expression is
2014 ambiguous, then sub-components of a parser other than the intended parts may become
2015 active. This means that actions that are irrelevant to the
2016 current subset of the parser may be executed, causing problems for the
2017 programmer.
2018
2019 Tools that are based on regular expression engines and that are used for
2020 recognition tasks will usually function as intended regardless of the presence
2021 of ambiguities. It is quite common for users of scripting languages to write
2022 regular expressions that are heavily ambiguous and it generally does not
2023 matter. As long as one of the potential matches is recognized, there can be any
2024 number of other matches present.  In some parsing systems the run-time engine
2025 can employ a strategy for resolving ambiguities, for example always pursuing
2026 the longest possible match and discarding others.
2027
2028 In Ragel, there is no regular expression run-time engine, just a simple state
2029 machine execution model. When we begin to embed actions and face the
2030 possibility of spurious action execution, it becomes clear that controlling
2031 nondeterminism at the machine construction level is very important. Consider
2032 the following example.
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}
2043 ws = [\n\t ];
2044 line = word $first ( ws word$tail )* '\n';
2045 lines = line*;
2046 \end{verbatim}
2047 \end{inline_code}
2048 % main := lines;
2049 % }%%
2050 % END GENERATE
2051
2052 \begin{center}
2053 \includegraphics[scale=0.53]{lines1}
2054 \end{center}
2055 \graphspace
2056
2057 Since the \verb|ws| expression includes the newline character, we will
2058 not finish the \verb|line| expression when a newline character is seen. We will
2059 simultaneously pursue the possibility of matching further words on the same
2060 line and the possibility of matching a second line. Evidence of this fact is
2061 in the state tables. On several transitions both the \verb|first| and
2062 \verb|tail| actions are executed.  The solution here is simple: exclude
2063 the newline character from the \verb|ws| expression.
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}
2074 ws = [\t ];
2075 line = word $first ( ws word$tail )* '\n';
2076 lines = line*;
2077 \end{verbatim}
2078 \end{inline_code}
2079 % main := lines;
2080 % }%%
2081 % END GENERATE
2082
2083 \begin{center}
2084 \includegraphics[scale=0.55]{lines2}
2085 \end{center}
2086 \graphspace
2087
2088 Solving this kind of problem is straightforward when the ambiguity is created
2089 by strings that are a single character long.  When the ambiguity is created by
2090 strings that are multiple characters long we have a more difficult problem.
2091 The following example is an incorrect attempt at a regular expression for C
2093
2094 % GENERATE: comments1
2095 % OPT: -p
2096 % %%{
2097 % machine comments1;
2098 % action comm {}
2099 \begin{inline_code}
2100 \begin{verbatim}
2101 comment = '/*' ( any @comm )* '*/';
2102 main := comment ' ';
2103 \end{verbatim}
2104 \end{inline_code}
2105 % }%%
2106 % END GENERATE
2107
2108 \begin{center}
2110 \end{center}
2111 \graphspace
2112
2113 Using standard concatenation, we will never leave the \verb|any*| expression.
2114 We will forever entertain the possibility that a \verb|'*/'| string that we see
2115 is contained in a longer comment and that, simultaneously, the comment has
2116 ended.  The concatenation of the \verb|comment| machine with \verb|SP| is done
2117 to show this. When we match space, we are also still matching the comment body.
2118
2119 One way to approach the problem is to exclude the terminating string
2120 from the \verb|any*| expression using set difference. We must be careful to
2121 exclude not just the terminating string, but any string that contains it as a
2122 substring. A verbose, but proper specification of a C comment parser is given
2123 by the following regular expression.
2124
2125 % GENERATE: comments2
2126 % OPT: -p
2127 % %%{
2128 % machine comments2;
2129 % action comm {}
2130 \begin{inline_code}
2131 \begin{verbatim}
2132 comment = '/*' ( ( any @comm )* - ( any* '*/' any* ) ) '*/';
2133 \end{verbatim}
2134 \end{inline_code}
2135 % main := comment;
2136 % }%%
2137 % END GENERATE
2138
2139 \graphspace
2140 \begin{center}
2142 \end{center}
2143 \graphspace
2144
2145 Note that Ragel's strong subtraction operator \verb|--| can also be used here.
2146 In doing this subtraction we have phrased the problem of controlling non-determinism in
2147 terms of excluding strings common to two expressions that interact when
2148 combined.
2149 We can also phrase the problem in terms of the transitions of the state
2150 machines that implement these expressions. During the concatenation of
2151 \verb|any*| and \verb|'*/'| we will be making transitions that are composed of
2152 both the loop of the first expression and the final character of the second.
2153 At this time we want the transition on the \verb|'/'| character to take precedence
2154 over and disallow the transition that originated in the \verb|any*| loop.
2155
2156 In another parsing problem, we wish to implement a lightweight tokenizer that we can
2157 utilize in the composition of a larger machine. For example, some HTTP headers
2158 have a token stream as a sub-language. The following example is an attempt
2159 at a regular expression-based tokenizer that does not function correctly due to
2160 unintended nondeterminism.
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}
2173 header_contents = (
2174     lower+ >start_str $on_char %finish_str | 2175 ' ' 2176 )*; 2177 \end{verbatim} 2178 \end{inline_code} 2179 % main := header_contents; 2180 % }%% 2181 % END GENERATE 2182 2183 \begin{center} 2184 \includegraphics[scale=0.55]{smallscanner} 2185 \end{center} 2186 \graphspace 2187 2188 In this case, the problem with using a standard kleene star operation is that 2189 there is an ambiguity between extending a token and wrapping around the machine 2190 to begin a new token. Using the standard operator, we get an undesirable 2191 nondeterministic behaviour. Evidence of this can be seen on the transition out 2192 of state one to itself. The transition extends the string, and simultaneously, 2193 finishes the string only to immediately begin a new one. What is required is 2194 for the 2195 transitions that represent an extension of a token to take precedence over the 2196 transitions that represent the beginning of a new token. For this problem 2197 there is no simple solution that uses standard regular expression operators. 2198 2199 \section{Priorities} 2200 2201 A priority mechanism was devised and built into the determinization 2202 process, specifically for the purpose of allowing the user to control 2203 nondeterminism. Priorities are integer values embedded into transitions. When 2204 the determinization process is combining transitions that have different 2205 priorities, the transition with the higher priority is preserved and the 2206 transition with the lower priority is dropped. 2207 2208 Unfortunately, priorities can have unintended side effects because their 2209 operation requires that they linger in transitions indefinitely. They must linger 2210 because the Ragel program cannot know when the user is finished with a priority 2211 embedding. A solution whereby they are explicitly deleted after use is 2212 conceivable; however this is not very user-friendly. Priorities were therefore 2213 made into named entities. Only priorities with the same name are allowed to 2214 interact. This allows any number of priorities to coexist in one machine for 2215 the purpose of controlling various different regular expression operations and 2216 eliminates the need to ever delete them. Such a scheme allows the user to 2217 choose a unique name, embed two different priority values using that name 2218 and be confident that the priority embedding will be free of any side effects. 2219 2220 In the first form of priority embedding the name defaults to the name of the machine 2221 definition that the priority is assigned in. In this sense priorities are by 2222 default local to the current machine definition or instantiation. Beware of 2223 using this form in a longest-match machine, since there is only one name for 2224 the entire set of longest match patterns. In the second form the priority's 2225 name can be specified, allowing priority interaction across machine definition 2226 boundaries. 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
2234 have priority int. When a transition is made going out of the machine (either
2235 by concatenation or kleene star) its priority is immediately set to the
2236 leaving priority.
2237 \end{itemize}
2238
2239 The second form of priority assignment allows the programmer to specify the name
2240 to 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 2252 Priority embeddings are a very expressive mechanism. At the same time they 2253 can be very confusing for the user. They force the user to imagine 2254 the transitions inside two interacting expressions and work out the precise 2255 effects of the operations between them. When we consider 2256 that this problem is worsened by the 2257 potential for side effects caused by unintended priority name collisions, we 2258 see that exposing the user to priorities is undesirable. 2259 2260 Fortunately, in practice the use of priorities has been necessary only in a 2261 small number of scenarios. This allows us to encapsulate their functionality 2262 into a small set of operators and fully hide them from the user. This is 2263 advantageous from a language design point of view because it greatly simplifies 2264 the design. 2265 2266 Going back to the C comment example, we can now properly specify 2267 it using a guarded concatenation operator which we call {\em finish-guarded 2268 concatenation}. From the user's point of view, this operator terminates the 2269 first machine when the second machine moves into a final state. It chooses a 2270 unique name and uses it to embed a low priority into all 2271 transitions of the first machine. A higher priority is then embedded into the 2272 transitions of the second machine that enter into a final state. The following 2273 example yields a machine identical to the example in Section 2274 \ref{controlling-nondeterminism}. 2275 2276 \begin{inline_code} 2277 \begin{verbatim} 2278 comment = '/*' ( 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 2288 Another guarded operator is {\em left-guarded concatenation}, given by the 2289 \verb|<:| compound symbol. This operator places a higher priority on all 2290 transitions of the first machine. This is useful if one must forcibly separate 2291 two lists that contain common elements. For example, one may need to tokenize a 2292 stream, but first consume leading whitespace. 2293 2294 Ragel also includes a {\em longest-match kleene star} operator, given by the 2295 \verb|**| compound symbol. This 2296 guarded operator embeds a high 2297 priority into all transitions of the machine. 2298 A lower priority is then embedded into the leaving transitions. When the 2299 kleene star operator makes the epsilon transitions from 2300 the final states into the new start state, the lower priority will be transferred 2301 to the epsilon transitions. In cases where following an epsilon transition 2302 out of a final state conflicts with an existing transition out of a final 2303 state, the epsilon transition will be dropped. 2304 2305 Other guarded operators are conceivable, such as guards on union that cause one 2306 alternative to take precedence over another. These may be implemented when it 2307 is clear they constitute a frequently used operation. 2308 In the next section we discuss the explicit specification of state machines 2309 using state charts. 2310 2311 \subsection{Entry-Guarded Concatenation} 2312 2313 \verb|expr :> expr| 2314 \verbspace 2315 2316 This operator concatenates two machines, but first assigns a low 2317 priority to all transitions 2318 of the first machine and a high priority to the starting transitions of the 2319 second machine. This operator is useful if from the final states of the first 2320 machine it is possible to accept the characters in the entering transitions of 2321 the second machine. This operator effectively terminates the first machine 2322 immediately upon starting the second machine, where otherwise they would be 2323 pursued concurrently. In the following example, entry-guarded concatenation is 2324 used to move out of a machine that matches everything at the first sign of an 2325 end-of-input marker. 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. 2334 main := 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 2345 Entry-guarded concatenation is equivalent to the following: 2346 2347 \verbspace 2348 \begin{verbatim} 2349 expr$(unique_name,0) . expr >(unique_name,1)
2350 \end{verbatim}
2351
2352 \subsection{Finish-Guarded Concatenation}
2353
2354 \verb|expr :>> expr|
2355 \verbspace
2356
2357 This operator is
2358 like the previous operator, except the higher priority is placed on the final
2359 transitions of the second machine. This is useful if one wishes to entertain
2360 the possibility of continuing to match the first machine right up until the
2361 second machine enters a final state. In other words it terminates the first
2362 machine only when the second accepts. In the following example, finish-guarded
2363 concatenation causes the move out of the machine that matches everything to be
2364 delayed until the full end-of-input marker has been matched.
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.
2373 main := 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
2384 Finish-guarded concatenation is equivalent to the following, with one
2385 exception. If the right machine's start state is final, the higher priority is
2386 also embedded into it as a leaving priority. This prevents the left machine
2387 from persisting via the zero-length string.
2388
2389 \verbspace
2390 \begin{verbatim}
2391 expr $(unique_name,0) . expr @(unique_name,1) 2392 \end{verbatim} 2393 2394 \subsection{Left-Guarded Concatenation} 2395 2396 \verb|expr <: expr| 2397 \verbspace 2398 2399 This operator places 2400 a higher priority on the left expression. It is useful if you want to prefix a 2401 sequence with another sequence composed of some of the same characters. For 2402 example, one can consume leading whitespace before tokenizing a sequence of 2403 whitespace-separated words as in: 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} 2415 main := ( ' '* >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 2427 Left-guarded concatenation is equivalent to the following: 2428 2429 \verbspace 2430 \begin{verbatim} 2431 expr$(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
2441 This version of kleene star puts a higher priority on staying in the
2442 machine versus wrapping around and starting over. The LM kleene star is useful
2443 when writing simple tokenizers.  These machines are built by applying the
2444 longest-match kleene star to an alternation of token patterns, as in the
2445 following.
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.
2458 main := (
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
2473 If a regular kleene star were used the machine above would not be able to
2474 distinguish between extending a word and beginning a new one.  This operator is
2475 equivalent to:
2476
2477 \verbspace
2478 \begin{verbatim}
2479 ( expr $(unique_name,1) %(unique_name,0) )* 2480 \end{verbatim} 2481 \verbspace 2482 2483 When the kleene star is applied, transitions that go out of the machine and 2484 back into it are made. These are assigned a priority of zero by the leaving 2485 transition mechanism. This is less than the priority of one assigned to the 2486 transitions leaving the final states but not leaving the machine. When 2487 these transitions clash on the same character, the 2488 transition that stays in the machine takes precedence. The transition 2489 that wraps around is dropped. 2490 2491 Note that this operator does not build a scanner in the traditional sense 2492 because there is never any backtracking. To build a scanner with backtracking 2493 use the Longest-Match machine construction described in Section 2494 \ref{generating-scanners}. 2495 2496 \chapter{Interface to Host Program} 2497 2498 The Ragel code generator is very flexible. The generated code has no 2499 dependencies and can be inserted in any function, perhaps inside a loop if 2500 desired. The user is responsible for declaring and initializing a number of 2501 required variables, including the current state and the pointer to the input 2502 stream. These can live in any scope. Control of the input processing loop is 2503 also possible: the user may break out of the processing loop and return to it 2504 at any time. 2505 2506 In the case of the C, D, and Go host languages, Ragel is able to generate very 2507 fast-running code that implements state machines as directly executable code. 2508 Since very large files strain the host language compiler, table-based code 2509 generation is also supported. In the future we hope to provide a partitioned, 2510 directly executable format that is able to reduce the burden on the host 2511 compiler by splitting large machines across multiple functions. 2512 2513 In the case of Java and Ruby, table-based code generation is the only code 2514 style supported. In the future this may be expanded to include other code 2515 styles. 2516 2517 Ragel can be used to parse input in one block, or it can be used to parse input 2518 in a sequence of blocks as it arrives from a file or socket. Parsing the input 2519 in a sequence of blocks brings with it a few responsibilities. If the parser 2520 utilizes a scanner, care must be taken to not break the input stream anywhere 2521 but token boundaries. If pointers to the input stream are taken during 2522 parsing, care must be taken to not use a pointer that has been invalidated by 2523 movement to a subsequent block. If the current input data pointer is moved 2524 backwards it must not be moved past the beginning of the current block. 2525 2526 Figure \ref{basic-example} shows a simple Ragel program that does not have any 2527 actions. The example tests the first argument of the program against a number 2528 pattern and then prints the machine's acceptance status. 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 }%% 2539 int main( int argc, char **argv ) 2540 { 2541 int cs; 2542 if ( argc > 1 ) { 2543 char *p = argv[1]; 2544 char *pe = p + strlen( p ); 2545 %%{ 2546 main := [0-9]+ ( '.' [0-9]+ )?; 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 2562 There are a number of variables that Ragel expects the user to declare. At a 2563 very minimum the \verb|cs|, \verb|p| and \verb|pe| variables must be declared. 2564 In Go, Java and Ruby code the \verb|data| variable must also be declared. If 2565 EOF actions are used then the \verb|eof| variable is required. If 2566 stack-based state machine control flow statements are used then the 2567 \verb|stack| and \verb|top| variables are required. If a scanner is declared 2568 then the \verb|act|, \verb|ts| and \verb|te| variables must be 2569 declared. 2570 2571 \begin{itemize} 2572 2573 \item \verb|cs| - Current state. This must be an integer and it should persist 2574 across invocations of the machine when the data is broken into blocks that are 2575 processed independently. This variable may be modified from outside the 2576 execution loop, but not from within. 2577 2578 \item \verb|p| - Data pointer. In C/D code this variable is expected to be a 2579 pointer to the character data to process. It should be initialized to the 2580 beginning of the data block on every run of the machine. In Go, Java and Ruby it is 2581 used as an offset to \verb|data| and must be an integer. In this case it should 2582 be initialized to zero on every run of the machine. 2583 2584 \item \verb|pe| - Data end pointer. This should be initialized to \verb|p| plus 2585 the data length on every run of the machine. In Go, Java and Ruby code this should 2586 be initialized to the data length. 2587 2588 \item \verb|eof| - End of file pointer. This should be set to \verb|pe| when 2589 the buffer block being processed is the last one, otherwise it should be set to 2590 null. In Go, Java and Ruby code \verb|-1| must be used instead of null. If the EOF 2591 event can be known only after the final buffer block has been processed, then 2592 it is possible to set \verb|p = pe = eof| and run the execute block. 2593 2594 \item \verb|data| - This variable is only required in Go, Java and Ruby code. It 2595 must be an array containting the data to process. 2596 2597 \item \verb|stack| - This must be an array of integers. It is used to store 2598 integer values representing states. If the stack must resize dynamically the 2599 Pre-push and Post-Pop statements can be used to do this (Sections 2600 \ref{prepush} and \ref{postpop}). 2601 2602 \item \verb|top| - This must be an integer value and will be used as an offset 2603 to \verb|stack|, giving the next available spot on the top of the stack. 2604 2605 \item \verb|act| - This must be an integer value. It is a variable sometimes 2606 used by scanner code to keep track of the most recent successful pattern match. 2607 2608 \item \verb|ts| - This must be a pointer to character data. In Go, Java and 2609 Ruby code this must be an integer. See Section \ref{generating-scanners} for 2610 more information. 2611 2612 \item \verb|te| - Also a pointer to character data. 2613 2614 \end{itemize} 2615 2616 \section{Alphtype Statement} 2617 2618 \begin{verbatim} 2619 alphtype unsigned int; 2620 \end{verbatim} 2621 \verbspace 2622 2623 The alphtype statement specifies the alphabet data type that the machine 2624 operates on. During the compilation of the machine, integer literals are 2625 expected to be in the range of possible values of the alphtype. The default 2626 is \verb|char| for all languages except Go where the default is \verb|byte|. 2627 2628 \begin{multicols}{2} 2629 \setlength{\columnseprule}{1pt} 2630 C/C++/Objective-C: 2631 \begin{verbatim} 2632 char unsigned char 2633 short unsigned short 2634 int unsigned int 2635 long unsigned long 2636 \end{verbatim} 2637 2638 Go: 2639 \begin{verbatim} 2640 byte 2641 int8 uint8 2642 int16 uint16 2643 int32 uint32 2644 int64 uint64 2645 rune 2646 \end{verbatim} 2647 2648 Ruby: 2649 \begin{verbatim} 2650 char 2651 int 2652 \end{verbatim} 2653 2654 \columnbreak 2655 2656 Java: 2657 \begin{verbatim} 2658 char 2659 byte 2660 short 2661 int 2662 \end{verbatim} 2663 2664 D: 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} 2679 getkey fpc->id; 2680 \end{verbatim} 2681 \verbspace 2682 2683 This statement specifies to Ragel how to retrieve the current character from 2684 from the pointer to the current element (\verb|p|). Any expression that returns 2685 a value of the alphabet type 2686 may be used. The getkey statement may be used for looking into element 2687 structures or for translating the character to process. The getkey expression 2688 defaults to \verb|(*p)|. In goto-driven machines the getkey expression may be 2689 evaluated more than once per element processed, therefore it should not incur a 2690 large cost nor preclude optimization. 2691 2692 \section{Access Statement} 2693 2694 \begin{verbatim} 2695 access fsm->; 2696 \end{verbatim} 2697 \verbspace 2698 2699 The access statement specifies how the generated code should 2700 access the machine data that is persistent across processing buffer blocks. 2701 This applies to all variables except \verb|p|, \verb|pe| and \verb|eof|. This includes 2702 \verb|cs|, \verb|top|, \verb|stack|, \verb|ts|, \verb|te| and \verb|act|. 2703 The access statement is useful if a machine is to be encapsulated inside a 2704 structure in C code. It can be used to give the name of 2705 a pointer to the structure. 2706 2707 \section{Variable Statement} 2708 2709 \begin{verbatim} 2710 variable p fsm->p; 2711 \end{verbatim} 2712 \verbspace 2713 2714 The variable statement specifies how to access a specific 2715 variable. All of the variables that are declared by the user and 2716 used by Ragel can be changed. This includes \verb|p|, \verb|pe|, \verb|eof|, \verb|cs|, 2717 \verb|top|, \verb|stack|, \verb|ts|, \verb|te| and \verb|act|. 2718 In Go, Ruby and Java code generation the \verb|data| variable can also be changed. 2719 2720 \section{Pre-Push Statement} 2721 \label{prepush} 2722 2723 \begin{verbatim} 2724 prepush { 2725 /* stack growing code */ 2726 } 2727 \end{verbatim} 2728 \verbspace 2729 2730 The prepush statement allows the user to supply stack management code that is 2731 written out during the generation of fcall, immediately before the current 2732 state is pushed to the stack. This statement can be used to test the number of 2733 available spaces and dynamically grow the stack if necessary. 2734 2735 \section{Post-Pop Statement} 2736 \label{postpop} 2737 2738 \begin{verbatim} 2739 postpop { 2740 /* stack shrinking code */ 2741 } 2742 \end{verbatim} 2743 \verbspace 2744 2745 The postpop statement allows the user to supply stack management code that is 2746 written out during the generation of fret, immediately after the next state is 2747 popped from the stack. This statement can be used to dynamically shrink the 2748 stack. 2749 2750 \section{Write Statement} 2751 \label{write-statement} 2752 2753 \begin{verbatim} 2754 write <component> [options]; 2755 \end{verbatim} 2756 \verbspace 2757 2758 The write statement is used to generate parts of the machine. 2759 There are seven 2760 components that can be generated by a write statement. These components make up the 2761 state machine's data, initialization code, execution code, and export definitions. 2762 A write statement may appear before a machine is fully defined. 2763 This allows one to write out the data first then later define the machine where 2764 it is used. An example of this is shown in Figure \ref{fbreak-example}. 2765 2766 \subsection{Write Data} 2767 \begin{verbatim} 2768 write data [options]; 2769 \end{verbatim} 2770 \verbspace 2771 2772 The write data statement causes Ragel to emit the constant static data needed 2773 by the machine. In table-driven output styles (see Section \ref{genout}) this 2774 is a collection of arrays that represent the states and transitions of the 2775 machine. In goto-driven machines much less data is emitted. At the very 2776 minimum a start state \verb|name_start| is generated. All variables written 2777 out in machine data have both the \verb|static| and \verb|const| properties and 2778 are prefixed with the name of the machine and an 2779 underscore. The data can be placed inside a class, inside a function, or it can 2780 be defined as global data. 2781 2782 Two variables are written that may be used to test the state of the machine 2783 after a buffer block has been processed. The \verb|name_error| variable gives 2784 the id of the state that the machine moves into when it cannot find a valid 2785 transition to take. The machine immediately breaks out of the processing loop when 2786 it finds itself in the error state. The error variable can be compared to the 2787 current state to determine if the machine has failed to parse the input. If the 2788 machine is complete, that is from every state there is a transition to a proper 2789 state on every possible character of the alphabet, then no error state is required 2790 and this variable will be set to -1. 2791 2792 The \verb|name_first_final| variable stores the id of the first final state. All of the 2793 machine's states are sorted by their final state status before having their ids 2794 assigned. Checking if the machine has accepted its input can then be done by 2795 checking if the current state is greater-than or equal to the first final 2796 state. 2797 2798 Data 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 2803 id of the error state. 2804 \item \verb|nofinal | - Do not generate the integer variable that gives the 2805 id of the first final state. 2806 \item \verb|noentry | - Do not generate the integer variables that give the 2807 values of the entry points. 2808 \item \verb|noprefix | - Do not prefix the variable names with the name of the 2809 machine. 2810 \end{itemize} 2811 2812 \begin{figure} 2813 \small 2814 \begin{verbatim} 2815 #include <stdio.h> 2816 %% machine foo; 2817 %% write data; 2818 int main( int argc, char **argv ) 2819 { 2820 int cs, res = 0; 2821 if ( argc > 1 ) { 2822 char *p = argv[1]; 2823 %%{ 2824 main := 2825 [a-z]+ 2826 0 @{ res = 1; fbreak; }; 2827 write init; 2828 write exec noend; 2829 }%% 2830 } 2831 printf("execute = %i\n", res ); 2832 return 0; 2833 } 2834 \end{verbatim} 2835 \caption{Use of {\tt noend} write option and the {\tt fbreak} statement for 2836 processing a string.} 2837 \label{fbreak-example} 2838 \end{figure} 2839 2840 \subsection{Write Start, First Final and Error} 2841 2842 \begin{verbatim} 2843 write start; 2844 write first_final; 2845 write error; 2846 \end{verbatim} 2847 \verbspace 2848 2849 These three write statements provide an alternative means of accessing the 2850 \verb|start|, \verb|first_final| and \verb|error| states. If there are many 2851 different machine specifications in one file it is easy to get the prefix for 2852 these wrong. This is especially true if the state machine boilerplate is 2853 frequently made by a copy-paste-edit process. These write statements allow the 2854 problem to be avoided. They can be used as follows: 2855 2856 \verbspace 2857 2858 { 2859 \small 2860 \begin{verbatim} 2861 /* Did parsing succeed? */ 2862 if ( cs < %%{ write first_final; }%% ) { 2863 result = ERR_PARSE_ERROR; 2864 goto fail; 2865 } 2866 \end{verbatim} 2867 } 2868 2869 2870 \subsection{Write Init} 2871 \begin{verbatim} 2872 write init [options]; 2873 \end{verbatim} 2874 \verbspace 2875 2876 The write init statement causes Ragel to emit initialization code. This should 2877 be executed once before the machine is started. At a very minimum this sets the 2878 current state to the start state. If other variables are needed by the 2879 generated code, such as call stack variables or scanner management 2880 variables, they are also initialized here. 2881 2882 The \verb|nocs| option to the write init statement will cause ragel to skip 2883 intialization of the cs variable. This is useful if the user wishes to use 2884 custom logic to decide which state the specification should start in. 2885 2886 \subsection{Write Exec} 2887 \begin{verbatim} 2888 write exec [options]; 2889 \end{verbatim} 2890 \verbspace 2891 2892 The write exec statement causes Ragel to emit the state machine's execution code. 2893 Ragel expects several variables to be available to this code. At a very minimum, the 2894 generated code needs access to the current character position \verb|p|, the ending 2895 position \verb|pe| and the current state \verb|cs| (though \verb|pe| 2896 can be omitted using the \verb|noend| write option). 2897 The \verb|p| variable is the cursor that the execute code will 2898 used to traverse the input. The \verb|pe| variable should be set up to point to one 2899 position past the last valid character in the buffer. 2900 2901 Other variables are needed when certain features are used. For example using 2902 the \verb|fcall| or \verb|fret| statements requires \verb|stack| and 2903 \verb|top| variables to be defined. If a longest-match construction is used, 2904 variables for managing backtracking are required. 2905 2906 The write exec statement has one option. The \verb|noend| option tells Ragel 2907 to generate code that ignores the end position \verb|pe|. In this 2908 case the user must explicitly break out of the processing loop using 2909 \verb|fbreak|, otherwise the machine will continue to process characters until 2910 it moves into the error state. This option is useful if one wishes to process a 2911 null terminated string. Rather than traverse the string to discover then length 2912 before processing the input, the user can break out when the null character is 2913 seen. The example in Figure \ref{fbreak-example} shows the use of the 2914 \verb|noend| write option and the \verb|fbreak| statement for processing a string. 2915 2916 \subsection{Write Exports} 2917 \label{export} 2918 2919 \begin{verbatim} 2920 write exports; 2921 \end{verbatim} 2922 \verbspace 2923 2924 The export feature can be used to export simple machine definitions. Machine definitions 2925 are marked for export using the \verb|export| keyword. 2926 2927 \verbspace 2928 \begin{verbatim} 2929 export machine_to_export = 0x44; 2930 \end{verbatim} 2931 \verbspace 2932 2933 When the write exports statement is used these machines are 2934 written out in the generated code. Defines are used for C and constant integers 2935 are used for D, Java and Ruby. See Section \ref{import} for a description of the 2936 import statement. 2937 2938 \section{Maintaining Pointers to Input Data} 2939 2940 In the creation of any parser it is not uncommon to require the collection of 2941 the data being parsed. It is always possible to collect data into a growable 2942 buffer as the machine moves over it, however the copying of data is a somewhat 2943 wasteful use of processor cycles. The most efficient way to collect data from 2944 the parser is to set pointers into the input then later reference them. This 2945 poses a problem for uses of Ragel where the input data arrives in blocks, such 2946 as over a socket or from a file. If a pointer is set in one buffer block but 2947 must be used while parsing a following buffer block, some extra consideration 2948 to correctness must be made. 2949 2950 The scanner constructions exhibit this problem, requiring the maintenance 2951 code described in Section \ref{generating-scanners}. If a longest-match 2952 construction has been used somewhere in the machine then it is possible to 2953 take advantage of the required prefix maintenance code in the driver program to 2954 ensure pointers to the input are always valid. If laying down a pointer one can 2955 set \verb|ts| at the same spot or ahead of it. When data is shifted in 2956 between loops the user must also shift the pointer. In this way it is possible 2957 to maintain pointers to the input that will always be consistent. 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 2998 In general, there are two approaches for guaranteeing the consistency of 2999 pointers to input data. The first approach is the one just described; 3000 lay down a marker from an action, 3001 then later ensure that the data the marker points to is preserved ahead of 3002 the buffer on the next execute invocation. This approach is good because it 3003 allows the parser to decide on the pointer-use boundaries, which can be 3004 arbitrarily complex parsing conditions. A downside is that it requires any 3005 pointers that are set to be corrected in between execute invocations. 3006 3007 The alternative is to find the pointer-use boundaries before invoking the execute 3008 routine, then pass in the data using these boundaries. For example, if the 3009 program must perform line-oriented processing, the user can scan backwards from 3010 the end of an input block that has just been read in and process only up to the 3011 first found newline. On the next input read, the new data is placed after the 3012 partially read line and processing continues from the beginning of the line. 3013 An example of line-oriented processing is given in Figure \ref{line-oriented}. 3014 3015 \section{Specifying the Host Language} 3016 3017 The \verb|ragel| program has a number of options for specifying the host 3018 language. 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 3032 There are three styles of code output to choose from. Code style affects the 3033 size and speed of the compiled binary. Changing code style does not require any 3034 change to the Ragel program. There are two table-driven formats and a goto 3035 driven format. 3036 3037 In addition to choosing a style to emit, there are various levels of action 3038 code reuse to choose from. The maximum reuse levels (\verb|-T0|, \verb|-F0| 3039 and \verb|-G0|) ensure that no FSM action code is ever duplicated by encoding 3040 each transition's action list as static data and iterating 3041 through the lists on every transition. This will normally result in a smaller 3042 binary. The less action reuse options (\verb|-T1|, \verb|-F1| and \verb|-G1|) 3043 will usually produce faster running code by expanding each transition's action 3044 list into a single block of code, eliminating the need to iterate through the 3045 lists. This duplicates action code instead of generating the logic necessary 3046 for reuse. Consequently the binary will be larger. However, this tradeoff applies to 3047 machines with moderate to dense action lists only. If a machine's transitions 3048 frequently have less than two actions then the less reuse options will actually 3049 produce both a smaller and a faster running binary due to less action sharing 3050 overhead. The best way to choose the appropriate code style for your 3051 application is to perform your own tests. 3052 3053 The table-driven FSM represents the state machine as constant static data. There are 3054 tables of states, transitions, indices and actions. The current state is 3055 stored in a variable. The execution is simply a loop that looks up the current 3056 state, looks up the transition to take, executes any actions and moves to the 3057 target state. In general, the table-driven FSM can handle any machine, produces 3058 a smaller binary and requires a less expensive host language compile, but 3059 results in slower running code. Since the table-driven format is the most 3060 flexible it is the default code style. 3061 3062 The flat table-driven machine is a table-based machine that is optimized for 3063 small alphabets. Where the regular table machine uses the current character as 3064 the key in a binary search for the transition to take, the flat table machine 3065 uses the current character as an index into an array of transitions. This is 3066 faster in general, however is only suitable if the span of possible characters 3067 is small. 3068 3069 The goto-driven FSM represents the state machine using goto and switch 3070 statements. The execution is a flat code block where the transition to take is 3071 computed using switch statements and directly executable binary searches. In 3072 general, the goto FSM produces faster code but results in a larger binary and a 3073 more expensive host language compile. 3074 3075 The goto-driven format has an additional action reuse level (\verb|-G2|) that 3076 writes actions directly into the state transitioning logic rather than putting 3077 all the actions together into a single switch. Generally this produces faster 3078 running code because it allows the machine to encode the current state using 3079 the processor's instruction pointer. Again, sparse machines may actually 3080 compile to smaller binaries when \verb|-G2| is used due to less state and 3081 action management overhead. For many parsing applications \verb|-G2| is the 3082 preferred output format. 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 3112 It is possible to use Ragel's machine construction and action embedding 3113 operators to specify an entire parser using a single regular expression. In 3114 many cases this is the desired way to specify a parser in Ragel. However, in 3115 some scenarios the language to parse may be so large that it is difficult to 3116 think about it as a single regular expression. It may also shift between distinct 3117 parsing strategies, in which case modularization into several coherent blocks 3118 of the language may be appropriate. 3119 3120 It may also be the case that patterns that compile to a large number of states 3121 must be used in a number of different contexts and referencing them in each 3122 context results in a very large state machine. In this case, an ability to reuse 3123 parsers would reduce code size. 3124 3125 To address this, distinct regular expressions may be instantiated and linked 3126 together by means of a jumping and calling mechanism. This mechanism is 3127 analogous to the jumping to and calling of processor instructions. A jump 3128 command, given in action code, causes control to be immediately passed to 3129 another portion of the machine by way of setting the current state variable. A 3130 call command causes the target state of the current transition to be pushed to 3131 a state stack before control is transferred. Later on, the original location 3132 may be returned to with a return statement. In the following example, distinct 3133 state machines are used to handle the parsing of two types of headers. 3134 3135 % GENERATE: call 3136 % %%{ 3137 % machine call; 3138 \begin{inline_code} 3139 \begin{verbatim} 3140 action return { fret; } 3141 action call_date { fcall date; } 3142 action call_name { fcall name; } 3143 3144 # A parser for date strings. 3145 date := [0-9][0-9] '/' 3146 [0-9][0-9] '/' 3147 [0-9][0-9][0-9][0-9] '\n' @return; 3148 3149 # A parser for name strings. 3150 name := ( [a-zA-Z]+ | ' ' )** '\n' @return; 3151 3152 # The main parser. 3153 headers = 3154 ( 'from' | 'to' ) ':' @call_name | 3155 ( 'departed' | 'arrived' ) ':' @call_date; 3156 3157 main := headers*; 3158 \end{verbatim} 3159 \end{inline_code} 3160 % }%% 3161 % %% write data; 3162 % void f() 3163 % { 3164 % %% write init; 3165 % %% write exec; 3166 % } 3167 % END GENERATE 3168 3169 Calling and jumping should be used carefully as they are operations that take 3170 one out of the domain of regular languages. A machine that contains a call or 3171 jump statement in one of its actions should be used as an argument to a machine 3172 construction operator only with considerable care. Since DFA transitions may 3173 actually represent several NFA transitions, a call or jump embedded in one 3174 machine can inadvertently terminate another machine that it shares prefixes 3175 with. Despite this danger, theses statements have proven useful for tying 3176 together sub-parsers of a language into a parser for the full language, 3177 especially for the purpose of modularizing code and reducing the number of 3178 states when the machine contains frequently recurring patterns. 3179 3180 Section \ref{vals} describes the jump and call statements that are used to 3181 transfer control. These statements make use of two variables that must be 3182 declared by the user, \verb|stack| and \verb|top|. The \verb|stack| variable 3183 must be an array of integers and \verb|top| must be a single integer, which 3184 will point to the next available space in \verb|stack|. Sections \ref{prepush} 3185 and \ref{postpop} describe the Pre-Push and Post-Pop statements which can be 3186 used to implement a dynamically resizable array. 3187 3188 \section{Referencing Names} 3189 \label{labels} 3190 3191 This section describes how to reference names in epsilon transitions (Section 3192 \ref{state-charts}) and 3193 action-based control-flow statements such as \verb|fgoto|. There is a hierarchy 3194 of names implied in a Ragel specification. At the top level are the machine 3195 instantiations. Beneath the instantiations are labels and references to machine 3196 definitions. Beneath those are more labels and references to definitions, and 3197 so on. 3198 3199 Any name reference may contain multiple components separated with the \verb|::| 3200 compound symbol. The search for the first component of a name reference is 3201 rooted at the join expression that the epsilon transition or action embedding 3202 is contained in. If the name reference is not contained in a join, 3203 the search is rooted at the machine definition that the epsilon transition or 3204 action embedding is contained in. Each component after the first is searched 3205 for beginning at the location in the name tree that the previous reference 3206 component refers to. 3207 3208 In the case of action-based references, if the action is embedded more than 3209 once, the local search is performed for each embedding and the result is the 3210 union of all the searches. If no result is found for action-based references then 3211 the search is repeated at the root of the name tree. Any action-based name 3212 search may be forced into a strictly global search by prefixing the name 3213 reference with \verb|::|. 3214 3215 The final component of the name reference must resolve to a unique entry point. 3216 If a name is unique in the entire name tree it can be referenced as is. If it 3217 is not unique it can be specified by qualifying it with names above it in the 3218 name tree. However, it can always be renamed. 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 3232 Scanners are very much intertwined with regular-languages and their 3233 corresponding processors. For this reason Ragel supports the definition of 3234 scanners. The generated code will repeatedly attempt to match patterns from a 3235 list, favouring longer patterns over shorter patterns. In the case of 3236 equal-length matches, the generated code will favour patterns that appear ahead 3237 of others. When a scanner makes a match it executes the user code associated 3238 with the match, consumes the input then resumes scanning. 3239 3240 \verbspace 3241 \begin{verbatim} 3242 <machine_name> := |* 3243 pattern1 => action1; 3244 pattern2 => action2; 3245 ... 3246 *|; 3247 \end{verbatim} 3248 \verbspace 3249 3250 On the surface, Ragel scanners are similar to those defined by Lex. Though 3251 there is a key distinguishing feature: patterns may be arbitrary Ragel 3252 expressions and can therefore contain embedded code. With a Ragel-based scanner 3253 the user need not wait until the end of a pattern before user code can be 3254 executed. 3255 3256 Scanners can be used to process sub-languages, as well as for tokenizing 3257 programming languages. In the following example a scanner is used to tokenize 3258 the contents of a header field. 3259 3260 \begin{inline_code} 3261 \begin{verbatim} 3262 word = [a-z]+; 3263 head_name = 'Header'; 3264 3265 header := |* 3266 word; 3267 ' '; 3268 '\n' => { fret; }; 3269 *|; 3270 3271 main := ( head_name ':' @{ fcall header; } )*; 3272 \end{verbatim} 3273 \end{inline_code} 3274 \verbspace 3275 3276 The scanner construction has a purpose similar to the longest-match kleene star 3277 operator \verb|**|. The key 3278 difference is that a scanner is able to backtrack to match a previously matched 3279 shorter string when the pursuit of a longer string fails. For this reason the 3280 scanner construction operator is not a pure state machine construction 3281 operator. It relies on several variables that enable it to backtrack and make 3282 pointers to the matched input text available to the user. For this reason 3283 scanners must be immediately instantiated. They cannot be defined inline or 3284 referenced by another expression. Scanners must be jumped to or called. 3285 3286 Scanners rely on the \verb|ts|, \verb|te| and \verb|act| 3287 variables to be present so that they can backtrack and make pointers to the 3288 matched text available to the user. If input is processed using multiple calls 3289 to the execute code then the user must ensure that when a token is only 3290 partially matched that the prefix is preserved on the subsequent invocation of 3291 the execute code. 3292 3293 The \verb|ts| variable must be defined as a pointer to the input data. 3294 It is used for recording where the current token match begins. This variable 3295 may be used in action code for retrieving the text of the current match. Ragel 3296 ensures that in between tokens and outside of the longest-match machines that 3297 this pointer is set to null. In between calls to the execute code the user must 3298 check if \verb|ts| is set and if so, ensure that the data it points to is 3299 preserved ahead of the next buffer block. This is described in more detail 3300 below. 3301 3302 The \verb|te| variable must also be defined as a pointer to the input data. 3303 It is used for recording where a match ends and where scanning of the next 3304 token should begin. This can also be used in action code for retrieving the 3305 text of the current match. 3306 3307 The \verb|act| variable must be defined as an integer type. It is used for 3308 recording the identity of the last pattern matched when the scanner must go 3309 past a matched pattern in an attempt to make a longer match. If the longer 3310 match fails it may need to consult the \verb|act| variable. In some cases, use 3311 of the \verb|act| 3312 variable can be avoided because the value of the current state is enough 3313 information to determine which token to accept, however in other cases this is 3314 not enough and so the \verb|act| variable is used. 3315 3316 When the longest-match operator is in use, the user's driver code must take on 3317 some buffer management functions. The following algorithm gives an overview of 3318 the steps that should be taken to properly use the longest-match operator. 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 3325 token to be preserved ahead of the buffer on the next invocation of the execute 3326 code. 3327 \begin{itemize} 3328 \item Shift the data beginning at \verb|ts| and ending at \verb|pe| to the 3329 beginning of the input buffer. 3330 \item Reset \verb|ts| to the beginning of the buffer. 3331 \item Shift \verb|te| by the distance from the old value of \verb|ts| 3332 to the new value. The \verb|te| variable may or may not be valid. There is 3333 no way to know if it holds a meaningful value because it is not kept at null 3334 when it is not in use. It can be shifted regardless. 3335 \end{itemize} 3336 \item Read another block of data into the buffer, immediately following any 3337 preserved data. 3338 \item Run the scanner on the new data. 3339 \end{itemize} 3340 3341 Figure \ref{preserve_example} shows the required handling of an input stream in 3342 which a token is broken by the input block boundaries. After processing up to 3343 and including the t'' of characters'', the prefix of the string token must be 3344 retained and processing should resume at the e'' on the next iteration of 3345 the execute code. 3346 3347 If one uses a large input buffer for collecting input then the number of times 3348 the shifting must be done will be small. Furthermore, if one takes care not to 3349 define tokens that are allowed to be very long and instead processes these 3350 items using pure state machines or sub-scanners, then only a small amount of 3351 data will ever need to be shifted. 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 3364 matched token (a). The data of the partially matched token 3365 must be preserved ahead of the new data on the next invocation (b).} 3366 \label{preserve_example} 3367 \end{figure} 3368 3369 Since scanners attempt to make the longest possible match of input, patterns 3370 such as identifiers require one character of lookahead in order to trigger a 3371 match. In the case of the last token in the input stream the user must ensure 3372 that the \verb|eof| variable is set so that the final token is flushed out. 3373 3374 An 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 3430 In addition to supporting the construction of state machines using regular 3431 languages, Ragel provides a way to manually specify state machines using 3432 state charts. The comma operator combines machines together without any 3433 implied transitions. The user can then manually link machines by specifying 3434 epsilon transitions with the \verb|->| operator. Epsilon transitions are drawn 3435 between the final states of a machine and entry points defined by labels. This 3436 makes it possible to build machines using the explicit state-chart method while 3437 making minimal changes to the Ragel language. 3438 3439 An interesting feature of Ragel's state chart construction method is that it 3440 can be mixed freely with regular expression constructions. A state chart may be 3441 referenced from within a regular expression, or a regular expression may be 3442 used in the definition of a state chart transition. 3443 3444 \subsection{Join} 3445 3446 \verb|expr , expr , ...| 3447 \verbspace 3448 3449 Join a list of machines together without 3450 drawing any transitions, without setting up a start state, and without 3451 designating any final states. Transitions between the machines may be specified 3452 using labels and epsilon transitions. The start state must be explicity 3453 specified with the start'' label. Final states may be specified with an 3454 epsilon transition to the implicitly created final'' state. The join 3455 operation allows one to build machines using a state chart model. 3456 3457 \subsection{Label} 3458 3459 \verb|label: expr| 3460 \verbspace 3461 3462 Attaches a label to an expression. Labels can be 3463 used as the target of epsilon transitions and explicit control transfer 3464 statements such as \verb|fgoto| and \verb|fnext| in action 3465 code. 3466 3467 \subsection{Epsilon} 3468 3469 \verb|expr -> label| 3470 \verbspace 3471 3472 Draws an epsilon transition to the state defined 3473 by \verb|label|. Epsilon transitions are made deterministic when join 3474 operators are evaluated. Epsilon transitions that are not in a join operation 3475 are made deterministic when the machine definition that contains the epsilon is 3476 complete. See Section \ref{labels} for information on referencing labels. 3477 3478 \subsection{Simplifying State Charts} 3479 3480 There are two benefits to providing state charts in Ragel. The first is that it 3481 allows us to take a state chart with a full listing of states and transitions 3482 and simplify it in selective places using regular expressions. 3483 3484 The state chart method of specifying parsers is very common. It is an 3485 effective programming technique for producing robust code. The key disadvantage 3486 becomes clear when one attempts to comprehend a large parser specified in this 3487 way. These programs usually require many lines, causing logic to be spread out 3488 over large distances in the source file. Remembering the function of a large 3489 number of states can be difficult and organizing the parser in a sensible way 3490 requires discipline because branches and repetition present many file layout 3491 options. This kind of programming takes a specification with inherent 3492 structure such as looping, alternation and concatenation and expresses it in a 3493 flat form. 3494 3495 If we could take an isolated component of a manually programmed state chart, 3496 that is, a subset of states that has only one entry point, and implement it 3497 using regular language operators then we could eliminate all the explicit 3498 naming of the states contained in it. By eliminating explicitly named states 3499 and replacing them with higher-level specifications we simplify a state machine 3500 specification. 3501 3502 For example, sometimes chains of states are needed, with only a small number of 3503 possible characters appearing along the chain. These can easily be replaced 3504 with a concatenation of characters. Sometimes a group of common states 3505 implement a loop back to another single portion of the machine. Rather than 3506 manually duplicate all the transitions that loop back, we may be able to 3507 express the loop using a kleene star operator. 3508 3509 Ragel allows one to take this state map simplification approach. We can build 3510 state machines using a state map model and implement portions of the state map 3511 using regular languages. In place of any transition in the state machine, 3512 entire sub-machines can be given. These can encapsulate functionality 3513 defined elsewhere. An important aspect of the Ragel approach is that when we 3514 wrap up a collection of states using a regular expression we do not lose 3515 access to the states and transitions. We can still execute code on the 3516 transitions that we have encapsulated. 3517 3518 \subsection{Dropping Down One Level of Abstraction} 3519 \label{down} 3520 3521 The second benefit of incorporating state charts into Ragel is that it permits 3522 us to bypass the regular language abstraction if we need to. Ragel's action 3523 embedding operators are sometimes insufficient for expressing certain parsing 3524 tasks. In the same way that is useful for C language programmers to drop down 3525 to assembly language programming using embedded assembler, it is sometimes 3526 useful for the Ragel programmer to drop down to programming with state charts. 3527 3528 In the following example, we wish to buffer the characters of an XML CDATA 3529 sequence. The sequence is terminated by the string \verb|]]>|. The challenge 3530 in our application is that we do not wish the terminating characters to be 3531 buffered. An expression of the form \verb|any* @buffer :>> ']]>'| will not work 3532 because the buffer will always contain the characters \verb|]]| on the end. 3533 Instead, what we need is to delay the buffering of \hspace{0.25mm} \verb|]| 3534 characters until a time when we 3535 abandon the terminating sequence and go back into the main loop. There is no 3536 easy way to express this using Ragel's regular expression and action embedding 3537 operators, and so an ability to drop down to the state chart method is useful. 3538 3539 % GENERATE: dropdown 3540 % OPT: -p 3541 % %%{ 3542 % machine dropdown; 3543 \begin{inline_code} 3544 \begin{verbatim} 3545 action bchar { buff( fpc ); } # Buffer the current character. 3546 action bbrack1 { buff( "]" ); } 3547 action bbrack2 { buff( "]]" ); } 3548 3549 CDATA_body = 3550 start: ( 3551 ']' -> one | 3552 (any-']') @bchar ->start 3553 ), 3554 one: ( 3555 ']' -> two | 3556 [^\]] @bbrack1 @bchar ->start 3557 ), 3558 two: ( 3559 '>' -> final | 3560 ']' @bbrack1 -> two | 3561 [^>\]] @bbrack2 @bchar ->start 3562 ); 3563 \end{verbatim} 3564 \end{inline_code} 3565 % main := CDATA_body; 3566 % }%% 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 3578 Many communication protocols contain variable-length fields, where the length 3579 of the field is given ahead of the field as a value. This 3580 problem cannot be expressed using regular languages because of its 3581 context-dependent nature. The prevalence of variable-length fields in 3582 communication protocols motivated us to introduce semantic conditions into 3583 the Ragel language. 3584 3585 A semantic condition is a block of user code that is interpreted as an 3586 expression and evaluated immediately 3587 before a transition is taken. If the code returns a value of true, the 3588 transition may be taken. We can now embed code that extracts the length of a 3589 field, then proceed to match$n$data values. 3590 3591 % GENERATE: conds1 3592 % OPT: -p 3593 % %%{ 3594 % machine conds1; 3595 % number = digit+; 3596 \begin{inline_code} 3597 \begin{verbatim} 3598 action rec_num { i = 0; n = getnumber(); } 3599 action test_len { i++ < n } 3600 data_fields = ( 3601 'd' 3602 [0-9]+ %rec_num 3603 ':' 3604 ( [a-z] when test_len )* 3605 )**; 3606 \end{verbatim} 3607 \end{inline_code} 3608 % main := data_fields; 3609 % }%% 3610 % END GENERATE 3611 3612 \begin{center} 3613 \includegraphics[scale=0.55]{conds1} 3614 \end{center} 3615 \graphspace 3616 3617 The Ragel implementation of semantic conditions does not force us to give up the 3618 compositional property of Ragel definitions. For example, a machine that tests 3619 the length of a field using conditions can be unioned with another machine 3620 that accepts some of the same strings, without the two machines interfering with 3621 one another. The user need not be concerned about whether or not the result of the 3622 semantic condition will affect the matching of the second machine. 3623 3624 To see this, first consider that when a user associates a condition with an 3625 existing transition, the transition's label is translated from the base character 3626 to its corresponding value in the space that represents condition$c$true''. Should 3627 the determinization process combine a state that has a conditional transition 3628 with another state that has a transition on the same input character but 3629 without a condition, then the condition-less transition first has its label 3630 translated into two values, one to its corresponding value in the space that 3631 represents condition$c$true'' and another to its corresponding value in the 3632 space that represents condition$c\$ false''. It
3633 is then safe to combine the two transitions. This is shown in the following
3634 example.  Two intersecting patterns are unioned, one with a condition and one
3635 without. The condition embedded in the first pattern does not affect the second
3636 pattern.
3637
3638 % GENERATE: conds2
3639 % OPT: -p
3640 % %%{
3641 % machine conds2;
3642 % number = digit+;
3643 \begin{inline_code}
3644 \begin{verbatim}
3645 action test_len { i++ < n }
3646 action one { /* accept pattern one */ }
3647 action two { /* accept pattern two */ }
3648 patterns =
3649     ( [a-z] when test_len )+ %one |
3650     [a-z][a-z0-9]* %two;
3651 main := patterns '\n';
3652 \end{verbatim}
3653 \end{inline_code}
3654 % }%%
3655 % END GENERATE
3656
3657 \begin{center}
3658 \includegraphics[scale=0.55]{conds2}
3659 \end{center}
3660 \graphspace
3661
3662 There are many more potential uses for semantic conditions. The user is free to
3663 use arbitrary code and may therefore perform actions such as looking up names
3664 in dictionaries, validating input using external parsing mechanisms or
3665 performing checks on the semantic structure of input seen so far. In the
3666 next section we describe how Ragel accommodates several common parser
3667 engineering problems.
3668
3669 \vspace{10pt}
3670
3671 \noindent {\large\bf Note:} The semantic condition feature works only with
3672 alphabet types that are smaller in width than the \verb|long| type. To
3673 implement semantic conditions Ragel needs to be able to allocate characters
3674 from the alphabet space. Ragel uses these allocated characters to express
3675 "character C with condition P true" or "C with P false." Since internally Ragel
3676 uses longs to store characters there is no room left in the alphabet space
3677 unless an alphabet type smaller than long is used.
3678
3680
3681 There are a few strategies for implementing lookahead in Ragel programs.
3682 Leaving actions, which are described in Section \ref{out-actions}, can be
3683 used as a form of lookahead.  Ragel also provides the \verb|fhold| directive
3684 which can be used in actions to prevent the machine from advancing over the
3685 current character. It is also possible to manually adjust the current character
3686 position by shifting it backwards using \verb|fexec|, however when this is
3687 done, care must be taken not to overstep the beginning of the current buffer
3688 block. In both the use of \verb|fhold| and \verb|fexec| the user must be
3689 cautious of combining the resulting machine with another in such a way that the
3690 transition on which the current position is adjusted is not combined with a
3691 transition from the other machine.
3692
3693 \section{Parsing Recursive Language Structures}
3694
3695 In general Ragel cannot handle recursive structures because the grammar is
3696 interpreted as a regular language. However, depending on what needs to be
3697 parsed it is sometimes practical to implement the recursive parts using manual
3698 coding techniques. This often works in cases where the recursive structures are
3699 simple and easy to recognize, such as in the balancing of parentheses
3700
3701 One approach to parsing recursive structures is to use actions that increment
3702 and decrement counters or otherwise recognize the entry to and exit from
3703 recursive structures and then jump to the appropriate machine defnition using
3704 \verb|fcall| and \verb|fret|. Alternatively, semantic conditions can be used to
3705 test counter variables.
3706
3707 A more traditional approach is to call a separate parsing function (expressed
3708 in the host language) when a recursive structure is entered, then later return
3709 when the end is recognized.
3710
3711 \end{document}
`