香川大学SLPからお届け！（Vol.75掲載）

著者：平西 宏彰

　プログラミング言語で記述されたプログラムを解釈して、実行可能な形式に変換するのがコンパイラの役割です。コンパイラは、簡単なものであれば200行程度のコードで作成できます。今回は、整数の四則演算用の数式を処理できるコンパイラを作成します。

シェルスクリプトマガジン Vol.75は以下のリンク先でご購入できます。

図4　「main.go.y」ファイルに最初に記述するコード

%{
package main
import (
  "fmt"
  "log"
  "strconv"
  "github.com/llir/llvm/ir"
  "github.com/llir/llvm/ir/constant"
  "github.com/llir/llvm/ir/types"
  "github.com/llir/llvm/ir/value"
)
%}
%%
%%
type Node struct { // 構文木
  ID string        // 構文の種類
  Value string     // 構文が持つ値
  Left *Node
  Right *Node
}
type Lexer struct { // 字句解析器
  src string  // ソースコード
  index int   // 調査中のインデックス
  node *Node  // 構文木
}
func (l *Lexer) Error(err string) { // エラー処理
  log.Fatal(err)
}
func main() {
  var code string
  fmt.Scan(&code) // コード入力
  lexer := &Lexer{src: code, index: 0} // 字句解析
  yyParse(lexer) // 構文解析
  generator(lexer.node) // コード生成
}

図5　「main.go.y」ファイルの宣言部に追加するコード

%union {
  num int
  ope string
  node *Node
}
%type<node> program expr
%token<num> NUMBER
%token<ope> ADD SUB MUL DIV
%left ADD, SUB
%left MUL, DIV

図6　「main.go.y」ファイルのプログラム部に追加するコード

func (l *Lexer) Lex(lval *yySymType) int {
  if len(l.src) <= l.index { return -1 }
  c := l.src[l.index]
  l.index++
  if c == '+' { return ADD }
  if c == '-' { return SUB }
  if c == '*' { return MUL }
  if c == '/' { return DIV }
  if '0' <= c && c <= '9' {
    la := l.index
    for la < len(l.src) && '0' <= l.src[la] && l.src[la] <= '9' {
      la++
    }
    num, _ := strconv.Atoi(l.src[l.index-1:la])
    lval.num = num
    l.index = la
    return NUMBER
  }
  return -1
}

図7　「main.go.y」ファイルの規則部に記述するコード

program // 構文解析を開始するための構文
  : expr {
    $$ = $1
    yylex.(*Lexer).node = &Node{} // nodeの初期化
    // 式の構文解析で生成された構文木をprogram構文に
    yylex.(*Lexer).node = $$ }
expr // 式の構文
  : NUMBER { // 生成規則が数値のときの動作を記述
    $$ = &Node{
      ID: "NUMBER",
      Value: strconv.Itoa($1),
    }
  }
  | expr ADD expr {
    $$ = &Node{
      ID: "expr",
      Value: "+",
      Left: $1, // 左の式
      Right: $3, // 右の式
    }
  }
  | expr SUB expr { 
    $$ = &Node{
      ID: "expr",
      Value: "-",
      Left: $1,
      Right: $3,
    }
  }
  | expr MUL expr { 
    $$ = &Node{
      ID: "expr",
      Value: "*",
      Left: $1,
      Right: $3,
    }
  }
  | expr DIV expr { 
    $$ = &Node{
      ID: "expr",
      Value: "/",
      Left: $1,
      Right: $3,
    }
  }

図8　「main.go.y」ファイルのプログラム部に追加するコード

func generator(node *Node) {
  m := ir.NewModule()
  main := m.NewFunc("main", types.I32)
  block := main.NewBlock("")
  block.NewRet(calc(block, node))
  fmt.Println(m.String())
}
func calc(block *ir.Block, node *Node) value.Value {
  if node.ID == "expr" { return expr(block, node) }
  if node.ID == "NUMBER" { return number(node) }
  log.Fatal("error: generator")
  return nil
}
func number(node *Node) value.Value {
  val, ok := strconv.Atoi(node.Value)
  if ok != nil {
    log.Fatal("error: generator")
    return nil
  }
  return constant.NewInt(types.I32, int64(val))
}
func expr(block *ir.Block, node *Node) value.Value {
  if node.Left == nil || node.Right == nil {
    log.Fatal("error: generator")
    return nil
  }
  left := calc(block, node.Left)
  right := calc(block, node.Right)
  if node.Value == "+" { return block.NewAdd(left, right) }
  if node.Value == "-" { return block.NewSub(left, right) }
  if node.Value == "*" { return block.NewMul(left, right) }
  if node.Value == "/" { return block.NewUDiv(left, right) }
  log.Fatal("error: generator")
  return nil
}