演算子に先行する降順パーサー

ダグラス・クロックフォード



2007-02-21

はじめに

1973年、最初の年次シンポジウム「 プログラミング言語の原則のシンポジウム 」で、 ウォンプラットは「 トップダウン演算子の優先順位 」という記事を紹介しました。 この記事では、Prattが、再帰降下の最善の側面とフロイド演算子の優先順位の方法を組み合わせた解析方法について説明しました。 プラットの方法は、再帰降下に非常に似ていますが、必要なコードが少なく、はるかに高速に動作します。 プラットは、彼の方法は学習、実装、使用が簡単で、非常に効果的で非常に柔軟であると述べました。 そのダイナミズムにより、拡張可能な言語に使用できます。



しかし、メソッドが本当に完璧な場合、コンパイラ開発者はまだそれを無視するのでしょうか？ プラットは、彼の記事で、BNF文法とその多数の修正、および関連する定理とオートマトンがより早くニッチを占有し、現在では他の方向の構文解析理論の開発を妨げることを示唆しました。



別の説明があります：この方法は、動的な関数型プログラミング言語に最も効果的であり、静的な手続き型言語で使用するのははるかに困難です。 プラットは彼の記事をLispで例として説明し、トークンのストリームを使用して構文木をふざけて構築します。 しかし、構文解析の手法は、Spartanによる構文の放棄を説くLispプログラマーのコミュニティでは特に重要ではありません。 Lispの作成以来、この言語にALGOLスタイルの豊富な構文を与える試みが多くありました： CGOL Pratt 、 Lisp-2 、 MLISP 、 Dylan 、 InterlispのClisp 、 オリジナルのMcCarthy M式など。 しかし、それらはすべて失敗しました。 Lispコミュニティにとって、プログラムとデータの一貫性は、表現力豊かな構文よりも重要でした。 一方、大多数のプログラマーは構文が大好きなので、Lisp自体は人気がありません。 プラットメソッドは動的言語を必要としますが、動的言語のコミュニティは歴史的に、プラットメソッドによって非常に便利に実装される構文を使用していません。

Javascript

JavaScriptの登場により状況は変わりました。 JavaScriptは動的で機能的な言語ですが、構文的には明らかにCファミリーに属します。 それは動的言語であり、そのコミュニティは構文が大好きです。



JavaScriptもオブジェクト指向です。 プラットの記事は、オブジェクト指向のアプローチを想定していましたが、これについての表現力豊かな表記法が欠けていました。 JavaScriptは、Prattメソッドを実装するための理想的な言語です。 JavaScriptパーサーを迅速かつ効率的に作成する方法を紹介します。



JavaScriptを完全に扱うには1つの記事では不十分であり、おそらく私たちはそうしたくありません。この言語では悪魔が彼の足を折るからです。 しかし、それには素晴らしい側面があり、非常に検討に値します。 Simplified JavaScriptを処理できるパーサーを作成します。 そして、このパーサーをSimplified JavaScriptで作成します。 簡素化されたJavaScriptは、以下を含むすべての言語で最高のものです。

• 最初のクラスのオブジェクトとして機能します。 簡略化されたJavaScriptでは、関数は字句スコープを持つラムダ式です。
• プロトタイプ継承を持つ動的オブジェクト。 クラスはありません。 通常の割り当てを使用して、オブジェクトに新しいメンバーを追加できます。 オブジェクトは別のオブジェクトのメンバーを継承できます。
• オブジェクトと配列のリテラル。 新しいオブジェクトと配列を作成するには、この表記法が非常に便利です。 JavaScriptリテラルは、 JSON形式のインスピレーションとして機能します 。

JavaScriptプロトタイプを利用して、文字を継承するトークンオブジェクトを作成します。 実装には、 Object.create



メソッド（既存のオブジェクトのメンバーを継承する新しいオブジェクトを作成する）と、入力行にトークンオブジェクトの配列を作成する字句解析Object.create



が必要です。 この配列を移動して、解析ツリーを構築します。

キャラクターテーブル

演算子や識別子などの各トークンは、キャラクターから継承されます。 可能なすべての文字（言語トークンのタイプを決定する）をsymbol_table



オブジェクトにsymbol_table



ます。

 var symbol_table = {};
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

original_symbol



オブジェクトは、他のすべての文字のプロトタイプです。 彼のメソッドは通常、オーバーロードされています。 nud



メソッドとled



