問題タブ [lr]

私は java_cup と解析がまったく初めてで、bnfc と javacup を使用して単純な文法のパーサーを生成したいと考えています。文法規則を指定し、bnfc を使用しました。

いくつかのファイルを生成しました（つまり、filename.cup）

それから私はjava_cupでそれを構築しようとしました:

こちらも無事終了。最後に、ファイル parser.java と sym.java を取得しました。

解析するかどうかを確認したい入力ファイルがいくつかあります。この生成されたパーサーの使用方法がわかりません。parser.java もコンパイルしましたが、実行しようとするとスローされます

k > 1 に対して人為的な LR(k) 文法を作成するのは簡単です。

しかし、LR(k > 1) で解析可能な現実世界の非 LR(1) コンピューター言語はありますか?
それとも、非 LR(1) 言語も LR(k) ではありませんか?

小さな Visual Basic 言語用のパーサーを作成しようとしています。そして、次のシフト/削減の競合を解決できません。私はこれらのルールを持っています:

バイソンは私にこう言います：

では、この紛争の正しい解決策は何ですか?

ウィキペディアからの次の引用に混乱しています。

言い換えれば、言語が効率的なワンパスパーサーを許可するのに十分合理的である場合、LR(k) 文法で記述できます。そして、その文法は常に同等の (しかしより大きな) LR(1) 文法に機械的に変換できます。したがって、理論的には、LR(1) 解析メソッドは、合理的な言語を処理するのに十分強力でした。実際には、多くのプログラミング言語の自然文法は LR(1) に近いものです。[要出典]

これは、文法を文法に変換できる場合、 のようなパーサー ジェネレーターbisonが非常に強力であることを意味します (文法を処理できるため) 。これのいくつかの例、またはこれを行う方法に関するレシピはありますか? 文法にシフト/リデュースの競合があるのでこれを知りたいのですが、これは文法であり、文法に変換したいからだと思います。副次的な質問: は理不尽な言語です。LR(k)LR(k)LR(1)LR(2)LR(1)C++bison

以下は、私の作業中の EBNF 文法の単純化です。

\n と EOF の両方がトークンとして NEWLINE を吐き出します (EOF の前に単一の末尾の NEWLINE が必要ないように)。次のようなストリームで動作します。

少なくとも 1 つが必須で、残りは で区切られてlineいます。例えば：blockNEWLINE

私はこれをやってみました：

しかし、先読みが の場合、Jison は S/R 競合について不平を言いNEWLINEます。NEWLINEステート マシンは、が新しいブロックの一部なのlineか、最後のNEWLINE*ブロックなのかを判断するのに混乱していると思いfileます (ファイルが NEWLINE/EOF で終わる可能性があるため、これが必要です)。

どうすればこれを修正できますか?

lrparsingこれは Python 用のモジュールを使用した文法です。モジュールは、文法の競合を報告しません。

{{0}}エラー で文字列を解析できませんlrparsing.ParseError: line 1 column 5: Got '}' when expecting __end_of_input__ while trying to match block in state 11

段階的なスタック状態は次のとおりです。

これは、それがシフトしていることを意味し、次に に減少するの{{0を見て、最初にシフトせずに再び減少するため、バジーザスが混乱します。}0expr}

これはバグですか、それとも私は非常に単純で愚かなことをしていますか?

それが私の文法である場合、どうすればそれをリファクタリングして、私の永遠の熱狂的で情熱的な欲求を満たすことができるでしょうか? それがバグである場合、誰かが動作する lrparsing に最も似た構文を持つ python モジュールに私を導くことができますか?

編集:次のようにリファクタリング:

適切な解析を可能にします。今の私への質問は...なぜですか？lrparsing解析の問題について以前に私に不平を言ったような気がします...Repeat単に期待どおりに機能しないのですか?

私は自由時間に構文解析を試していて、非常に単純な文法のシフト削減パーサーを実装したいと考えていました。多くのオンライン記事を読みましたが、解析ツリーの作成方法についてはまだ混乱しています。これが私がやりたいことの例です：

文法：

入力例を次に示します。

トークン化すると、次のようになります。

という事は承知しています：

1. シフトとは、最初の入力トークンをスタックにプッシュし、それを入力から削除することを意味します
2. 削減とは、スタック上の 1 つ以上の要素を文法要素に置き換えることを意味します。

したがって、基本的には、次のようになります。

「何を減らすか」とは別に 間違いなく、解析ツリーを正しく構築する方法がわかりません。ツリーはおそらく次のようになります。

リダクションで新しいノードを作成する必要がありますか?

また、新しく作成したノードにいつ子を追加する必要がありますか? / 新しいルート ノードをいつ作成する必要がありますか?

LR(1) パーサーはこのタイプの文法を解析できますか?

このタイプのパーサーを実装する Java プログラムを作成しようとしていますが、左再帰を使用しない文法では正しい結果しか得られません。