問題タブ [lalr]

Yecc を使用して Erlang パーサーを作成しようとしていますが、セマンティック ルールの優先順位に問題があります。私の場合、文法、終端記号と非終端記号、規則、および関連するコードを定義しました。

これは私がテストのために書いたものです。

次に、特定の用語を実行して、ルールがどのように適用されるかを確認してみましょう。

パーサーの出力は次のとおりです。

しかし、私はこれが必要です。パーサーが用語を処理する限り、出力を書いています (デバッグ出力のように)。

初任期。

ルール %[req1 & req2]。(これは正しく適用されます – Case '$1' == '$5')

さて、何が起こるかわかりませんが、出力は次のようになるはずです。

ルール %[mand2 & mand3]。(ケース真)

ルール %[mand2 & mand3]。(ケース '$2' == '$7')

Rule %[tick] – 最終結果。

私はすでにこれを試しました：

Yeccマニュアルで説明されているように、私はこれを行うことができました:

• 演算子の優先順位で遊んでいます。
• ルールに優先順位を適用します。ドキュメントから (「1 レベル上」の非端末の優先順位を宣言することも可能です。これは、演算子がオーバーロードされている場合に実用的です (以下の例 3 も参照))。

しかし、それは私にはうまくいかないようです。助けて？

ありがとう！

ペット プロジェクトとして LALR パーサー ジェネレーターを作成しています。

私はパープル ドラゴン ブックを使用して設計を支援しています。そこから収集したことは、パーサーには 4 つのエラー回復方法があるということです。

• パニック モード: コンパイラ設計者によって事前に選択されたシンボルが見つかるまで、入力シンボルのダンプを開始します。
• フレーズ レベルの復元: 入力文字列を、現在の生産量を減らすことができるものに変更します。
• エラー生成: エラーを文法に組み込むことでエラーを予測する
• グローバルな修正: フレーズ レベルの回復のより複雑なバージョン (私が理解しているように)

そのうちの 2 つは入力文字列を変更する必要があり (これは避けたい)、他の 2 つはコンパイラ設計者がエラーを予測し、言語の知識に基づいてエラー回復を設計する必要があります。しかし、パーサージェネレーターも言語に関する知識を持っているので、同期トークンを事前に選択したり、文法をエラー生成で埋めたりせずに、解析エラーから回復するより良い方法があるかどうかに興味があります.

同期トークンを選択する代わりに、パーサーは、現在のプロダクションが同期トークンとして削減できるすべての非終端記号の後に続くシンボルを扱うことはできませんか? 私はそれがどれほどうまく機能するかを実際には考えていません.パーサーが進行中のプロダクションのチェーンをたどっていると思いますが、もちろんそれはボトムアップパーサーの仕組みではありません. 実行可能な状態を見つけようとして、あまりにも多くの無関係なエラーが発生するでしょうか? 無効な状態でパーサーを再開しようとしますか? エラーが発生したときに実際の解析プログラムが次にどこに行くべきかについて推論する必要がないように、パーサーテーブルに有効なエラーアクションを事前に入力する良い方法はありますか?

LALR(1) パーサーの先読み計算に関して少し混乱しています。

本「Parsing Techniques - A Practical Guide」では、先読み (+ 自発的に生成された先読み) を伝播することは、変数の FOLLOW() を計算することと同等であると述べています。では、単純で簡単に計算できる FIRST() と FOLLOW() を使用できるのに、なぜ LALR(1) パーサー (Dragon book によると) が伝播/自発的手法を使用するのでしょうか?

そうでない場合、2 つの手法の違いは何ですか?

主に解析の詳細に関連する、LALR(1) パーサーの競合に関するいくつかの質問:

1. 教科書に記載されているさまざまな LALR(1) パーサーによると、シフト/リデュースの競合が発生した場合、そもそも文法が LALR(1) ではないという兆候ですよね?

2. LR(1) から LALR(1) への状態のマージが行われるため、有効なLALR(1) 文法でReduce/Reduce の競合が発生する可能性がありますよね?

