########################################
Ragel
########################################

Ragel 是一个基于状态机的字符串解析工具

构造状态机
****************************************

Ragel 状态机声明
========================================

Ragel 的输入文件一般后缀名为 rl，其内容为包含了状态机声明的源文件。Ragel （可能）会在状态机声明的原地生成代码。输入文件中可以包含任意数量的状态机声明，单行的状态机声明以 %% 开头，多行状态机声明被包含到 %%{}%% 中。

Ragel 会自动识别注释或字符串中的 %%，因此无需在其中进行反转义。Ragel 不会进行预编译，因此 include、define 等不会被展开，因此也没法使用 #if 禁用状态机代码。

.. code-block:: ragel

   #include <string.h>
   #include <stdio.h>

   %%{
      machine foo;
      main :=
         ( 'foo' | 'bar' )
         0 @{ res = 1; };
   }%%
   %% write data;

   int main( int argc, char **argv ){
      int cs, res = 0;
      if ( argc > 1 ) {
         char *p = argv[1];
         char *pe = p + strlen(p) + 1;
         %% write init;
         %% write exec;
      }
      printf("result = %i\n", res );
      return 0;
   }

上面的代码分别用到了块声明和行声明。功能是检查字符串是否为 foo 或者 bar

具名 Ragel 代码块
========================================

**machine fs_name;**

**machine** 语句被用于声明一个 FSM，其必须位于 FSM 声明块的第一行，如果没有指定 machine，那么它会使用上一个 machine，如果根本没有 machine 定义，将会抛出错误。由于 include，此语句的作用范围可能会扩散到其它文件

**<name> = <expression>**

声明一个 FSM 表达式。name 之后被其它表达式引用。但是声明本身不会导致生成任何代码。状态机只会在被实例化时才会生成代码，这要求此声明被其它实例化语句引用。

**<name> := <expression>;**

此语句用于实例化 FSM 语句，将会导致生成一系列代码用来表示 expression。生成的语句根据 name 被放入数据部分。如果被实例化的是 main，那么此语句将会被视为 FSM 的初始状态，并通过 *write init* 写入 cs 变量中。如果没有 main 被实例化，那么最后一个实例化的 FSM 将会作为机器的初始状态。

在执行循环之外，通过将入口点分配到 cs 变量可以将控制移交到其它状态机。在执行循环之内，可以通过 fcall, fgoto 或 fnext 控制执行

**include FsmName "inputfile.rl";**

用于包含另一个状态机， FsmName 和 inputfile.rl 都是可选的，如果两者都指定，那么 inputfile.rl 将会被是为名为 FsmName 的状态机。

**import "inputfile.h";**

Ragel 将形式如下的语句视为状态机定义并将其导入：

- name ’=’ number
- name ’=’ lit_string
- ’define’ name number
- ’define’ name lit_string

Ragel 从当前文件位置搜索导入的文件，额外的路径可以通过 *-I* 选项添加

Ragel 块词法规则
========================================

在状态机中，遵顼以下语法规则

- 行注释为以 # 开头
- ``''``, ``""``, ``//``, ``[]`` 被是为字符串的分隔符。其中允许 *\0, \a, \b, \t, \n, \v, \f, \r* 这些转义字符。使用行尾的反斜杠可以将多行语句合并到一行
- ``{}`` 中的代码被视为宿主语言代码，并被视为一个 action。其中遵循宿主语言的词法规则
- 模式 *[+-]?[0-9]+* 被视为整数，只有字母表类型是有符号数时才会出现负数。用于标识优先级的数组总是可正可负的
- 模式 *0x[0-9A-Fa-f]+* 被视为一个十六进制整数
- 模式 *[a-zA-Z_][a-zA-Z_0-9]\** 被视为一个标识符
- access, action, alphtype, getkey, write, machine 和 include 是关键字
- [a-zA-Z\_][a-zA-Z_0-9]\* 被视为关键字
- 空白字符可以用来分割 tokens

基本状态机
========================================

基本的机器机是正则表达式，其是构造 FSM 和能够操作的最小单位。

