lex /yaccを使用してC++コンパイラを作成するにはどのくらいの時間がかかりますか？
どこから始めればよいですか？
6192 次
13 に答える
23
bison / yaccパーサーでは解析できない解析ルールが多数あります（たとえば、状況によっては宣言と関数呼び出しを区別します）。さらに、特にC ++ 0xでは、トークンの解釈にパーサーからの入力が必要になる場合があります。>>たとえば、文字シーケンスの処理は、構文解析コンテキストに大きく依存します。
これらの2つのツールは、C ++を解析するための非常に不適切な選択であり、C ++を正しく解析するために、これらのツールが依存する基本的なフレームワークを回避する多くの特殊なケースを設定する必要があります。それはあなたに長い時間がかかるでしょう、そしてそれでもあなたのパーサーはおそらく奇妙なバグを持っているでしょう。
yaccとbisonはLALR（1）パーサージェネレーターであり、C++を効果的に処理するには十分に洗練されていません。他の人が指摘しているように、ほとんどのC ++コンパイラは現在、再帰下降パーサーを使用しており、他のいくつかの回答は、独自の記述を行うための優れたソリューションを示しています。
C ++テンプレートは、定数の文字列であっても、文字列の処理には適していません（ただし、これはC ++ 0xで修正される可能性がありますが、慎重に調査していません）が、そうであれば、C++テンプレートで再帰下降パーサーを簡単に作成できます。言語。それはかなり面白いと思います。
于 2009-12-25T18:18:58.217 に答える
10
おそらく何年もかかるでしょうし、その過程でおそらく他のパーサジェネレータに切り替えるでしょう。
C ++の解析は、エラーが発生しやすいことで有名です。多くの部分が状況依存であるため、文法は完全にLR解析可能ではありません。flex / yaccで正しく動作させることはできません。少なくとも、実装するのは非常に面倒です。私が知っているフロントエンドは2つだけです。最善の策は、これらのいずれかを使用して、バックエンドの作成に集中することです。とにかく面白いものがあるところです:-)。
既存のC++フロントエンド：
EDGフロントエンドは、ほとんどの商用ベンダー（Intel 、 Portland Groupなど）のコンパイラーで使用されています。それはお金がかかりますが、それは非常に徹底的です。自分でC++パーサーを作成するという苦痛に対処したくないので、人々はそれに多額のお金を払っています。
GCCのC++フロントエンドは、実稼働コードには十分ですが、これをプロジェクトに統合する方法を理解する必要があります。GCCから分離することはかなり複雑だと思います。これもGPLになりますが、それがあなたにとって問題であるかどうかはわかりません。プロジェクトでgcc_xmlを介してGCCフロントエンドを使用できますが、これにより、クラス、関数、名前空間、およびtypedefのXMLのみが提供されます。コードの構文ツリーは提供されません。
もう1つの可能性は、clangを使用することですが、C++のサポートは現在不十分です。彼らがすべてのバグを取り除くのを見るのは素晴らしいことですが、彼らのC ++ステータスページを見ると、まだ壊れているテストケースがいくつかあることに気付くでしょう。注意してください-clangは大きなプロジェクトです。これらの人がC++フロントエンドを実装するのに何年もかかる場合は、さらに時間がかかります。
他の人はANTLRについて言及していて、それに利用できるC ++文法がありますが、私は懐疑的です。ANTLRフロントエンドが主要なコンパイラで使用されていることは聞いたことがありませんが、NetBeansIDEで使用されていると思います。IDEには適しているかもしれませんが、実稼働コードで使用できるかどうかは疑問です。
于 2009-12-25T19:08:44.133 に答える
10
あなたは構文解析/コンパイラの作成にかなり慣れていないようです。その場合は、C++から始めないことを強くお勧めします。それは言語の怪物です。
あなた自身のささいなおもちゃの言語を発明するか、もっと小さくて単純なものをモデルにした何かをしてください。文法の定義が約1ページの長さのluaパーサーを見ました。それは出発点としてはるかに合理的でしょう。
于 2009-12-25T19:20:21.870 に答える
6
長い間、lexとyaccは役に立ちません
このような大規模な言語用のコンパイラーを作成するスキルがあれば、lexやyaccが提供する少量の支援は必要ありません。実際、lexは問題ありませんが、yaccの使用には時間がかかる場合があります。これは、CまたはC ++には十分な機能がないため、再帰的に記述するよりもはるかに多くの時間を費やして正しく機能させることができるためです。降下パーサー。
lexとyaccは、単純な文法、または文法が実験的で変更される可能性があるため、読みやすい文法ファイルを作成するために余分な努力を払う価値がある場合に最適であると思います。
さらに言えば、コードジェネレーターの目標によっては、パーサー全体が仕事の主要な部分ではない可能性があります。
于 2009-12-25T18:24:09.987 に答える
4
他の人がすでに言っているように、yaccはC++パーサーを実装するための悪い選択です。それを行うことができます。元のGCCは、GCCチームが維持と拡張がどれほど難しいかにうんざりする前に、そうしました。（フレックスはレクサーとしては問題ないかもしれません）。
Bjarne Stroustropがそう言ったので、再帰下降パーサーが最適であると言う人もいます。私たちの経験では、GLR解析がこれに対する正しい答えであり、Elsaフロントエンドと同様に、GLRベースのC++フロントエンドは優れた証拠です。私たちのフロントエンドは、プログラム分析と大規模なソースコード変換を実行するために、数百万行のC ++（MicrosoftおよびGCC方言を含む）で怒りに使用されてきました。
しかし、十分に強調されていないのは、構文解析は、特にC ++の場合、コンパイラーの構築に必要なもののごく一部にすぎないということです。また、シンボルテーブル（「このコンテキストでこの識別子は何を意味するのか」）を作成する必要があります。そのためには、C++標準の数百ページのほとんどを本質的にエンコードする必要があります。コンパイラのようなツールであるDMSを構築するための基盤は、これを行うのに非常に優れていると信じており、この部分を正しく行うには1年以上かかりました。
しかし、その後、コンパイラの残りの部分を考慮する必要があります。
- プリプロセッサ
- AST建設
- セマンティック分析とタイプチェック
- 制御、データフロー、およびポインター分析
- 基本的なコード生成
- 最適化
- レジスタ割り当て
- 最終的なコード生成
- デバッグサポート
私はこれを言い続けます：言語のためのパーサー（BNF部分）を構築することはヒマラヤの丘陵地帯を登るようなものです。完全なコンパイラを構築することは、エベレストに登るようなものです。ほとんどすべての群れが前者を実行できます（ただし、C ++は端にあります）。後者を行うのは本当に深刻なことであり、非常によく準備されている場合に限ります。
C++コンパイラの構築には何年もかかることを期待してください。
（SD C ++フロントエンドは、主要なC ++ダイアレクトについて、字句解析、解析、AST生成、シンボルテーブル、一部の型チェック、および元のコメントを含むASTからのコンパイル可能なソーステキストの再生成を処理します。約6年）。
編集：2015年5月。元の回答は2010年に書かれました。現在、私たちは11年間投資しており、C++14を採用しています。重要なのは、これらの1つを構築することは無限の大きな努力であるということです。
于 2010-01-24T11:13:03.527 に答える
3
まず、SOの「flex」タグはAdobeの製品に関するものであり、レクサージェネレーターに関するものではありません。第二に、Bjarne Stroustrupは、テーブル駆動ツールではなく再帰下降を使用してCfront（最初のC ++コンパイラ）を実装したいと言っていると記録されています。そして第三に、あなたの質問に直接答えること-たくさん。作成する必要があると思われる場合は、ANTLRをご覧ください。私のお気に入りのツールではありませんが、すでにC++パーサーがあります。
于 2009-12-25T18:05:13.393 に答える
3
これは重要な問題であり、正しく実行するにはかなりの時間がかかります。一つには、C ++の文法は、yaccなどのLALRパーサーでは完全には解析できません。言語のサブセットを作成することはできますが、言語仕様全体を正しくするのは難しいことです。
これが楽しいと思うのはあなたが最初ではありません。これは、このトピックに関する素晴らしいブログスタイルの記事です： C++の解析
記事からの重要な引用は次のとおりです。
「多くの調査の結果、C ++用のパーサー/分析ツールを作成することは十分に困難であり、趣味としてやりたいことを超えていると判断しました。」
その記事の問題は、それが少し古く、いくつかのリンクが壊れていることです。C++パーサーの作成に関する他のリソースへのリンクは次のとおりです。
于 2009-12-25T18:24:42.940 に答える
2
Lex、yaccでは十分ではありません。リンカ、アセンブラも必要です。cプリプロセッサ。それはあなたがそれをどのように行うかに依存します。どのくらいの既製のコンポーネントを使用する予定ですか？構文の説明とそのトークンをどこかから取得する必要があります。
たとえば、LLVMを使用すると、より速く進むことができます。すでに多くのツール、アセンブラー、リンカー、オプティマイザーを提供しています。ブーストプロジェクトからACプリプロセッサーを入手できます。コンパイラーを自動的にテストするには、テストスイートを作成する必要があります。
毎日それに取り組んでいる場合は1年かかる場合がありますが、それよりもはるかに少ない才能とモチベーションがあります。
于 2009-12-25T18:05:56.887 に答える
2
他のいくつかのコンパイラをすでに作成していない限り、C ++は、コンパイラーを最初から作成し始めたい言語ではありません。言語には多くの場所があり、状況を明確にする前に、意味には多くのコンテキストが必要です。
コンパイラーの作成経験が豊富な場合でも、開発者チームのために数年を見ています。これは、コードを中間形式に正しく解析するためだけのものです。コードを生成するためのバックエンドの記述は、さらに別の特殊なタスクです（ただし、gccバックエンドを盗むことはできます）。
あなたが「C++文法」のためにグーグルをするならば、あなたが始めるために周りにいくつかあります。
C++ LEX Tokens: http://www.computing.surrey.ac.uk/research/dsrg/fog/CxxLexer.l
C++ YACC Grammer: http://www.computing.surrey.ac.uk/research/dsrg/fog/CxxGrammar.y
http://www.computing.surrey.ac.uk/research/dsrg/fog/CxxTester.y
于 2009-12-25T21:06:06.080 に答える
2
数年-新しいlex/yaccを書き直すための研究助成金を得ることができれば:-)
人々はこれについて多くのことを追い続けています-実際のコンパイラライターではなく言語の「デザイナー」であることに常に夢中だったStroustrupから始めます（彼のC ++は何年もの間単なるコード生成者であり、gccがなかった場合でも存在することを忘れないでください）および他の人々）。
中心的な問題は、CPUが関数型言語とブルートフォース再帰下降を処理するのに十分な速度になったため、パーサジェネレータに関する実際の研究がほとんど存在しなくなったことです。再帰下降は、何をすべきかわからない場合の最後の手段です。それは、発火する1つの「ルール」を取得するまで徹底的な検索を行います。それに満足したら、それを効率的に行う方法を研究することに少し興味がなくなります。
基本的に必要なのは、合理的な中間点です。LALR（2）のように、固定された制限付きのバックトレース（さらに、「desiogner」が非決定論的なツリーに飛び込んだ場合に叫ぶ静的チェッカー）と、制限されたパーティション化されたシンボルテーブルフィードバック（最新のパーサー）があります。並行性に対応している必要があります）。
研究助成金の提案のようですね:-)実際に資金を提供してくれる人を見つけたら、それは何かでしょう:-)）
于 2010-08-07T21:18:00.680 に答える
1
C++コンパイラは非常に複雑です。ほとんどのC++コードと互換性のある十分なC++を実装するには、数人の開発者がフルタイムで2、3年かかります。clangは、C、C ++、Objective-C用の新しいコンパイラを開発するためにAppleが資金提供しているコンパイラプロジェクトであり、数人のフルタイムの開発者がいます。C++のサポートは、2、3年の開発後もまだ完全にはほど遠いです。
于 2009-12-25T18:21:20.770 に答える
0
再帰下降構文解析は、C++を解析するための良い選択です。GCCとclangはそれを使用します。
Elsaパーサー（および私のellccコンパイラー）は、ElkhoundGLRコンパイラージェネレーターを使用します。
いずれの場合も、C++コンパイラの作成は大きな仕事です。
于 2009-12-25T18:07:54.277 に答える
0
さて、コンパイラを書くとはどういう意味ですか？
アセンブリコードに至るまで真のC++コンパイラを作成した人はいないと思いますが、lexとyaccを使用してCコンパイラを作成しましたが、それを使用せずに作成しました。
両方を使用すると、数日でセマンティクスを除外するコンパイラを作成できますが、それらの使用方法を理解するには、数週間から数か月かかる場合があります。コンパイラの作り方を理解するには、何週間も何ヶ月もかかりますが、私が覚えているのは、それがどのように機能するかを知ったら、lexとyaccを使用すると数日、使用しない場合は数週間かかりましたが、2番目の方が良い結果が得られましたバグが少ないので、使用する価値があるかどうかは本当に疑わしいです。
「セマンティクス」は実際のコード生成です。これは非常に単純なコードであり、機能するのに十分で、まったく時間がかからない場合があります。または、一生をかけて最適化を行うこともできます。
C ++の場合、大きな問題はテンプレートですが、これを実行したいと思っている人を想像することのできない小さな問題やルールがたくさんあります。終了しても、問題は必ずしもバイナリ互換性がないことです。つまり、C ++だけでなく、標準を特定するのが難しいため、リンカーまたはOSによって実行可能なプログラムとして認識できるとは限りません。また、利用できる標準がさらに少ないことを心配する必要があります。
于 2009-12-27T10:27:53.993 に答える