超シンプルな構文解析をやってみた。

天国の木に実っている技術の実の端っこの方を
舌の先端で触ってみては苦い、渋いとかいって
かじるのを躊躇っている虫がいたとすればいればそれが僕です。
どうもkondogです。
もう29にもなろうというのに自分がどこに進めばいいのかよくわかりません。
やばい。ああ、そういえば最近暖かくなってきましたね。

ちょっと前に見たやつ。
Googleで1400万円以上稼ぐエンジニアになるためにマスターすべき11のスキル
1400万欲しい!けど全部面倒くさそう。。。
あー、コンパイラ？構文解析？だっけ？やってみっか。。。

ということでGWにやってみました。
目標はシンプルに1 + 1 = 2 を構文解析するということで決定。
構文解析の基本のkを理解するにはこれで十分(つーか限界)。
多分[[[1:数値], [1:数値], [+,+]], [2:数値], [=,=]]みたいな
感じの結果になればいいはず。。

適当に調べて、
どうやらyaccとかいうのを一般的には使うらしい。
あと構文解析の前に字句解析とかいうのもあるらしい。
yaccをrubyで使えるようにした(という言い方であってるか知らんが)
Raccなるものを発見。これを使えばいいのよね。。。
Racc の使い方

なんだこれは黒魔術か...?全然分からん。。。
実際に使っているページコピペ元を発見。嗚呼、ありがとうございます。
platform-echo: Raccを使って言語処理系作ってた

よし、なるほど。俺のしょっぱい梅色の脳細胞でも5%理解できた。
見よう見まねで実装。

ちなみに下記で実装してます。
Ruby 1.9.3
Racc 1.4.12

sample_parser.y

class SampleParser
    prechigh
        left    '+'
        left    '='
    preclow
    token int
rule
  EXP : int
        { p @stack; @stack << val[0].to_i }
      | EXP '+' EXP
        { p @stack; @stack << [@stack.pop, @stack.pop, :add] }
      | EXP '=' EXP
        { p @stack; @stack << [@stack.pop, @stack.pop, :equal] }

---- inner
def parse(tokens)
    @q      = tokens + [[false, '$']]
    @stack  = []
    do_parse
    return @stack
end

def next_token
    @q.shift
end

ははぁ、なんか式の評価がどうとか、
大学でやった覚えがあるな。。。あれそういう授業だったんだ。。
prechigh/lowとかいうのは評価順序、
inner以下とかtokenとかなんじゃこりゃと思ってたけど、
Raccにこいつを噛ませて実行するとどういう感じになるかちょっと分かる。
以下こいつを使うコード。

parse.rb

require './sample_parser.tab.rb'

def lexical_analyze(str)
  tokens = str.split(/\s+/)
  res    = []
  tokens.each do |token|
    case token
    when '+'      
      res << ['+', '+']
    when '='
      res << ['=', '=']
    when /\d+/ 
      res << [:int, token]
    end
  end
  return res
end

def parse(tokens)
  parser = SampleParser.new
  return parser.parse(tokens)
end

p tokens = lexical_analyze('1 + 1 = 2')
p parse(tokens)
#$ ruby parse.rb 
# 1 + 1 = 2
# [[:int, "1"], ["+", "+"], [:int, "1"], ["=", "="], [:int, "2"]]
# []
# [1]
# [1, 1]
# [[1, 1, :add]]
# [[1, 1, :add], 2]
# [[2, [1, 1, :add], :equal]]

1 + 1 = 2を字句解析して構文解析木に突っ込むだけ。
とりあえずそれっぽくなった時点で疲れたので終了。。
てさぐりかんがヤバイ。結果は合っているのか？？？

これを利用して=の左辺と右辺が一致するかどうかとか調べたりするのは
できそうだし面白そうではある。
その辺は多分意味解析とやらになっていくと思われる。