1

そのため、レクサー、パーサー、インタープリター、さらにはコンパイルについても少し読んでいます。

私が実装しようとしている言語については、Recrusive Descent Parser に落ち着きました。この言語の元の文法には左再帰があったため、少し書き直さなければなりませんでした。

これは私が持っていた文法の簡略化されたバージョンです（これは標準形式の文法ではありませんが、やや疑似的なものであることに注意してください。ドキュメントで見つけた方法です）：

expr:
-----
expr + expr
expr - expr
expr * expr
expr / expr
( expr )
integer
identifier

左再帰を取り除くために、これを次のように変更しました (NOT 演算子の追加に注意してください)。

expr:
-----
expr_term {+ expr}
expr_term {- expr}
expr_term {* expr}
expr_term {/ expr}

expr_term:
----------
! expr_term
( expr )
integer
identifier

そして、次のサブルーチンを使用してトークンを調べます (簡略化された疑似コードっぽい):

public string Expression()
{
    string term = ExpressionTerm();

    if (term != null)
    {
        while (PeekToken() == OperatorToken)
        {
            term += ReadToken() + Expression();
        }
    }

    return term;
}

public string ExpressionTerm()
{
    //PeekToken and ReadToken accordingly, otherwise return null
}

これはうまくいきます！呼び出し後の結果Expressionは、与えられた入力と常に等しくなります。

これらのサブルーチンで文字列ではなく AST ノードを作成し、中置エバリュエーターを使用して AST を評価すると (結合性と演算子の優先順位なども考慮されます)、同じ結果が得られるでしょうか? ?

そして、私がそうするなら、実際には解決するのが「非常に単純」であるか、問題がないように見えるのに、「左再帰を修正し、結合性などを念頭に置いて」をカバーするトピックが非常に多いのはなぜですか? それとも、実際に人々が関心を持っている結果の AST の構造なのでしょうか (それが評価されるものではなく)? 誰かが光を当てることができますか、私もそれをすべて間違っているかもしれません、ハハ！

4

2 に答える 2

2

AST の形状は重要です。なぜなら、a+(b*3)通常は と同じではなく、パーサーがこれらの手段(a+b)*3のどれを示すかを合理的に期待できるからです。a+b*3

通常、AST は実際に括弧を削除します。(解析ツリーはそうではありませんが、AST は構文上のノイズを抽象化することが期待されています。)したがって、AST は次のa+(b*3)ようになります。

          Sum
           |
       +---+---+
       |       |
      Var     Prod
       |       |
       a   +---+---+
           |       |
          Var    Const
           |       |
           b       3

あなたの言語が通常の数学表記規則に従うなら、AST for a+b*3.

「中置エバリュエーター」-またはあなたが言及していると私が想像するもの-は、単なる別のパーサーです。したがって、後で解析してもよければ、今解析する必要はありません。

ところで、トークンを読み取った順に並べることができることを示しても、実際にはパーサーの機能についてはあまり示されていません。トークナイザーの出力をエコーするだけで、はるかに簡単に行うことができます。

于 2013-10-19T01:16:05.650 に答える