VBScriptを作ってみる(構文解析編・代入文まで)

さて、前日に字句解析した結果を構文解析器に入力することで構文解析をしましょう。
言語実装をするときの大きな山の1つが構文解析器の実装です。
字句解析同様に、一から実装するということはせず、ライブラリを利用します。

RubyにはraccというLALR(1)パーサージェネレーターが付属しているので、これを使います。
yaccに似た書式なので、yaccを使ったことがある方ならば、ある程度雰囲気で読めるかと思います。
yaccもraccも使ったことがない場合は、以下のオンラインマニュアルが一番詳しくまとまっているので、以下の記事を読む前に一読することをおすすめします。

Racc User Manual

経験的に構文解析ルールを一気に書くと、conflictが大量に発生して辛い思いをすることが多いので、一旦小さなマイルストーンを決めることにします。
まずは、変数宣言と変数代入文が動くところまでを目指します。

具体的には以下のスクリプトを実行できれば良しとします。

Dim a, b
a = 10
b = (a + 1) * 3

' この時点でaに10がbに33が代入されている

VBScriptの文法とにらめっこすることで、以下の構文解析ルールを得ます。

# vim:filetype=ruby

class TinyVbsParser

start program

rule
  program : nl_opt global_statement_list { result = val[1] }

  nl_opt : nl
         |
  nl : NEWLINE nl
     | NEWLINE

  global_statement_list : global_statement { result = AST::Program.new(val[0]) }
                        | global_statement_list global_statement { result = result.add_child(val[1]) }
  global_statement : option_explicit
                   | block_statement

  option_explicit : 'Option' 'Explicit' nl { result = AST::OptionExplicit.new }
  block_statement : var_declartion
                  | inline_statement nl

  var_declartion : 'Dim' var_name other_vars_opt nl { result = AST::Dim.new([val[1]] + val[2]) }
  other_vars_opt : ',' var_name other_vars_opt { result = val[2] + [val[1]] }
                 | { result = [] }
  var_name : extended_id

  inline_statement : assign_statement

  assign_statement : left_expr '=' expr { result = AST::AssignStatement.new(val[0], val[2]) }

  left_expr : qualified_id { result = AST::LeftExpr.new(val[0]) }
  qualified_id : ID        { result = AST::Identifier.new(val[0]) }
  extended_id : safe_keyword_id
              | ID { result = AST::Identifier.new(val[0]) }
  safe_keyword_id : 'Option' { result = AST::Identifier.new(val[0]) }
                  | 'Step' { result = AST::Identifier.new(val[0]) }

  expr : imp_expr
  imp_expr : imp_expr 'Imp' eqv_expr { result = AST::BinaryExpr.new('Imp', val[0], val[2]) }
           | eqv_expr
  eqv_expr : eqv_expr 'Eqv' xor_expr { result = AST::BinaryExpr.new('Eqv', val[0], val[2]) }
           | xor_expr
  xor_expr : xor_expr 'Xor' or_expr { result = AST::BinaryExpr.new('Xor', val[0], val[2]) }
           | or_expr
  or_expr : or_expr 'Or' and_expr { result = AST::BinaryExpr.new('Or', val[0], val[2]) }
          | and_expr
  and_expr : and_expr 'And' not_expr { result = AST::BinaryExpr.new('And', val[0], val[2]) }
           | not_expr
  not_expr : 'Not' compare_expr { result = AST::UnaryExpr.new('Not', val[1]) }
           | compare_expr
  compare_expr : compare_expr '>=' concat_expr { result = AST::BinaryExpr.new('>=', val[0], val[2]) }
               | compare_expr '<=' concat_expr { result = AST::BinaryExpr.new('<=', val[0], val[2]) }
               | compare_expr '>' concat_expr { result = AST::BinaryExpr.new('>', val[0], val[2]) }
               | compare_expr '<' concat_expr { result = AST::BinaryExpr.new('<', val[0], val[2]) }
               | compare_expr '<>' concat_expr { result = AST::BinaryExpr.new('<>', val[0], val[2]) }
               | compare_expr '=' concat_expr { result = AST::BinaryExpr.new('=', val[0], val[2]) }
               | concat_expr
  concat_expr : concat_expr '&' add_expr { result = AST::BinaryExpr.new('&', val[0], val[2]) }
              | add_expr
  add_expr : add_expr '+' mod_expr { result = AST::BinaryExpr.new('+', val[0], val[2]) }
           | add_expr '-' mod_expr { result = AST::BinaryExpr.new('-', val[0], val[2]) }
           | mod_expr
  mod_expr : mod_expr 'Mod' mult_expr { result = AST::BinaryExpr.new('Mod', val[0], val[2]) }
           | mult_expr
  mult_expr : mult_expr '*' unary_expr { result = AST::BinaryExpr.new('*', val[0], val[2]) }
            | mult_expr '/' unary_expr { result = AST::BinaryExpr.new('/', val[0], val[2]) }
            | unary_expr
  unary_expr : '+' exp_expr { result = AST::UnaryExpr.new('+', val[1]) }
             | '-' exp_expr { result = AST::UnaryExpr.new('-', val[1]) }
             | exp_expr
  exp_expr : value '^' exp_expr { result = AST::BinaryExpr.new('^', val[0], val[2]) }
           | value
  value : const_expr
        | left_expr
        | '(' expr ')' { result = val[1] }
  const_expr : int_literal { result = AST::NumberLiteral.new(val[0]) }
             | bool_literal { result = AST::BoolLiteral.new(val[0]) }
             | STRING_LITERAL { result = AST::StringLiteral.new(val[0]) }
             | nothing
  int_literal : INT_LITERAL
              | HEX_LITERAL
              | OCT_LITERAL
  bool_literal : 'True' | 'False'
  nothing : null
          | empty
  null : 'Null' { result = AST::NullLiteral.new }
  empty : 'Empty' { result = AST::EmptyLiteral.new }
