[インデックス 1440] ファイルの概要

このコミットは、Go言語の初期のコンパイラ（またはそれに類するツール）の一部である pretty パッケージ内のファイルを変更しています。

• usr/gri/pretty/parser.go: ソースコードを解析し、抽象構文木（AST）を構築する役割を担うパーサーのコードです。このコミットで大幅な追加と修正が行われています。
• usr/gri/pretty/selftest2.go: pretty パッケージの自己テスト用ファイルの一つです。新しいテストケースが追加されています。
• usr/gri/pretty/typechecker.go: 構文解析されたコードの型チェックを行う役割を担う型チェッカーのコードです。このコミットで大幅な削除が行われています。

コミット

• コミットハッシュ: 4dc3d74a361dfa069b09747fa716000d57264ca1
• Author: Robert Griesemer gri@golang.org
• Date: Thu Jan 8 12:04:00 2009 -0800

GitHub上でのコミットページへのリンク

https://github.com/golang/go/commit/4dc3d74a361dfa069b09747fa716000d57264ca1

元コミット内容

- fixed a bug with building right-recursive trees iteratively
- moving scope handling into parser (simpler)
- snapshot of work today so far

R=r
OCL=22301
CL=22301

変更の背景

このコミットは、Go言語のコンパイラ開発の非常に初期段階における重要な改善を含んでいます。主な背景は以下の2点です。

1. 右再帰ツリーの構築バグの修正: 構文解析において、右再帰的な構造（例: a + b + c のような連鎖的な二項演算）を反復的に（再帰を使わずにループで）構築する際に発生していたバグが修正されました。これは、パーサーが生成する抽象構文木の正確性に直結する問題です。
2. スコープハンドリングのパーサーへの移行: これまで型チェッカー（typechecker.go）が担当していたスコープ（変数の有効範囲）の管理ロジックが、パーサー（parser.go）へと移管されました。コミットメッセージには「(simpler)」とあり、この変更によってコードベースがよりシンプルになることが意図されています。コンパイラの設計において、各フェーズの責任範囲を明確にすることは、コードの保守性、理解しやすさ、そしてバグの発生率に大きく影響します。スコープ情報をパーシング時に収集することで、後続の型チェックフェーズでの処理が簡素化される可能性があります。

このコミットは、Robert Griesemer氏によるその日の作業のスナップショットであり、Go言語のコンパイラがどのように進化していったかを示す貴重な記録です。

前提知識の解説

コンパイラの基本構造

コンパイラは、人間が書いたソースコードをコンピュータが実行できる形式（機械語など）に変換するソフトウェアです。一般的なコンパイラは、いくつかのフェーズに分かれています。

1. 字句解析 (Lexical Analysis): ソースコードをトークン（意味を持つ最小単位、例: 識別子、キーワード、演算子）の並びに変換します。
2. 構文解析 (Syntax Analysis): トークンの並びが言語の文法規則に合致するかをチェックし、抽象構文木（AST: Abstract Syntax Tree）を構築します。ASTは、ソースコードの構造を木構造で表現したものです。
3. 意味解析 (Semantic Analysis): ASTに対して、型チェック、スコープ解決、名前解決などの意味的なチェックを行います。
4. 中間コード生成 (Intermediate Code Generation): ASTを、特定の機械に依存しない中間的な表現（中間コード）に変換します。
5. コード最適化 (Code Optimization): 中間コードをより効率的な形に変換します。
6. コード生成 (Code Generation): 最適化された中間コードをターゲットの機械語に変換します。

パーサー (Parser)

構文解析を担当するコンパイラのコンポーネントです。字句解析器から受け取ったトークン列を基に、言語の文法規則に従ってASTを構築します。このコミットでは、パーサーがスコープ管理の役割も担うようになりました。

型チェッカー (Type Checker)

意味解析の一部として、プログラム中の各式の型が言語の型システム規則に適合しているかを検証するコンポーネントです。例えば、整数型と文字列型を直接加算しようとした場合にエラーを報告します。

スコープ (Scope)

プログラミング言語において、変数や関数などの識別子が有効である（参照できる）プログラムの領域を指します。スコープは通常、ネストされた構造を持ち、内側のスコープは外側のスコープの識別子を参照できますが、その逆はできません。スコープ管理は、識別子の名前解決（どの識別子がどの宣言に対応するかを決定するプロセス）に不可欠です。

