文法用のBNFとEBNFがあります。BNFは明らかにより冗長です。BNFを使用して再帰下降パーサーを構築する限り、私はかなり良い考えを持っています。これには多くのリソースがあります。EBNFを再帰下降パーサーに変換するためのリソースを見つけるのに問題があります。これはもっと難しいからですか？CS理論のクラスで、EBNFを調べたことを思い出しますが、EBNFを再帰下降パーサーに変換することはしませんでした。BNFを再帰下降パーサーに変換することをやり直しました。
私が尋ねている理由は、EBNFがよりコンパクトだからです。
{EBNFの一般的な見方から、との間に囲まれた用語はループ}に変換できることに気付きました。while他にガイドラインやルールはありますか？
基本的に EBNF を再帰降下パーサーにコンパイルする、いわゆるメタコンパイラーを調査する必要があります。彼らがどのようにそれを行うかは、まさにあなたの質問への答えです。（かなり単純ですが、詳細を理解するのは良いことです）。
本当に素晴らしい論文は、Val Schorre による "MetaII" 論文です。これは神に正直な 1964 年のメタコンパイラ技術です。10 ページで、彼はメタコンパイラを構築する方法を示し、それだけでなく別のコンパイラも提供し、両方の出力を提供します!. これらのいずれかをビルドすると、メタコンパイラが独自の文法を使用して自分自身をコンパイルする方法を理解するという驚くべき瞬間があります。1970 年頃、私が最初にこの論文に出くわしたとき、この瞬間に私はコンパイラに夢中になりました。これは、ソフトウェア ビジネスに携わるすべての人が読むべきコンピューター サイエンスの論文の 1 つです。
James Neighbors (ソフトウェア エンジニアリングにおける「ドメイン」という用語の発明者であり、[これらのメタコンパイラに基づく] 最初のプログラム変換システムの作成者) は、オンラインで素晴らしい MetaII チュートリアルを提供しています。ゼロからの経験 (Neighbors と私が一緒に学部生だったことを除いて、私はこれとは何の関係もありません)。
どちらの方法も、メタコンパイラについて学び、EBNF からパーサーを生成するための優れた方法です。
重要なアイデアは、ルールの左側で、その非終端記号を解析し、一致する場合に true を返し、入力ストリームを進める関数を作成することです。一致せず、入力ストリームが進まない場合は false。関数の内容は右辺で決まります。リテラル トークンは直接一致します。非終端は、他のルール用に生成された他の関数への呼び出しを引き起こします。Kleene* は while ループにマップされ、代替は条件分岐にマップされます。EBNF が対処せず、メタコンパイラが対処するのは、「一致した」かどうか以外に解析がどのように行うかです。その秘密は、出力操作を EBNF に織り込むことです。MetaII 論文は、このすべてを非常に明確にしています。
どちらも他方より難しいものではありません。何かを反復的に実装することと、何かを再帰的に実装することの実際の違いです。BNF では、すべてが再帰的です。EBNF では、再帰の一部が反復的に表現されます。EBNF 構文にはさまざまなバリエーションがあるため、英語を使用します...「ゼロ以上」は、ご存知のように単純な while ループです。「1 つ以上」は、1 の後に「0 以上」が続くのと同じです。「0 回または 1 回」は単純な if ステートメントです。これでほとんどのケースがカバーされるはずです。
初期のメタ コンパイラである META II と TREEMETA およびそれらの類は、正確には再帰的で適切なパーサーではありません。それらは再帰関数を使用していると述べられていました。それは彼らが彼ら自身を呼ぶことができることを意味しました。
C を再帰言語とは呼びません。AC または C++ 関数は、初期のメタ コンパイラが再帰的であるのと同じように再帰的です。
再帰が使用できます。それらはプログラミング言語でした。再帰は通常、次の言語構造を分析する場合にのみ使用されます。たとえば、括弧で囲まれた式と次のブロック。
LR再帰的な適切な組み合わせの詳細。最後に文書化された CWIC には、広範なバックトラッキング機能と先読み機能があります。「-」not 演算子は、どの言語構造にも一致できます。そして、成功か失敗かを反転します。-term は、たとえば用語が一致した場合に失敗します。入力が進むことはありません。「?」たとえば、expr は expr を解析しようとします。先読み「?」一致した構成が保持されないか、入力が進められます。