Rubyで簡単な再帰下降構文解析

ほとんどお気楽 Haskell プログラミング入門の電卓プログラムの作成をRubyに直しただけのものです。括弧も単項演算子も使えませんが、それゆえにシンプルでわかりやすいと思います。字句解析して、構文木を作って、評価するだけです。これさえ理解してしまえば、あとは肉付けして機能を追加していくだけで自作言語のできあがりです。

``` end: ``` lang: filename: option:

require 'strscan'

class Token
  attr_accessor :type
  attr_accessor :obj

  def initialize(type, obj)
    @type = type
    @obj = obj
  end
end

class Expr
  attr_accessor :type
  attr_accessor :expr1
  attr_accessor :expr2
  
  def initialize(type, expr1, expr2)
    @type = type
    @expr1 = expr1
    @expr2 = expr2
  end
end

def main
  if ARGV.size != 1 then
    puts "Usage: ruby lang.rb 'parse string'"
  end

  tokenArray = lexer(ARGV[0])
  p tokenArray
  if tokenArray == "error" then
    puts "Error: lexer"
    return
  end 

  expr = getParseTree(tokenArray)
  p expr
  if expr == "error" then
    puts "Error: getParseTree"
    return
  end
  
  ret = evalExpr(expr)
  p ret
  if expr == "error" then
    puts "Error: evalExpr"
    return
  end
end

def evalExpr(expr)
  if expr.type == "Int" then
    p expr.expr1
  elsif expr.type == "Add" then
    expr1 = evalExpr(expr.expr1).to_i
    expr2 = evalExpr(expr.expr2).to_i
    p expr1 + expr2
  elsif expr.type == "Sub" then
    expr1 = evalExpr(expr.expr1).to_i
    expr2 = evalExpr(expr.expr2).to_i
    p expr1 - expr2
  elsif expr.type == "Mul" then
    expr1 = evalExpr(expr.expr1).to_i
    expr2 = evalExpr(expr.expr2).to_i
    p expr1 * expr2
  elsif expr.type == "Div" then
    expr1 = evalExpr(expr.expr1).to_i
    expr2 = evalExpr(expr.expr2).to_i
    p expr1 / expr2
  else
    return "error"
  end
end

def getParseTree(tokenArray)
  expr = getExpr(tokenArray)
  if tokenArray.size > 1 then
    return "error"
  end
  return expr
end

def getExpr(tokenArray)
  expr = getTerm(tokenArray)
  expr = getExprSub(expr, tokenArray)
end

def getExprSub(expr, tokenArray)
  return expr if tokenArray.empty?
  t = tokenArray.first
  if t.type == "Add" then
    tokenArray.shift
    f = getTerm(tokenArray)
    return getExprSub(Expr.new("Add", expr, f), tokenArray)
  elsif t.type == "Sub" then
    tokenArray.shift
    f = getTerm(tokenArray)
    return getExprSub(Expr.new("Sub", expr, f), tokenArray)
  end
  return expr
end

def getTerm(tokenArray)
  expr = getFactor(tokenArray)
  expr = getTermSub(expr, tokenArray)
end

def getTermSub(expr, tokenArray)
  return expr if tokenArray.empty?
  t = tokenArray.first
  if t.type == "Mul" then
    tokenArray.shift
    f = getFactor(tokenArray)
    return getTermSub(Expr.new("Mul", expr, f), tokenArray)
  elsif t.type == "Div" then
    tokenArray.shift
    f = getFactor(tokenArray)
    return getTermSub(Expr.new("Div", expr, f), tokenArray)
  end
  return expr
end

def getFactor(tokenArray)
  t = tokenArray.shift
  if t.type == "Int" then
    return Expr.new("Int", t.obj, nil)
  end
end

def lexer(str)
  s = StringScanner.new(str)
  tokenArray = []
  while !s.eos? do
    ret = getToken(s)
    if ret == "error" then
      return "error"
    end
    tokenArray << ret
  end
  return tokenArray
end

def getToken(s)
  s.scan(/\s*/)
  if obj = s.scan(/\d+/) then
    return Token.new("Int", obj)
  elsif obj = s.scan('+') then
    return Token.new("Add", obj)
  elsif obj = s.scan('-') then
    return Token.new("Sub", obj)
  elsif obj = s.scan('*') then
    return Token.new("Mul", obj)
  elsif obj = s.scan('/') then
    return Token.new("Div", obj)
  end
  return "error"
end

main