パーサーを構築する（パートI）

Question

私は自分のJavaScriptベースのプログラミング言語を作っています（ええ、それは狂っていますが、それは学ぶためだけです... 多分？）。まあ、私は、パーサーについて読んだし、最初のパスは次のように、トークンにコードソースを変換することです：私のロジックが正しいかどうかはわからない

T_IF   "if" 
T_LPAREN  "(" 
T_IDENTIFIER "x" 
T_GT   ">" 
T_NUMBER  "5" 
T_RPAREN  ")" 
T_IDENTIFIER "return" 
T_TRUE  "true" 
T_TERMINATOR ";" 

：に

if(x > 5) 
    return true; 

トークナイザその間ずっと。私のパーサではそれも良いですし、（ええ、多次元配列）、それに変換（か？）：

T_IF    "if" 
    T_EXPRESSION  ... 
    T_IDENTIFIER  "x" 
    T_GT    ">" 
    T_NUMBER   "5" 
    T_CLOSURE  ... 
    T_IDENTIFIER  "return" 
    T_TRUE   "true" 

私はいくつかの疑問があります。

1. を良くも悪くもその私の方法ですオリジナルの方法？私のコードはいつも解釈されるのではなく、PHPのような別の言語に翻訳されて読み込まれ、コンパイルされることに注意してください。
2. 私はトークナイザーの後、正確に何をする必要がありますか？私はこのパスで本当に失われています！
3. 私はそれを行う方法を学ぶための良いチュートリアルがありますか？

これはそうです。さようなら！

Answer 1

通常、コンパイラまたはインタープリタの他の段階から、トークンシャーの機能（別名lexer）を分離したいと考えています。この理由は、基本的なモジュール性である。各パスは、1種類の物（例えば、文字）を消費し、別のパス（例えば、トークン）を生成する。

あなたは文字をトークンに変換しました。今では、フラットなトークンリストを意味のあるネストされた式に変換したいと考えています。これは、従来はという構文解析と呼ばれています。 JavaScriptのような言語の場合は、recursive descent parsingを調べる必要があります。異なる優先順位の中置演算子で式を解析する場合は、Pratt parsingが非常に便利で、特別な場合には通常の再帰的な下降解析に戻すことができます。

あなたのケースに基づいてより具体的な例を与えるだけで、作成したストリーム内の次のトークンをテストする、accept(token)とexpect(token)という2つの関数を書くことができます。あなたはあなたの言語の文法の中で文章や表現の種類ごとに関数を作ります。ここで例えば、statement()機能のためPythonish擬似コードです：これは、あなたがして操作することができますあなたのプログラム、（最適化および分析）、出力（コンパイル）の抽象構文木（AST）と呼ばれる何あなたを与える

def statement(): 

    if accept("if"): 
    x = expression() 
    y = statement() 
    return IfStatement(x, y) 

    elif accept("return"): 
    x = expression() 
    return ReturnStatement(x) 

    elif accept("{") 
    xs = [] 
    while True: 
     xs.append(statement()) 
     if not accept(";"): 
     break 
    expect("}") 
    return Block(xs) 

    else: 
    error("Invalid statement!") 

、または実行する（解釈する）。

Answer 2

元の方法は私の方法が良くて悪いですか？私のコードはいつも解釈されるのではなく、PHPのような別の言語に翻訳されて読み込まれ、コンパイルされることに注意してください。

オリジナルの方法はとは何ですか？言語を実装するにはさまざまな方法があります。私はあなたのことが実際には良いと思う、私はかつてC＃に翻訳された自分自身で言語を構築しようとした、hack programming language。多くの言語コンパイラは中間言語に翻訳されていますが、それはかなり一般的です。

私はトークナイザの後、正確に何をする必要がありますか？私はこのパスで本当に失われています！トークン化の後

、あなたはにそれを解析する必要があります。 Boost.SpiritやCocoなど、良いlexer/parserフレームワークを使用してください。それらの何百もあります。あるいは、独自のレクサーを実装することもできますが、それには時間とリソースが必要です。コードを解析する方法はたくさんありますが、私は一般的にrecursive descent parsingに依存しています。

次に、コード生成を行う必要があります。それは私の意見で最も難しい部分です。それにはツールもありますが、私は自分のプロジェクトでそれをやろうとしましたが、手軽に行うことができますが、かなり基本的でバグがありました。有用なコードhereとhereがあります。

私はそれを行う方法を学ぶための良いチュートリアルがありますか？

前述したように、ツールを使用してください。かなり良い文書化されたパーサフレームワークがたくさんあります。詳細については、あなたはこのことについて知っている人に尋ねることができます。 Lounge C++の@DeadMGは、「ワイド」と呼ばれるプログラミング言語を構築しています。彼に相談してみてください。

Answer 3

ほとんどのツールキットは、2つの別個部品

に完全なプロセスを分割

• レクサー（別名。トークナイザ）
• パーサー（別名。文法）

トークナイザは、入力データを分割しますトークンに変換する。パーサーはトークン "ストリーム"に対してのみ動作し、構造体を構築します。

あなたの質問はトークナイザーに焦点を当てているようです。しかし、2番目のソリューションは、文法パーサとトークナイザを1つのステップにミックスしています。理論的にはこれも可能ですが、初心者にとってはです。他のほとんどのツール/フレームワークと同じ方法で簡単に行うことができます。あなたの最初の溶液に

：私はこのようなあなたの例をトークン化します：ほとんどの言語キーワードで

T_KEYWORD_IF "if" 
T_LPAREN  "(" 
T_IDENTIFIER "x" 
T_GT   ">" 
T_LITARAL  "5" 
T_RPAREN  ")" 
T_KEYWORD_RET "return" 
T_KEYWORD_TRUE "true" 
T_TERMINATOR ";" 

はようにメソッド名、変数名として使用することはできません。これは、トークナイザレベル（T_KEYWORD_IF、T_KEYWORD_RET、T_KEYWORD_TRUE）に既に反映されています。

次のレベルは、このストリームを取ると考え - 正式な文法を適用することにより、 - いくつかのデータ構造を構築するだろう（と呼ばれることが多いAST - 抽象構文木）のようになります。

IfStatement: 
    Expression: 
     BinaryOperator: 
      Operator:  T_GT 
      LeftOperand: 
       IdentifierExpression: 
        "x" 
      RightOperand: 
       LiteralExpression 
        5 
    IfBlock 
     ReturnStatement 
      ReturnExpression 
       LiteralExpression 
        "true" 
    ElseBlock (empty) 

手でパーサの実装通常、いくつかのフレームワークによって行われます。とのようなものを効率的に実装するのは、通常、ある学期中に大学で行われます。だからあなたは本当に何らかのフレームワークを使うべきです。

文法パーサフレームワークの入力は、通常、何らかの形式の文法であるBNFです。あなたの「if」の部分は次のようになります。

IfStatement: T_KEYWORD_IF T_LPAREN Expression T_RPAREN Statement ; 

Expression: LiteralExpression | BinaryExpression | IdentifierExpression | ... ; 

BinaryExpression: LeftOperand BinaryOperator RightOperand; 

.... 

これは唯一のアイデアです。 Javascript のような現実世界の言語を正確に解析すると、は簡単な作業ではありません。しかし面白い。