3. YACC と GNU Bison で使用されている優先順位と結合性は、シフト/競合の削減を支援するために導入されたツールですよね?

4. さらに、競合するシフト/リデュース ルールの優先順位が先読みシンボルの優先順位と等しい場合にのみ、パーサーが結合性をチェックする必要があります。それ以外の場合、結合性は無関係ですよね?

私は 100% 確信が持てないので質問しています。本は競合解決についてあまり詳しく説明していません。この件に関して私が見つけた数行は GNU Bison マニュアルにあるだけです。

上記の Bison マニュアル リンクに関する質問:

• 競合ルールや先読みトークンに優先順位がなければ、選択肢は SHIFT だと主張するのはなぜですか? リダクション ルールに優先順位がある場合、優先順位がまったくない先読みよりも優先されると思います。

Whttleを使用して文法を解析していますが、古典的なLALR のあいまいさの問題に直面しています。私の文法は次のようになります（簡略化）：

もちろん、問題は<string>. すべての印刷可能な文字が含まれているため、非常に貪欲です。<name>これは LALR パーサーであるため、a を aとして解析しようとする<string>と、すべてが壊れます。文法は、さまざまなものにさまざまな文字列区切り文字を使用するため、物事を複雑にします。そのため<string>、最初にルールを作成しようとしました。

可能であれば、この文法を正規化して LALR に準拠させる標準的な方法はありますか?

次の状態があるとします。

I1: S->TaV.,$

T -> V.,a

I2: T -> V.,a|$

これらの州をマージしますか?

基本的に、I1の核心は何か知りたいです。{ S->TaVです。、T->V。} I1 のコア、または I1 には 2 つのコア ( S->TaVとT->V ) が含まれていると言えますか?

Dragonbook によると、LR(1) アイテムのセットに存在するコアごとに、そのコアを持つすべてのセットを見つけて、それらの和集合に置き換えます。

ここで、{ S->TaV . 、T->V。} は I1 のコアなので、セットをマージしません。ただし、コアのT->V については。の場合、I1 と I2 の両方にコアが含まれているため、それらの和集合に置き換える必要があります。

セットをマージする必要がありますか？

役に立つかもしれないいくつかの背景の詳細​​:

最初の元の文法は

G: S->TaV | T

T->V | b

V->Ta | c

歴史的に、LR(1) パーサーによって生成される多数の状態に必要なリソース要件のため、LALR(1) パーサーは LR(1) パーサーよりも好まれていました。これが今日のコンピューティング環境で引き続き問題であるとは信じがたいことです。LALR文法はLR文法の適切なサブセットであるため、これはまだ当てはまるのでしょうか、それとも現在のコンパイラは正規のLRパーサーで構築されているのでしょうか?

Ironyを使用して C99 を解析しようとしていますが、オンラインで文法を見つけました。

宣言とステートメントの競合に問題があります。次のルールは、イニシャライザを使用したポインタ宣言の検出に失敗します。

失敗している行のタイプは次のとおりです。

ステートメントのルール (どちらも識別子で始まる可能性があります) から、labeledStatement と expressionStatement を削除すると、このタイプの宣言が正しく認識されます。

ステートメントを試す前に、Irony に宣言ルールを使い果たすように強制する最良の方法は何ですか? または、Irony が解析するときに文法に追加して、MyType を識別子ではなく端末として登録できるようにすることはできますか?

(LA)LRパーサーの欠点は、reduce がルールの最後でのみ処理されることです。これは、 のようなスコープ変数を持つプログラミング言語の問題ですjavascript。

例：

上記のコード例を参照してください。パーサーは次のようになります。

これで、識別子がパーサーによって消費されるたびに明らかになりました。識別子をレジスタに登録できます。ただし、問題は、関数 (行/*1*/) が関数の最後でのみ考慮されることです。したがって、関数内で識別子 (; など) を使用する命令はa = 4、パーサー時にローカル/グローバル識別子にバインドできません。

この問題に取り組むための良い方法は何ですか?そのような状況を処理するために C# (標準ライブラリ) が提供する機能は何ですか?