右再帰ツリー (Right-Recursive Tree)

構文解析において、文法規則が右側に再帰的に定義されている場合に生成されるASTの構造を指します。例えば、Expr -> Expr + Term | Term のような左再帰文法を直接解析すると左結合になりますが、Expr -> Term + Expr | Term のような右再帰文法は右結合になります。 a + b + c のような式を例にとると、左結合では (a + b) + c と解釈され、右結合では a + (b + c) と解釈されます。このコミットの文脈では、パーサーがこのような構造を反復的に（再帰呼び出しではなくループを使って）構築する際にバグがあったことを示唆しています。

Go言語の初期開発

Go言語は、GoogleでRobert Griesemer、Rob Pike、Ken Thompsonによって設計されました。このコミットが行われた2009年1月は、Go言語が一般に公開される前の非常に初期の段階であり、言語仕様やコンパイラの実装が活発に開発・変更されていた時期にあたります。usr/gri/pretty/ というパスは、Robert Griesemer氏（gri）の作業ディレクトリ内の、おそらくコード整形（pretty-printing）や初期のコンパイラ関連の実験的なコードを指していると考えられます。

技術的詳細

このコミットの最も重要な技術的変更は、スコープハンドリングの責任が typechecker.go から parser.go へと移されたことです。

スコープハンドリングの移行

• typechecker.go からの削除:

  • typechecker.go から OpenScope(), CloseScope(), Lookup(), DeclareInScope(), Declare(), DeclareIdent() といったスコープ管理に関連する関数が削除されました。
  • CheckProgram 関数内のスコープを開閉するロジックも削除されています。
  • これにより、型チェッカーはスコープ解決のロジックから解放され、純粋に型の整合性チェックに集中できるようになりました。

• parser.go への追加:

  • Parser 構造体に top_scope *Globals.Scope; フィールドが追加され、現在のスコープスタックのトップを保持するようになりました。
  • OpenScope(), CloseScope(), Lookup(), DeclareInScope(), Declare() といったスコープ管理のための新しいメソッドが Parser に追加されました。これらのメソッドは、Globals.Scope 型を使用してスコープの階層構造を管理します。
  • ParseFunctionType(), ParseInterfaceType(), ParseStructType(), ParseBlock(), ParseIfStat(), ParseForStat(), ParseSwitchStat(), ParseProgram() といった、スコープを導入する構文要素の解析関数内で、P.OpenScope() と P.CloseScope() が呼び出されるようになりました。これにより、パーサーが構文解析中にスコープの開始と終了を正確に追跡し、識別子の宣言と参照を適切なスコープに紐付けることが可能になります。
  • ParseImportSpec(), ParseConstSpec(), ParseVarSpec() の中で、P.Declare() を呼び出して、インポートされたパッケージ、定数、変数を現在のスコープに登録するようになりました。

この変更により、パーサーはASTを構築する際に、同時に識別子のスコープ情報を解決し、ASTノードに付与できるようになります。これは、コンパイラのフロントエンドにおける「ワンパス」処理の原則に近づくもので、後続のフェーズ（型チェックなど）がより単純なASTを受け取ることができるため、全体的なコンパイラの設計が「よりシンプルに」なります。

右再帰ツリー構築バグの修正

コミットメッセージには「fixed a bug with building right-recursive trees iteratively」とありますが、具体的なコード変更は ParseIdentList() と ParseCompositeElements() 関数に見られます。

• ParseIdentList() の修正:

  • 識別子のリスト（例: a, b, c）を解析する際に、以前は first というブール変数で最初の要素かどうかを判定していましたが、これを last *AST.Expr という変数で最後に処理したASTノードを追跡するように変更されました。
  • これにより、連鎖的なカンマ区切りのリストを正しく右結合的に（または少なくとも意図した結合順序で）ASTに変換できるようになります。

• ParseCompositeElements() の修正:

  • 複合リテラル（例: []int{1, 2, 3}）の要素リストを解析する際にも、ParseIdentList() と同様に last *AST.Expr を使用して、要素の連鎖を正しくASTに構築するように変更されました。

