Ragel 入門： 簡単な使い方から JSON パーサまで

$ wget http://www.cs.queensu.ca/~thurston/ragel/ragel-6.0.tar.gz
$ tar xzf ragel-6.0.tar.gz
$ cd ragel-6.0/
$ ./configure --prefix=/usr/local
$ make
$ sudo make install
$ which ragel
/usr/local/bin/ragel
$ ragel -v
Ragel State Machine Compiler version 6.0 January 2008
Copyright (c) 2001-2007 by Adrian Thurston

$ sudo port install graphviz

{{*%%{*}}

  ## ステートマシンの名前
  {{*machine ex1;*}}

  ## 文法定義
  {{*main := ('+' | '-')? [0-9]+ ('.' [0-9]+)? ;*}}

{{*}%%*}}

### Ragel でコンパイル
$ ragel -Vp ex1.rl > ex1.dot
### Graphviz で画像ファイルに変換
$ dot -Tpng ex1.dot > ex1.png

%%{

  ## ステートマシンの名前
  machine ex2;

  {{*## 別名の定義*}}
  {{*sign = '+' | '-';*}}
  {{*d    = [0-9];*}}
  
  ## 文法定義
  main := {{*sign*}}? d+ ('.' {{*d*}}+)? ;

}%%

%%{

  ## ステートマシンの名前
  machine ex3;

  ## 別名の定義
  sign = '+' | '-';
  #d    = [0-9];

  ## アクションの定義
  ##  (アクションとは、パターンにマッチしたとき実行される処理のこと)
  {{*action on_sign {*}}
    ## 「fc」は現在読み込んでいる文字のことであり、
    ## Ragel によって「data[p]」に展開される。
    ## (「data」と「p」については後述)
    sign_char = {{*fc*}}
    puts "*** on_sign: sign_char=#{sign_char.inspect}" if $DEBUG
  {{*}*}}
  {{*action on_int {*}}    # 整数部のアクション
    ch = {{*fc*}}
    puts "*** on_integer: ch=#{ch.inspect}" if $DEBUG
    val = val * 10 + (ch - ?0)
  {{*}*}}
  {{*action on_float {*}}  # 小数部のアクション
    ch = {{*fc*}}
    puts "*** on_float: ch=#{ch.inspect}" if $DEBUG
    e = 0.1 * e
    val += e * (ch - ?0)
  {{*}*}}
  
  ## 文法定義において、アクション名を指定する。
  main := sign? {{*@on_sign*}} digit+ {{*@on_int*}} ('.' digit+)? {{*@on_float*}} ;

}%%

class Ex3Scanner

  def initialize
    ## ステートマシンに必要なデータを生成する
    {{*%% write data;*}}
  end

  def scan(input)
    ## 入力文字列をバイトの配列に変換する。
    ## (Ragel では 1 バイトずつ読んで状態遷移するため。)
    ## なお「data」という変数名は Ragel により決めうち。
    {{*data = input.unpack('c*')*}}

    ## アクションで使う変数
    sign_char = nil
    val = 0
    e = 1.0

    ## ステートマシンを初期化する
    ##  (Ragel により
    ##      p ||= 0              # 現在位置 (pointer)
    ##      pe ||= data.length   # 終了位置 (end pointer)
    ##      cs = ex3_start       # 現在の状態 (current state)
    ##   に展開される)
    {{*%% write init;*}}
    
    ## ステートマシンの実行
    {{*%% write exec;*}}

    ## エラーチェック
    ##  (cs は現在の状態を表す番号、
    ##   ext3_first_final() は受理状態を表す番号のうち
    ##   最も小さいもの (今回なら 4) を返す。)
    unless {{*cs >= ex3_first_final*}}  # 受理状態でなければエラー
      raise "** syntax error (p=#{p}, data[p]='#{data[p].chr}')"
    end

    ## 解析した値を返す
    return sign_char == ?- ? -val : val
  end

end

if $0 == __FILE__
  scanner = Ex3Scanner.new
  while line = gets()
    line.chomp!
    val = scanner.scan(line)
    puts "val=#{val.inspect}"
    puts "OK."
  end
end

$ ragel -R ex3.rl     # ex3.rl から ex3.rb を生成
$ ruby ex3.rb
-123
val=-123
OK.
3.14
val=3.14
OK.
123daa!
ex3.rb:277:in `scan': ** syntax error (p=3, data[p]='d') (RuntimeError)
        from ex3.rb:290

%%{
    main := |*
       {{/pattern1/}}  {  {{/action1/}}  };
       {{/pattern2/}}  {  {{/action2/}}  };
       {{/pattern3/}}  {  {{/action3/}}  };
    *|;
}%%

%%{

  ## ステートマシンの名前
  machine ex4;

  ## 別名の定義
  sign = '+' | '-';

  ## 文法定義
  main := {{*|**}}

    ## 空白
    {{*space+ {*}}
      ## 読み飛ばす
    {{*};*}}

    ## 整数
    {{*sign? digit+ {*}}
      {{*token = :INT*}}
      {{*fbreak;*}}        # 状態遷移のループを抜ける
    {{*};*}}

    ## 小数
    {{*sign? digit+ '.' digit+ => {*}}
      {{*token = :FLOAT*}}
      {{*fbreak;*}}        # 状態遷移のループを抜ける
    {{*};*}}

    ## 識別子
    {{*[a-zA-Z_] [a-zA-Z0-9_]* {*}}
      {{*token = :IDENT*}}
      {{*fbreak;*}}        # 状態遷移のループを抜ける
    {{*};*}}
  
  {{**|;*}}

}%%


class Ex4Scanner

  def initialize
    ## ステートマシンのデータ
    %% write data;
  end

  def scan_all(input)
    ## 入力文字列をバイトの配列に変換する。
    ## なお「data」という変数名は Ragel により決めうち。
    data = input.unpack('c*')

    ## ステートマシンの初期化
    ##  (Ragel により
    ##      p ||= 0              # 現在位置 (pointer)
    ##      pe ||= data.length   # 終了位置 (end pointer)
    ##      cs = ex4_start       # 現在の状態 (current state)
    ##      ts = nil             # トークン開始位置 (token start)
    ##      te = nil             # トークン終了位置 (token end)
    ##      act = 0              # バックトラックで使う変数
    ##   に展開される)
    %% write init;

    ## 変数 eof を設定する (必須)
    {{*eof = data.length*}}      # eof = pe でもよい

    ## メインループ
    while true
      token = nil

      ## ステートマシンの実行
      %% write exec;

      ## エラーチェック
      unless cs >= ex4_first_final
        s = data[p].chr
        raise "** syntax error (cs=#{cs}, p=#{p}, data[p]='#{s}')"
      end

      ## 入力の終わりならループを抜ける
      break unless token

      ## トークンを表示する
      ## (ts と te はトークンの開始位置と終了位置を表す)
      token_str = {{*input[ts...te]*}}
      puts "** token=#{token.inspect}, str=#{token_str.inspect}"
    end

  end

end


if $0 == __FILE__
  scanner = Ex4Scanner.new
  while line = gets()
    scanner.scan_all(line)
    puts "OK."
  end
end

$ ragel -R ex4.rl     # ex4.rl をコンパイルして ex4.rb を生成
$ ruby ex4.rb
123  -3.14   foo
** token=:INT, str="123"
** token=:FLOAT, str="-3.14"
** token=:IDENT, str="foo"
OK.
func(123)
** token=:IDENT, str="func"
ex4.rb:418:in `scan_all': ** syntax error (cs=0, p=4, data[p]='(') (RuntimeError)
        from ex4.rb:438

%%{

    ## ステートマシンの名前 (接頭辞)
    machine json;

    ## 変数 cs の頭に「@」をつける
    access @;

    ## 変数 p, pe, eof も同様
    variable p   @p;
    variable pe  @pe;
    variable eof @eof;

    ## 別名の定義
    sign = ('+' | '-');

    ## 文法定義
    main :=  |*

        ## 空白類を読み飛ばす
        space+ {     # (「space」は「[ \t\v\f\n\r]」の別名)
        };

        ## '//' から改行まで読み飛ばす (行コメント)
        '//' [^\n]* '\n' {
        };

        ## '/*' から '*/' まで読み飛ばす (範囲コメント)
        '/*' any* :>> '*/' {   # 「any」は任意の文字を表す
        };

        ## 小数 (float)
        sign? [0-9]+ '.' [0-9]+ {
            @token = :FLOAT;
            fbreak;
        };

        ## 10進数 (decimal)
        sign? [0-9]+ {
            @token = :DECIMAL;
            fbreak;
        };

        ## 16進数 (hexadecimal)
        sign? '0x' [0-9a-fA-F]+ {
            @token = :HEXADEC;
            fbreak;
        };

        ## 予約語 (keyword)
        ##  (末尾の i は大文字小文字を区別しないことを表す)
        'true'i {
            @token = :TRUE;
            fbreak;
        };
        'false'i {
            @token = :FALSE;
            fbreak;
        };
        'null'i {
            @token = :NULL;
            fbreak;
        };

        ## 識別子 (identifier)
        [a-zA-Z_] [a-zA-Z0-9_]* {
            @token = :IDENT;
            fbreak;
        };

        ## 文字列 (string)
        dqchar = [^"\\] | ( '\\' any );    #"
        '"' . dqchar* . '"' {
            @token = :STRING;
            ## 先頭と末尾の '"' を取り除く
            ## ("\n" や "\uXXX" のデコード処理は省略)
            @token_str = @input[(@ts+1)...(@te-1)]
            fbreak;
        };

        ## 記号 (symbol)
        [\{\}\[\]:,]  {
            @token = fc;
            fbreak;
        };

    *|;

}%%


##
## 字句解析クラス
##
## 使い方:
##   scanner = JsonScanner.new(File.read('file.json'))
##   while token = scanner.scan()
##     token_str = scanner.token_str
##     puts "** token=#{token.inspect}, str=#{token_str.inspect}
##   end
##
class JsonScanner

  def initialize(input=nil)
    ## ステートマシンのデータを生成
    %% write data;
    ## 文字列があればそれを使って初期化
    setup(input) if input
  end

  def setup(input)
    @input = input
    ## 入力文字列をバイトの配列に変換
    @data = input ? input.unpack('c*') : []
    ## ステートマシンに必要な変数を初期化
    %% write init;
    #@p  ||= 0;
    #@pe ||= @data.length;
    #@cs  = json_start
    #@ts  = nil
    #@te  = nil
    #@act = 0
    @eof = @pe;
  end
  attr_reader :cs, :p, :pe, :eof, :ts, :te, :act
  attr_reader :input, :token, :token_str

  def scan
    @token = @token_str = nil
    ## ステートマシンを実行
    %% write exec;
    ## エラーチェック
    handle_error() unless @cs >= self.json_first_final
    ## トークンの文字列を設定する
    @token_str = @input[@ts...@te] if !@token_str && @token
    ## トークンを返す
    return @token
  end

  def handle_error
    if @cs == self.json_error   ## 不正な文字があった場合
      ch = @data[@p]
      s = [ch].pack('c')
      _raise "#{s.dump}: invalid character."
    else
      s = @input[@ts..-1]
      case s
      when /\A"/     ## 文字列が閉じるまえに EOF になった場合
        _raise "string literal is not closed by '\"'."
      when /\A\/\*/  ## 範囲コメントが閉じずに EOF になった場合
        _raise "region comment is not closed by '*/'."
      when /\A\/\//  ## 行コメントが改行で終わらずに EOF になった場合
        ## これはエラーにしなくてよい
      end
    end
  end
  private :handle_error

  def _raise(mesg)
    linenum, column = get_position()
    err = StandardError.new("#{linenum}:#{column}: #{mesg}")
    err.set_backtrace(caller())
    raise err
  end
  private :_raise

  def get_position(index=nil)
    index ||= @ts
    s = @input[0..index]
    linenum = s.count("\n") + 1
    column  = s.length - (s.rindex("\n") || -1) - 1
    return linenum, column
  end

end


## 字句解析クラスの使い方
if __FILE__ == $0
  input = ARGF.read()
  scanner = JsonScanner.new(input)
  while token = scanner.scan()
    token_str = scanner.token_str
    puts "** token='#{token.chr}', token_str=#{token_str.dump}"
  end
end

require 'json_scanner'

##
## 構文解析クラス
##
## 使い方:
##   parser = JsonParser.new
##   obj = parser.parse(File.read('file.json'))
##   p obj
##
class JsonParser

  def initialize()
    @scanner = JsonScanner.new
  end

  def setup(input)
    @scanner.setup(input)
  end

  def parse(input)
    setup(input)
    token = @scanner.scan()
    unless token == ?{
      _raise "not started with '{'."
    end
    obj = parse_object()
    token = @scanner.scan()
    unless token.nil?
      s = @scanner.token_str
      _raise "EOF expected but got #{s.inspect}."
    end
    return obj
  end

  def parse_object()
    #assert @scanner.token == ?{
    obj = {}
    while true
      ## key
      token = @scanner.scan()
      if token == ?}
        if obj.empty?  # '}' が '{' の直後なら空 Hash を返す
          break
        else           # '}' が ',' の直後なら文法エラー
          _raise "extra ',' found before '}'."
        end
      end
      unless token == :STRING || token == :IDENT
        _raise "object key should be string."
      end
      key = @scanner.token_str
      ## ':'
      token = @scanner.scan()
      unless token == ?:
        _raise "':' expected."
      end
      ## value
      token = @scanner.scan()
      value = parse_value(token)
      obj[key] = value
      ## ',' or '}'
      token = @scanner.scan()
      next  if token == ?,
      break if token == ?}
      _raise "object is not closed by '}'."
    end
    return obj
  end

  def parse_array()
    #assert @scanner.token == ?[
    arr = []
    while true
      ## value
      token = @scanner.scan()
      if token == ?]
        if arr.empty?  # ']' が '{' の直後なら空 Array を返す
          break
        else           # ']' が ',' の直後なら文法エラー
          _raise "extra ',' found before ']'."
        end
      end
      value = parse_value(token)
      arr << value
      ## ',' or ']'
      token = @scanner.scan()
      next  if token == ?,
      break if token == ?]
      _raise "array is not closed by ']'."
    end
    return arr
  end

  def parse_value(token)
    case token
    when :STRING  ; return @scanner.token_str
    when :DECIMAL ; return @scanner.token_str.to_i
    when :FLOAT   ; return @scanner.token_str.to_f
    when :HEXADEC ; return Integer(@scanner.token_str)
    when ?{       ; return parse_object()
    when ?[       ; return parse_array()
    when :TRUE    ; return true
    when :FALSE   ; return false
    when :NULL    ; return nil
    when :IDENT
      s = @scanner.token_str
      _raise "#{s}: unexpected identifier."
    when nil
      _raise "unexpected EOF."
    else
      s = @scanner.token_str
      _raise "#{s.dump}: unexpected token."
    end
  end

  def _raise(mesg)
    linenum, column = @scanner.get_position()
    err = StandardError.new("#{linenum}:#{column}: #{mesg}")
    err.set_backtrace(caller())
    raise err
  end
  private :_raise

end


## 構文解析クラスの使い方
if __FILE__ == $0
  require 'pp'
  input = ARGF.read()
  parser = JsonParser.new
  obj = parser.parse(input)
  pp obj
end