[インデックス 1737] ファイルの概要
このコミットは、Go言語のコンパイラにおける字句解析器(scanner)の内部構造を改善し、トークン定義を独立したパッケージに分離することを目的としています。これにより、コンパイラのモジュール性が向上し、コードの保守性および理解度が向上します。具体的には、scanner
パッケージからトークン関連の定数や関数をtoken
パッケージに移動し、それに伴う依存関係の更新とコードのクリーンアップが行われています。
コミット
- コミットハッシュ:
77567265a8052bd6ef75c0ae3c28bc9caccbfa91
- Author: Robert Griesemer gri@golang.org
- Date: Tue Mar 3 18:25:07 2009 -0800
GitHub上でのコミットページへのリンク
https://github.com/golang/go/commit/77567265a8052bd6ef75c0ae3c28bc9caccbfa91
元コミット内容
Preparation for moving scanner into a lib:
- separated out token definition from scanner
- cleaned up token and scanner implementation
- added comments to exported interfaces
R=r
OCL=25665
CL=25665
変更の背景
このコミットの主な背景は、Go言語のコンパイラ(特にpretty
ディレクトリ内の初期実装)におけるモジュール性の向上と、将来的なライブラリとしての再利用性の確保です。
初期のコンパイラ設計では、字句解析器(scanner)がトークンの定義も内包していました。これは、単一のコンポーネントが複数の責任を持つ「密結合」の状態であり、以下のような問題を引き起こす可能性があります。
- 保守性の低下: トークン定義の変更がscannerの実装に直接影響を与え、その逆もまた然りであるため、一方の変更が予期せぬ形で他方に影響を及ぼすリスクがありました。
- 再利用性の低さ: scannerコンポーネントを他のプロジェクトやコンテキストで再利用しようとした場合、トークン定義も一緒に持ち運ぶ必要があり、不必要な依存関係を生み出します。
- コードの複雑性: 単一のファイルやパッケージに多くの異なる概念が混在することで、コードの読みやすさや理解度が低下します。
このコミットは、これらの問題を解決するために、トークン定義をscanner
パッケージからtoken
という新しい独立したパッケージに分離する「関心の分離(Separation of Concerns)」の原則を適用しています。これにより、scanner
は純粋に字句解析の機能に集中し、token
パッケージはトークンの種類や属性に関する情報を提供する役割を担うようになります。これは、コンパイラの各フェーズ(字句解析、構文解析、意味解析など)が明確に分離され、それぞれが独立したライブラリとして機能できるようにするための重要なステップでした。
また、エクスポートされたインターフェースへのコメント追加は、コードの可読性とドキュメントの品質を向上させ、将来の開発者がこれらのコンポーネントをより容易に理解し、利用できるようにするためのものです。
前提知識の解説
このコミットを理解するためには、コンパイラの基本的な構造とGo言語の設計思想に関する以下の知識が役立ちます。
1. コンパイラの基本構造
コンパイラは、ソースコードを機械が実行できる形式に変換するソフトウェアです。その過程は通常、いくつかのフェーズに分かれています。
- 字句解析 (Lexical Analysis / Scanning):
- ソースコードの文字列を読み込み、意味のある最小単位である「トークン(Token)」のストリームに変換します。
- 例えば、
if x == 10 {
というコードは、if
(キーワード),x
(識別子),==
(演算子),10
(整数リテラル),{
(区切り文字) といったトークンに分解されます。 - このフェーズを担当するコンポーネントを「字句解析器(Lexer)」または「スキャナー(Scanner)」と呼びます。
- 構文解析 (Syntax Analysis / Parsing):
- 字句解析器から受け取ったトークンのストリームが、言語の文法規則に則っているかを検証します。
- 文法的に正しい場合、ソースコードの構造を表現する「抽象構文木(Abstract Syntax Tree: AST)」を構築します。
- このフェーズを担当するコンポーネントを「構文解析器(Parser)」と呼びます。
- トークン (Token):
- ソースコードにおける意味のある最小単位です。各トークンは通常、「トークン種別(Token Type)」と「リテラル値(Literal Value)」を持ちます。
- 例:
IDENT
(識別子) という種別のトークンがx
というリテラル値を持つ、INT
(整数) という種別のトークンが10
というリテラル値を持つ、など。
2. Go言語のコンパイラ設計思想
Go言語の初期のコンパイラ開発では、以下のような設計思想が重視されていました。
- 手書きのパーサー: 多くの言語がYaccやANTLRのようなパーサー生成ツールを使用するのに対し、Goの字句解析器と構文解析器は、その大部分が手書きで実装されています。これは、生成されたコードよりも手書きのコードの方が、制御が容易でデバッグしやすく、パフォーマンスも最適化しやすいというGo開発チームの信念に基づいています。
- 再帰下降パーサー (Recursive Descent Parser): Goのパーサーは、再帰下降方式を採用しています。これは、文法の各非終端記号(例: 式、文、宣言)に対応する関数が存在し、それらの関数が再帰的に呼び出されることで構文解析を進める方式です。
- 最初のシンボルによる識別可能性: Goの文法設計の基本的な原則として、すべての言語構造は、その開始シンボルによって一意に識別できる必要があります。これにより、構文解析プロセスが簡素化されます。
- モジュール性: コンパイラの各コンポーネント(スキャナー、パーサー、ASTなど)は、明確な責任を持ち、独立して機能するように設計されています。これにより、コードベースの管理が容易になり、将来的な拡張や変更がしやすくなります。
このコミットは、特に「モジュール性」の原則を強化するものであり、scanner
とtoken
の分離は、Goコンパイラの設計における重要なマイルストーンの一つと言えます。
技術的詳細
このコミットの技術的詳細は、主にscanner
パッケージとtoken
パッケージの役割分担、およびそれに関連する他のコンポーネントへの影響に集約されます。
1. token
パッケージの導入と役割
- トークン定義の集約: 以前は
scanner.go
内に散在していたGo言語のすべてのトークン(キーワード、演算子、区切り文字、リテラル種別など)の定数定義が、新しく作成されたusr/gri/pretty/token.go
ファイルに集約されました。これにより、トークンに関するすべての情報が一元管理されるようになります。 TokenString
関数の移動: トークン種別(整数値)を対応する文字列表現に変換するTokenString
関数もscanner.go
からtoken.go
に移動されました。これは、トークンの文字列表現がトークンそのものの属性であり、スキャナーの機能ではないという設計思想に基づいています。- 優先順位の定義: 演算子の優先順位を定義する
LowestPrec
,UnaryPrec
,HighestPrec
定数と、特定のトークンの優先順位を返すPrecedence
関数もtoken.go
に移動されました。これにより、構文解析器が演算子の結合規則を判断する際に必要な情報がtoken
パッケージから提供されるようになります。 - キーワードマップの初期化: Go言語のキーワード(
if
,for
,func
など)を文字列からトークン種別にマッピングするためのkeywords
マップの初期化ロジックもtoken.go
に移動されました。
2. scanner
パッケージの変更
- トークン定義の削除:
usr/gri/pretty/scanner.go
から、すべてのトークン定数(ILLEGAL
,EOF
,IDENT
,ADD
など)と、TokenString
関数、Precedence
関数、キーワードマップの初期化ロジックが削除されました。 token
パッケージへの依存:scanner
パッケージは、トークン定義のために新しく導入されたtoken
パッケージをインポートするようになりました。これにより、スキャナーはトークンの種類を識別する際にtoken.IDENT
のように参照するようになります。- クリーンアップとコメント追加: スキャナーの実装自体も、より明確な構造とコメントが追加され、可読性が向上しました。特に、エクスポートされたインターフェース(
Scanner
構造体やInit
メソッドなど)には、その役割と使用方法を説明するコメントが追加されています。
3. 他のコンポーネントへの影響
この変更は、scanner
パッケージに依存していた他のコンポーネントにも波及しました。
Makefile
の更新: ビルドシステムを定義するusr/gri/pretty/Makefile
が更新され、compilation.6
,typechecker.6
,scanner.6
,ast.6
,parser.6
,printer.6
などのターゲットがtoken.6
に依存するように変更されました。これは、これらのコンポーネントがtoken
パッケージの定義を利用するようになったため、ビルド順序を正しく設定する必要があるためです。ast.go
の更新: 抽象構文木(AST)を定義するusr/gri/pretty/ast.go
では、Scanner "scanner"
のインポートが"token"
に置き換えられ、Scanner.COMMA
などのトークン参照がtoken.COMMA
に変更されました。parser.go
の更新: 構文解析器を定義するusr/gri/pretty/parser.go
は、最も広範な変更を受けました。Scanner "scanner"
のインポートが削除され、"token"
と"scanner"
(小文字のscanner
は新しいパッケージ名)がインポートされました。Parser
構造体のscanner
フィールドの型が*Scanner.Scanner
から*scanner.Scanner
に変更されました。- コード全体で
Scanner.IDENT
,Scanner.LPAREN
,Scanner.SEMICOLON
などのトークン参照がすべてtoken.IDENT
,token.LPAREN
,token.SEMICOLON
に置き換えられました。 Scanner.TokenString
の呼び出しがtoken.TokenString
に、Scanner.Precedence
の呼び出しがtoken.Precedence
にそれぞれ変更されました。
printer.go
の更新: コード整形を行うusr/gri/pretty/printer.go
でも、Scanner "scanner"
のインポートが"token"
に置き換えられ、Scanner.LowestPrec
,Scanner.COMMA
,Scanner.LPAREN
などのトークン参照がtoken.LowestPrec
,token.COMMA
,token.LPAREN
に変更されました。
これらの変更は、コンパイラの各フェーズがより明確に分離され、それぞれの責任範囲が明確になったことを示しています。
コアとなるコードの変更箇所
このコミットにおけるコアとなるコードの変更は、主に以下のファイルに集中しています。
-
usr/gri/pretty/scanner.go
:- トークン定数(
ILLEGAL
,EOF
,INT
,IDENT
など)の定義がすべて削除されました。 TokenString
関数、Precedence
関数、およびキーワードマップの初期化ロジックが削除されました。import "token"
が追加され、外部のtoken
パッケージに依存するようになりました。Scanner
構造体のコメントが更新され、使用例が追加されました。
--- a/usr/gri/pretty/scanner.go +++ b/usr/gri/pretty/scanner.go @@ -4,247 +4,48 @@ package scanner +// A Go scanner. Takes a []byte as source which can then be +// tokenized through repeated calls to the Scan() function. +// +// Sample use: +// +// import "token" +// import "scanner" +// +// +// func tokenize(src []byte) { +// var s scanner.Scanner; +// s.Init(src, nil, false); +// for { +// pos, tok, lit := s.Scan(); +// if tok == Scanner.EOF { +// return; +// } +// println(pos, token.TokenString(tok), string(lit)); +// } +// } + import ( "utf8"; "unicode"; "strconv"; + "token"; ) -const ( -... (トークン定数の削除) ... - -func TokenString(tok int) string { -... (TokenString関数の削除) ... - -const ( - LowestPrec = -1; - UnaryPrec = 7; - HighestPrec = 8; -) - -func Precedence(tok int) int { -... (Precedence関数の削除) ... - -var keywords map [string] int; - -func init() { -... (キーワードマップ初期化の削除) ... - +type ErrorHandler interface { + Error(pos int, msg string); +} + +type Scanner struct { + // setup + src []byte; // source + err ErrorHandler; + scan_comments bool; + + // scanning + pos int; // current reading position + ch int; // one char look-ahead
- トークン定数(
-
usr/gri/pretty/token.go
:scanner.go
から削除されたすべてのトークン定数がここに移動されました。TokenString
関数、Precedence
関数、およびキーワードマップの初期化ロジックがここに移動されました。- このファイルは完全に新規作成されました。
--- /dev/null +++ b/usr/gri/pretty/token.go @@ -0,0 +1,286 @@ +package token + +import ( + "strconv"; +) + +const ( + // Special tokens + ILLEGAL = iota; + EOF; + COMMENT; + + // Identifiers and basic type literals + // (these tokens stand for classes of literals) + IDENT; // main + INT; // 12345 + FLOAT; // 123.45 + CHAR; // 'a' + STRING; // "abc" + + // Operators and delimiters + ADD; // + + SUB; // - + MUL; // * + QUO; // / + REM; // % + + AND; // & + OR; // | + XOR; // ^ + SHL; // << + SHR; // >> + AND_NOT; // &^ + + ADD_ASSIGN; // += + SUB_ASSIGN; // -= + MUL_ASSIGN; // *= + QUO_ASSIGN; // /= + REM_ASSIGN; // %= + + AND_ASSIGN; // &= + OR_ASSIGN; // |= + XOR_ASSIGN; // ^= + SHL_ASSIGN; // <<= + SHR_ASSIGN; // >>= + AND_NOT_ASSIGN; // &^= + + LAND; // && + LOR; // || + ARROW; // <- + INC; // ++ + DEC; // -- + + EQL; // == + LSS; // < + GTR; // > + ASSIGN; // = + NOT; // ! + + NEQ; // != + LEQ; // <= + GEQ; // >= + DEFINE; // := + ELLIPSIS; // ... + + LPAREN; // ( + LBRACK; // [ + LBRACE; // { + COMMA; // , + PERIOD; // . + + RPAREN; // ) + RBRACK; // ] + RBRACE; // } + SEMICOLON; // ; + COLON; // : + + // Keywords + keywords_beg; + BREAK; + CASE; + CHAN; + CONST; + CONTINUE; + + DEFAULT; + DEFER; + ELSE; + FALLTHROUGH; + FOR; + + FUNC; + GO; + GOTO; + IF; + IMPORT; + + INTERFACE; + MAP; + PACKAGE; + RANGE; + RETURN; + + SELECT; + STRUCT; + SWITCH; + TYPE; + VAR; + keywords_end; +) + + +func TokenString(tok int) string { + switch tok { + case ILLEGAL: return "ILLEGAL"; + case EOF: return "EOF"; + case COMMENT: return "COMMENT"; + + case IDENT: return "IDENT"; + case INT: return "INT"; + case FLOAT: return "FLOAT"; + case CHAR: return "CHAR"; + case STRING: return "STRING"; + + case ADD: return "+"; + case SUB: return "-"; + case MUL: return "*"; + case QUO: return "/"; + case REM: return "%"; + + case AND: return "&"; + case OR: return "|"; + case XOR: return "^"; + case SHL: return "<<"; + case SHR: return ">>"; + case AND_NOT: return "&^"; + + case ADD_ASSIGN: return "+="; + case SUB_ASSIGN: return "-="; + case MUL_ASSIGN: return "*="; + case QUO_ASSIGN: return "/="; + case REM_ASSIGN: return "%="; + + case AND_ASSIGN: return "&="; + case OR_ASSIGN: return "|="; + case XOR_ASSIGN: return "^="; + case SHL_ASSIGN: return "<<="; + case SHR_ASSIGN: return ">>="; + case AND_NOT_ASSIGN: return "&^="; + + case LAND: return "&&"; + case LOR: return "||"; + case ARROW: return "<-"; + case INC: return "++"; + case DEC: return "--"; + + case EQL: return "=="; + case LSS: return "<"; + case GTR: return ">"; + case ASSIGN: return "="; + case NOT: return "!"; + + case NEQ: return "!="; + case LEQ: return "<="; + case GEQ: return ">="; + case DEFINE: return ":="; + case ELLIPSIS: return "..."; + + case LPAREN: return "("; + case LBRACK: return "["; + case LBRACE: return "{"; + case COMMA: return ","; + case PERIOD: return "."; + + case RPAREN: return ")"; + case RBRACK: return "]"; + case RBRACE: return "}"; + case SEMICOLON: return ";"; + case COLON: return ":"; + + case BREAK: return "break"; + case CASE: return "case"; + case CHAN: return "chan"; + case CONST: return "const"; + case CONTINUE: return "continue"; + + case DEFAULT: return "default"; + case DEFER: return "defer"; + case ELSE: return "else"; + case FALLTHROUGH: return "fallthrough"; + case FOR: return "for"; + + case FUNC: return "func"; + case GO: return "go"; + case GOTO: return "goto"; + case IF: return "if"; + case IMPORT: return "import"; + + case INTERFACE: return "interface"; + case MAP: return "map"; + case PACKAGE: return "package"; + case RANGE: return "range"; + case RETURN: return "return"; + + case SELECT: return "select"; + case STRUCT: return "struct"; + case SWITCH: return "switch"; + case TYPE: return "type"; + case VAR: return "var"; + } + + return "token(" + strconv.Itoa(tok) + ")"; +} + + +const ( + LowestPrec = 0; // non-operators + UnaryPrec = 7; + HighestPrec = 8; +) + + +func Precedence(tok int) int { + switch tok { + case LOR: + return 1; + case LAND: + return 2; + case EQL, NEQ, LSS, LEQ, GTR, GEQ: + return 3; + case ADD, SUB, OR, XOR: + return 4; + case MUL, QUO, REM, SHL, SHR, AND, AND_NOT: + return 5; + } + return LowestPrec; +} + + +// IsLiteral returns true if the token is a literal (IDENT, INT, FLOAT, CHAR, STRING). +func IsLiteral(tok int) bool { + return IDENT <= tok && tok <= STRING; +} + +// IsOperator returns true if the token is an operator. +func IsOperator(tok int) bool { + return ADD <= tok && tok <= AND_NOT_ASSIGN; +} + +// IsKeyword returns true if the token is a keyword. +func IsKeyword(tok int) bool { + return keywords_beg < tok && tok < keywords_end; +} + +var keywords map [string] int; + +func init() { + keywords = make(map [string] int); + for i := keywords_beg + 1; i < keywords_end; i++ { + keywords[TokenString(i)] = i; + } +}
-
usr/gri/pretty/parser.go
:Scanner "scanner"
のインポートが削除され、"token"
と"scanner"
(小文字のscanner
)がインポートされました。Parser
構造体のscanner
フィールドの型が*Scanner.Scanner
から*scanner.Scanner
に変更されました。- ファイル全体で
Scanner.XXX
形式のトークン参照がtoken.XXX
に置き換えられました。 Scanner.TokenString
の呼び出しがtoken.TokenString
に、Scanner.Precedence
の呼び出しがtoken.Precedence
にそれぞれ変更されました。
--- a/usr/gri/pretty/parser.go +++ b/usr/gri/pretty/parser.go @@ -8,7 +8,8 @@ import ( "flag"; "fmt"; "vector"; - Scanner "scanner"; + "token"; + "scanner"; AST "ast"; SymbolTable "symboltable"; ) @@ -20,7 +21,7 @@ type ErrorHandler interface { type Parser struct { - scanner *Scanner.Scanner; + scanner *scanner.Scanner; err ErrorHandler; // Tracing/debugging @@ -29,7 +30,7 @@ type Parser struct { comments *vector.Vector; - // Scanner.Token + // The next token pos int; // token source position tok int; // one token look-ahead val string; // token value (for IDENT, NUMBER, STRING only) @@ -106,29 +107,29 @@ func (P *Parser) next0() { if P.trace { P.printIndent(); switch P.tok { - case Scanner.IDENT, Scanner.INT, Scanner.FLOAT, Scanner.STRING: - fmt.Printf("[%d] %s = %s\n", P.pos, Scanner.TokenString(P.tok), P.val); - case Scanner.LPAREN: + case token.IDENT, token.INT, token.FLOAT, token.CHAR, token.STRING: + fmt.Printf("[%d] %s = %s\n", P.pos, token.TokenString(P.tok), P.val); + case token.LPAREN: // don't print '(' - screws up selection in terminal window fmt.Printf("[%d] LPAREN\n", P.pos); - case Scanner.RPAREN: + case token.RPAREN: // don't print ')' - screws up selection in terminal window fmt.Printf("[%d] RPAREN\n", P.pos); default: - fmt.Printf("[%d] %s\n", P.pos, Scanner.TokenString(P.tok)); + fmt.Printf("[%d] %s\n", P.pos, token.TokenString(P.tok)); } } } func (P *Parser) next() { - for P.next0(); P.tok == Scanner.COMMENT; P.next0() { + for P.next0(); P.tok == token.COMMENT; P.next0() { P.comments.Push(AST.NewComment(P.pos, P.val)); } } -func (P *Parser) Open(scanner *Scanner.Scanner, err ErrorHandler, trace, sixg, deps bool) { +func (P *Parser) Open(scanner *scanner.Scanner, err ErrorHandler, trace, sixg, deps bool) { P.scanner = scanner; P.err = err; @@ -152,9 +153,8 @@ func (P *Parser) error(pos int, msg string) { func (P *Parser) expect(tok int) { if P.tok != tok { - msg := "expected '" + Scanner.TokenString(tok) + "', found '" + Scanner.TokenString(P.tok) + "'"; - switch P.tok { - case Scanner.IDENT, Scanner.INT, Scanner.FLOAT, Scanner.STRING: + msg := "expected '" + token.TokenString(tok) + "', found '" + token.TokenString(P.tok) + "'"; + if token.IsLiteral(P.tok) { msg += " " + P.val; } P.error(P.pos, msg); @@ -164,7 +164,7 @@ func (P *Parser) expect(tok int) { func (P *Parser) OptSemicolon() { - if P.tok == Scanner.SEMICOLON { + if P.tok == token.SEMICOLON { P.next(); } } ... (以下、同様の置換がファイル全体にわたって行われる) ...
コアとなるコードの解説
このコミットのコアとなる変更は、Go言語のコンパイラにおける「関心の分離」という設計原則を具体的に適用したものです。
-
scanner.go
からのトークン定義の削除:- 以前の
scanner.go
は、字句解析のロジックと、Go言語のすべてのトークン(キーワード、演算子、リテラル種別など)の定義の両方を含んでいました。これは、scanner
が「トークンを生成する」という役割と「トークンとは何かを定義する」という役割の両方を担っていることを意味します。 - このコミットでは、トークンの定義を
scanner.go
から完全に削除しました。これにより、scanner
パッケージは純粋にソースコードを読み込み、トークンを識別して出力する機能に特化するようになりました。これは、単一責任の原則(Single Responsibility Principle)に則った改善です。
- 以前の
-
token.go
の新規作成とトークン定義の移動:- 新しく作成された
token.go
ファイルは、Go言語のすべてのトークン定数、それらの文字列表現を返すTokenString
関数、演算子の優先順位を定義するPrecedence
関数、およびキーワードのマップを保持します。 - これにより、
token
パッケージはGo言語の「トークン」という概念に関するすべての情報を提供する、独立した「辞書」のような役割を担うことになります。他のコンポーネント(parser
やprinter
など)は、トークンの種類や属性を知る必要がある場合、scanner
を介さずに直接token
パッケージを参照できるようになりました。
- 新しく作成された
-
parser.go
およびprinter.go
における依存関係の更新:parser.go
とprinter.go
は、以前はScanner.IDENT
のようにscanner
パッケージ経由でトークンを参照していました。この変更により、これらのファイルは直接token.IDENT
のようにtoken
パッケージを参照するようになりました。- これは、構文解析器やコード整形器が、トークンの「生成元」であるスキャナーではなく、トークンの「定義元」である
token
パッケージに直接依存するようになったことを意味します。これにより、依存関係がより論理的かつ直接的になり、コードの理解が容易になります。
この変更は、Goコンパイラの初期段階における重要なリファクタリングであり、コンパイラの各コンポーネントがより明確な役割を持ち、互いに疎結合になるように設計を進める上での基盤を築きました。これにより、将来的な機能追加や変更が容易になり、コンパイラ全体の保守性と拡張性が大幅に向上しました。