メソッドの意味、および結合力については、後の「優先順位」セクションで説明します。

 var original_symbol = { nud: function () { this.error("Undefined."); }, led: function (left) { this.error("Missing operator."); } };
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

文字を作成する関数を定義します。 シンボル識別子（ id



）とバインディング強度（オプションのパラメーターbp



、デフォルトはゼロ）を受け入れ、このid



シンボルオブジェクトを返します。 シンボルがsymbol_table



に既に存在する場合、関数はそれを返します。 それ以外の場合、 original_symbol



から継承された新しいキャラクターを作成し、キャラクターテーブルに保存して戻ります。 シンボルオブジェクトには、最初はid



、value、左バインディング強度（ lbp



）、およびoriginal_symbol



からのすべてが含まれてoriginal_symbol



ます。

 var symbol = function (id, bp) { var s = symbol_table[id]; bp = bp || 0; if (s) { if (bp >= s.lbp) { s.lbp = bp; } } else { s = Object.create(original_symbol); s.id = s.value = id; s.lbp = bp; symbol_table[id] = s; } return s; };
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

一般的な区切り文字と末尾の文字を宣言します。

 symbol(":"); symbol(";"); symbol(","); symbol(")"); symbol("]"); symbol("}"); symbol("else");
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

記号(end)



は、トークンストリームの終了を示します。 シンボル(name)



は、変数名などの新しい名前のプロトタイプです。 ユーザートークンとの一致の可能性を避けるために、識別子にブラケットを含めました。

 symbol("(end)"); symbol("(name)");
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

トークン

ソーステキストは、 type



フィールド（ "name"



、 "string"



、 "number"



または"operator"



）およびvalue



フィールド（stringまたはnumber）を含むプリミティブトークンのtokens



配列に既に変換されていると仮定します。 token



変数は常に現在のトークンを参照します。

 var token;
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

advance



関数は、次のプリミティブトークンから新しいトークンオブジェクトを作成し、トークンtokenを割り当てtoken



。 オプションのid



パラメータが渡された場合、関数はトークンに対応する識別子があることを確認します。 新しいトークンオブジェクトのプロトタイプは、現在のスコープ内のシンボル(name)



またはシンボルテーブルのシンボルです。 新しいトークンのarity



フィールドは、 "name"



、 "literal"



、または"operator"



いずれかになります。 その後、プログラムでのトークンの役割についてさらに学習すると、この値は"binary"



、 "unary"



または"statement"



変更できます。

 var advance = function (id) { var a, o, t, v; if (id && token.id !== id) { token.error("Expected '" + id + "'."); } if (token_nr >= tokens.length) { token = symbol_table["(end)"]; return; } t = tokens[token_nr]; token_nr += 1; v = t.value; a = t.type; if (a === "name") { o = scope.find(v); } else if (a === "operator") { o = symbol_table[v]; if (!o) { t.error("Unknown operator."); } } else if (a === "string" || a === "number") { a = "literal"; o = symbol_table["(literal)"]; } else { t.error("Unexpected token."); } token = Object.create(o); token.value = v; token.arity = a; return token; };
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

範囲

ほとんどの言語には、新しい文字（変数名など）を定義するための表記があります。 単純な言語では、新しい単語に出会うと、それを自動的に識別してシンボルテーブルに入れます。 より複雑な言語には、プログラマが変数へのアクセスとその有効期間を制御できる範囲があります。



スコープは、変数が定義されて使用可能なプログラムの一部です。 スコープはネストできます。 特定のスコープで定義された変数は、外部からは見えません。



現在のスコープを別のscope



変数に保存します。

 var scope;
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

original_scope



オブジェクトは、スコープであるすべてのオブジェクトのプロトタイプです。 新しい変数を定義できるdefine



メソッドが含まれていdefine



。 define



