さて、前日に字句解析した結果を構文解析器に入力することで構文解析をしましょう。
言語実装をするときの大きな山の1つが構文解析器の実装です。
字句解析同様に、一から実装するということはせず、ライブラリを利用します。
RubyにはraccというLALR(1)パーサージェネレーターが付属しているので、これを使います。
yaccに似た書式なので、yaccを使ったことがある方ならば、ある程度雰囲気で読めるかと思います。
yaccもraccも使ったことがない場合は、以下のオンラインマニュアルが一番詳しくまとまっているので、以下の記事を読む前に一読することをおすすめします。
経験的に構文解析ルールを一気に書くと、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 メソッドの実行を行います。