問題タブ [lr1]

LR1 パーサーがどのように機能するかを理解しようとしていますが、奇妙な問題が発生しました: 文法にイプシロンが含まれている場合はどうなりますか? 例：文法がある場合：

開始方法は明らかです。

... 等々

しかし、私はそのような文法のためにそれを行う方法がわかりません:

するのは正しいですか：

そして、DFA でこの状態を受け入れますか?

どんな助けでも本当に感謝します！

現在、次の文法から LR(1) 状態を構築しています。

これがI0の構成です

そしてI1。

等々。しかし、I4 の構築に取り掛かると...

問題は A -> .aA

a から次の状態を構築しようとすると、まったく同じ内容の I4 が再び取得され、これが無限に続きます。同様のループが発生します

それで、私は何を間違っていますか？見逃している詳細があるはずですが、メモと本を閲覧しましたが、ここで何が問題なのかを見つけることができないか、単に理解していません. 何か助けはありますか？

WORD および SOMETHING は非ヌル端末です

これは LR1 文法なので、bison は問題なく解析できるはずです。

ただし、実行時に予期しない問題に直面しました。プログラムは入力を2回要求するため、たとえば「qwerty」と入力すると、2回目の入力を要求され、デバッグしようとすると次のようになります。

LR（1）パーサジェネレータの単純な（可能な限り、しかし単純ではありません！）実装はどこにありますか？

私はパフォーマンスを求めているのではなく、LR（1）状態（アイテムセット）を生成する機能だけを求めています。
C ++、C＃、Java、Pythonはすべて私のために機能します。

私は現在、GNU Bison を調べてプログラム コードを解析しています (または、実際に Bison を使用するプログラムを拡張してそれを実行しています)。私は、Bison が LR(1) 文法、つまり特殊な形式の文脈自由文法しか処理できない (または: 最適) ことを理解しています。そして、私は実際に、文脈自由文法と LR(1) 文法の規則も (信じている) 理解しています。

しかし、どういうわけか、LR(1) 文法の概念をよく理解していません。たとえば、SQL を想定します。SQL には、文脈自由文法が組み込まれていると思います。しかし、それは LR(1) 文法でもありますか? どうすればわかりますか？はいの場合、LR(1) 規則に違反するのはどれですか?

与えられた文脈自由文法について:

LR(1) になるように文法を書き直すにはどうすればよいですか?
現在の文法では、入力 "id : .id" を解析するときにシフト/リデュースの競合があります。パーサーの入力ポインターです。
この文法は、正規表現 (id:(id)*)+ を満たす言語を生成します。

次のような変数、単純な条件、サイクル、および関数を使用して、コードのパーサーを作成する必要があります。

私は多くの理論を読みましたが、Lr(1) Parser for code の実際の例は見つかりませんでした。パーサージェネレーターなしでそれを行う必要があります..誰か？

テーブル駆動の LR(1) パーサーをコーディングしましたが、非常にうまく機能していますが、解析を構文ツリー/抽象構文ツリーに変換する段階で少し切断されています。これは私が非常に情熱を注いでいるプロジェクトですが、ここで行き詰まりを迎えました。よろしくお願いいたします。

編集: また、私のパーサーは、2 次元配列とアクション オブジェクトを使用して、次に移動する場所や、移動先とポップするアイテムの数を減らすかどうかを指示します。多くの人がビジターパターンを使用していることに気付きました。彼らがどのタイプのノードを作成するかをどのように知っているかわかりません。

コンテキストのプッシュダウンオートマトンは次のとおりです