23

複雑な分析を行わずに文法を調べるだけで、文法が LL(1)、LR(0)、SLR(1) であるかどうかを判断する簡単な方法はありますか?

例: BNF Grammar が LL(1) であるかどうかを判断するには、First セットと Follow セットを計算する必要がありますが、これには時間がかかる場合があります。

これをより速く行う方法を知っている人はいますか? どんな助けでも本当に感謝します!

4

7 に答える 7

34

まず、ちょっとした衒学者。言語がLL（1）であるかどうかは、文法を調べて判断することはできません。文法自体についてのみステートメントを作成できます。LL（1）文法が存在する言語の非LL（1）文法を書くことは完全に可能です。

それが邪魔にならないように：

  • 文法のパーサーを作成し、プログラムに最初に計算させ、セットやその他のプロパティを追跡させることができます。結局のところ、それがBNF文法の大きな利点であり、機械で理解できるのです。

  • 文法を調べて、さまざまな文法タイプの制約の違反を探します。例：LL（1）は右再帰を許可しますが、左再帰は許可しません。したがって、左再帰を含む文法はLL（1）ではありません。（他の文法プロパティについては、今は頭のてっぺんから他に何も思い出せないので、定義にある程度の時間を費やす必要があります:)。

于 2009-01-24T13:22:23.427 に答える
15

あなたの主な質問への答え: 非常に単純な文法の場合、FIRST および FOLLOW セットを構築せずに LL(1) であるかどうかを判断できる場合があります。

A → A + A | a

は LL(1) ではありませんが、

あ → あ | b

は。

しかし、それよりも複雑になると、何らかの分析を行う必要があります。

A→B | a
B → A + A

これは LL(1) ではありませんが、すぐにはわからない可能性があります

算術の文法規則はすぐに非常に複雑になります。

expr → term { '+' term }
term → factor { '*' factor }
factor → number | '('式')'

この文法は掛け算と足し算のみを扱い、その文法が LL(1) であるかどうかはすぐにはわかりません。文法を調べることでそれを評価することはまだ可能ですが、文法が成長するにつれて、それは実行可能性が低くなります。プログラミング言語全体の文法を定義する場合、ほぼ確実に複雑な分析が必要になります。

そうは言っても、文法が LL(1) ではないことを示す明白な兆候がいくつかあります — 上記の A → A + A のように — そして、これらのいずれかが文法に見つかれば、書き直す必要があることがわかります。再帰降下パーサーを書いている場合。しかし、文法がLL(1)であることを確認する近道はありません。

于 2009-02-16T21:13:12.557 に答える
9

Aho 他著「コンパイラ: 原則、技法、およびツール」からの抜粋です。アル。

223ページ：

文法 G が LL(1)になるのは、常に A -> alpha | betaが G の 2 つの異なる生成物である場合、次の条件が成り立ちます。

  1. 終端 "a" がない場合、alphaとbetaの両方が "a" で始まる文字列を導出します
  2. 空の文字列を導出できるのは、 alphaとbetaの最大 1 つです。
  3. betaが 0 回以上の遷移を介して空の遷移に到達できる場合、 alphaは FOLLOW(A) の終端で始まる文字列を導出しません。同様に、alphaが 0 回以上の遷移を介して空の遷移に到達できる場合、 betaは FOLLOW(A) の終端で始まる文字列を導出しません。

基本的に、これは、文法がペアワイズ分離テストに合格し、左再帰を含まないことを確認する問題です。もっと簡潔に言えば、左再帰的またはあいまいな文法 G は LL(1) にはなりません。

于 2012-04-27T18:44:00.400 に答える
9

「言語/文法があいまいであるか」という 1 つの側面は、 Post の対応や停止問題のような既知の決定不能な質問です。

于 2009-01-25T02:14:31.310 に答える
2

文法が曖昧かどうかを確認してください。そうである場合、あいまいな文法はLL（1）ではないため、文法はLL（1）ではありません。

于 2012-12-25T14:47:46.600 に答える
0

ll（1）文法のショートカットがあります

1）A-> B1 | B2 | ....... | Bnの場合、first（B1）intersection first（B2）intersection .first（Bn）= empty setの場合、ll（1）文法になります。

2）A-> B1 | epsilonの場合、B1交差点follow（A）は空集合です

3）Gが任意の文法であり、すべての非終端記号が1つの生成のみを導出する場合、その文法はLL（1）です。

于 2011-12-17T12:38:26.380 に答える
-2 
p0 S' → E
p1 E → id
p2 E → id ( E )
p3 E → E + id
  • LR(0) DFA、E の FOLLOW セット、および SLR アクション/goto テーブルを構築します。
  • これは LR(0) 文法ですか? あなたの答えを証明してください。
  • SLR テーブルを使用して、LR パーサーの解析の手順 (シフト、リダクション、受け入れ) を示します。
    id ( id + id )
于 2011-12-12T15:38:12.197 に答える