たとえば ((), (), (())) という文字列を入力として与えると
p parse("((), (), (()))")
#=> [[], [], [[]]]
このように入れ子の配列を出力する（入れ子の配列に変換する）パーサを作ります。
入力文字列として使える文字は (, ), ,, 半角スペースの4つだけとします。
いきなり全部やろうとすると大変なので、4つのステップに分けましょう。
以下、「配列」と書いているところは Ruby の配列のイメージで大丈夫です。
- (1)
()をパースできる- 空配列
- (2)
(())や((()))をパースできる- 配列の入れ子
- (3)
(要素, 要素)や(要素, 要素, 要素)をパースできる- 配列の要素のくりかえし
- (4)
((), (()))- 入れ子とくりかえしの組み合わせ
(0) 全体像と字句解析
全体のイメージはこんな感じ。これを育てていきます。
def parse(src)
# ここを書いていく
end
src = "()"
tokens = tokenize(src)
tree = parse(tokens)
p tree
字句解析はこれでOK。
$tokens = nil
def tokenize(src)
src.delete(" ").chars
end
def parse(tokens)
$tokens = tokens
# TODO
end
p parse(tokenize("()"))
たとえば tokenize("( )") の結果は ["(", ")"] になります。今回はスペースはあってもなくても同じなのでここで取り除いてしまいます。
グローバル変数 $tokens というのがありますが、きちんと書くなら次のようにパーサクラスのインスタンス変数になるでしょう。
class Parser
def initialize(tokens)
@tokens = tokens
@pos = 0 # 後で出てくる $pos も同様
end
# ...
end
この記事ではシンプルさを優先してグローバル変数を使っています。「パーサのしくみを知る」のに必要なもの以外のノイズを減らすため。練習用・おためし用の小さなコードなので問題ないでしょう。
(1) 空配列
トークンの列を先頭から順番に見ていって、最初のトークンが (、次のトークンが ) という順番になっていたら空配列であるとみなし、結果として [] を返します。
$tokens = nil
$pos = nil # 現在のカーソル位置
def tokenize(src); src.delete(" ").chars end
# 現在のカーソル位置のトークンを返す
def peek
$tokens[$pos]
end
# "(" から、対応する ")" までをパースする
def parse_array
if peek() == "(" # $toekns[0] をチェック
# 期待したトークンだったらカーソルを進める
$pos += 1
else
raise "$tokens[0] は ( であるはず"
end
if peek() == ")" # $toekns[1] をチェック
$pos += 1
else
raise "$tokens[1] は ) であるはず"
end
# 入力トークン列が ["(", ")"] だったらここまで到達するはず
# → 空配列を返す
[]
end
def parse(tokens)
# トークン列とカーソル位置をリセット
$tokens = tokens
$pos = 0
parse_array()
end
p parse(tokenize("()")) #=> []
( → ) という順番になっているかチェックしているので、たとえば ) や (( のような入力を渡すとパース失敗という結果になります（期待通りに失敗する）。
(2) 入れ子
再帰呼び出しを使います。再帰が出てくるのでここからちょっと難しくなりますね。
$tokens = nil
$pos = nil
def tokenize(src); src.delete(" ").chars end
def peek; $tokens[$pos] end
# "(" と対応する ")" までの中身をパースする
def parse_elements
elements = []
if peek() == ")"
return elements
end
elements << parse_array() # 再帰
elements
end
def parse_array
if peek() == "("
$pos += 1
else
raise "$tokens[#{$pos}] は ( であるはず"
end
ary = parse_elements() # 再帰
if peek() == ")"
$pos += 1
else
raise "$tokens[#{$pos}] は ) であるはず"
end
ary
end
def parse(tokens)
puts "tokens: " + $tokens.inspect
# トークン列とカーソル位置をリセット
$tokens = tokens
$pos = 0
parse_array()
end
p parse(tokenize("()" )) #=> []
p parse(tokenize("(())" )) #=> [[]]
p parse(tokenize("((()))")) #=> [[[]]]
(3) くりかえし
くりかえしだけをやってみます。
p parse(tokenize("" )) #=> []
p parse(tokenize("x" )) #=> ["x"]
p parse(tokenize("x,x" )) #=> ["x", "x"]
p parse(tokenize("x,x,x")) #=> ["x", "x", "x"]
最初に「入力文字列として使える文字は (, ), ,, 半角スペースの4つだけ」と言っていましたが、このステップでは単純化のために配列の要素として x という文字を使います。
$tokens = nil
$pos = nil
def tokenize(src); src.delete(" ").chars end
def peek; $tokens[$pos] end
def parse_repeat
elements = []
if $tokens.size <= $pos
# 要素が0個の場合
return elements
end
# 最初の要素
elements << peek()
$pos += 1
# 2番目以降の要素
while peek() == ","
$pos += 1 # カーソルを , の次に進める
elements << peek()
$pos += 1
end
elements
end
def parse(tokens)
puts "tokens: " + $tokens.inspect
$tokens = tokens
$pos = 0
parse_repeat()
end
p parse(tokenize("" )) #=> []
p parse(tokenize("x" )) #=> ["x"]
p parse(tokenize("x,x" )) #=> ["x", "x"]
p parse(tokenize("x,x,x")) #=> ["x", "x", "x"]
(4) 入れ子とくりかえしの組み合わせ
(2) と (3) を組み合わせるだけ。
$tokens = nil
$pos = nil
def tokenize(src); src.delete(" ").chars end
def peek; $tokens[$pos] end
def parse_elements
elements = []
if peek() == ")"
return elements
end
elements << parse_array()
while peek() == ","
$pos += 1
elements << parse_array()
end
elements
end
def parse_array
if peek() == "("
$pos += 1
else
raise "$tokens[#{$pos}] は ( であるはず"
end
ary = parse_elements()
if peek() == ")"
$pos += 1
else
raise "$tokens[#{$pos}] は ) であるはず"
end
ary
end
def parse(tokens)
puts "tokens: " + $tokens.inspect
$tokens = tokens
$pos = 0
parse_array()
end
p parse(tokenize("()")) #=> []
p parse(tokenize("(())")) #=> [[]]
p parse(tokenize("((), ())")) #=> [[], []]
p parse(tokenize("((), (), ())")) #=> [[], [], []]
p parse(tokenize("((), (()))")) #=> [[], [[]]]
p parse(tokenize("(((), (())))")) #=> [[[], [[]]]]
これで完成です 
おまけ
if peek() == "("
# 期待したトークンだったらカーソルを進める
$pos += 1
else
raise "$tokens[#{$pos}] は ( であるはず"
end
この部分はメソッドに抽出するとよさそうですね。
あわせて、クラス化まで行ったものも貼っておきます。
class Parser
def initialize(tokens)
@tokens = tokens
@pos = 0
end
def peek
@tokens[@pos]
end
def consume(expected)
if peek() == expected
@pos += 1
else
raise "@tokens[#{@pos}] は #{expected.inspect} であるはず"
end
end
def parse_elements
elements = []
if peek() == ")"
return elements
end
elements << parse_array()
while peek() == ","
@pos += 1
elements << parse_array()
end
elements
end
def parse_array
consume "("
ary = parse_elements()
consume ")"
ary
end
end
def tokenize(src)
src.delete(" ").chars
end
def parse(tokens)
puts "tokens: " + tokens.inspect
Parser.new(tokens).parse_array()
end
発展
- 演算子の優先順位
- AST（抽象構文木）を組み立ててから評価（実行）