2

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

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

4

2 に答える 2

3

LR(1) は、削減されるすべてのトークンに加えて、それらの後に 1 つのトークンを知ることによって、削減する適切なルールを選択できることを意味します。ANDブールクエリと操作に問題はありませんBETWEEN。たとえば、次の文法は LL(1) であり、したがって LR(1) でもあります。

expr ::= and_expr | between_expr | variable
and_expr ::= expr "and" expr
between_expr ::= "between" expr "and" expr
variable ::= x

私は、SQL 文法全体が LR(1) よりもさらに単純であると信じています。おそらくLR（0）またはLL（n）です。

于 2013-02-13T12:48:55.500 に答える
1

私の顧客の何人かは、私の LALR(1) パーサー ジェネレーターを使用して SQL および DB2 パーサーを作成し、長年にわたってそれらを正常に使用していました。彼らが私に送った文法は LALR(1) です (あなたが望む方法で解決される shift-reduce 競合を除いて)。純粋主義者の場合 -- LALR(1) ではありませんが、実際には問題なく動作します。GLR や LR(1) は必要ありません。より強力な LR(1) も必要ありません。

これを理解する最善の方法は、SQL 文法と優れた LALR/LR(1) パーサー ジェネレーターを見つけて、競合レポートが得られるかどうかを確認することだと思います。LALR(1) という SQL 文法 (少し古い) を覚えているので、次のダウンロードで入手できます: http://lrstar.tech/downloads.html

LRSTARは、競合レポートを提供する LR(1) パーサー ジェネレーターです。競合を解決できない場合も LR(*) です。

于 2013-06-17T17:55:18.427 に答える