5

私はペット プロジェクト用のパーサーを作成しています。教育目的で、パーサー ジェネレーターを使用する代わりに手動で作成したいと考えています。残念ながら、多くのオンライン リソース (および私が大学で受講したコンパイラ コース) は、ある種の LL(k) 文法を前提としています。ただし、次のような左再帰的な非終端記号があるため、文法を左因数分解したくありません。

E ::= E * E
    | E / E
    | E + E
    | E - E
    | ...

バイソンのようなパーサージェネレーターで可能なことは、文法を大幅に簡素化するようです。

そのような文法を手作業で解析する最も簡単な方法は何でしょうか? これまでの私の調査によると、ここで説明した理由により、再帰的降下はオプションではなく、再帰的上昇を使用した LR 解析は適切な選択である可能性がありますが、いくつかのサイトはそれが直感的ではないことに言及するために一時停止しています。

4

2 に答える 2

4

左再帰のみが多かれ少なかれ標準的な式構文であるおもちゃの言語用にほとんど再帰的な降下パーサーを構築したい場合は、プラットパーサー ( Java ) ( Javascript ) を検討する必要があります。別の方法として (結果的には同等です)、operator precedence parserを使用できます。このアルゴリズムは Dragon book で詳しく説明されており、分水車場アルゴリズムを使用した利用可能な例はたくさんあります(ただし、このアルゴリズムを熱心に発見してすぐにブログに書き留める多くの人々は、信頼できる権威とはかけ離れていることに注意してください)。

緩やかな解析に関する注意:

式の文法を解析する必要があり、演算子の優先順位を気にしない場合 (たとえば、コードの構文に色を付けるだけでよい場合)、式の文法を簡単に再構成して左再帰を回避できます。

出発点はこれで*、Kleene スター、?オプション、および( )グループ化に使用します。

expression: term (INFIX term)*
term: PREFIX* operand postfix*
operand: ID
       | CONSTANT 
       | '(' expression ')'
       ;
postfix: POSTFIX
       | '[' expression ']'
       | '(' ( expression (',' expression)* )? ')' 
       ;

*再帰降下パーサーは、上記のand演算子を簡単に処理でき?、左再帰がないため、それで十分です。

C には、最初の括弧で囲まれた式に式ではなく型が含まれていることがわかっていない限り、構文的に関数呼び出しと区別できないキャスト式の扱いにくさがあることに注意してください。ただし、緩やかな解析の目的では、上記の文法を使用して関数呼び出しであるかのように解析しても問題ありません。

C++ では、演算子とテンプレート パラメーターの両方として山かっこを使用すると、扱いが難しくなります。私が見た多くの構文カララーは、テンプレート パラメーターの大文字と小文字を完全に無視します。それらを正しくすることは挑戦ですが、価値があるかもしれません。

編集者コメント:

よろしければこれは無視してください。しかし個人的には、ボトムアップ LR パーサー、特に GLR パーサーを使って作業することを学ぶことは、言語を制限された構文解析アルゴリズムに押し込むよりもはるかに充実した教育的経験になると思います。文法の一部はコード パスとして隠されています。しかし、そうは言っても、Bisonパーサーがどれだけエレガントでシンプルになるかを見るためだけに、bisonパーサーと手動で生成されたパーサーの両方を実行することは価値があるかもしれません。

于 2013-07-29T15:40:50.080 に答える