これらの変更は、パーサーが特定の構文構造（特にリストや連鎖的な要素）を反復的に処理する際のロジックを改善し、ASTの構築が正確に行われるようにするためのものです。

その他の変更

• parser.go に unimplemented(), unreachable(), assert() といったデバッグ・開発支援用のヘルパー関数が追加されました。これらは、開発中のコードの健全性を保つためのアサーションや、未実装・到達不能なコードパスを検出するために使用されます。
• selftest2.go に d0() という新しいテスト関数が追加されました。これは、複数の変数宣言（例: var (a string; b, c string; ...)）が正しく解析されることを確認するためのものです。これは、スコープハンドリングの変更と関連している可能性があります。

コアとなるコードの変更箇所

usr/gri/pretty/parser.go

スコープ関連の追加

// Scopes
top_scope *Globals.Scope;

func (P *Parser) OpenScope() {
	P.top_scope = Globals.NewScope(P.top_scope);
}

func (P *Parser) CloseScope() {
	P.top_scope = P.top_scope.parent;
}

func (P *Parser) Lookup(ident string) *Globals.Object {
	for scope := P.top_scope; scope != nil; scope = scope.parent {
		obj := scope.Lookup(ident);
		if obj != nil {
			return obj;
		}
	}
	return nil;
}

func (P *Parser) DeclareInScope(scope *Globals.Scope, x *AST.Expr, kind int) {
	if P.scope_lev < 0 {
		panic("cannot declare objects in other packages");
	}
	obj := x.obj;
	assert(x.tok == Scanner.IDENT && obj.kind == Object.NONE);
	obj.kind = kind;
	obj.pnolev = P.scope_lev;
	if scope.Lookup(obj.ident) != nil {
		P.Error(obj.pos, `"` + obj.ident + `" is declared already`);
		return;  // don't insert it into the scope
	}
	scope.Insert(obj);
}

// Declare a comma-separated list of idents or a single ident.
func (P *Parser) Declare(p *AST.Expr, kind int) {
	for p.tok == Scanner.COMMA {
		P.DeclareInScope(P.top_scope, p.x, kind);
		p = p.y;
	}
	P.DeclareInScope(P.top_scope, p, kind);
}

スコープ開閉の追加例 (ParseFunctionType)

