問題タブ [lr]

私は過去に再帰降下と PEG のようなパーサーを実装しました。ここでは、次のようなことができます。

• whereSegment+は「1 つ以上に一致する」ことを意味しSegmentます
• そして、1つ以上の単語文字を一致させるための普通の古い正規表現があります\w+

LR文法/パーサーを使用して、これと同じ種類のことを通常どのように達成しますか? 私が見た LR パーサーの例はすべて非常に基本的なもの1 + 2 * 3で、パターンは非常に単純で、「1 つ以上」の機能 (またはゼロ以上の、またはオプションの)(())()を含まないようです。. 一般に、LR パーサーでどのように行うのですか?*?

それとも、LR 構文解析は最初に字句解析フェーズを必要としますか (つまり、LR パーサーは端末と非端末の「トークン」を必要とします)。そのような 2 つのフェーズなしで LR 解析を行う方法があることを願っています。LRパーサーの定義は、私が読んでいる本/サイトの「入力文字」について語っていますが、さりげなく/微妙に次のような行が表示されます。

文法の終端記号は、字句スキャナによって入力ストリームで検出された複数文字記号または「トークン」です。

そして、スキャナーはどこから来たのですか。

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

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

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

それで、最近これを締めくくる質問をしたところ、非常に良い答えが返ってきました。ただし、説明されている手順は、具体的な構文ツリーを作成する手順のように見えました。

LR 解析プロセスの各縮小は、解析ツリーの内部ノードに対応します。削減されるルールは内部 AST ノードであり、スタックからポップされた項目はその内部ノードの子に対応します。goto でプッシュされたアイテムは内部ノードに対応し、shift アクションによってプッシュされたアイテムは AST のリーフ (トークン) に対応します。

これらすべてをまとめると、リダクションを行うたびに新しい内部ノードを作成し、すべてを適切に接続することで、簡単に AST を構築できます。〜クリス・ドッド

実行した手順によって解析ツリーが暗示されることはわかっていますが、解析ツリーを明示的に構築したくありません。また、リダクションごとにノードを生成すると、解析ツリー全体が生成されるように見えます。特定の状態が見られた場合にのみノードを構築することを検討しました。ただし、これは正しく機能しないようです。

私は Java で小さな LR(1) パーサー ジェネレーターを書きました。これは、入力で文脈自由文法を与えられ (より適切に言えば、プロダクションです)、入力単語は、1) 文法が LR(1) ではないかどうかを出力します。2) 単語が3) 単語は文法によって拒否されます

これまでのところ、私はこの文法で試しました

S -> CC
C -> CC | d

この

A -> BA | e
B -> aB | b

(e は空の文字列であることに注意してください)

この文法では、パーサーは機能しますが、テスト用にLR(1)言語を確実に生成することがわかっている文法(プロダクションのリスト)を見つけるのに苦労しています。
さらに、プログラムのポイント (1) をテストするには、LR(1) ではない文脈自由文法が必要です。

あなたが私に与えることができる例はありますか？

私は LR(1) アイテムに取り組んでいますが、少し疑問があり、誰かが私のために明確にしてくれることを願っています. 次の文法を考えると、LR(1) 項目を生成する必要があります。最初のアイテムを生成しましたが、それが正しいかどうか確信が持てません。続行する前に、最初のアイテムが正しいことを確認したいと思います。誰かが私を助けてくれたり、明確にしてくれたりしたら、本当に感謝しています。ありがとうございました。ここに私が持っているものがあります:

この LR(0) オートマトンでは

非端末にもトランジションがありますが、わかりません。入力がaab. それからあなたはただの状態になってしまうでしょうA->a·。入力またはその他の入力によって到達した状態を視覚化する場合aab、それらの間にアークがない状態間の遷移はありませんか?

これが、開始状態から開始し、受け入れ状態に到達するまでオートマトンのアークに沿ってのみ移行する DFA や NFA と異なる理由がわかりません。

非 LR(0) 削減状態がどこから来るのかわかりません。それは次のことを意味しますか?

1. LR(0) 還元状態を削除し、LR'(0) 状態を取得します
2. LR'(0) states を使用して LR(K) states を生成します。非 LR(0) 還元状態は LR(K) 状態から来ます。

これは、Authomatic Error Recovery を使用して効率的な LALR(K) Parders を構築するためのパティカル メソッドのコピーです。

4.2章をお読みください

章 4.2 の自動エラー回復を使用して効率的な LALR(K) パーサーを構築するための実用的な方法によると。

パーサーが shift-reduce に遭遇すると、|α| をポップする必要があります。要素。しかし、JDT のパーサーは要素をポップしませんでした。理由はわかりませんが、何か助けてくれますか。

parser.java の shift-reduce アクション

DiagnoseParser.java の shift-reduce アクション