問題タブ [lalr]

知っている：

言語が LL(1) 文法によって生成できる場合、その言語は LL(1) であると言われます。LL(1) 文法が

しかし、私は問題に遭遇しました。

なぜ文法

S-> aBDb

B -> ラムダ

D-> dD | ラムダ

なぜこの文法は LL(1) でも SLR でも LALR でもないのですか? 誰か私を説明できますか？

私は正確に混乱しました!!!!!!

教授ノートの1つで次の例を読みました。

1) 次のような SLR(1) Grammar G があります。SLR(1) パーサー ジェネレーターを使用して、G の解析テーブル S を生成します。LALR(1) パーサー ジェネレーターを使用して、G の解析テーブル L を生成します。

解決策: S の R (reduce) を持つ要素の数が L を超えています。

しかし、あるサイトで私が読んだ：

2) T1、T2 が文法 G の SLR(1) と LALR(1) で作成されたとします。G が SLR(1) 文法の場合、次のうちどれが真ですか?

a) T1 と T2 に違いはありません。

b) T1 の非エラー エントリの合計数が T2 より少ない

c) T1 のエラー エントリの合計数が T2 より少ない

解決：

LALR(1) アルゴリズムは、SLR(1) アルゴリズムとまったく同じ状態を生成しますが、異なるアクションを生成できます。SLR(1) アルゴリズムよりも多くの競合を解決できます。ただし、文法が SLR(1) の場合、両方のアルゴリズムがまったく同じマシンを生成します (a が正しい)。

どれが真実であるかを説明できる人はいますか?

編集: 実際、私の質問は、特定の SLR(1) 文法について、LALAR(1) と SLR(1) の解析テーブルがまったく同じである理由です (エラーと非エラーのエントリは等しく、reduce の数は等しい)。しかし、上記の文法では、S の Reduced の数は L より多いです。

私は別の本で、一般的に次のことを知っています。

概要：

1) 質問 1 で私が書いた上記の文法の場合、還元される数が異なるのはなぜですか?

2) SLR(1) 文法がある場合、テーブルがまったく同じなのはなぜですか? (削減エントリとエラーエントリの数は同じになります)

論理式を評価するためのパーサーを作成しました。flex と bison がグローバル変数 (yylval など) を使用することは知っています。スレッド プログラミング用の純粋なパーサーとリエントラント スキャナーが必要です。私の「.y」ファイルはここにあります：

私の「.y」ファイルはここにあります：

両方のファイルに追加%pure_parserし、yylex 宣言を に変更してint yylex (YYSTYPE* lvalp);に置き換えyylvalました*lvalpが、エラーが表示されました: 'lvalp' is undeclared identifier.. 「再入可能」と「純粋」については多くの例がありますが、最適なガイドラインを見つけることができません。

誰かが私を案内してもらえますか？

前もって感謝します。

次のコードがあります。

私のカスタム トークナイザーは次のように変換されます。

しかし、次の Yecc では解析できません。

次の出力が得られます。

どんな助けでも大歓迎です、ありがとう。

TA によって解決された古い試験問題に出くわしました。誰でも私を助けることができますか？

文法について作成すると、項目セットの 1 つがSLR(1)次のようになります。S--> aSb | aLR(0)

{ S-->a.Sb, S-->a., S-->.aSb, S-->.a}

上記のセットから抽出されたルールについて、どれが真ですか：

(3)が正しい理由を誰が言えるでしょうか? この質問についての詳細は？

編集: Goto は Action を参照し、goto テーブルを参照すると思います。

Haskell のように、通常の中置操作と中置セクションを含む文法の yacc のような実装 (特に ocamlyacc を使用) に問題があります。私はこれらすべてが文法的であることを望みます:

ただし、結合性/優先順位の宣言をいじっても、これを機能させることができませんでした。問題が発生している場所は grammar.output で確認できますが (削減したい場所に移動しています)、思い通りに進むように誘導することはできませんでした。これは、問題の単純化されたデモンストレーションです。

lex.mll には次のものがあります。

main.ml には次のものがあります。

そしてparse.mly（問題があるところ）には次のものがあります：

それを実行ocamlyaccすると、 があることがわかります1 shift/reduce conflict。特に、詳細ログの関連部分は次のとおりです。

コンパイルされたプログラムを実行すると、次のすべてが正しく解析されます。

しかし、次のように失敗します:

一方、HIGH優先度の高いダミー トークンを作成する場合:

次に%prec HIGH、ルール 9 を適用します。

その場合(1+2)は解析しますが、し(1+)ません。

shift/reduce 競合の一般的な背景を理解しています。この解析の課題を解決するために交渉する方法がわかりません。

私は現在、初めて Flex と Bison で遊んでいます。Bison man pageで文脈上の優先順位について読みました。ディレクティブを使用せずに最小限の例を作成しようとしました%precが、それが実際に何をするのかよくわかっていません。これが私の最小限の例です。

フレックスファイル

バイソンファイル

メイン cpp ファイル

詳細なテストは行っていませんが、単項マイナスを使用したすべての組み合わせで、正しい結果が得られました。私は幸運ですか、それとも%precディレクティブは特別な場合にのみ必要ですか? また、スタック上のシフトと削減を自分で評価できるように、ディレクティブが必要な場合の例をいただければ幸いです。

ありがとう