問題タブ [recursive-descent]

私は LL(1) 文法の構文解析テーブルを構築しようとしていますが、それは 1 つの側面を除いてすべて理にかなっています!?

フォロー セット シームのルールが矛盾しています。

• 各生産 X → αAβ について、FIRST (β) − {€} を FOLLOW(A)
に入れる • € が FIRST (β) にある場合、FOLLOW(X) を FOLLOW(A) に入れる

それらはルール 1 と 2 です (3 は問題ありません)。

その生産ルールがまだルール 1 に該当しない場合、ルール 2 をどのように実装できますか?

それで、誰かがどのルールがどこに適用されるかを微妙に説明できますか?

Recursive Descendent Parser Builder を使用して式を作成する必要があります。

これが私の文法です：

これで、端末ごとに 1 つのクラスを持つ Composite 構造ができました。上記の文法の規則に従って構築しようとしています。

アイデアは、文法規則ごとにメソッドが必要であり、このメソッドのそれぞれが式ツリーの一部を構築する必要があるということです。

より単純な文法 (たとえば、ブール式のみを許可する文法) で動作しますが、これにはいくつか問題があります。

主な問題はexpr、 + と - の単項バージョンでさえ、 のような式を許可することで作業を強制する規則から来てい+3-4ます。これには、オペランドを単項と見なす必要がある場合と、2 項と見なす必要がある場合を見つける必要があります。

これが私の Builder クラスのコードです。何かがイタリア語で書かれていることに注意してください。コメントを使用して、私の問題を含め、すべてを説明しました。また、疑似コードを使用した行が 1 行あるため、これはコンパイルできません。

既知の問題:

(a<=b && c>1) || a==4に評価されますa <= b && c > 1

a==[-4]に評価されますa == a - 4

-4+3>c-2に評価されます+3 > c - 2

おそらく他にもいくつかのエラーがありますが、それらは最も一般的なエラーです。

だからここに私の質問があります：

まず、このコードには論理的な問題があると思いますか? つまり、文法が言うことをするのでしょうか、それとも私は何か本当に間違ったことをしましたか? expr単項およびバイナリ + または - オペランドの両方で機能するようにメソッドをどのように修正しますか?

私のコードが完全に間違っている場合、動作するバージョンを書くのを手伝ってくれる人はいますか? クラス名からわかるように、これは私が作成した6 番目の実装であり、次に何をすべきか本当にわかりません!

ありがとう。

私は複雑なPythonデータ構造を持っています（それが重要な場合、それは大きなmusic21 Scoreオブジェクトです）。オブジェクト構造の奥深くにweakrefが存在するため、ピクルスになりません。私は以前にスタックトレースとPythonデバッガーでこのような問題をデバッグしましたが、それは常に大きな苦痛です。オブジェクトのすべての属性に対してdir（）を再帰的に実行し、リスト、タプル、dictなどに隠されているオブジェクトを検索し、特定の値に一致するオブジェクト（ラムダ関数など）を返すツールはありますか？大きな問題は再帰的な参照であるため、ある種のメモ関数（copy.deepcopyが使用するような）が必要です。私は試した：

私はおそらくこれに穴を埋め続けることができます（たとえば、反復は私がdictに望むものではありません）が、私がそれにもっと時間をかける前に、誰かがより簡単な答えを知っているかどうか疑問に思います。それはかなり便利な一般的なツールかもしれません。

私はこのようなテーブルを持っています：

私はこのようにすべての量と息子の量を合計する必要があります：

私の悩みは、父と息子の関係が再帰的であるため、祖父の量なども合計したいのですが…何度も参加できないので、最大の深さはわかりません。

私に何ができる？ありがとうございました。

この文法の完全に括弧で囲まれた Exp を解析しようとしています:

...しかし、問題があります。「1+4」と入力してもエラーは表示されません。どうすれば解決できますか??

TL;DR:

私の電卓の文法は、再帰降下に依存して括弧グループを相互にネストしますが、ネストされた括弧が多すぎる (約 20) と、スタック オーバーフローが発生します。どうすればこれを修正できますか? 問題をより平坦にする方法はありますか？

長い形式：

それほど前のことではありませんが、私の頭は小規模な組み込みシステムに深く突き刺さっていましたが、脳の半分しかスタック オーバーフローに陥るはずがありませんでした。今はもっと抽象的な仕事に頭を悩ませているので、アドバイスを求めてここに来ました。

やる気を起こさせるプロジェクトは、Android 用の電卓です。現在の電卓は多くの点で明らかに不十分ですが、今日はソープボックスを持ってこなかったので、私が直面している問題に直行します: スタック オーバーフローです!

具体的には、ユーザーが関数などを含むネストされた括弧グループを作成しすぎた場合です。ANTLRこれは、計算機が文法に依存しているために発生します。つまり、再帰降下を使用しています。便利なことに、これにより PEMDAS を介して継続的に実行できるため、ネストされた関数と括弧の計算が簡単になります。しかし！電話によっては、かっこボタンを 20 回ほど押すとクラッシュが発生することがわかりました。これは、約 100 の関数呼び出しの深さから発生するスタック オーバーフローが原因で、再帰的降下法の自然な結果です。

フラットはネストされたものよりも優れていることはわかっていますが、それが通過する 4 つのレベル (関数) は完全に必要であり、他のいくつかのレベルは私の人生を対数的に容易にします。これらのレベルを削除しても問題は解決しません。ユーザーは数分以内にシステムをクラッシュさせることができます。「かっこが多すぎる！」エラーメッセージが悪いです (他の計算機の 1 つが行うことです)。また、私は AST 出力を使用して入力文字列を書式設定し、きれいなようにします。そのため、括弧グループの事前計算により、システム全体が少し複雑になりすぎます。

だから、質問：

この質問をすることさえばかげているように思えますが、コール スタックを爆発させることなく、複雑で深くネストされた式を解析および解釈できる文法を ANTLR に実装する方法はありますか?

文法：

Issue is because of -- addExpression ((EQ | NE | GT | LT | LE | GE) addExpression)+ --- . By doing this I want to filter the math expressions from being alone unless followed by a relational to make it logical as a whole... I don't want my parser to parse math expressions if alone...

Tests:

次の文法があり、C で再帰降下パーサーを作成する必要があります。

左因数分解を使用して、次の文法を取得しました

ここで、次の文法を取得するために左再帰を削除しました

e はイプシロンを表します

この文法の C プログラムを作成しましたが、セグメンテーション エラーが発生します。

この CFG で左再帰を削除するにはどうすればよいですか?