60

いくつかの主要な構文解析アルゴリズム (LL(1)、LR(1)、LR(0)、LALR(1)) の文法を集めたオンラインの優れたリソースはありますか? 私はこれらのファミリーに分類される多くの個々の文法を見つけましたが、誰かが大量の文法例を書き上げた優れたリソースを知りません。

そのようなリソースを知っている人はいますか？

4

4 に答える 4

39

ウィキペディアの例

LL(1)

文法

S -> F
S -> ( S + F )
F -> a

入力

( a + a )

解析手順

S -> "(" S "+" F ")"
  -> ( "F" + F ) 
  -> ( "a" + F ) 
  -> ( a + "a" )

LR(0)

文法

(1) E → E * B
(2) E → E + B
(3) E → B
(4) B → 0
(5) B → 1

入力

1 + 1

解析手順

need to build a parser table and traverse through states.

LR(1)

文法

S’ -> S S 
S  -> C C 
C  -> c C | d

入力

cd

解析手順

large table

LALR

文法

A -> C x A | ε
B -> x C y | x C
C -> x B x | z

入力

xxzxx

解析手順

traverse large parser table

あなたも見てみたいかもしれません

于 2011-07-04T20:34:20.667 に答える
24

Parsing Techniques - A Practical Guideには、ほぼすべてのタイプの文法の例がいくつか (タイプごとにおそらく半ダースほど) あります。第 2 版は購入できますが、第 1 版は著者のWeb サイトで PDF 形式で無料で入手できます (リンクの下部近く)。

著者は、第 2 版のコード例にバンドルされているいくつかのテスト文法も持っています。これは、ここで見つけることができます。

注: これらの文法はすべて小さいものです (数十個の規則未満)。これは明らかに出版された本であるためです。

于 2011-08-20T20:05:42.800 に答える
2

意図的にそのように編成された大量の文法コレクションが見つかるとは思いません。主催者は見返りに何を得ますか？

可能性として考えられるのは、各ファミリ (たとえば LL(1)) に対応するパーサー ジェネレーターを見つけて、そのパーサー ジェネレーターの入力のインスタンスを探しに行くことです。意味。たとえば、ANTLR の文法はすべて、選択した ANTLR のバージョンに応じて LL(k) のさまざまなバージョンです (ANTLR バージョンの説明は、それが受け入れる k を示します)。Bison 文法はすべて LALR(1) [最近の GLR オプションを無視] です。私のウェブサイト (略歴を参照) にアクセスすると、ほとんど文脈に依存しない (つまり、説明したどのクラスにもない) 文法のリストが表示されます。

編集：ANTLRが特定のkに対して文法を明示的にLL（k）としてマークできるという@Bart Kierの説明に注意してください。

于 2011-06-30T08:19:11.640 に答える