メソッドは、名前トークンを変数トークンに変換します。 変数がスコープ内で既に定義されている場合、または名前が予約語である場合、エラーがスローされます。

 var itself = function () { return this; }; var original_scope = { define: function (n) { var t = this.def[n.value]; if (typeof t === "object") { n.error(t.reserved ? "Already reserved." : "Already defined."); } this.def[n.value] = n; n.reserved = false; n.nud = itself; n.led = null; n.std = null; n.lbp = 0; n.scope = scope; return n; },
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

find



メソッドは、名前で定義を検索するために使用されます。 現在のスコープから検索を開始し、必要に応じてチェーンをさかのぼり、文字のテーブルで終了します。 定義が見つからなかった場合、 symbol_table["(name)"]



返します。 メソッドは、指定された名前の値がundefined



と等しくundefined



（つまり、未宣言の名前にアクセスすることを意味します）および関数ではないこと（継承されたメソッドとの衝突を示すこと）をチェックします。

  find: function (n) { var e = this, o; while (true) { o = e.def[n]; if (o && typeof o !== 'function') { return e.def[n]; } e = e.parent; if (!e) { o = symbol_table[n]; return o && typeof o !== 'function' ? o : symbol_table["(name)"]; } } },
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

pop



メソッドはスコープを閉じ、親に置き換えます。

  pop: function () { scope = this.parent; },
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

reserve



メソッドは、特定の名前が現在のスコープ内の予約語であることを示すために使用されます。

  reserve: function (n) { if (n.arity !== "name" || n.reserved) { return; } var t = this.def[n.value]; if (t) { if (t.reserved) { return; } if (t.arity === "name") { n.error("Already defined."); } } this.def[n.value] = n; n.reserved = true; } };
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

次に、予約語を処理するための戦略が必要です。 一部の言語では、プログラムの構造を記述する単語（ if



）は予約されており、変数名として使用できません。 パーサーの柔軟性により、さらに多くを達成できます。 たとえば、どの関数でも、取得した名前は言語演算子または変数名として使用できます。 予約語として使用された後にのみ、単語をローカルで予約します。 新しいキーワードを追加しても既存のプログラムが中断されることはないため、言語の作成者の生活が簡素化され、名前の使用に関する不必要な制限に邪魔されないため、プログラマーの生活が単純化されます。



関数またはブロックの新しいスコープを作成する場合、 new_scope



関数を呼び出します。これにより、 original_scope



プロトタイプの新しいインスタンスが作成されます。

 var new_scope = function () { var s = scope; scope = Object.create(original_scope); scope.def = {}; scope.parent = s; return scope; };
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

優先順位

トークンオブジェクトには、優先順位に関する決定、他のトークンの選択、ツリーの構築を可能にするメソッドが含まれています（さらに複雑なプロジェクトでは、タイプのチェック、コードの最適化と生成も可能）。 優先順位の主なタスクは次のとおりです。2つの演算子の間の指定されたオペランドについて、オペランドが左演算子を参照するか右演算子を参照するかを決定します。



d



A e



B f







AとBが演算子である場合、どのオペランドe



がそれらに属しますか？ つまり、 (d



A e)



B f



選択する必要があります

およびd



A (e



B f)



。



最終的に、解析の主な問題は、このあいまいさを解決することです。 このメソッドのトークンオブジェクトには、バインディング強度（または優先度レベル）と、単純なメソッドnud



（null表記、nullマッチ）およびled



（左表記、左マッチ）が格納されます。 nud



は、どのトークンが左側にあるかは関係ありませんが、 led



メソッドは重要です。 nud



メソッドnud



、値（変数とリテラル）およびプレフィックス演算子によって使用されます。 led



メソッドは、中置演算子と後置演算子によって使用されます。 トークンには、 nud



メソッドとled



メソッドの両方をnud



ます。 たとえば、マイナス（ -



）はプレフィックス（数字の符号を変更）またはインフィックス（減算）のいずれかであるため、両方のメソッドが定義されています。



パーサーは、次のバインド力を使用します。