- ``'hello'`` ：关联字面量。产生一个状态机来表示单引号包裹的字符序列（大小写不敏感），5 个字符将会产生 6 种状态，其中可以包含转义序列。 ``''i`` 用来指定大小写敏感的序列
- ``"hello"`` ：与单引号版本相同
- ``[hello]`` ：或是表达式。重复的字符将会被合，并对字符进行排序，上述字符串只产生 e, h, l, o 四个字符的状态机，一共五个状态
- 空串：零长度的状态机，只有一个状态，开始即是结束
- 42 ：数字字面量。产生两个状态，并且只有一个过渡。数字可以是十进制或者十六进制，但是必须要在字母表范围内。其最大值和最小值依宿主语言而定。例如，i386 处理器上 short 类型的字母表允许范围为 -32768-32767
- ``/simple_regex/`` ：正则表达式，其中 . 代表 any, [] 代表字符集，并允许在字符集之前使用 ^ 取反。同样支持带 i 后缀的大小写敏感版本。Ragel 并不支持特别复杂的正则表达式。
- 'a'..'z' ：范围。要求范围大小在字母表内，数字（十进制和十六进制）或者字符都是允许的
- variable_name：查找与 variable_name 相等的状态机定义
- 还包括了一些内建状态机：

   +--------+----------------------------------------------+
   | 状态机 | 作用                                         |
   +========+==============================================+
   | any    | 字母表中的任意字符                           |
   +--------+----------------------------------------------+
   | ascii  | Ascii 字符 0..127                            |
   +--------+----------------------------------------------+
   | extend | Ascii 拓展字符，范围为 -128..127 或者 0..255 |
   +--------+----------------------------------------------+
   | alpha  | [A-Za-z]                                     |
   +--------+----------------------------------------------+
   | digit  | [0-9]                                        |
   +--------+----------------------------------------------+
   | alnum  | [0-9A-Za-z]                                  |
   +--------+----------------------------------------------+
   | lower  | [a-z]                                        |
   +--------+----------------------------------------------+
   | upper  | [A-Z]                                        |
   +--------+----------------------------------------------+
   | xdigit | 16 进制数组 [0-9A-Fa-f]                      |
   +--------+----------------------------------------------+
   | cntrl  | 控制字符 0..31                               |
   +--------+----------------------------------------------+
   | graph  | 可视字符 [!-~]                               |
   +--------+----------------------------------------------+
   | print  | 可打印字符 [ -~]                             |
   +--------+----------------------------------------------+
   | punct  | 标点符号 [!-/:-@[-‘{-~]                      |
   +--------+----------------------------------------------+
   | space  | 空白字符 [\t\v\f\n\r ]                       |
   +--------+----------------------------------------------+
   | zlen   | 长度为零的字符串 ""                          |
   +--------+----------------------------------------------+
   | empty  | ^any                                         |
   +--------+----------------------------------------------+

正则表达式操作
========================================

+--------------+--------------------------------------------------+
| 操作符       | 作用                                             |
+==============+==================================================+
| expr | expr  | 满足两个状态机中的任一个                         |
+--------------+--------------------------------------------------+
| expr & expr  | 同时满足两个表达式的状态机                       |
+--------------+--------------------------------------------------+
| expr - expr  | 满足第一个状态机而不满足第二个状态机             |
+--------------+--------------------------------------------------+
| expr -- expr | 满足第一个状态机而且不包含满足第二个状态机的子串 |
+--------------+--------------------------------------------------+
| expr.expr    | 前半部分满足 expr1，后半部分满足 expr2           |
+--------------+--------------------------------------------------+
| expr*        | expr 后跟任意个 expr                             |
+--------------+--------------------------------------------------+
| expr+        | 相当于 expr.expr*                                |
+--------------+--------------------------------------------------+
| expr?        | expr 可以出现任意次                              |
+--------------+--------------------------------------------------+
| expr {n}     | expr 出现 n 次                                   |
+--------------+--------------------------------------------------+
| expr {,n}    | expr 至多出现 n 次                               |
+--------------+--------------------------------------------------+
| expr {n,}    | expr 至少出现 n 次                               |
+--------------+--------------------------------------------------+
| expr {n,m}   | expr 出现 n...m 次                               |
+--------------+--------------------------------------------------+
| !expr        | 不符合条件的状态机，相当于 any* - expr           |
+--------------+--------------------------------------------------+
| ^expr        | 字符级否定，相当于 any - expr                    |
+--------------+--------------------------------------------------+

可视化
========================================

Ragel 可以使用 -V 选项将状态机输出为 Graphviz 支持的格式，因此能够将状态机可视化。

Action
****************************************

Ragel 允许用户在状态机状态改变时运行自定义 Action。

Action 的声明类似于：

.. code-block:: ragel

   action ActionName {
      // 自定义代码
      count += 1;
   }

action 需要配合 action 操作符使用：

+---------------+-------------------------------+
| 操作符        | 作用                          |
+===============+===============================+
| expr > action | 进入状态机时执行 Action       |
+---------------+-------------------------------+
| expr @ action | 离开状态机时执行 Action       |
+---------------+-------------------------------+
| expr $ action | 在状态机的所有时刻执行 Action |
+---------------+-------------------------------+
| expr % action | 在状态机的最终状态执行 Action |
+---------------+-------------------------------+

例如：

.. code-block:: ragel

   main := lower* @{ cout<<fc<<' '; };

@ 后跟的 action 会在每个字符末尾运行

在 action 中跳转需要使用 *fgoto, fnext, fcall* 语句。在状态机外，可以修改 cs 变量

+---------------+-----------------------------------------------+
| 语句          | 作用                                          |
+===============+===============================================+
| fhold         | 相当于 p--                                    |
+---------------+-----------------------------------------------+
| fexec <expr>  | 设置下一个要处理的字符                        |
+---------------+-----------------------------------------------+
| fgoto <label> | 跳转到一个被 <label> 定义的入口点             |
+---------------+-----------------------------------------------+
| fgoto \*<expr> | 跳转到一个被 <expr> 定义的入口点             |
+---------------+-----------------------------------------------+
| fnext <label> | 将下一个状态设置为 label 定义的入口点         |
+---------------+-----------------------------------------------+
| fnext \*<expr> |                                              |
+---------------+-----------------------------------------------+
| fcall <label> | 推入 target 状态并跳转到 <label> 定义的入口点 |
+---------------+-----------------------------------------------+
| fcall \*<expr> |                                              |
+---------------+-----------------------------------------------+
| fret          | 返回最后一个 fcall 调用的 target 状态         |
+---------------+-----------------------------------------------+
| fbreak        | ++p，保存 target 属性到 cs 并立即跳出循环     |
+---------------+-----------------------------------------------+

代码块可用变量
========================================

+-----------------+----------------------------------+
| 变量            | 作用                             |
+=================+==================================+
| fpc             | 指向当前字符的指针，相当于变量 p |
+-----------------+----------------------------------+
| fc              | 当前字符，相当于 \*p             |
+-----------------+----------------------------------+
| fcurs           | 代表当前状态的只读整数           |
+-----------------+----------------------------------+
| ftargs          | 代表目标状态的只读整数           |
+-----------------+----------------------------------+
| fentry(<label>) | 从 label 拿到代表入口点的整数    |
+-----------------+----------------------------------+

对宿主语言的接口
****************************************

Ragel 是非常灵活的，可以在任意函数或者循环中生成无依赖的代码。用户需要初始化必要的变量，包括当前状态和指向输入流的指针。控制输入处理也是可能的，用户可以在处理的任何阶段打断并返回。对于 C, D, Go 三种语言来讲，Ragel 可以生成运行非常快的状态机代码。

Ragel 既可以在一个代码块中解析输入，也能用于解析来自文件或者套接字中的流数据。但是在解析字节流时不要打断输入流，而且不要使用哪些移动后续指针会失效的指针。而且流指针只能前进，不能后退。

Ragel 使用的变量
========================================

在使用 Ragel 之前至少要声明 *cs*, *p* 和 *pe* 三个变量，对于 Go, Java 和 Ruby， *data* 变量必须声明。如果使用了 EOF action，那么也需要声明 *eof* 。如果使用了基于栈的状态机控制语句，那么 *stack* 和 *top* 也需要声明。如果声明了 scanner 变量，那么 *act*, *ts*, *te* 变量也需要声明

+----------------------------+-----------------+----------------------------+
| 变量                       | 数据类型        | 说明                       |
+============================+=================+============================+
| :abbr:`cs (Current State)` | int             | 当前状态                   |
+----------------------------+-----------------+----------------------------+
| p                          | char\*          | 数据指针                   |
+----------------------------+-----------------+----------------------------+
| pe                         | char\*          | 数据末尾指针               |
+----------------------------+-----------------+----------------------------+
| eof                        | char\*          | 文件末尾指针               |
+----------------------------+-----------------+----------------------------+
| data                       | array           | 只有 Go, Java 和 Ruby 才用 |
+----------------------------+-----------------+----------------------------+
| stack                      | stack\<int>     | 用来储存代表当前状态的数字 |
+----------------------------+-----------------+----------------------------+
| act                        | int             |                            |
+----------------------------+-----------------+----------------------------+
| ts                         | char\* 或者 int |                            |
+----------------------------+-----------------+----------------------------+
| te                         | char\*          |                            |
+----------------------------+-----------------+----------------------------+

代码例子
****************************************

这里写一个使用 Ragel 解析的例子：

检查字符串中是否包含 foo
========================================

.. code-block:: ragel

   #include <iostream>
   #include <cstring>

   using namespace std;

   bool hasFoo(string const&  str){
      char const* p = str.c_str();
      char const* pe = p + str.length() + 1;
      int res = 0;
      int cs;
      %%{
         machine foo;
         main := any?.'foo'.any? 0 @{ res = 1;};

         write data;
         write init;
         write exec;
      }%%
      return res;
   }

   int main(int argc, char** argv){
      cout<<hasFoo(argv[1])<<endl;
   }

从此代码中可以知道： *write data* 必须位于 *write init* 之前

当然了，如果只是这样，直接使用正则表达式看起来更加直观。

str2i 函数
========================================

下面我们实现一个将字符串转为整形的函数：

.. code-block:: ragel

   #include <iostream>

   using namespace std;

   int str2i(string const& str) {
      char const*  p  = str.c_str();
      char const*  pe = p + str.length();
      int  cs;
      int  res = 0;
      bool neg = false;
      %%{
         machine str2i;
         write data;
         action see_neg {
               neg = true;
         }
         action add_digit {
               res = res * 10 + (fc - '0');
         }
         main := ('-'@see_neg | '+') ? (digit@add_digit) + '\n';

         write init;
         write exec;
      }%%
      return neg ? -1 * res : res;
   }

   int main(int argc, char** argv) {
      cout << str2i(argv[1]) << endl;
   }

在此代码中可以知道： machine 必须位于整个状态机声明之前。