--- a/usr/gri/pretty/parser.go
+++ b/usr/gri/pretty/parser.go
@@ -460,11 +535,17 @@ func (P *Parser) ParseResult() *AST.Type {
 func (P *Parser) ParseFunctionType() *AST.Type {
 	P.Trace("FunctionType");

+	P.OpenScope();
+	P.scope_lev++;
+
 	t := AST.NewType(P.pos, Scanner.LPAREN);
 	t.list = P.ParseParameters(true).list;  // TODO find better solution
 	t.end = P.pos;
 	t.elt = P.ParseResult();

+	P.scope_lev--;
+	P.CloseScope();
+
 	P.Ecart();
 	return t;
 }

右再帰ツリー構築バグ修正の例 (ParseIdentList)

--- a/usr/gri/pretty/parser.go
+++ b/usr/gri/pretty/parser.go
@@ -195,16 +268,18 @@ func (P *Parser) ParseIdent() *AST.Expr {
 func (P *Parser) ParseIdentList() *AST.Expr {
 	P.Trace("IdentList");

+	var last *AST.Expr;
 	x := P.ParseIdent();
-	for first := true; P.tok == Scanner.COMMA; {
+	for P.tok == Scanner.COMMA {
 		pos := P.pos;
 		P.Next();
 		y := P.ParseIdent();
-		if first {
+		if last == nil {
 			x = P.NewExpr(pos, Scanner.COMMA, x, y);
-			first = false;
+			last = x;
 		} else {
-			x.y = P.NewExpr(pos, Scanner.COMMA, x.y, y);
+			last.y = P.NewExpr(pos, Scanner.COMMA, last.y, y);
+			last = last.y;
 		}
 	}

usr/gri/pretty/typechecker.go

スコープ関連の削除

--- a/usr/gri/pretty/typechecker.go
+++ b/usr/gri/pretty/typechecker.go
@@ -17,10 +17,6 @@ import (
 type State struct {
 	// setup
 	err Scanner.ErrorHandler;
-
-	// state
-	level int;
-	top_scope *Globals.Scope;
 }


@@ -54,66 +50,6 @@ func (s *State) Error(pos int, msg string) {
 }


-// ----------------------------------------------------------------------------
-// Scopes
-
-func (s *State) OpenScope() {
-	s.top_scope = Globals.NewScope(s.top_scope);
-}
-
-
-func (s *State) CloseScope() {
-	s.top_scope = s.top_scope.parent;
-}
-
-
-func (s *State) Lookup(ident string) *Globals.Object {
-	for scope := s.top_scope; scope != nil; scope = scope.parent {
-		obj := scope.Lookup(ident);
-		if obj != nil {
-			return obj;
-		}
-	}
-	return nil;
-}
-
-
-func (s *State) DeclareInScope(scope *Globals.Scope, obj *Globals.Object) {
-	if s.level > 0 {
-		panic("cannot declare objects in other packages");
-	}
-	obj.pnolev = s.level;
-	if scope.Lookup(obj.ident) != nil {
-		s.Error(obj.pos, "`" + obj.ident + "` is declared already");
-		return;  // don't insert it into the scope
-	}
-	scope.Insert(obj);
-}
-
-
-func (s *State) Declare(obj *Globals.Object) {
-	s.DeclareInScope(s.top_scope, obj);
-}
-
-
-// ----------------------------------------------------------------------------
-// Common productions
-
-func (s *State) DeclareIdent(ident *AST.Expr, kind int, typ *AST.Type) {
-	// ident is either a comma-separated list or a single ident
-	switch ident.tok {
-	case Scanner.IDENT:
-		obj := Globals.NewObject(ident.pos, kind, ident.obj.ident);
-		s.Declare(obj);
-	case Scanner.COMMA:
-		s.DeclareIdent(ident.x, kind, typ);
-		s.DeclareIdent(ident.y, kind, typ);		
-	default:
-		unreachable();
-	}
-}
-
-
 // ----------------------------------------------------------------------------

 func (s *State) CheckType() {
@@ -131,48 +67,11 @@ func (s *State) CheckDeclaration(d *AST.Decl) {
 		// single declaration
 		switch d.tok {
 		case Scanner.IMPORT:
-			assert(d.ident == nil || d.ident.tok == Scanner.IDENT);
-			if d.ident != nil {
-				s.DeclareIdent(d.ident, d.tok, d.typ);
-			} else {
-			}
-
 		case Scanner.EXPORT:
-			// TODO
-
 		case Scanner.CONST:
-			s.DeclareIdent(d.ident, d.tok, d.typ);
-
 		case Scanner.VAR:
-			s.DeclareIdent(d.ident, d.tok, d.typ);
-
 		case Scanner.TYPE:
-			assert(d.ident.tok == Scanner.IDENT);
-			// types may be forward-declared
-			obj := s.Lookup(d.ident.obj.ident);
-			if obj != nil {
-				// TODO check if proper forward-declaration
-
-			} else {
-				s.DeclareIdent(d.ident, d.tok, d.typ);
-			}
-
 		case Scanner.FUNC:
-			assert(d.ident.tok == Scanner.IDENT);
-			if d.typ.key != nil {
-				// method
-				// TODO
-			} else {
-				// functions may be forward-declared
-				obj := s.Lookup(d.ident.obj.ident);
-				if obj != nil {
-				  // TODO check if proper forward-declaration
-				  
-				} else {
-					s.DeclareIdent(d.ident, d.tok, d.typ);
-				}
-			}
-
 		default:
 			unreachable();
 		}
@@ -181,16 +80,9 @@ func (s *State) CheckDeclaration(d *AST.Decl) {


 func (s *State) CheckProgram(p *AST.Program) {
-\ts.OpenScope();
-\t
-\t{\ts.OpenScope();
-\t\tfor i := 0; i < p.decls.Len(); i++ {
-\t\t\ts.CheckDeclaration(p.decls.At(i).(*AST.Decl));
-\t\t}\n-\t\ts.CloseScope();
+\tfor i := 0; i < p.decls.Len(); i++ {
+\t\ts.CheckDeclaration(p.decls.At(i).(*AST.Decl));
 \t}
-\t\
-\ts.CloseScope();
 }

コアとなるコードの解説

parser.go におけるスコープ管理の導入

• Parser 構造体に top_scope フィールドが追加されたことで、パーサー自身が現在のスコープ階層を追跡できるようになりました。
• OpenScope() は新しいスコープを作成し、それを現在の top_scope の子として設定します。これにより、関数、ブロック、型定義などの新しいスコープが開始されるたびに、新しいスコープがスタックのように積まれていきます。
• CloseScope() は現在のスコープを閉じ、親スコープに戻ります。これにより、スコープの終了時にそのスコープ内で宣言された識別子が有効範囲外になることをシミュレートします。
• Lookup() は、指定された識別子を現在のスコープから親スコープへと遡って検索し、その識別子に対応するオブジェクト（変数、関数など）を見つけます。これは名前解決の基本的なメカニズムです。
• DeclareInScope() と Declare() は、識別子を現在のスコープに登録するために使用されます。これにより、パーサーが構文解析中に識別子の宣言を検出し、それを適切なスコープに紐付けることができます。特に Declare() は、カンマ区切りのリスト（例: var a, b, c int）のような複数の識別子を一度に宣言する構文に対応しています。
• ParseFunctionType(), ParseInterfaceType(), ParseStructType(), ParseBlock(), ParseIfStat(), ParseForStat(), ParseSwitchStat(), ParseProgram() といった関数内で OpenScope() と CloseScope() が呼び出されるようになったことで、Go言語のスコープ規則（関数、ブロック、型定義などが新しいスコープを形成する）がパーサーレベルで強制されるようになりました。これにより、ASTが構築される時点で、各識別子がどのスコープに属するかが明確になります。

parser.go における右再帰ツリー構築バグの修正

• ParseIdentList() と ParseCompositeElements() における first フラグから last *AST.Expr への変更は、連鎖的なリスト構造（例: a, b, c や 1, 2, 3）を解析する際のAST構築ロジックを改善しています。
• 以前は first フラグで最初の要素かどうかを判定していましたが、last 変数を使用することで、常にリストの末尾に新しい要素を追加する形でASTを構築できるようになります。これにより、再帰的な構造を反復的に処理する際のバグが修正され、生成されるASTがより正確で意図した構造を持つようになります。

typechecker.go からのスコープ管理の削除

• typechecker.go からスコープ管理に関連するフィールド (level, top_scope) やメソッド (OpenScope, CloseScope, Lookup, DeclareInScope, Declare, DeclareIdent) が完全に削除されました。
• CheckDeclaration や CheckProgram 関数からも、スコープを開閉したり識別子を宣言したりするロジックが取り除かれました。
• この変更により、型チェッカーはスコープ解決の複雑さから解放され、パーサーによって既に解決されたスコープ情報を持つASTを受け取ることになります。これにより、型チェッカーの役割がより明確になり、コードベース全体のモジュール性が向上し、各コンポーネントの責任が分離されることで、将来的な開発やデバッグが容易になります。

関連リンク

• Go言語の公式ドキュメント: https://go.dev/
• Go言語のコンパイラに関する情報 (Go Wiki): https://go.dev/wiki/Compiler
• コンパイラ設計の基本概念 (Wikipedia): https://ja.wikipedia.org/wiki/%E3%82%B3%E3%83%B3%E3%83%91%E3%82%A4%E3%83%A9
• 抽象構文木 (AST) (Wikipedia): https://ja.wikipedia.org/wiki/%E6%8A%BD%E8%B1%A1%E6%A7%8B%E6%96%87%E6%9C%A8
• スコープ (プログラミング) (Wikipedia): https://ja.wikipedia.org/wiki/%E3%82%B9%E3%82%B3%E3%83%BC%E3%83%97_(%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%9F%E3%83%B3%E3%82%B0)

参考にした情報源リンク

• コミット情報: ./commit_data/1440.txt
• GitHubコミットページ: https://github.com/golang/go/commit/4dc3d74a361dfa069b09747fa716000d57264ca1
• Go言語の歴史と開発に関する一般的な知識
• コンパイラ設計に関する一般的な知識
• Go言語の初期のソースコード構造に関する推測