探索Lua 5.2内部実装:コンパイルシステム(1)概要
5246 ワード
テキスト
Luaは軽量級で効率的な言語です.この軽量レベルと高効率は、それ自体の仮想マシンの稼働効率だけでなく、コンパイルシステム全体の実現にも現れています.ほとんどのluaスクリプトは、ダイナミックなロードコンパイルを実行する必要があるため、コンパイルプロセス自体が非常に時間がかかり、メモリが多く消費される場合、全体的な実行効率にも影響し、この言語が「ダイナミック」ではないと感じます.コンパイルシステムが非常に優れているからこそ,luaを実際に使用する際にこのプロセスの存在をほとんど感じない.
Luaのコンパイルシステムを実現するのは難しくないかもしれませんが、効率的に実現するには、いくつかの課題があります.これはいくつかのすばらしい設計と実現技術が必要で、私たちがいくつかの時間をかけて探求する価値があります.
入力と出力
コンパイルシステムの仕事は,構文規則に合致するchunkを実行可能なclosureに変換することである.コンパイルシステムを理解するには,まず入力としてのchunkと最も出力されるclosure,およびそれらの対応関係を理解する.
closureといえば、protoを先に言わないわけにはいきません.closureオブジェクトはluaランタイムの関数のインスタンスオブジェクトであり、ランタイムに呼び出されるのはclosureです.protoオブジェクトはlua内部でclosureプロトタイプを表すオブジェクトであり、関数に関するほとんどの情報はここに保存されています.次の情報が含まれます.命令リスト:関数コンパイル後に生成された仮想マシン命令を含む. 定数テーブル:この関数の実行期間に必要なすべての定数は、命令で定数テーブルidを使用してインデックスされます. サブprotoテーブル:この関数に埋め込まれたすべてのprotoリスト、OP_CLOSURE命令のproto idがインデックスのこのテーブルです. ローカル変数の説明:この関数で使用されるすべてのローカル変数名、およびライフサイクル.すべての局所変数の実行期間がレジスタidに変換されるため、これらの情報はdebugでのみ使用される. Upvalue記述:closureの作成時にUpvalueを初期化するために関数で使用されるUpvalueの記述を設定します.
各closureは独自のprotoに対応し、実行期間の1つのprotoは、この関数インスタンスを表すために複数のclosureを生成することができる.
このことからclosureは実行期間のオブジェクトであり、実行期間との関係がより大きいことがわかる.コンパイル期間に関連するのはprotoオブジェクトであり、コンパイルプロセスが本当に生成する必要があるターゲットオブジェクトである.
ChunkはLuaの構文に合致するコードを表します.luaを呼び出すことができますload apiは、chunkをコンパイルします.lua_loadは、現在のchunkに基づいてmainfunc protoを生成し、このprotoのためにclosureを作成して現在のスタックの上部に配置し、次の実行を待つ.Chunk内部の各function statementも対応するprotoを生成し、外層関数のサブ関数リストに保存します.最外層のfunction statementのprotoはmainfunc protoのサブ関数リストに保存されます.したがって、コンパイルプロセス全体でmainfuncをルートノードとするprotoツリーが生成されます.
概要
機能区分によって、コンパイルシステム全体は以下の3つのモジュールに分けられる.語法分析モジュールllex.h .c 構文解析モジュールlparser.h .c 指令生成モジュールlcode.h .c
Luaはllexやyaccではなく、完全に手書きの文法や文法分析器を使っています.手書きアナライザを使用する理由は,まず効率を考慮することである.さらにyacc/bison自身が生成したコードは移植性にいくつかの問題があり,Luaの高い移植性の設計目標を達成することはなかった.また、手書きアナライザは、コンパイル中に必要なデータオブジェクトをC stackに割り当てることができます.これは後述します.一つのchunkに対して、Luaはその分析の過程で直接最終的な命令を生成し、ソースコードや文法構造の遍歴は余分ではない.すなわち,Luaはソースコードを1回遍歴して最終結果を生成する.
語法分析
Luaの文法解析モジュールは比較的簡単で独立しており,ソースコードを1つずつtokenに分割し,文法解析に提供することである.構文解析プログラムはluaX_を呼び出します.nextで次の単語を取得し、文法分析を行います.
Tokenは、タイプtokenと意味seminfoを含む単語を表すために使用されます.タイプはintで表され、文字でもenum RESERVEDでもよい.Enum RESERVEDは257から文字を残すために使用されている.タイプがTK_の場合NUMBER,seminfo.rはこの数字を表すために用いられる.TK_ならNAMEまたはTK_STRING,seminfo.tsは対応する文字列を表す.
LexState構造体の用途は、実際にはその名前に適切ではありません.LexStateは,現在の構文解析状態情報だけでなく,コンパイルシステム全体のグローバル状態も保存するために用いられるが,これは後述する.
構文解析と命令生成
構文解析器は、コンパイルプロセス全体のドライブです.対luaY_parser関数の呼び出しは、コンパイルプロセス全体を開始します.構文解析は「再帰的に下がる」方法を採用し、構文解析器から次のtokenを読み出し、このtokenとluaの構文規則に基づいて、上層部の構文規則を下層の構文規則に分解し、さらに解析を行う.構文によると、「再帰」はlua構文ではstatement関数とsubexpr関数の2つの場所にしか現れません.これは、この2つの関数でenterlevelとleveleavelを呼び出し、現在の呼び出しの深さを検出する理由です.再帰が深すぎると、コンパイルが間違って報告されます.解析の過程で,構文解析器は命令生成器を呼び出し,最終的な命令を直接生成する.
マクロ的には、コンパイルプロセス全体がproto treeを生成するプロセスです.構文解析器はmainfuncから出発し,mainfuncのprotoの解析と生成を開始する.1つのprotoを生成する過程で、生成された命令はprotoの命令リストに直接保存される.function statementまたはlocal function statementに遭遇した場合、まずサブ関数のprotoを生成し、次に戻って続行します.このような遍歴方式により,最終的にproto treeが構築される.
コンパイル中にFuncState構造体を使用して、関数コンパイルのステータスデータを保存します.各FuncStateには、周辺関数のFuncStateを参照するためのprev変数があり、現在分析が完了していないすべてのFuncStateがスタック構造を形成します.スタックの下部はmainfuncのFuncStateであり、スタックの上部は現在分析中のFuncStateである.新しい関数の解析を開始するたびに、新しいFuncStateが作成され、現在のFuncStateが新しいFuncStateのprevに保存され、現在のFuncStateが新しいFuncStateを指します.これは、スタック(open_func)に相当します.この新しい関数解析が完了するのを待つと、現在のFuncStateは役に立たず、現在のFuncStateを元のFuncStateに復元します.これはスタック(close_func)に相当します.
Dyndataはグローバルデータであり、彼自身もスタックです.上のFuncStateスタックに対応して、Dyndataは各FuncStateに対応するローカル変数記述リスト、gotoリスト、labelリストを保存します.これらのデータは、現在のFuncStateに従ってスタックとスタックを圧縮します.
前述したように,コンパイルシステム全体のグローバル状態はLexStateに保存される.LexStateにおけるグローバル状態に関連する主な変数は2つである.fsは現在コンパイル中の関数のFuncStateを指す.dydはグローバルなDyndataデータを指します.
FuncState自体はfでProtoへの参照を保存します.すべてのプロセスで生成された命令はProtoの命令リストに直接保存されます.FuncStateはまた、コンパイル中にprotoの定数テーブルを生成するためにhによってtableを参照する.このtableはkeyとして定数値,valueとして定数idを用いる.コンパイル中に定数が見つかった場合、まずこの定数値を使用してこのテーブルを検索します.見つかった場合は、この定数を定数テーブルに追加したことを示し、idを直接使用します.いいえ、定数テーブルに定数を追加し、それに応じてこのテーブルに追加します.
FuncState自体の解析にも階層関係がある.1つの関数自体はblockを使用して局所変数の有効範囲を制御します.関数自体がblockで、中にはwhile statement、for statementなど、サブblockも形成されます.関数内のこれらのblockは、関数自体のblockをルートノードとするblock treeを形成します.LuaはBlockCntを使用してblockのデータを保存します.FuncStateの解析法と同様に,BlockCntは周辺ブロックの参照をprevious変数で保存し,スタック構造を形成した.Enterblockとleaveblock関数は、スタックとスタックを圧縮します.FuncStateでは、blは現在のblockを指すために使用されます.
構文解析プロセス全体を見渡すと,Luaは実際には深さ優先の順序でFuncState treeとサブ構造BlockCnt treeを遍歴している.遍歴の過程で、すべてのコンパイル状態(FuncState,BlockCnt)がC stackに保存され、これは現在処理中のコンパイル状態のみが保存され、処理が完了したものがスタックに破棄されることを意味する.特定の構文構造を解析する場合も、Luaは構文ツリーオブジェクトを完全に構築するのではなく、プロセス中の構文構造を関数スタックに保存し、解析が完了するとすぐに破棄します.だからLuaで大きなプログラムを分析しても、メモリをあまり消費しません.しかし,これも命令生成に多くの面倒をもたらした.例えば、後方ジャンプでは、分析中に具体的なジャンプアドレスが分からない.完全な構文ツリーを構築すれば、これらの未決のアドレスを最後に解決することができます.Luaはこれらの問題を解決するためにいくつかのテクニックを使っています.後の文章で詳しく説明します.
C stackにコンパイル状態データを保存するもう一つの理由は,コンパイルシステムのエラーメカニズムに関連する.コンパイルシステム全体のエラーメカニズムは,仮想マシンの稼働期間と一致する異常処理メカニズム,すなわちlongjumpを採用する.エラーが発生した場合、直接最外層に飛び出して処理します.この場合、現在のコンパイルステータスデータはすべて自動的に破棄されます.
Luaは軽量級で効率的な言語です.この軽量レベルと高効率は、それ自体の仮想マシンの稼働効率だけでなく、コンパイルシステム全体の実現にも現れています.ほとんどのluaスクリプトは、ダイナミックなロードコンパイルを実行する必要があるため、コンパイルプロセス自体が非常に時間がかかり、メモリが多く消費される場合、全体的な実行効率にも影響し、この言語が「ダイナミック」ではないと感じます.コンパイルシステムが非常に優れているからこそ,luaを実際に使用する際にこのプロセスの存在をほとんど感じない.
Luaのコンパイルシステムを実現するのは難しくないかもしれませんが、効率的に実現するには、いくつかの課題があります.これはいくつかのすばらしい設計と実現技術が必要で、私たちがいくつかの時間をかけて探求する価値があります.
入力と出力
コンパイルシステムの仕事は,構文規則に合致するchunkを実行可能なclosureに変換することである.コンパイルシステムを理解するには,まず入力としてのchunkと最も出力されるclosure,およびそれらの対応関係を理解する.
closureといえば、protoを先に言わないわけにはいきません.closureオブジェクトはluaランタイムの関数のインスタンスオブジェクトであり、ランタイムに呼び出されるのはclosureです.protoオブジェクトはlua内部でclosureプロトタイプを表すオブジェクトであり、関数に関するほとんどの情報はここに保存されています.次の情報が含まれます.
各closureは独自のprotoに対応し、実行期間の1つのprotoは、この関数インスタンスを表すために複数のclosureを生成することができる.
このことからclosureは実行期間のオブジェクトであり、実行期間との関係がより大きいことがわかる.コンパイル期間に関連するのはprotoオブジェクトであり、コンパイルプロセスが本当に生成する必要があるターゲットオブジェクトである.
ChunkはLuaの構文に合致するコードを表します.luaを呼び出すことができますload apiは、chunkをコンパイルします.lua_loadは、現在のchunkに基づいてmainfunc protoを生成し、このprotoのためにclosureを作成して現在のスタックの上部に配置し、次の実行を待つ.Chunk内部の各function statementも対応するprotoを生成し、外層関数のサブ関数リストに保存します.最外層のfunction statementのprotoはmainfunc protoのサブ関数リストに保存されます.したがって、コンパイルプロセス全体でmainfuncをルートノードとするprotoツリーが生成されます.
概要
機能区分によって、コンパイルシステム全体は以下の3つのモジュールに分けられる.
Luaはllexやyaccではなく、完全に手書きの文法や文法分析器を使っています.手書きアナライザを使用する理由は,まず効率を考慮することである.さらにyacc/bison自身が生成したコードは移植性にいくつかの問題があり,Luaの高い移植性の設計目標を達成することはなかった.また、手書きアナライザは、コンパイル中に必要なデータオブジェクトをC stackに割り当てることができます.これは後述します.一つのchunkに対して、Luaはその分析の過程で直接最終的な命令を生成し、ソースコードや文法構造の遍歴は余分ではない.すなわち,Luaはソースコードを1回遍歴して最終結果を生成する.
語法分析
Luaの文法解析モジュールは比較的簡単で独立しており,ソースコードを1つずつtokenに分割し,文法解析に提供することである.構文解析プログラムはluaX_を呼び出します.nextで次の単語を取得し、文法分析を行います.
typedef union {
lua_Number r;
TString *ts;
} SemInfo; /* semantics information */
typedef struct Token {
int token;
SemInfo seminfo;
} Token;Tokenは、タイプtokenと意味seminfoを含む単語を表すために使用されます.タイプはintで表され、文字でもenum RESERVEDでもよい.Enum RESERVEDは257から文字を残すために使用されている.タイプがTK_の場合NUMBER,seminfo.rはこの数字を表すために用いられる.TK_ならNAMEまたはTK_STRING,seminfo.tsは対応する文字列を表す.
LexState構造体の用途は、実際にはその名前に適切ではありません.LexStateは,現在の構文解析状態情報だけでなく,コンパイルシステム全体のグローバル状態も保存するために用いられるが,これは後述する.
構文解析と命令生成
構文解析器は、コンパイルプロセス全体のドライブです.対luaY_parser関数の呼び出しは、コンパイルプロセス全体を開始します.構文解析は「再帰的に下がる」方法を採用し、構文解析器から次のtokenを読み出し、このtokenとluaの構文規則に基づいて、上層部の構文規則を下層の構文規則に分解し、さらに解析を行う.構文によると、「再帰」はlua構文ではstatement関数とsubexpr関数の2つの場所にしか現れません.これは、この2つの関数でenterlevelとleveleavelを呼び出し、現在の呼び出しの深さを検出する理由です.再帰が深すぎると、コンパイルが間違って報告されます.解析の過程で,構文解析器は命令生成器を呼び出し,最終的な命令を直接生成する.
マクロ的には、コンパイルプロセス全体がproto treeを生成するプロセスです.構文解析器はmainfuncから出発し,mainfuncのprotoの解析と生成を開始する.1つのprotoを生成する過程で、生成された命令はprotoの命令リストに直接保存される.function statementまたはlocal function statementに遭遇した場合、まずサブ関数のprotoを生成し、次に戻って続行します.このような遍歴方式により,最終的にproto treeが構築される.
コンパイル中にFuncState構造体を使用して、関数コンパイルのステータスデータを保存します.各FuncStateには、周辺関数のFuncStateを参照するためのprev変数があり、現在分析が完了していないすべてのFuncStateがスタック構造を形成します.スタックの下部はmainfuncのFuncStateであり、スタックの上部は現在分析中のFuncStateである.新しい関数の解析を開始するたびに、新しいFuncStateが作成され、現在のFuncStateが新しいFuncStateのprevに保存され、現在のFuncStateが新しいFuncStateを指します.これは、スタック(open_func)に相当します.この新しい関数解析が完了するのを待つと、現在のFuncStateは役に立たず、現在のFuncStateを元のFuncStateに復元します.これはスタック(close_func)に相当します.
Dyndataはグローバルデータであり、彼自身もスタックです.上のFuncStateスタックに対応して、Dyndataは各FuncStateに対応するローカル変数記述リスト、gotoリスト、labelリストを保存します.これらのデータは、現在のFuncStateに従ってスタックとスタックを圧縮します.
前述したように,コンパイルシステム全体のグローバル状態はLexStateに保存される.LexStateにおけるグローバル状態に関連する主な変数は2つである.fsは現在コンパイル中の関数のFuncStateを指す.dydはグローバルなDyndataデータを指します.
FuncState自体はfでProtoへの参照を保存します.すべてのプロセスで生成された命令はProtoの命令リストに直接保存されます.FuncStateはまた、コンパイル中にprotoの定数テーブルを生成するためにhによってtableを参照する.このtableはkeyとして定数値,valueとして定数idを用いる.コンパイル中に定数が見つかった場合、まずこの定数値を使用してこのテーブルを検索します.見つかった場合は、この定数を定数テーブルに追加したことを示し、idを直接使用します.いいえ、定数テーブルに定数を追加し、それに応じてこのテーブルに追加します.
FuncState自体の解析にも階層関係がある.1つの関数自体はblockを使用して局所変数の有効範囲を制御します.関数自体がblockで、中にはwhile statement、for statementなど、サブblockも形成されます.関数内のこれらのblockは、関数自体のblockをルートノードとするblock treeを形成します.LuaはBlockCntを使用してblockのデータを保存します.FuncStateの解析法と同様に,BlockCntは周辺ブロックの参照をprevious変数で保存し,スタック構造を形成した.Enterblockとleaveblock関数は、スタックとスタックを圧縮します.FuncStateでは、blは現在のblockを指すために使用されます.
構文解析プロセス全体を見渡すと,Luaは実際には深さ優先の順序でFuncState treeとサブ構造BlockCnt treeを遍歴している.遍歴の過程で、すべてのコンパイル状態(FuncState,BlockCnt)がC stackに保存され、これは現在処理中のコンパイル状態のみが保存され、処理が完了したものがスタックに破棄されることを意味する.特定の構文構造を解析する場合も、Luaは構文ツリーオブジェクトを完全に構築するのではなく、プロセス中の構文構造を関数スタックに保存し、解析が完了するとすぐに破棄します.だからLuaで大きなプログラムを分析しても、メモリをあまり消費しません.しかし,これも命令生成に多くの面倒をもたらした.例えば、後方ジャンプでは、分析中に具体的なジャンプアドレスが分からない.完全な構文ツリーを構築すれば、これらの未決のアドレスを最後に解決することができます.Luaはこれらの問題を解決するためにいくつかのテクニックを使っています.後の文章で詳しく説明します.
C stackにコンパイル状態データを保存するもう一つの理由は,コンパイルシステムのエラーメカニズムに関連する.コンパイルシステム全体のエラーメカニズムは,仮想マシンの稼働期間と一致する異常処理メカニズム,すなわちlongjumpを採用する.エラーが発生した場合、直接最外層に飛び出して処理します.この場合、現在のコンパイルステータスデータはすべて自動的に破棄されます.