問題タブ [recursive-descent]

私は試験のために勉強していますが、この概念を理解するのに苦労しています。オブジェクトの再帰的な定義を考えると、再帰的な認識エンジンを書くことができます。これを行う方法がよくわかりません。

質問の例を次に示します。正の整数が 2 のべき乗の 1 倍または 2 倍の場合、正の整数は 2 のべき乗です。 2.

私はこの文法を持っており、最初のセットを自分で計算しましたが、示されている方法がわかりにくかったため、作業を表示する方法がわかりませんが、作業を表示する方法ではなく、セットを取得する方法を理解しています.

文法は次のとおりです。

私の最初のセットは次のとおりです。

バックトラッキングによるインデントにも適した再帰的降下パーサーアルゴリズムを見つけようとしています。しかし、私はこれに対する面倒な解決策を見つけ続けています。

インデントも扱うリソースはありますか?

ありがとう

ポインターに関する K&R C 第 2 版の第 5 章の終わりまで到達しました。ここまでは問題なく、すべて理解できましたが、何らかの理由で、演習 5-18 が何を求めているのかを理解するのに苦労しています:「入力エラーから dcl を回復させる」

簡単に聞こえますが、この質問は私がどこまで行くことを期待していますか? 括弧の欠落、改行の欠落などですか？他の人がこの問題をどのように解決したかを知っていただければ幸いです。ありがとう。

正規表現を使用して端末を照合する再帰降下パーサーを Ruby で作成しています。ターミナルは実際には正規表現であり、文字列内の現在の位置と照合されます。

問題は、端末の正規表現には、改行に一致する正規表現を含め、何でも含めることができることです。たとえば、括弧内のすべてに一致する端末は、/\([^\)]*\)/カウントする必要がある改行を含め、空白を消費します。私はいくつかの解決策を考え出しましたが、それらにはすべて、私が特に気に入らない欠点があります。

1. 端末が一致するたびに、一致した のすべての出現をカウントします\n。これは事実上、すべての文字列が 1 回ではなく 2 回一致することを意味します。

2. 現在の行を格納する代わりに、文字列の現在の位置を格納し、必要なときにのみ文字列を走査して行番号と列番号を取得できます。行番号が必要になるたびに文字列全体がトラバースされるため、明らかに問題があります。

3. 端末として正規表現を許可する代わりに、ANTLR で許可されているものと同様に、より単純な形式のマッチャーを許可してから、手動で文字列を照合し、改行をカウントすることができます。ただし、これには少なからず余分な作業が必要であり、正規表現のマッチング機能が失われます。

私は3番目の解決策に傾いていますが、誰かが同様の問題に対処し、問題を解決するより良い解決策を持っているかどうかを確認したいと思います.

私は、変数を使用して式のパーサーを作成し、それらを二次式の形式に単純化しようとしています。

これは私のパーサー文法です:

解析には、再帰降下パーサーを使用しています。これを解析したいとしましょう：

「2 - 1 + 1 = 0」

結果が 0 の場合、パーサーは間違ったツリーを作成します:

この文法を左結合にするにはどうすればよいですか? 私はこれが初心者です。より多くの情報を見つけることができるソースを教えてください。再帰降下パーサーでこれを達成できますか?

Expressionたとえば、ブール式のような式を表す再帰クラスがあります。

Expressionが単項式と 2 項式の両方を処理することに注意してください。基本的にExpression、ブール式と同様に CFG に従う必要があります。

私はこのようにクラスを設計しました：

コンストラクターの実装と、二項演算子と単項演算子のそれぞれ 1 つを以下に示します。

クラスはコンパイルに失敗します

error: use of deleted function 'Fuzzy::Expression::Expression(const Fuzzy::Expression&)'

オーバーロードされた各演算子 (return ステートメント内)。一部の関数が、存在しない unique_ptr のコピー コンストラクターを内部的に使用しようとしているように感じます。ポインターをあちこちに移動すると何か問題がありますか? GCCv4.8 で C++11 を使用しています。

何らかの方法でクラス インターフェイスの変更を提案することは大歓迎です。生のポインターの使用は避けたいと思います。

注: Boost.Spirit、YARD、YACC などのパーサー ジェネレーターなどの使用を提案しないでください。アプリケーションでは、これを最初から実装する必要があります。

y=x^2Javascriptのような単純な関数を区別する calc クラスのサイド プロジェクトに取り組んでいます。そのために、式を抽象構文ツリーに解析し、積規則や連鎖規則などの導関数規則をハードコーディングしました。

これに入れられる唯一の関数は、AP 微積分/1 年目の微積分の問題です。そのため、三角関数、対数、指数はすべて有効です。

私のプログラムは導関数を問題なく取りますが、最終的に得られるのは、途方もなく単純化されていない方法で記述された関数です。

たとえば、微分するとx^2が得られます(2*(x^(2-1)))。これは技術的には正しいですが、2*x のように簡単に記述できます。これまでのところ、基本的にツリーを繰り返し分析し、いくつかの基本的なルールを適用する基本的な単純化機能があります。

私が持っている一般的な手順は、再帰降下で分析することです。

現在のツリーに変数がない場合は、それを評価し、現在のノードを結果で置き換えます。

それ以外の場合は、大量の if ステートメントを適用して単純化します。これには次のようなものが含まれます

• ゼロを掛ける場合は、式をゼロに置き換えます
• 1 を掛ける場合は、式を他のオペランドに置き換えます
• 0 乗する場合は、式を 1 に置き換えます。

などなど。似たような用語を組​​み合わせるなど、本当の単純化を実際に行いたい場合、これはすぐに制御不能になります。また、任意の 2 つの式が等しいかどうかを判断したい場合、私が持っている最善の解決策は、単に関数のドメインで乱数を生成し、それらが等しいかどうかを確認することです。ただし、これはあまり効率的ではないようです。

x+22 つの異なる式 (単純な例はand )の等価性をより効率的に判断するに2+xはどうすればよいですか? また、大量の if ステートメントを使用せずに関数を単純化する方法はありますか?