end

---- header
require_relative 'ast'
require_relative 'tiny_vbs.rex'

VBScriptでは代入は式ではなく文であるということが理解できていれば、比較的シンプルな構文解析ルールです。

また、要素を還元したときのルール中に AST::Hoge クラスが多く登場しますが、一旦は以下の以下の抽象クラスを継承している具象クラスであるという理解でも問題ないです。
デザインパターンでいうところのインタープリターパターンです。

module AST
  class Node
    def eval(environment)
      raise 'not implemented'
    end
  end

  class Leaf < Node
  end

  class List < Node
    def initialize(children)
      @children = children
    end

    def children
      @children
    end

    def child(index)
      @children[index]
    end

    def add_child(child)
      @children.push(child)
      self
    end

    def add_child_head(child)
      @children.unshift(child)
      self
    end
  end

さて、これで構文解析に必要なものは揃ったので、最後はVBScriptのプログラムを構文解析器に入力する部分を作ればOKです。

program = ARGF.read
parser = TinyVbsParser.new
ast = parser.scan(program)
pp ast

上記のプログラムを実行することで、以下の抽象構文木(AST)を得ることが出来ます。

#<AST::Program:0x00007f7f2a81f280
 @children=
  [#<AST::Dim:0x00007f7f2a81f2f8
    @var_names=
     [#<AST::Identifier:0x00007f7f2a81ff00 @identifier="a">,
      #<AST::Identifier:0x00007f7f2a81f6e0 @identifier="b">]>,
   #<AST::AssignStatement:0x00007f7f2a81ece0
    @children=
     [#<AST::LeftExpr:0x00007f7f2a81f190
       @children=[],
       @identifier=#<AST::Identifier:0x00007f7f2a81f1e0 @identifier="a">>,
      #<AST::NumberLiteral:0x00007f7f2a81edd0 @value=10>]>,
   #<AST::AssignStatement:0x00007f7f2a81da98
    @children=
     [#<AST::LeftExpr:0x00007f7f2a81eb50
       @children=[],
       @identifier=#<AST::Identifier:0x00007f7f2a81eba0 @identifier="b">>,
      #<AST::BinaryExpr:0x00007f7f2a81db10
       @children=
        [#<AST::BinaryExpr:0x00007f7f2a81e038
          @children=
           [#<AST::LeftExpr:0x00007f7f2a81e600
             @children=[],
             @identifier=
              #<AST::Identifier:0x00007f7f2a81e650 @identifier="a">>,
            #<AST::NumberLiteral:0x00007f7f2a81e290 @value=1>],
          @operator="+">,
         #<AST::NumberLiteral:0x00007f7f2a81dc50 @value=3>],
       @operator="*">]>]>

@children で表現されているインスタンス毎の入れ子構造を見ると、正しく構文解析が出来ていることがわかります。

次回はこのASTオブジェクトに対する eval メソッドの実行を行います。