0

Dragon-book の付録では、LL(1) フロント エンドが例として示されています。とても参考になると思います。ただし、以下の文脈自由文法では、代わりに少なくとも LL(2) パーサーが必要であることがわかりました。

statement : variable ':=' expression
          | functionCall

functionCall : ID'(' (expression ( ',' expression )*)? ')'
             ;
variable : ID
         | ID'.'variable
         | ID '[' expression ']'
         ;

k 先読みトークンをサポートするように LL(1) パーサーのレクサーをどのように適応させることができますか? エレガントな方法はありますか？

トークン用のバッファーをいくつか追加できることはわかっています。プログラミングの詳細について説明したいと思います。

これはパーサーです:

class Parser
{
    private Lexer lex;
    private Token look;
    public Parser(Lexer l)
    {
        lex = l;
        move();
    }

    private void move()
    {
        look = lex.scan();
    }
}

そして、Lexer.scan()ストリームから次のトークンを返します。

4

1 に答える 1

1

実際には、解析kを行うために先読みトークンをバッファリングする必要があります。LL(k)が 2 の場合は、別のプライベート メンバーなどを使用して、 k1 つのトークンを にバッファリングする現在のメソッドを拡張するだけです。より大きい場合は、リング バッファを使用できます。looklook2k

実際には、常に完全な先読みは必要ありません。ほとんどの場合、1 トークンの先読みで十分です。あいまいさを解決するために必要な場合にのみ、将来のトークンが参照されるデシジョン ツリーとしてコードを構造化する必要があります。(先読みがまだそのポイントに達していないことを示すために、バッファリングされたトークンリストに割り当てることができる特別なトークンタイプ「不明」を提供すると便利なことがよくあります。別の方法として、常にk先読みのトークンを維持することもできます。パーサー、その方が簡単です。)

あるいは、フォールバック構造を使用して、1 つの代替案を試してみて、それが機能しない場合は、構文エラーを報告する代わりに、パーサーとレクサーの状態を次の代替案に復元することができます。このモデルでは、レクサーは現在の入力バッファーの位置を明示的な引数として受け取り、入力バッファーは巻き戻し可能である必要があります。ただし、先読みバッファを使用してレクサー関数を効果的にメモ化することで、巻き戻しや再スキャンを回避できます。(スキャンは通常、時折の再スキャンが問題にならないほど十分に高速であるため、プロファイリングで有用であることが示されるまで、コードの複雑さの追加を延期することをお勧めします。)

2 つの注意事項:

1) 私はルールに懐疑的です:

functionCall : ID'(' (expression ( ',' expression )*)* ')'
             ;

これにより、たとえば次のことが可能になります。

function(a[3], b[2] c[x] d[y], e.foo)

これは私には正しくありません。通常、の内容をrepeatableではなくoptional()としてマークします。2 番目の Kleene スターの代わりにオプションのマーカーを使用:?*

functionCall : ID'(' (expression ( ',' expression )*)? ')'
             ;

LR(1)2) 私の意見では、生成されたパーサーまたは手作りの Pratt パーサーのいずれかで、式言語にボトムアップ解析を使用することを本当に検討する必要があります。LL(1)はめったに十分ではありません。もちろん、パーサー ジェネレーターを使用している場合は、ANTLR などの効果的に実装するツールを使用できますLL(∞)。それはあなたのために先読みを処理します。

于 2014-05-14T14:47:28.997 に答える