😺

Nand2tetrisをGoで実装する ~ コンパイラ(コンパイラ・フロントエンド)編(10,11章) ~

2021/12/09に公開

Golang

compiler

nand2tetris

tech

1.はじめに

タイトルにもあるとおり、本記事は「コンピュータシステムの理論と実装」の10,11章に該当するコンパイラ(コンパイラ・フロントエンド)編の実装に関する記事です。

本記事で紹介するjackcompilerというGoで実装したコンパイラは、Nand2tetrisが提供するプログラミング言語であるJackを中間言語にコンパイルします。

jackcompilerを通して得られた中間言語を、前の記事までに実装したvmtranslator,assemblerという2つのソフトウェアによって機械語に変換すれば、高級言語Jackによるプログラムを機械語に変換することができます。

すなわち、今回実装したjackcompilerとvmtranslator,assemblerという3つのソフトウェアを使えば、高級言語のJackによって、ハードウェアを操作することがついにできるようになるということです！

それでは、Jackの文法とJackを中間言語に変換するコンパイラの実装を見ていきましょう。

2.プログラミング言語・Jackの文法

その実装について解説していく前に、前の記事での解説と重複するのですがコンパイルをする対象である「Jack」というプログラミング言語を簡単に説明していきます。

「Jackがどんな言語なのか？」を直感的に把握してもらうために、Jackで記述されたプログラムを見ていきましょう。以下は「長さlengthを持つ配列aの各要素に標準入力から値を入力していき、その平均値を出力する」という処理を行うJackプログラムです。

class Main {
   function void main() {
     var Array a; 
     var int length;
     var int i, sum;

     let length = Keyboard.readInt("How many numbers? ");
     let a = Array.new(length); 
     
     let i = 0;
     while (i < length) {
        let a[i] = Keyboard.readInt("Enter a number: ");
        let sum = sum + a[i];
        let i = i + 1;
     }
     
     do Output.printString("The average is ");
     do Output.printInt(sum / length);
     return;
   }
}

普段私たちが慣れ親しんでいるプログラミング言語とほとんど同じように見えませんか？

今回そのコンパイラを実装していく「Jack」というプログラミング言語には以下のような特徴があります。

オブジェクト指向型言語
静的型付け
コンパイル時、直接実行可能な機械語・アセンブリには変換されず、独自のVirtual Machine上で動作する中間コードに変換される。(like Java,Scala,Kotlin & JVM)

また、Jackには上で例として挙げたプログラム以外にも、以下のような言語機能があります。

if-else文
クラス変数
クラススタティック変数
クラスメソッド
コンストラクタ

4.Jackによるプログラムが機械語に変換されるまで.

前章で今回コンパイルする「Jack」というプログラミング言語について簡単に紹介しました。しかし、Jackという「高級言語」で記述されたプログラムをハードウェア上で直接動作させることは、当然できません。

高級言語により記述されたプログラムをハードウェア上で実行するためには、プログラムを実行させたいハードウェア・プラットホーム上で動作するような機械語に最終的には変換する必要があります。

それでは、ここで「Jackによるプログラム」が「Nand2tetrisが提供するハードウェア上で動作する16bit機械語」に変換されるまでの全体像を改めて見てみましょう.

Jack言語によるプログラムは「中間言語」「アセンブリ」という二つの形態を経て、最終的に16bit機械語に変換されます。そして本記事で解説するのはJackによるプログラムを中間言語に変換するコンパイラのGo言語による実装です。

4. GoによるJackコンパイラの実装

4.1 Jackによるプログラムが中間言語に変換されるまで

それでは,GoによるJackコンパイラの実装を見ていきましょう。まずは全体像として、Jackによるプログラムが中間言語に変換されるまでのプロセスを図示したものを以下に示します。

Jackによるソースプログラムを字句解析によって、「トークン」という単位に分割し、それらからastを構築し、構築したastを評価することによって、中間言語を生成します。それでは
以上のことを踏まえて詳細な実装を見ていきましょう。

4.2 jackcompilerのフォルダ構成

まずは、実装したJackコンパイラ(nand2tetris/jackcompiler)のrootで、treeコマンドを実行し、プロジェクトの全体像を把握していきます。

