香川大学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) // コード生成
}

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

%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
}

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,
    }
  }

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
}

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

}