0	コミュニケーションのないオペレーター; など
10	代入演算子： = など。
20	?:
30	|| &&
40	比較演算子： === など
50	+ -
60	* /
70	単項演算子：！ など
80	. [ (

表現

Prattメソッドの主要なコンポーネントはexpression



関数です。 入力として正しい結合力を受け入れます。これは、式がどの程度アクティブに正しいトークンに結合するかを示します。

 var expression = function (rbp) { var left; var t = token; advance(); left = t.nud(); while (rbp < token.lbp) { t = token; advance(); left = t.led(left); } return left; }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

expression



関数は、リテラル、変数、プレフィックス演算子を処理する現在のトークンtoken



のnud



メソッドを呼び出します。 次に、右のバインディング強度が次のトークンの左のバインディング強度より小さくなるまで、 led



メソッドが呼び出されます。 このメソッドは、中置演算子と後置演算子を処理します。 nud



メソッドとled



メソッド自体がexpression



を呼び出すことができるため、プロセスは再帰的になります。

中置演算子

+



演算子は中置演算子であるため、トークンオブジェクトを、 +



記号の左右のオペランドである2つのブランチ（ first



とsecond



）を持つツリーに変換するled



メソッドがあります。 led



メソッドは左側のオペランドをパラメーターとして受け取り、右側のオペランドはexpression



を呼び出すことで検出されexpression



。

 symbol("+", 50).led = function (left) { this.first = left; this.second = expression(50); this.arity = "binary"; return this; };
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

*



記号は、 id



値とバインディング強度を除いて+



と同じです。 オペランドとより強く結び付けられているため、バインディングの強度が高くなります。

 symbol("*", 60).led = function (left) { this.first = left; this.second = expression(60); this.arity = "binary"; return this; };
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

すべての中置演算子が同じように見えるわけではありませんが、多くはそうです。 したがって、中置演算子の作成に役立つinfix



関数を定義することにより、作業を簡素化できます。 infix



関数は、 id



、バインディングパワー、およびオプションでled



関数を受け入れます。 関数が指定されていない場合、 infix



はデフォルトのled



関数を作成します。これはほとんどの場合に機能します。

 var infix = function (id, bp, led) { var s = symbol(id, bp); s.led = led || function (left) { this.first = left; this.second = expression(bp); this.arity = "binary"; return this; }; return s; }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

これで、中置演算子をより宣言的なスタイルで記述できます。

 infix("+", 50); infix("-", 50); infix("*", 60); infix("/", 60);
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

===



はJavaScriptの正確な比較演算子です。

 infix("===", 40); infix("!==", 40); infix("<", 40); infix("<=", 40); infix(">", 40); infix(">=", 40);
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

三項演算子は、 ?



区切られた3つの式を受け入れ?



および:



これは通常の挿入演算子ではないため、ここでled



関数を設定する必要があります。

 infix("?", 20, function (left) { this.first = left; this.second = expression(0); advance(":"); this.third = expression(0); this.arity = "ternary"; return this; });
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

ドット演算子（ .



）は、オブジェクトのメンバーを参照するために使用されます。 その右側に名前がなければなりませんが、リテラルとして使用されます。

 infix(".", 80, function (left) { this.first = left; if (token.arity !== "name") { token.error("Expected a property name."); } token.arity = "literal"; this.second = token; this.arity = "binary"; advance(); return this; });
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

[



演算子は、オブジェクトのメンバーまたは配列の要素を動的に参照するために使用されます。 右側の式の後には右大括弧が続くべきです。

 infix("[", 80, function (left) { this.first = left; this.second = expression(0); this.arity = "binary"; advance("]"); return this; });
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

これらの挿入演算子はすべて左結合です。 また、右結合演算子（論理||や&&など）を作成して、適切な結合力を減らすこともできます。

 var infixr = function (id, bp, led) { var s = symbol(id, bp); s.led = led || function (left) { this.first = left; this.second = expression(bp - 1); this.arity = "binary"; return this; }; return s; }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

&&



演算子は、falseの場合は最初のオペランドを返し、そうでない場合は2番目のオペランドを返します。 演算子||



trueの場合、最初のオペランドを返します。 false値は0



で、空の文字列は""



、 false



またはnull



です。 他の値（オブジェクトを含む）はすべてtrueと見なされます。

 infixr("&&", 30); infixr("||", 30);
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

プレフィックス演算子

連想インフォグラフィック演算子に使用したコードは、プレフィックス演算子に適合させることができます。 プレフィックス演算子は結合的です。 プレフィックスは左側の何にもバインドしないため、左側のバインド力はありません。 プレフィックス演算子は予約語である場合があります。

 var prefix = function (id, nud) { var s = symbol(id); s.nud = nud || function () { scope.reserve(this); this.first = expression(70); this.arity = "unary"; return this; }; return s; } prefix("-"); prefix("!"); prefix("typeof");
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

ブラケットのnud



メソッド(



advance(")")



呼び出しますadvance(")")



は、ペアブラケットを見つけます。 トークン自体は、 nud



が括弧の内容のみを返すため、構文ツリーに分類されません。

 prefix("(", function () { var e = expression(0); advance(")"); return e; });
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

割り当て演算子

infixr



関数を使用して、 infixr



をinfixr



できます。 ただし、別の操作を行うため、別のassignment



関数を作成することをお勧めします。左側の式が左辺値であることを確認してください。 。

 var assignment = function (id) { return infixr(id, 10, function (left) { if (left.id !== "." && left.id !== "[" && left.arity !== "name") { left.error("Bad lvalue."); } this.first = left; this.second = expression(9); this.assignment = true; this.arity = "binary"; return this; }); }; assignment("="); assignment("+="); assignment("-=");
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

注：継承のようなものを実装しました。 assignment



関数はinfixr



を呼び出しinfixr



結果をinfixr



symbol



を呼び出しinfixr



結果をinfixr



。

定数

constant



関数は、言語定数を作成します。 nud



メソッドは、名前トークンをリテラルトークンに変換します。

 var constant = function (s, v) { var x = symbol(s); x.nud = function () { scope.reserve(this); this.value = symbol_table[this.id].value; this.arity = "literal"; return this; }; x.value = v; return x; }; constant("true", true); constant("false", false); constant("null", null); constant("pi", 3.141592653589793);
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

シンボル(literal)



は、すべての文字列リテラルと数値リテラルのプロトタイプです。 nud



トークンのnud



メソッドは、トークン自体を返します。

 symbol("(literal)").nud = itself;
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

申し出

オリジナルでは、式のみが存在する関数型言語用にPrattメソッドが作成されました。 ほとんどの一般的な言語は、式として埋め込むのがそれほど難しくないステートメントを使用します。 トークンに新しいメソッドを追加すると、文を簡単に処理できます： std



（文の表示、文の一致）。 std



メソッドはnud



に似ていますが、文の先頭でのみ呼び出されます。



statement



関数は1つの文を解析します。 現在のトークンにstd



メソッドが含まれている場合、トークンは予約され、このメソッドが呼び出されます。 それ以外の場合、文はセミコロンで終わる式であると見なします。 信頼性のために、割り当てでも関数呼び出しでもない式をエラーと見なします。

 var statement = function () { var n = token, v; if (n.std) { advance(); scope.reserve(n); return n.std(); } v = expression(0); if (!v.assignment && v.id !== "(") { v.error("Bad expression statement."); } advance(";"); return v; };
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

statements



関数は、ブロックの終了を示すトークン(end)



または}



を検出するまでstatements



解析します。 この関数は、文、文の配列、または文が見つからない場合はnull



返します。

 var statements = function () { var a = [], s; while (true) { if (token.id === "}" || token.id === "(end)") { break; } s = statement(); if (s) { a.push(s); } } return a.length === 0 ? null : a.length === 1 ? a[0] : a; };
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

stmt



関数は、文字テーブルに文の文字を追加するために使用されます。 id



とstd



関数をパラメーターとして受け取ります。

 var stmt = function (s, f) { var x = symbol(s); x.std = f; return x; };
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

ブロック提案は、新しいスコープが定義されている中括弧内の文のリストです。 通常のJavaScriptにはブロックのスコープはありませんが、Simplified JavaScriptには含まれます。

 stmt("{", function () { new_scope(); var a = statements(); advance("}"); scope.pop(); return a; });
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

block



関数はblock



解析します。

 var block = function () { var t = token; advance("{"); return t.std(); };
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

var



句は、現在のブロックの1つ以上の変数を定義します。 変数名の後に等号=



と変数の初期値を続けることができます。

 stmt("var", function () { var a = [], n, t; while (true) { n = token; if (n.arity !== "name") { n.error("Expected a new variable name."); } scope.define(n); advance(); if (token.id === "=") { t = token; advance("="); t.first = n; t.second = expression(0); t.arity = "binary"; a.push(t); } if (token.id !== ",") { break; } advance(","); } advance(";"); return a.length === 0 ? null : a.length === 1 ? a[0] : a; });
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

while



句はループを定義します。 括弧内の式とブロックが含まれます。

 stmt("while", function () { advance("("); this.first = expression(0); advance(")"); this.second = block(); this.arity = "statement"; return this; });
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

if



節は条件付き構成を作成します。 else



シンボルがブロックの後に続くif



、次のブロックまたは次のif



句も分析します。

 stmt("if", function () { advance("("); this.first = expression(0); advance(")"); this.second = block(); if (token.id === "else") { scope.reserve(token); advance("else"); this.third = token.id === "if" ? statement() : block(); } else { this.third = null; } this.arity = "statement"; return this; });
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

break



句は、ループを事前に終了するために使用されます。

 stmt("break", function () { advance(";"); if (token.id !== "}") { token.error("Unreachable statement."); } this.arity = "statement"; return this; });
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

return



節は、関数を終了するために使用されます。 オプションの式（関数の戻り値）を含めることができます。

 stmt("return", function () { if (token.id !== ";") { this.first = expression(0); } advance(";"); if (token.id !== "}") { token.error("Unreachable statement."); } this.arity = "statement"; return this; });
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

機能

関数は実行可能な値です。 関数は、オプションの名前（それ自体を再帰的に呼び出すことができるように）、括弧内のパラメーター名のリスト、および本体（中括弧内の文のリスト）を持つことができます。 関数には独自のスコープがあります。

 prefix("function", function () { var a = []; new_scope(); if (token.arity === "name") { scope.define(token); this.name = token.value; advance(); } advance("("); if (token.id !== ")") { while (true) { if (token.arity !== "name") { token.error("Expected a parameter name."); } scope.define(token); a.push(token); advance(); if (token.id !== ",") { break; } advance(","); } } this.first = a; advance(")"); advance("{"); this.second = statements(); advance("}"); this.arity = "function"; scope.pop(); return this; });
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

関数は演算子(



。を使用して実行されます。呼び出すとき、引数の数を指定できます。左側のオペランドをチェックして、左側の値が関数にならない状況をカットします。

 infix("(", 80, function (left) { var a = []; if (left.id === "." || left.id === "[") { this.arity = "ternary"; this.first = left.first; this.second = left.second; this.third = a; } else { this.arity = "binary"; this.first = left; this.second = a; if ((left.arity !== "unary" || left.id !== "function") && left.arity !== "name" && left.id !== "(" && left.id !== "&&" && left.id !== "||" && left.id !== "?") { left.error("Expected a variable name."); } } if (token.id !== ")") { while (true) { a.push(expression(0)); if (token.id !== ",") { break; } advance(","); } } advance(")"); return this; });
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

this



文字は特別な変数です。 メソッドが呼び出されると、オブジェクト参照がその中に保存されます。

 symbol("this").nud = function () { scope.reserve(this); this.arity = "this"; return this; };
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

オブジェクトと配列のリテラル

配列リテラルは、コンマで区切られた角括弧内の式のセットです。 各式が評価され、すべての結果が新しい配列を形成します。

 prefix("[", function () { var a = []; if (token.id !== "]") { while (true) { a.push(expression(0)); if (token.id !== ",") { break; } advance(","); } } advance("]"); this.first = a; this.arity = "unary"; return this; });
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

オブジェクトのリテラルは、カンマで区切られた中括弧内のペアのセットです。 このペアは、コロン（ :



区切られたキーと式で構成されます。 キーは、リテラルとして解釈されるリテラルまたは名前です。

 prefix("{", function () { var a = []; if (token.id !== "}") { while (true) { var n = token; if (n.arity !== "name" && n.arity !== "literal") { token.error("Bad key."); } advance(); advance(":"); var v = expression(0); v.key = n.value; a.push(v); if (token.id !== ",") { break; } advance(","); } } advance("}"); this.first = a; this.arity = "unary"; return this; });
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

何を考え、何をすべきか

作成されたツリーは、コードジェネレーターまたはインタープリターに渡すことができます。 ツリーを作成するには、最小限の計算が必要です。 そして、私たちが見るように、そのようなパーサーを書くためにプログラマーからそれほど多くの努力を必要としません。



操作コードパラメーターをinfix



関数に追加して、コードジェネレーターを支援できます。また、定数を折りたたみ、コードを生成するための追加のメソッドを渡すこともできます。



私たちは、（例えば、他の提案を追加することができfor



、switch



かつtry



、ラベル、エラーをチェックするために多くのコード、エラー回復、および新しい演算子の束を）。タスクと型の推論を追加できます。



言語を拡張可能にすることができます。プログラマーに、新しい変数を宣言するのと同じくらい簡単に、新しいステートメントとステートメントを宣言させることができます。



この記事で説明されているパーサーを自分で試してください。 JSLint



プロジェクトでこの解析メソッドを使用する別の例を見つけることができます。翻訳者から：



私はJSLintのソースを選択し、この素晴らしい記事のロシア語の翻訳が害にならないことを決めました。JSLintパーサーは、非常に明確で強力で、簡単に拡張できます。翻訳を編集してくれたKVieに感謝します。



この記事は、Beautiful Code（第9章）の一部として出版されました。電子形式の本全体のロシア語訳は、出版社「ピーター」のウェブサイトで購入できます。