コンパイラで前方参照を実装するにはどうすればよいですか？

Question

私はLexとYACC（実際にFlexとBison）を使ってコンパイラを作成しています。この言語は、任意のシンボル（C＃など）への無制限の前方参照を可能にします。問題は、識別子が何であるか知らずに言語を解析することは不可能だということです。

私が知っている唯一の解決策は、ソース全体をレックスし、次に「幅優先」解析を行うことです。クラス宣言や関数宣言などの上位レベルのものは、関数を使用する関数の前に解析されます。しかし、これは大きなファイルのために大量のメモリを必要とし、YACCで処理するのは難しいでしょう（私は宣言/本体の種類ごとに別々の文法を作成しなければなりません）。私はレクサーを手書きしなければなりません（それはそれほど問題ではありません）。

私はそれを完了したらコンパイラ自体を書き直すつもりだから効率については大したことはないが（まだ重要だが） Lex/YACCで行うことはできないが、手作業で行うことができる高速な一般的なテクニックであり、それらも示唆してください。だから今、開発の容易さが最も重要な要素です。

この問題の解決策はありますか？これはC＃やJavaのような言語のコンパイラでどのように行われますか？

Answer 1

これは完全に解析できます。識別子とキーワードの間にはあいまいさがありますが、lexはキーワードに優先順位を付けることでそれにうまく対処します。

他に何か問題はありません。構文解析段階で識別子が有効かどうかを判断する必要はありません。パースツリーまたは抽象構文ツリーのいずれかを構築しています（違いは微妙ですが、この議論の目的とは無関係です）。その後、解析中に生成したASTを渡してネストしたシンボルテーブル構造を構築します。次に、ASTをもう一度渡して、使用された識別子が有効であることを確認します。これに続いて、出力コードやその他の中間データ構造を生成するためのAST上での1つ以上の追加の解析を行い、完了です！

EDIT：どのように処理されているかを確認するには、Mono C＃コンパイラのソースコードを確認してください。これは実際にはCやC++ではなくC＃で書かれていますが、yaccに非常に似ているJayの.NETポートを使用します。

Answer 2

「パニックモード」のようなエラーリカバリのようなものを実際にどのように知っているかを知るまで、トークンをスキャンしキャッシングするだけで前方参照を処理することができます。完全なファイルを実行したら、前に戻って、解析しなかったビットを再度解析してみてください。

レクサーを手書きで書くことについては、通常のパーサーを生成するためにlexを使用し、手書きshimを使ってそれを読み込みます。これは、あなたが戻ってキャッシュからパーサーだけでなくlexが作るものをフィードすることができます。 YACCファイルのプリプロセッサで、いくつかの文法、ささやかな楽しみを作り、あなたが同じ元のソースこれは、キーワードとは何の関係もありません