はじめに
こんにちは
私はコンパイラーに近いトピックについて書き続けます。 今回は、構文木で動作するインタープリターの設計と作成に触れます。
以前の記事- 「LR（0）アナライザーを作成します。 複雑さについての簡単な言葉で、「インタープリターではパーサーをゼロから構築するのではなく、その記事で説明されているベストプラクティスを使用しているためです。 ええ、もう1つ重要な点があります。JavaScriptで記述します。 私はこの言語のファンではありませんが、これは一般の人が結果を見るのに最も便利な方法だと思います。 誰もがそれをダウンロードすることを敢えてしているわけではなく、何を知らないのか、そして単にページを開くよりもさらに困難です。 機器の非定型性は、例の「学習」によって相殺されます。 作業の速度は重要ではありません（100〜150行の制限、インタープリターで遊ぶために他の人はタイプしたくないようです）。JSのコードの理解度は非常に高いです。
3つの住所コード
まず、何を解釈するかを決める必要があります。 3つのアドレスコードを選択しました。
これは何ですか これは、高レベルのコードとコンパイルされたバイトコードの間の中間言語であると想定されていました。 たとえば、Sishnaya文字列：
これは次のようになります。a = (b + c) * (d - e)
f = b + c g = d - e a = f * g
この言語の主な前提は、各コマンドに含まれるオペランドが3つ以下であることです。 これにより、中間コードをバイトコードに非常に簡単にコンパイルできます。
言語には算術演算以外に何が含まれますか？
これらは主に変数と配列の宣言です。 すべての変数は整数です。 ところで、配列インデックスもオペランドとみなされるため、バイナリ演算では、3つのオペランドの制限を超えないように配列を使用することはできません。 変数はポインターにすることができます（この場合、ポインターのタイプは整数と同じです）。
言語にユーザーデータを入力および出力する機能を追加することは論理的です。 また、コードの実行を制御する必要があります（制御フロー）-条件付きジャンプと無条件ジャンプ。 さて、スタックなしで行う方法は、変数の数に制限がないという事実のために必要ではありませんが、それでも多くの場合非常に便利です。 言語について考えた後、文法を設計する必要があります。 また、これは私たちの合成言語で行うのはそれほど難しくありません。
// <line> = <vars_decl>|<command> // <var_decl> = <ident>|<ident><left_sq_bracket><number><right_sq_bracket> // <var_list> = <var_decl>|<var_list><comma><whitespace><var_decl> // <vars_decl> = <var_keyword><whitespace><var_list> // L: operation <command> = <ident><colon><whitespace><operation>|<operation> // <operation> = <io>|<binary>|<control>|<assign>|<stack> // / in var, out var <io> = <in_keyword><whitespace><var_output_array>|<out_keyword><whitespace><var_input_array> // - [], , <var_output> = <var_ptr>|<ident> <var_output_array> = <var_output>|<var_ar> // <var_ar> = <ident><left_sq_bracket><var_numb><right_sq_bracket> <var_numb> = <ident>|<number> // <var_ptr> = <asterisk><ident> // <var_ref> = <ref><ident> // - [], , , , <var_input_array> = <var_input>|<var_ar> <var_input> = <var_output>|<var_ref>|<number> // , 3 <binary> = <var_output><assign_sign><var_input><operator><var_input> <operator> = <plus>|<minus>|<asterisk>|<div>|<mod> // <control> = <goto>|<if> // <goto> = <goto_keyword><whitespace><ident> // <if> = <if_keyword><whitespace><var_input><comp_operator><var_input><whitespace><goto> // <assign> = <var_output_array><assign_sign><var_input>|<var_output><assign_sign><var_input_array> // <stack> = <pop_keyword><whitespace><var_output_array>|<push_keyword><whitespace><var_input_array>
他のすべての文字（右の部分にあり、左にはありません）は端末です。以下で少し説明します。
解析ツリーの構築
前に書いたように、トークンのストリームはパーサーの入力に送られます。このストリームは、入力文字列に基づいて字句解析プログラムによって生成されます。
たとえば、文字列の場合
if a<b goto L
トークンの次のストリーム、 LexKeywordIf 、 LexWhitespace 、 LexIdent 、 LexComp 、 LexIdent 、 LexWhitespace 、 LexKeywordGoto 、 LexWhitespace 、 LexIdentを取得します。
非端末の説明から必要なトークンを簡単に追跡できます。
<ident> = <letter>|<ident><letter>|<ident><digit> <number> = <digit>|<number><digit> <plus> = '+' <minus> = '-' <div> = '/' <mod> = '%' <comp_operator> = '<'|'>'|'>='|'<='|'=='|'!=' <whitespace> = ' ' <pop_keyword> = "pop" <push_keyword> = "push" <goto_keyword> = "goto" <in_keyword> = "in" <out_keyword> = "out" <var_keyword> = "var" <if_keyword> = "if" <left_sq_bracket> = '[' <right_sq_bracket> = ']' <colon> = ':' <asterisk> = '*' <assign_sign> = '=' <ref> = '&' <comma> = ',' $ = end of line
コード自体は非常にシンプルで、一般的な形式でのみ提供します。
function GetLex(stream) { var c = stream.get(); switch ( c ) { case ' ': return {type: LexTypes.LexWhitespace}; ... } if (c <= '9' && c >= '0') return {type: LexTypes.LexNumber, number: readNumber()}; if (c > 'z' || c < 'a') return {type: LexTypes.LexError}; var ident = readIdent(); if (ident == 'pop') return {type: LexTypes.LexKeywordPop}; ... return {type: LexTypes.LexIdent, ident: ident}; }
これでトークンのストリームができました。
パーサーに渡すことができます。 もちろん、インタープリター用に事前生成されたテーブルを使用してLR（0）を選択しました（取得方法も書きました）。 82の状態と、テーブルの1400行の書式付きコードが判明しました。 パーサーのコード自体は、C ++の同様のコードと実際には変更されていません。ツリー自体の構築について言及するだけです。
ActionShiftアクションごとに、トークンを含むツリーリーフ（子を持たないノード）を作成します。 そして、ルールを折りたたむと、右側の対応するシンボルを1つのバンドルに関連付けて、新しいノードを形成し、このノード（文法のフレームワークのノード）の非終端を示します。 少し複雑に聞こえますが、実際は単純で、バイナリ操作のツリーの例です。
通訳の構造と打ち上げの準備
インタープリターには、ソースコードの各行のツリー、現在の行の番号（エラーの表示に必要、IPとして-指示ポインター 'a、実行コードのアドレス）、ラベルの配列、変数の配列、スタック操作の実際のスタック、およびいくつかのオブジェクトが含まれますヘルパー。
開始する前に、すべてのオブジェクトをリセットする必要があります。 次に、各行を解析します。 なぜこれを行うのですか？ ラベルの配列を構成するために、コマンド内でラベルへの遷移に出会うことができます。ラベルは、実行中の行よりもコード内にあります。 したがって、実行を開始する前にコード分析を実行します。 ここでは、構文的に間違った行を取得した場合でも、すぐに報告する必要があるという意味ではないことを考慮に入れる必要があります。
解釈するとき、このセクションに到達しないことがあります。
コード実行
ステップバイステップとシンプルの2つの実行モードを導入しました。 名前から、それぞれが何であるかが明らかです。
コード：
function executeLine() { if (input_data.active) { setTimeout(executeLine, 100); return ; } if (input_data.error) return ; var line = lines[currentline]; var ret; if (!line.correct) { addlog('syntax error at position ' + line.pos); return ; } var general = line.tree.childs[0]; if (general.nonterm == NonTerminals.vars_decl) ret = interp_var_list(general.childs[0]); else ret = interp_operation(general.childs[0]); if (!ret) return ; currentline++; if (currentline == linecount) { addlog('Finish!', true); return ; } if (!step_by_step) setTimeout(executeLine, 0); }
input_dataは最初のヘルパーオブジェクトです。 JavaScriptには独自のイベントモデルがあり、独自のイベントを使用することはできません。そのため、（コマンドで）値入力ダイアログを表示するとき、「フリーズ」フラグ-input_data.activeを設定します。つまり、ダイアログが完了するのを待ってから、コードの実行を続ける必要があります。 2番目のオブジェクトstep_by_stepは、ステップバイステップモードが使用されていることを示します。使用されていない場合は、関数を再度呼び出すことを計画しています。
実行自体はプリミティブです-ほとんどすべての非ターミナルには、それを処理する関数があります。 そして、ツリーを下って非端末を収集し、その値を取得します。
非端末処理の例：
function interp_control_goto(node) { var ident = node.childs[0].lex.ident; if (ident in labels) { currentline = labels[ident] - 1; return true; } if (!check_var(ident)) return false; var val = vars[ident]; if (val >= linecount) { addlog('invalid address of code'); return false; } currentline = val.value - 1; return true; }
あなたはここでの仕事でこれをすべて見ることができます。
FireFoxで最適に動作し、Opera（キー押下/キーダウン）でエディターの「チップ」の一部が動作しません。ChromeとIE（selectionStart）でも同様です。 しかし、インタープリター自体は適切に動作するはずです。
例として、階乗を計算するための再帰関数があります（もちろん、コードでオーバーロードされますが、これは特に言語の機能を示すためです）。