diff options
Diffstat (limited to 'chapter04')
| -rw-r--r-- | chapter04/README.ja.md | 342 | ||||
| -rw-r--r-- | chapter04/README.md | 2 | ||||
| -rw-r--r-- | chapter04/appendix/dce.ja.md | 187 | ||||
| -rw-r--r-- | chapter04/appendix/dce.md | 2 | ||||
| -rw-r--r-- | chapter04/docs/04-grammar.ja.md | 81 | ||||
| -rw-r--r-- | chapter04/docs/04-grammar.md | 2 |
6 files changed, 616 insertions, 0 deletions
diff --git a/chapter04/README.ja.md b/chapter04/README.ja.md new file mode 100644 index 00000000..1c6faa4b --- /dev/null +++ b/chapter04/README.ja.md @@ -0,0 +1,342 @@ +# 第4章: 外部からの引数と比較 + +[English](README.md) | 日本語 + +この文書は [原文](README.md) の日本語訳です。 + +[前の章: 第3章](../chapter03/README.ja.md) | +[次の章: 第5章](../chapter05/README.ja.md) + +# 目次 + +1. [中間表現の拡張](#中間表現の拡張) +2. [射影ノード](#射影ノード) +3. [可視化](#可視化) +4. [初期値](#初期値) +5. [制御が null でないのはいつか](#制御が-null-でないのはいつか) +6. [可視化についての注記](#可視化についての注記) +7. [型システムの変更](#型システムの変更) +8. [タプル型](#タプル型) +9. [$ctrl の名前の束縛](#ctrl-の名前の束縛) +10. [ピープホール最適化の追加](#ピープホール最適化の追加) +11. [ピープホール最適化の処理を追う](#ピープホール最適化の処理を追う) +12. [デッドコード除去（DCE）](#デッドコード除去dce) + +[linear](https://github.com/SeaOfNodes/Simple/tree/linear) ブランチの直線的な Git のリビジョン履歴で [この章](https://github.com/SeaOfNodes/Simple/tree/linear-chapter04) を読み、前の章と [比較](https://github.com/SeaOfNodes/Simple/compare/linear-chapter03...linear-chapter04) することもできます。 + +この章では、言語の文法を拡張して次の機能を追加します。 + +* プログラムは、外部環境から整数型の引数 `arg` を1つ受け取ります。 +* 式で比較演算子をサポートします。 +* 現在入ってくる制御ノードに対し、スコープを考慮する名前の束縛 `$ctrl` を導入します。これにより Return は Start に固定的につながるのではなく、スコープ内の `$ctrl` の束縛を追跡します。 + +この章の [完全な言語文法](docs/04-grammar.ja.md) はこちらです。 + +## 中間表現の拡張 + +この章では、新しいノードを追加し、既存のノードの一部を変更します。変更するノードと新しいノードは次のとおりです。 + +| ノード名 | 種類 | 説明 | 入力 | 値 | +|-----------|----------------|------------------------------------------------|-----------------------|----------------------------------------------------------------------------| +| MultiNode | 抽象クラス | 結果がタプルであるノード | | タプル | +| Start | 制御 | 関数の開始点。今回から MultiNode になる | | 制御トークンと `arg` データノードを含むタプル | +| Proj | データ / 制御 | MultiNode から値を取り出す射影ノード | MultiNode とインデックス | 入力 MultiNode のインデックス位置から取り出した値 | +| Bool | データ | 比較演算子の結果を表す | 2つのデータノード | 比較結果を整数値で表す。1=true、0=false | +| Not | データ | 論理否定 | 1つのデータノード | 0を1に、1を0に変換する | + +> `Proj` は制御スロットを射影するとき、すなわち `Start` の `Proj#0` のときに制御ノードです。それ以外の射影はすべてデータノードです。`ProjNode.isCFG()` を参照してください。 + +前の章までのほかのすべてのノードも引き続き使います。 + +## 射影ノード + +複数の値を返すノードから、特定のタプル要素を取り出す射影ノードを追加します。各射影ノードは、入力ノードから取り出すフィールドのインデックスを持ちます。射影ノードによって、ラベル付きの使用・定義（use-def）エッジを単純なノード参照として管理できます。 + +図では、射影ノードを、接続先ノードの内側にある長方形の箱として示します。 + +### 可視化 + + + +この図では、Start ノードの出力に対応する名前を射影ノードのラベルにしています。制御を含む MultiNode と制御ノードは、どちらも黄色です。`$ctrl` と `arg` は StartNode（`START`）の出力（利用側）であり、唯一の入力としてスロット0に MultiNode を持ちます。`label` に意味上の役割はなく、デバッグ出力で使います。 + +```java +public ProjNode(MultiNode ctrl, int idx, String label) { + super(ctrl); +``` + +```java +_scope.define(ScopeNode.CTRL, new ProjNode(START, 0, ScopeNode.CTRL).peephole()); +_scope.define(ScopeNode.ARG0, new ProjNode(START, 1, ScopeNode.ARG0).peephole()); +``` + +これらの射影ノードは、`START` MultiNode から `CTRL` と `ARG0` の型を取り出します。MultiNode は型を TypeTuple として保持します。 + +```java +public StartNode(Type[] args) { + super(); + _args = new TypeTuple(args); +``` + +型の取り出しには `_idx` を使います。 + +```java +return t instanceof TypeTuple tt ? tt._types[_idx] : Type.BOTTOM; +``` + +### 初期値 + +引数は常に与えられ、デフォルトは `TypeInteger.BOT` です。個々のテストでは、引数を指定して `new Parser` を呼ぶことで、ほかの整数値を渡すことができますし、実際にそうしています。 + +```java +Parser parser = new Parser("return arg; ", TypeInteger.constant(2)); +``` + +グラフは次のようになります。 + + + +* `$ctrl` と `arg` はどちらも最外側のシンボルテーブル、レキシカルな深さ0で定義されます。 +* 深さ1には空のグローバルスコープのシンボルテーブルを作ります。将来、ここでグローバル変数を定義します。 +* return の後では制御が死ぬため、スコープの `$ctrl` の線はありません。明示的に null を設定すると `setDef` が呼ばれてノードが削除されます（削除されたノードはプログラムの一部ではなく、可視化にも現れません）。 + +``` + ctrl(null); // Kill control +``` + +* `arg` は定数なので、`arg` 射影ノードはクラスタに含まれません。もともと `arg` は ProjNode により定義されていましたが、ピープホール最適化の呼び出しで計算された型が定数となるため、ProjNode を ConstantNode に置き換えます。 + +```java +public final Node peephole( ) { + Type type = _type = compute(); + /* type = {TypeInteger@1527} "2" */ + + // ProjNode is not a constant unlike its type. + if (!(this instanceof ConstantNode) && type.isConstant()) + /* Create Constant(2) */ + return deadCodeElim(new ConstantNode(type).peephole()); + + /* won't get called */ + ... +``` + +引数を渡さなければ、`TypeInteger.BOT` になります。 + +```java + Parser parser = new Parser("return arg; "); + ... + +public Parser(String source) { + this(source, TypeInteger.BOT); +} + +``` + +これが定数ではないことは明らかです。 + +```java +public final static TypeInteger BOT = new TypeInteger(false, 1); + /* _is_con = false */ +``` + +そのため、`arg` 射影ノードはクラスタ内に残ります。 + + + +#### 制御が null でないのはいつか + +後の章では、`$ctrl` は `If` や `Region`（さらに `Loop`）などのほかの制御ノードを指すようになります。現時点ではほかの制御フローがないため、`Return` の後には必ず null を設定します。 + +#### 可視化についての注記 + +この章以降は、定数から Start ノードへのエッジを省略します。主な目的は図の混雑を減らし、グラフのより重要な部分に読者の注意を向けることです。 + +## 型システムの変更 + +[第2章](../chapter02/README.ja.md) で型システムを導入しました。 + +ノードには型を付けています。この型の注釈には2つの目的があります。 + +* そのノードで許される演算の集合を定義すること。 +* そのノードが取りうる値の集合を定義すること。 + +[第2章](../chapter02/README.ja.md) では、特定のノードにおいて型に対応する値の集合を、[束](https://en.wikipedia.org/wiki/Lattice_(order)) として便利に表せることを述べました。 + +型そのものは Java の `Type` クラスとそのサブタイプで識別します。型の実装では、型の内部構造を扱う便利な方法として Java のクラスを使っています。ただし、Java のクラスと束の中での型の位置に関連はありません。 + +この章では、型の階層を次のように拡張します。 + +``` +Type (Enhanced - now has Control, and a global Top and Bottom) ++-- TypeInteger (Enhanced - now has Top and Bottom types) ++-- TypeTuple (New - represents multi-valued result) +``` + +拡張した束は次のようになります。 + + + +この章では、`arg` という名前のプログラム入力変数を導入します。この変数についてわかるのは、何らかの整数値だということだけで、定数かどうかはわかりません。 + +定数でない整数値を扱うため、`TypeInteger` を拡張し、これまでの定数値に加えて整数型 `IntTop` と `IntBot` も表せるようにします。 + +整数値が定数の場合と定数でない場合を持つようになったため、束に *meet* 演算子を導入する必要があります。`meet` 演算子は、整数値を組み合わせたときの結果の型を決める規則を表します。束の図では、`meet` を取る2つの要素から始めて、矢印を下向きにたどり、最初に合流する地点を見つけます。 + +| | IntBot | Con1 | Con2 | IntTop | +|--------|--------|--------|--------|--------| +| IntBot | IntBot | IntBot | IntBot | IntBot | +| Con1 | IntBot | Con1 | IntBot | Con1 | +| IntTop | IntBot | Con1 | Con2 | IntTop | + +この表の `Con1` と `Con2` は2つの異なる整数値を表し、次の規則を説明するためのものです。 + +* `IntTop` と任意の整数定数の `meet` は、その定数です。 +* `IntBot` と任意の整数値の `meet` は `IntBot` です。 +* 任意の整数とそれ自身の `meet` は、その整数です。 +* 互いに異なる2つの整数定数の `meet` は `IntBot` です。 + +現時点では、整数値を持つノードはすべて、定数か `IntBot` 整数型のどちらかです。ループの最適化を始めると、`IntTop` の値も現れるようになります。 + +### タプル型 + +タプル型にはもう少し説明が必要です。型を固定数まとめたもので、文字どおり `Type[]` です。タプルは、ほかの点では互いに無関係な型の集まりを表し、`MultiNode` から得られます。`ProjNode` は、タプルから適切な `Type` 配列要素を取り出します。StartNode は今回から、制御と `arg` の型からなる2要素の `TypeTuple`、`[ctrl, TypeInteger.INTBOT]` を生成します。 + +タプルに対する束の `meet` 演算子は、要素ごとに適用します。各配列要素で再帰的に `meet` を呼び出します。異なるサイズのタプルを組み合わせるのはコンパイラ内部エラーであり、その場合 `meet` はボトムを使います。 + +## `$ctrl` の名前の束縛 + +前の章までは、Start から Return への制御入力エッジを固定していました。この章では、そのような固定エッジを使いません。代わりに `$ctrl` という名前で、現在のスコープ内の制御ノードを追跡します。したがって、先行する制御ノードへのエッジを作る必要があるときは、現在のスコープでこの名前を検索するだけです。 + +## ピープホール最適化の追加 + +定数でない整数値を扱えるようになったので、代数式を並べ替えて定数畳み込みを可能にする追加の最適化を行えます。たとえば、次の式です。 + +``` +return 1 + arg + 2; +``` + +ここではコンパイラに `arg+3` を出力してほしいのですが、現状では次のようになります。 + + + +よりよい結果を得るには、代数的な簡約が必要です。たとえば、式を次のように並べ替えます。 + +``` +arg + (1 + 2) +``` + +これで定数畳み込みが可能になり、最終的な結果は次のようになります。式を正規形にすることで、よく使われるアドレス計算の定数を畳み込み、代数的な恒等式を取り除き、全般的にコードを簡単にします。 + + + +この章で導入するピープホール最適化を次に示します。後の章ではさらに追加します。 + +| 変更前 | 変更後 | 説明 | +|-----------------------|-----------------------|------------------------------------------------| +| (arg + 0 ) | arg | 0の加算の恒等式 | +| (arg - 0 ) | arg | 0の減算の恒等式 | +| (arg * 1 ) | arg | 1の乗算の恒等式 | +| (con + arg) | (arg + con) | 畳み込みを促すため定数を右に移す | +| (con * arg) | (arg * con) | 畳み込みを促すため定数を右に移す | +| (con1 + (arg + con2)) | (arg + (con1 + con2)) | 畳み込みを促すため定数を右に移す | +| ((arg1 + con) + arg2) | ((arg1 + arg2) + con) | 畳み込みを促すため定数を右に移す | +| (arg + arg) | (arg * 2) | 積の和の形式 | +| (arg - arg) | 0 | 同じ値の減算は0 | +| (0 - arg) | (-arg) | 0からの減算は符号反転 | +| (arg1 - (-arg2)) | (arg1 + arg2) | 符号反転した値の減算は加算 | +| ((-arg1) - arg2) | -(arg1 + arg2) | 符号反転した値からの減算は和の符号反転 | +| (con / 1) | con | 1による除算 | +| (arg == arg) | 1 | 同じ値の比較 | +| (arg != arg) | 0 | 同じ値の比較 | +| (arg < arg) | 0 | 同じ値の比較 | +| (arg > arg) | 0 | 同じ値の比較 | +| (arg <= arg) | 1 | 同じ値の比較 | +| (arg >= arg) | 1 | 同じ値の比較 | + +## ピープホール最適化の処理を追う + +この章で導入するピープホール最適化は、すべて局所的です。解析中に新しいノードを作ったとき、そのノードがまだどこからも使われていない段階で実行します。 + +たとえば、単項式を解析してその式のノードを作ると、新しく作った `MinusNode` に対して `peephole()` を呼び出します。 + +```java +private Node parseUnary() { + if (match("-")) return new MinusNode(parseUnary()).peephole(); + return parsePrimary(); +} +``` + +もう1つの例として、この章で導入した比較演算子の解析を示します。 + +```java +private Node parseComparison() { + var lhs = parseAddition(); + if (match("==")) return new BoolNode.EQNode(lhs, parseComparison()).peephole(); + if (match("!=")) return new BoolNode.NENode(lhs, parseComparison()).peephole(); + if (match("<=")) return new BoolNode.LENode(lhs, parseComparison()).peephole(); + if (match("<" )) return new BoolNode.LTNode(lhs, parseComparison()).peephole(); + if (match(">=")) return new BoolNode.GENode(lhs, parseComparison()).peephole(); + if (match(">" )) return new BoolNode.GTNode(lhs, parseComparison()).peephole(); + return lhs; +} +``` + +`peephole()` は基底の `Node` クラスで実装しているため、`Node` のすべてのサブクラスが共有します。 + +```java +public final Node peephole( ) { + // Compute initial or improved Type + Type type = _type = compute(); + + // Replace constant computations from non-constants with a constant node + if (!(this instanceof ConstantNode) && type.isConstant()) + return deadCodeElim(new ConstantNode(type).peephole()); + + // Ask each node for a better replacement + Node n = idealize(); + if( n != null ) // Something changed + // Recursively optimize + return deadCodeElim(n.peephole()); + + return this; // No progress +} +``` + +ピープホールメソッドは次の処理を行います。 + +* ノードの型を計算します。 +* 型が定数で、ノードが ConstantNode でなければ、ConstantNode に置き換え、新しい定数に対してピープホール最適化を再帰的に呼び出します。 +* そうでなければ、`idealize()` を呼び、ノードによりよい置き換えを求めます。「よりよい置き換え」とは、`(1+2)` を `3` に、`1+(x+2)` を `(x+(1+2))` にするようなものです。 +* `idealize()` の処理内容を決めるのは、各 Node サブタイプの責任です。よりよい置き換えがあれば、ノードは `null` ではない値を返します。 +* `null` ではない値が返ったら何かが変わったので、もう一度 `peephole()` を呼び、その後、（置き換えられて死んだ）`this` ノードにデッドコード除去を行います。 + +`peephole()` は、次に示す `deadCodeElim()` を呼び出します。 + +## デッドコード除去（DCE） + +グラフの編集時に、ノードの利用側が1つから0になるたびに `kill` を呼びます。ピープホール最適化による置き換えや、スコープを抜けるときによく起こります。この再帰的な `kill` は、ほかの多くのコンパイラでいうデッドコード除去に相当します。ここでは、それを非常に細かな単位で呼び出します。パーサーが作った多くのノードは、次の字句を解析するより前に削除されます。 + +詳しくは、デッドコード除去の [付録](appendix/dce.ja.md#付録) を読んでください。 + +名前が示唆するとおり、`deadCodeElim` 関数は `kill` の薄いラッパーです。利用側が一時的に1から0になるだけのノードを早まって削除しないよう、`peepholeOpt` が使います。 + +```java +// m is the new Node, self is the old. +// Return 'm', which may have zero uses but is alive nonetheless. +// If self has zero uses (and is not 'm'), {@link #kill} self. +private Node deadCodeElim(Node m) { + // If self is going dead and not being returned here (Nodes returned + // from peephole commonly have no uses (yet)), then kill self. + if( m != this && isUnused() ) { + // Killing self - and since self recursively kills self's inputs we + // might end up killing 'm', which we are returning as a live Node. + // So we add a bogus extra null output edge to stop kill(). + m.addUse(null); // Add bogus null use to keep m alive + kill(); // Kill self because replacing with 'm' + m.delUse(null); // Remove bogus null. + } + return m; +} +``` + +ノード `m` にダミーの利用側を一時的に追加していることに注目してください。`m` は新しい置き換え先であり、生きているとわかっていますが、まだグラフにつないでいないため、利用側がありません。ダミーの利用側を加えることで、死んだと誤認されて削除されるのを防ぎます。 diff --git a/chapter04/README.md b/chapter04/README.md index f9a2dd36..d0335cd6 100644 --- a/chapter04/README.md +++ b/chapter04/README.md @@ -1,5 +1,7 @@ # Chapter 4: External Argument and Comparisons +English | [日本語](README.ja.md) + [Previous: Chapter 3](../chapter03/README.md) | [Next: Chapter 5](../chapter05/README.md) diff --git a/chapter04/appendix/dce.ja.md b/chapter04/appendix/dce.ja.md new file mode 100644 index 00000000..4c461277 --- /dev/null +++ b/chapter04/appendix/dce.ja.md @@ -0,0 +1,187 @@ +# 付録 + +[English](dce.md) | 日本語 + +この文書は [原文](dce.md) の日本語訳です。 + +## デッドコード除去（DCE） + +デッドコード除去は、死んだ（使われていない）ノードを取り除く処理です。 + +この章には、2種類のデッドコード除去があります。 + +* スコープをポップするときに、使われていないノードを削除する。 +* よりよい置き換えを見つけた後（`idealize()` の呼び出し後）に、古いノードを削除する。 + +どちらの方法もノードを再帰的に削除します。ただし、最初のケースは `peephole` を呼ぶかどうかにかかわらず発生します。 + +### スコープをポップするときに使われていないノードを削除する + +出力（利用側）のないノードは、使われていません。 + +### 例1 + + ``` + int a = 12; // the only output it has is the scope itself + return 1; + ``` + +`a` が使われていないことは明らかです。これから得られる、DCE なしのグラフは次のとおりです。 + + + +`a` を削除するため、スコープのポップ時に次の方法を導入します。 + + ```java + var ret = (ReturnNode) parseBlock(); + _scope.pop(); + ``` + +現時点ではプログラムの終わりは return に固定されており、解析を終えたらスコープをポップします。ポップ前のスコープの状態は次のとおりです。 + + ``` + _scope = {ScopeNode@1422} "Scope[$ctrl:null, arg:arg][a:12]" + 1 = {ProjNode@1528} "arg" + 2 = {ConstantNode@1529} "12" + _inputs = {ArrayList@1523} size = 3 + ``` + +`a` の出力: + + ``` + _outputs = {ArrayList@1544} size = 1 + 0 = {ScopeNode@1422} "Scope[$ctrl:null, arg:arg][a:12]" + ``` + +`a` の唯一の出力はスコープ自身であることに注目してください。`a` を導入するとき、スコープの入力に追加するとともに、スコープを `a` の出力に追加します（使用・定義の連鎖を思い出してください）。 + +`a` は戻り値ではないため、使われておらず、削除できます。 + +`_scope.pop`: + +```java +public void pop() { popN(_scopes.pop().size()); } +``` + +`_scope.popN`（使われていないノードを *再帰的に* 削除する処理）: + +```java +void popN(int n) { + for (int i = 0; i < n; i++) { + Node old_def = _inputs.removeLast(); // start from the back + if (old_def != null && // If it exists and + old_def.delUse(this)) { // If we removed the last use, the old def is now dead + old_def.kill(); // Kill the old def + } + } +} +``` + +まず、スコープの入力をループでたどります（スコープもほかと同じノードであり、スコープのシンボルが入力であることを *思い出してください*）。`removeLast` が返すノードが null でなく、`old_def` の唯一の利用側が現在のノードなら、削除できます。 + +`old_def.delUse(this)` は、`old_def` の出力から *this* を削除します。 + +```java +protected boolean delUse( Node use ) { + Utils.del(_outputs, Utils.find(_outputs, use)); + return _outputs.isEmpty(); + } +``` + +`use` の削除後に `_outputs` が空になれば true を返します。`old_def.kill()` は再帰的な削除処理を開始します。 + +`old_def.kill()`: + +```java +public void kill( ) { + assert isUnused(); // Has no uses, so it is dead + popN(nIns()); // Set all inputs to null, recursively killing unused Nodes + _type=null; // Flag as dead + assert isDead(); // Really dead now + } +``` + +再び `popN` を呼びます。目的は、`a` を解放した結果、同様に削除できるノードを探すことです。`a` の唯一の入力は、値12の定数ノードです。ほかのノードと同様に、`ConstantNode` も最初の入力として制御ノード（`Start`）を取ります。`ConstantNode` の入力から `Start` ノードを取り除いたら、 + +``` +Node old_def = _inputs.removeLast(); +``` + +`Start` の出力から `ConstantNode`（`this`）も取り除けます。 + +``` +old_def.delUse(this) +``` + +### 例2 + +``` +int a = 12; +int b = a + 1; +return 1; +``` + +* 現在のスコープで `popN` を呼びます。 +* `b = a + 1;` に利用側がないとわかるので、削除できます。 +* kill 関数では再び `popN` を呼べますが、今回は `b = a + 1;` の入力を対象にします（再帰的な削除を始めます）。 +* 末尾から削除処理を始め、まず「1」を調べます。これには `AddNode` 以外の出力がありません。`this = AddNode` なので、`delUse` を呼ぶと「1」が死んだ状態になります。 +* 「1」を削除し、1つの入力（制御ノード）に対して `popN` を呼べます。 +* 次に「a」を調べます。この時点ではスコープと `AddNode` の2つの利用側があります。`this = AddNode` なので、出力から `AddNode` を取り除きますが、まだスコープが利用側として残るため、ここでは削除できません。 +* `a = 12` に進みます。「a」の利用側は1つ（スコープ）だけで、`this = scope` なので、容易に削除できます。 +* 前と同じように「a」の入力をたどり、制御ノードの出力からそれらを削除します。 + + + +## よりよい置き換えを見つけた後に古いノードを削除する + +次のコードを考えます。 + +``` +return (2+1)+3; +``` + +`idealize` の呼び出し後に DCE を行わなければ、次のようになります。 + + + +式 (2 + 1) + 3 に対して、より最適な置き換え値（6）を見つけた後、その値を保持する定数ノードを作りました。しかし、元の式を取り除かなかったため、構造内に不要なノードが残っています。 + +これを直すため、使われていないノードを削除する `deadCodeElim` の呼び出しを追加します。 + +```java +public final Node peephole( ) { + ... + if (!(this instanceof ConstantNode) && type.isConstant()) + return new deadCodeElim(ConstantNode(type).peephole()); + + ... + + Node n = idealize(); + if( n != null ) // Something changed + // Recursively optimize + return deadCodeElim(n.peephole()); + + ... +} +``` + +> 訳注: 上の原文コードの `return new deadCodeElim(ConstantNode(type).peephole());` は、そのままでは Java の構文として正しくありません。コードは原文どおり保持しています。章本文の対応するコードでは `return deadCodeElim(new ConstantNode(type).peephole());` となっています。 + +```java +// m is the new Node, self is the old. +// Return 'm', which may have zero uses but is alive nonetheless. +// If self has zero uses (and is not 'm'), {@link #kill} self. +private Node deadCodeElim(Node m) { + // If self is going dead and not being returned here (Nodes returned + // from peephole commonly have no uses (yet)), then kill self. + if( m != this && isUnused() ) { + // Killing self - and since self recursively kills self's inputs we + // might end up killing 'm', which we are returning as a live Node. + // So we add a bogus extra null output edge to stop kill(). + m.addUse(null); // Add bogus null use to keep m alive + kill(); // Kill self because replacing with 'm' + m.delUse(null); // Remove bogus null. + } + return m; +} +``` diff --git a/chapter04/appendix/dce.md b/chapter04/appendix/dce.md index 1f9dfa7a..10ff6bf1 100644 --- a/chapter04/appendix/dce.md +++ b/chapter04/appendix/dce.md @@ -1,4 +1,6 @@ # Appendix + +English | [日本語](dce.ja.md) ## Dead Code Elimination(DCE) Dead Code Elimination is the process or removing nodes that are dead(unused). diff --git a/chapter04/docs/04-grammar.ja.md b/chapter04/docs/04-grammar.ja.md new file mode 100644 index 00000000..b8b6bff5 --- /dev/null +++ b/chapter04/docs/04-grammar.ja.md @@ -0,0 +1,81 @@ +# 第4章の文法 + +[English](04-grammar.md) | 日本語 + +この文書は [原文](04-grammar.md) の日本語訳です。 + +> 訳注: 原文の見出しは「Grammar for Chapter 1」ですが、このファイルは第4章に属するため、訳の見出しは第4章としています。文法は原文のまま保持しています。 + + +[第4章に戻る](../README.ja.md) + +```antlrv4 +grammar SimpleLanguage; + +program + : statement+ EOF + ; + +statement + : returnStatement + | declStatement + | blockStatment + | expressionStatement + ; + + +expressionStatement + : IDENTIFIER '=' expression ';' + ; + +blockStatement + : '{' statement+ '}' + ; + +declStatement + : 'int' IDENTIFIER '=' expression ';' + ; + +returnStatement + : 'return' expression ';' + ; + +expression + : comparisonExpression + ; + +comparisonExpression + : additiveExpression (('==' | '!='| '>'| '<'| '>='| '<=') additiveExpression)* + ; + +additiveExpression + : multiplicativeExpression (('+' | '-') multiplicativeExpression)* + ; + +multiplicativeExpression + : unaryExpression (('*' | '/') unaryExpression)* + ; + +unaryExpression + : ('-') unaryExpression + | primaryExpression + ; + +primaryExpression + : IDENTIFIER + | INTEGER_LITERAL + | '(' expression ')' + ; + +INTEGER_LITERAL + : [1-9][0-9]* + | [0] + ; + +IDENTIFIER + : NON_DIGIT (NON_DIGIT | DIGIT)* + ; + +NON_DIGIT: [a-zA-Z_]; +DEC_DIGIT: [0-9]; +``` diff --git a/chapter04/docs/04-grammar.md b/chapter04/docs/04-grammar.md index 0600679e..3ea27850 100644 --- a/chapter04/docs/04-grammar.md +++ b/chapter04/docs/04-grammar.md @@ -1,5 +1,7 @@ # Grammar for Chapter 1 +English | [日本語](04-grammar.ja.md) + ```antlrv4 grammar SimpleLanguage; |