.
├── README.md
├── ast // Jack言語の構文の定義
│   └── ast.go
├── compilationengine // parserパッケージにより構築されたソースプログラムのastを中間言語に変換する。
│   ├── compilationengine.go
│   └── compilationengine_test.go
├── go.mod
├── jack // Jackのサンプルプログラム
│   ├── Add
│   ├── Average
│   ├── ComplexArrays
│   ├── ConsumptionTaxCalculator
│   ├── ConvertToBin
│   ├── HelloWorld
│   ├── Pong
│   ├── Seven
│   ├── SimpleArray
│   ├── SimpleIf
│   ├── SimpleWhile
│   ├── Square
│   └── StaticTest
├── main.go
├── parser // ソースプログラムからastを構築する
│   ├── parser.go
│   └── parser_test.go
├── symboltable // Jackにおける変数などの管理を行う。
│   ├── symboltable.go
│   └── symboltable_test.go
├── token
│   └── token.go
├── tokenizer // 字句解析器。ソースプログラムを
│   ├── tokenizer.go
│   └── tokenizer_test.go
├── value
│   └── value.go
├── vm
│   ├── Array.vm
│   ├── Keyboard.vm
│   ├── Math.vm
│   ├── Memory.vm
│   ├── Output.vm
│   ├── Screen.vm
│   ├── String.vm
│   ├── Sys.vm
│   └── program
└── vmwriter // 中間言語によるプログラムをファイルに書き込む
    ├── vmwriter.go
    └── vmwriter_test.go

4.3 字句解析器

まずは字句解析器についてです。字句解析器は、高級言語によるソースプログラムを「トークン」という単位に分割します。
例えば以下のようなプログラムを字句解析器でトークナイズすることを想定します。

while(i<10){
   let i = i + 1;
}

上のようなプログラムを字句解析器によってトークナイズすると、以下のように分割されます。

"while" ,"(" ,"i" ,"<" ,"10" ,")" ,"{" ,"let" ,"i" ,"=" ,"i" ,"+" ,"1" ,";" ,"}"

こちらについては、nand2tetris/jackcompiler/tokenizerに実装が存在するので興味がある方はチェックしてみてください。

4.4 構文解析器

構文解析器では、jackのソースプログラムを解析して、astを構築します。ここでは例として、while文に対する構文解析の実装を見てみましょう

parser.go

func (p *Parser) ParseWhileStatement() *ast.WhileStatement {
	stmt := &ast.WhileStatement{Token: p.curToken} 
	if p.expectNext(token.SYMBOL) {
		if token.Symbol(p.curToken.Literal) != token.LPAREN {
			return nil
		}
	}
	p.advanceToken()
	stmt.Condition = p.ParseExpression() // whileの()内の条件をparseする。
	p.advanceToken()
	if token.Symbol(p.curToken.Literal) != token.RPAREN {
		return nil
	}
	p.advanceToken()
	stmt.Statements = p.ParseBlockStatement() // whileの{}内に書かれた処理をparseする。
	return stmt
}

こちらについては、nand2tetris/jackcompiler/parserに実装が存在します。

4.5 中間言語への変換・評価

最後に、「中間言語への変換・評価」です。その役割を担うcompilationengineパッケージでは、jackのソースプログラムを解析して、astを中間言語に変換します。ここでは例として、while文に対するその実装を見てみましょう

compilationengine.go

func (ce *CompilationEngine) CompileWhileStatement(whileStatement *ast.WhileStatement) error {
	ce.incrementLabelFlag()
	WHILE_LOOP_LABEL, WHILE_END_LABEL := fmt.Sprintf("WHILELOOP%d", ce.labelFlag), fmt.Sprintf("WHILEEND%d", ce.labelFlag)
	ce.WriteLabel(WHILE_LOOP_LABEL) // 条件がTrueであった場合、再び処理を行うために、ラベルを貼る
	ce.CompileExpression(whileStatement.Condition) // 条件式をCompileする
	ce.WriteArithmetic(vmwriter.NOT)
	ce.WriteIf(WHILE_END_LABEL) // 条件式がfalseであった場合は、WHILE_END_LABELにjumpする
	for _, stmt := range whileStatement.Statements.Statements {
		ce.CompileStatement(stmt)
	}
	ce.WriteGoto(WHILE_LOOP_LABEL)
	ce.WriteLabel(WHILE_END_LABEL)
	return nil
}

こちらについては、nand2tetris/jackcompiler/compilationengineに実装が存在します。

5. 最後に

本記事では,高級言語を中間言語に変換するJackCompilerの実装について説明しました。記事では解説しませんでしたが、最後にJackでOSを実装し、それでNand2tetrisの実装は完了です。

6. 参考文献

GitHubで編集を提案